need a pathfinding algorithm from 1 column to another

Question

grid contains weights and I need a max path sum from one column to another possible movement directions are (right, up & down only).

Can Djikstra or A* help ??

Answer 1

What is a graph?

A graph consists of 3 things.

1. objects called "vertices" (singular "vertex"),
2. connections between the objects called "edges", which are ordered pairs of the form (a,b) this means that "a is connected to b", it does not mean that b is connected to a.*
3. weights or worths assigned to the edges. This is done by a function, w: connections -> numbers with w(x,y) being the weight of the edge from x to y

---

Dijikstra and A*

These algorithms take a graph and the assumption that w(x,y)>=0 for all x and y and return a shortest path (between some or all vertices of the graph)+

They will work provided you can satisfy the definitions above.

---

Footnotes:

* - so called "undirected" graphs are graphs where if the edge (a,b) exists then so does (b,a) and they require that w(a,b)=w(b,a)

+ - suppose that your weight is "time taken" and you have a portal that'll take you back in time to a location p, the "weight" of going to p might be the weight to the portal - the time difference. Suppose you can go from p back to the portal before you even leave through the portal. This is called a negtive weight cycle and totally buggers up the algorithm (see Floyd's algorithm) - even if it isn't a negative weight cycle it causes severe problems.

Answer 2

Of course.

Dijkstra's (of which A* is just a refinement) adds nodes to an open list. The usual grid implementation is to consider all adjacent nodes. You can simply change this to only consider nodes on the same column or the column to the right.

For termination, the usual algorithm is looking for a specific node or position. You can also change the algorithm to terminate on a specific set of nodes ie. a specific column.

Ultimately, this is no different than games that filter out nodes for different types of units (e.g. airborne vs terrestrial vs aquatic units pathing over a map in an RTS) or games that search for points near a target location (e.g. to get within 10 meters of a point a user clicked, rather than the exact node the user clicked).