Representing a map and running A* on it

Question

My question is mainly about map representation and I would like your opinions.

Having a map represented by a bunch of roads and a connection between them - let's say road A is connected to B,C,D on one edge but there are only turns possible from A to C and D. Let's say I represent this by a graph where each road is an edge and each road meeting/end is a vertex.

I want to run an A* or any other on such representation but... moving from node to node in the graph I strictly need to know where did I come from... I mean - from what direction. The next vertexes I can move to depend on the open turns that I have.

I can keep where I came from but I also want this to be as generic as possible and the simple graph solution doesn't provide me a knowledge where do I come from.

Could you please advice me how would you approach this one?

Thanks!

Answer 1

Represent each node as a bunch of nodes, one for each incoming road.

So let us have the following graph.

And let use the following rules:

• If Came to B from A than we can only turn to D
• If Came to B from C than we can only go to E
• If Came to C from A than we can go to both B and D
• If Came to C from E than we can only go to B

Than we have the following equivalent graph, now every node marked by original name and incoming road:

This is universal way that allow as to use any standard algorithm for directed graph in such situation. For some algorithms you may need to create fake source or initial and sink or goal nodes to handle that in such graph they can be represented as several nodes each, in current case we may need an additional node to describe behavior if we start from this nose, instead of coming from some other, but generally it is just original structure represented as classical graph.

Also we don't really need to split A, D or E if they always have the same behavior.