In a sidescrolling video game a character moves through an e

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 de ne 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 nding
a minimum-cost monotone path in the graph, G, that represents this game. Describe and analyze
an ecient algorithm for nding a minimum-cost monotone path in such a graph.

Solution

Algorithm:

//This while loop will find the shortest path to end by moving left.

{
for (each unvisited neighbor of current node)

{
Set neighbor.distance to the smaller of its current value and (current.distance + length of an edge between current and neighbor).
}
Mark current node as visited.
current = node from the unvisited set with the smallest distance
}

movingLeft = false
Set all nodes to unvisited and their distances to 0.
Set current to start node.
Set current to visit and its distance to 0.

// this while loop will find the shortest path to end by moving right.
// (Same while loop as above.)

{
for (each unvisited neighbor of current node)

{
Set neighbor.distance to the smaller of its current value and (current.distance + length of an edge between current and neighbor).
}
Mark current node as visited.
current = node from unvisited set with the smallest distance
}