In a side-scrolling video game, a character moves through an environment from, s
ID: 3576012 • 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-sc rolling 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 in such a graph, G.Explanation / Answer
ALGORITHM:
1. Initialization of all nodes with distance "infinite"; initialization of the starting node with 0
2. Marking of the distance of the starting node as permanent, all other distances as temporarily.
3. Setting of starting node as active.
4. Calculation of the temporary distances of all neighbour nodes of the active node by summing up its distance with the weights of the edges.
5. If such a calculated distance of a node is smaller as the current one, update the distance and set the current node as antecessor. This step is also called update and is Dijkstra's central idea.
6. Setting of the node with the minimal temporary distance as active. Mark its distance as permanent.
7. Repeating of steps 4 to 7 until there aren't any nodes left with a permanent distance, which neighbours still have temporary distances.
Pseudocode:
function Algo(Graph, source):
for each vertex v in Graph:
// Initialization
dist[v] := infinity
// initial distance from source to vertex v is set to infinite
previous[v] := undefined
// Previous node in optimal path from source
dist[source] := 0
// Distance from source to source
Q := the set of all nodes in Graph
// all nodes in the graph are unoptimized - thus are in Q
while Q is not empty:
// main loop
u := node in Q with smallest dist[ ]
remove u from Q
for each neighbor v of u:
// where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]
// Relax (u,v)
dist[v] := alt
previous[v] := u
return previous[ ]
function Algo(Graph, source):
for each vertex v in Graph:
// Initialization
dist[v] := infinity
// initial distance from source to vertex v is set to infinite
previous[v] := undefined
// Previous node in optimal path from source
dist[source] := 0
// Distance from source to source
Q := the set of all nodes in Graph
// all nodes in the graph are unoptimized - thus are in Q
while Q is not empty:
// main loop
u := node in Q with smallest dist[ ]
remove u from Q
for each neighbor v of u:
// where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]
// Relax (u,v)
dist[v] := alt
previous[v] := u
return previous[ ]