# Pathfinding making my head spin

## Recommended Posts

##### Share on other sites
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 :)

##### Share on other sites
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.

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

##### Share on other sites
Quote:
 Original post by daniel_i_lIf 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

##### Share on other sites
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.

##### Share on other sites
Quote:
Original post by Timkin
Quote:
 Original post by daniel_i_lIf 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.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by RandOP, 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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628372
• Total Posts
2982305

• 10
• 9
• 13
• 24
• 11