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 dene 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

In this type of graphs, we prefer for A* algorithm, as here we have only two vertices i.e, P and G, we have to find the minimum time to travel from P to G, with earning points as positive values of weigths of particluar edge and loosing points will be treated as negative weight on particular edge. we will have nodes in this algorithm. health points,time can be earned by teavelling from node to node. If you find any prices dont catch them, this mean you have negative weights on your edges. these weights will be given from node to node till you reach destination point G.

minimum cost i.e, path to reach can be calculated by O(|E|) =O(b) as worst case.