CODEWITHSUNDEEP
algorithmconstraintspath-findinga-star
Lucinda Rigetti
Lucinda Rigetti

Reputation: 596

Adding bot turn costs to A* search in pathfinding within a grid

I have an NxM grid of square cells. traversal can only happen in North, South, East and West directions in the cells. Some of the cells are blocked and cannot be traversed.

A bot is given a start and end location and needs to find the path that takes the least amount of time.

Traversing between neighboring cells costs 1 unit of time. So N cells traversed should be equal to N units of time.

However in this problem there as slight issue. If a bot ends up making a 90 degree turn in any direction. The turn itself (which is in place) will cost 2.3 units of time.

I currently have a simple A* search implementation that is able to accomplish the normal path finding, however I'm stuck on how to incorporate the turn cost, as it can only be known in the third cell that is traversed - in short maintaining a window of length 3 in the path and determining if a turn has occurred.

What is the best way(s) to incorporate such a turn penalty in A* search?

Upvotes: 6

Views: 56

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86116

One simple way is to encode the unit's direction as part of the graph itself. You can do this by making four copies of the graph - one for each direction - and then connecting the each node in each graph to its neighbors in the appropriate graphs.

For example, in the "facing up" graph, each node would be connected to:

  • The node above it, in the same graph and with the usual length
  • The node to the left in the "facing left" graph, with the cost to turn added to its usual weight
  • Similarly with the node on the right

Once the graph is setup, you can run any off-the-shelf pathfinding implementation.

Upvotes: 5

Related Questions