Hi, I've been doing lots of pathfinding reading, and implementing (trying) algorithms like DFS, BFS, Dijkstra and A*. Before I explain my headach's, I'll show how I'm implementing the graph's I'm searching in: Basically, the graph consists of tile based grid, of width x height, containing tiles that each is represented by a Node. The Pathfinder algorithm I implemented knows nothing about the Map, that is where each Node is (x,y) in the grid. I feed my Pathfinder.findPath method a startNode and goalNode, and it returns me a LinkedList containing the Nodes I need to travel from the startNode to reach the goalNode. An example of this would be: // give me a path between tiles 0,0 and 31,31. myPath = myPathfinder.findPath(mapNodes[0][0], mapNodes[31][31]); Remember that I said that the Pathfinder knows nothing about this mapNodes[][], but rather mapNodes[0][0] contains "neighbours", that is array/list of adjacent and diagonal Nodes. Also! (important) each of the Nodes in mapNodes know nothing about it's position (x,y). (This is because I want my pathfinder to be abstract enough to handle not only grid-based games, but also other types). Here's my headache: The problem is that when in the Pathfinder.findPath method, I iterate through all the Nodes in the "open" list, and for each of those Nodes I iterate through all of it's neighbour Nodes (those adjacent and diagonal Nodes). Since I want adjacent movement cost to be 10, and diagonal movement cost to be 14, I run into problems. I do not know in what direction, when iterating through the neighbours, each Node is in relation to the "parental" Node. So I can not assign costs "on the fly". I cannot either define if a Node is diagonal or adjacent, since mapNodes[3][3] is adjacent to mapNodes[3][2], but is diagonal to mapNodes[2][2], and mapNodes[2][2] is adjacent to mapNodes[3][2]. When I implement Dijkstra, and diagonal and adjacent movement costs are the same , I get strange paths. I've been reading so much about pathfinding that I'm going nuts... am I fundamentally misunderstanding something about pathfinding?

Perhapse I'm in error in trying to force an pathfinding abstraction upon two types of pathfinding problems, namely;

- pathfinding in grids, where each tile in the grid is represented by a Node
- pathfinding in general, where nodes are connected by edges

In general pathfinding I see no mention of adjacent/diagonal movement, and in pathfinding for grids (computer games) I see no mention about edges.

Any clearing up would be helpful :)

No matter what the underlying representation, pathfinding can always be viewed as a graph. A graph has nodes and edges. Sometimes the edges all have the same cost and sometimes they have weights associated with them.

One of the advantages of using a uniform grid is that you don't need to store the edges in memory; they can always be generated on demand using the grid's coordinates. Doing this generically in C++ can be tricky; possible implementations might use callbacks or iterators to describe the edges from a given node. If one tile is accessible from another, that implicitly means that there is an edge connecting them. A list of nodes accessible from a given node along with costs is equivalent to a list of edges with costs.

If your doing pathfinding with a grid of nodes and edges, store the cost of transversing an edge in the edge structure.

Quote: Original post by daniel_i_l
If your doing pathfinding with a grid of nodes and edges, store the cost of transversing an edge in the edge structure.

Implementation-wise, it's often simpler to encode all of this information at the culminating node of an edge; i.e., store the action and its cost in the culminating node. Then, during search, when you arrive at a node you have already discovered, set the parent of the node as the one lying on the path of lowest cost. I've experimented with having separate node and edge data structures, but in the end it just creates extra overhead (at least IMO).

Cheers,

Timkin

Quote: "each of the Nodes in mapNodes know nothing about it's position (x,y). (This is because I want my pathfinder to be abstract enough to handle not only grid-based games, but also other types)."

Quote: "Since I want adjacent movement cost to be 10, and diagonal movement cost to be 14, I run into problems. do not know in what direction, when iterating through the neighbours, each Node is in relation to the "parental" Node. So I can not assign costs "on the fly". I cannot either define if a Node is diagonal or adjacent, since mapNodes[3][3] is adjacent to mapNodes[3][2], but is diagonal to mapNodes[2][2], and mapNodes[2][2] is adjacent to mapNodes[3][2]."

These statements are contradictory. You can't make it both generic enough to handle non-grid-based games and specific so that it's locked into grid-based mentality.

Quote: Original post by Timkin

Quote: Original post by daniel_i_l
If your doing pathfinding with a grid of nodes and edges, store the cost of transversing an edge in the edge structure.

Implementation-wise, it's often simpler to encode all of this information at the culminating node of an edge; i.e., store the action and its cost in the culminating node. Then, during search, when you arrive at a node you have already discovered, set the parent of the node as the one lying on the path of lowest cost. I've experimented with having separate node and edge data structures, but in the end it just creates extra overhead (at least IMO).

Cheers,

Timkin

In the hex-grid path-finding algorithm I recently implemented. I followed this approach. Movement costs to adjacent tiles, not to mentional total movement cost, were stored directly in the node, not in a secondary structure. I was thinking about doing a second structure, but it would have just been additional overhead and I don't see the benefit Yeah, my MapTile class got a little bit more complex and was maybe storing extraneous information. So shoot me.

OP, i think you need to think more about edges if you want your algorithm to be generic. Then Each tiled node would have a list of neighbours, being 8. Then in edge is a cost, which would be 14 for diagonal and 10 for not. The value of the cost would be map/game specific, but the algorithm would just look at the cost irrelavent of what it means. It doesn't know 14 is diagonal, but it does know its better than going right then down.

Quote: Original post by Rand
OP, i think you need to think more about edges if you want your algorithm to be generic.

One could as easily build a generic graph search tool using edge-based or node-based data structures. Either is as good as the other, since you need to encode the same information: cost and connectivity.