In a side-scrolling video game, a character moves through an environment from, s
ID: 3821357 • Letter: I
Question
In a side-scrolling video game, a character moves through an environment from, say, left-to-right, while encountering obstacles, attackers, and prizes. The goal is to avoid or destroy the obstacles, defeat or avoid the attackers, and collect as many prizes as possible while moving from a starting position to an ending position. We can model such a game with a graph, G, where each vertex is a game position, given as an (x, y) point in the plane, and two such vertices, v and w, are connected by an edge, given as a straight line segment, if there is a single movement that connects v and w.
Furthermore, we can define the cost, c(e), of an edge to be a combination of the time, health points, prizes, etc., that it costs our character to move along the edge e (where earning a prize on this edge would be modeled as a negative term in this cost).
A path, P , in G is monotone if traversing P involves a continuous sequence of left-to-right movements, with no right-to-left moves. Thus, we can model an optimal solution to such a side- scrolling computer game in terms of finding a minimum-cost monotone path in the graph, G, that represents this game.
Describe and analyze an efficient algorithm for finding a minimum-cost monotone path in such a graph, G.
Explanation / Answer
Monotonic shortest path. Given an edge-weighted digraph, find a monotonic shortest path from s to every other vertex. A path is monotonic if the weight of every edge on the path is either strictly increasing or strictly decreasing.
This problem could be solved by modified Dijkstra’s algorithm. The main point is that relaxation should be done not with min operation in every graph node (as usual) but in the priority queue.
Here is the list of modifications for usual Dijkstra’s algorithm. I consider only edges' relaxation in ascending order, which results in strictly decreasing shortest path (to get increasing shortest path, alter items 2 and 4):
This algorithm guarantees that each edge is processed at most once (or twice if we consider both strictly decreasing and strictly increasing paths), so its complexity is O(E log E).