CODEWITHSUNDEEP
path-findinga-star
Mike Stoddart
Mike Stoddart

Reputation: 506

Avoid u-turns in A* algorithm

I have defined nodes and edges for a graph, which I want to use to resolve pathfinding using the A* algorithm. I have an A* algorithm that seems to work but I now need to prevent u-turns. These aren't 2 or more lanes roads, these are single direction only, although two nodes form two edges (one in either direction).

So, for example, if I want to calculate the route from 1114-1105, the algorithm gives me 1114-1112-1105. This is invalid as it involves a u-turn from 1112 to 1105. The result I want to achieve would be more like 1114-1110-1111-1113-1112-1105.

I naively thought I could calculate the angle between the previous, current and next nodes, which in this case would be 0 and then add a large number to the 'f' value. But this doesn't seem to do anything.

Any suggestions for how to implement this? Thanks

Example graph

Upvotes: 0

Views: 271

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86146

Your "state" in the graph depends on two things:

  • The node you're in
  • The node you came from

To model this, we can create a new (directed) graph where each "state" is its own node. In other words, you create a new graph by splitting each node in your old graph in N nodes in the new graph (where N is the number of incoming edges to that old-node). The new-node will then have fewer outgoing edges.

This may split your start/end nodes into multiple nodes. To fix this, you can create new single start/end nodes, and connect them to the old start/end nodes with 0-cost edges.

Upvotes: 1

Related Questions