# A* path finding for road network - data structure to represent directivity

I have been reading A* path finding to apply on a road like network structure. Most of the code I saw is about A* on tile based maps. There is a short description at Amit's page here about what I am looking for. My question is about what data-structure should I use to define a road network map.

I have infromation like, node, cost,etc. But not sure how to represent both one directional and bidirectional roads. In a graph structure, can I mix directed and undirected edges or use two edges to represent that a segment of road can be traversed in both direction. Any good example available?

Thank you so much.

• Each node independently has a list of adjacent nodes reachable FROM itself. This may be stored statically, or calculated dynamically, or a combination. – Pieter Geerkens Apr 24 '13 at 2:07
• Have you considered a directed graph data structure? There are a number of algorithms to accomplish what you want, plus graphs are one of the most studied of comp-sci data structures. – Patrick Hughes Apr 24 '13 at 17:54
• thanks Patrick for the comment. With the below answers, I came to read more about Adjacency list, and have an idea about how to approach my problem. – bsr Apr 24 '13 at 22:29

The edges of a graph are implicit; they are defined by each node's adjacency list.

If node A has both node B and C registered as adjacent nodes, but only node B has A registered as an adjacent node, then the edge between nodes A and C is implicitly directed towards C.

Nodes can be implemented as a collection of its adjacent nodes and its data (position would be relevant to pathfinding).

struct Node
{

Vector3 position;
};

• For A* you need the true distances (cost function) per neighbor as well. – MSalters Apr 25 '13 at 12:36
• Not really. If each node contains its position, the algorithm should easily be able to calculate the distance between two adjacent nodes. However, if the cost is non-trivial, such as terrain cost, that should be stored in each node or in dedicated edge structures. – jmegaffin Apr 25 '13 at 15:56

In road network it is better to have cost in edges, not in nodes. When I was doing road networks (for navigation, not for games) related programming, I used Node that contained set of incoming and outgoing edges (and other data) and edge with both ends, reference to edge in oposite direction and again, other data.

Some of this you will probubly not need (depends on what you want to do with this graph. For A* I would guess that you need: cost of edge, cost to reach node from start, outgoing edges and used incoming edges (for creating actual path once you find cost of path to goal).

Another complicating thing (that can significantly reduce size of graph): Nodes with 2 neighbours are not interesting, unless they are start or goal, theefore you can create simplified graph where they are romeved and replaced with edges connecting their neighbours (if they were originaly connected by removed node)

Nodes with just one neighbours are not interesting too, so they again can be removed.

Applying both these rules can in some cases reduce graph size multiple times (on some islands it reduced our graph to single node which was not so usefull ;) ), but in grid like road network it will help only little.

How excatly I represented this I don't remember (proprietary work I did few years ago).

And my experience was not with games, but with preprocessing graphs, so I had lot of memeory available (eg. Vieana needed computer with more than 4GB ram)

• +1 thank you very much for sharing your experience. My graph would be relatively simple, and would comment if I face similar issues you mentioned. Thanks again for your input. – bsr Apr 24 '13 at 22:33