CODEWITHSUNDEEP
c#unity-game-enginepath-findinggame-development
Hammy
Hammy

Reputation: 13

Trouble implementing gridbased pathfinding with limited turns

I'm in the process of making a 2d, gridbased game and have reached a standstill due to challenging code. I need to navigate from one cell in the grid to another if possible, but with a maximum of 2 turns.

See here

The red ball is the goal, and the green paths are ones that are valid, "turns" are highlighted by a blue circle.

Without brute forcing the issue and checking every posssible path how could this be done? I've experimented with a few ideas along with an a* implementation, but no luck so far. Any ideas, using unity's API or anything else is highly appreciated.

Upvotes: 1

Views: 584

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

This can be solved using normal A* by creating a specially-designed directed weighted graph from your original grid.

The trick is to create a graph with multiple "layers". Layer 0 represents 0 turns having been made so far, layer 1 represents 1 turn made, and layer 2 is 2 turns. A node connects to its neighbors on the same layer if they can be reached without turning, and its neighbors on the next layer if they require a turn.

Hopefully this is enough information for you to create the graph, but if not, the explicit steps would be:

  1. Create 6 copies of the graph, Layer_0_Horizontal, Layer_0_Vertical, Layer_1_Horizontal, Layer_1_Vertical, Layer_2_Horizontal, Layer_2_Vertical.
  2. For each node in a Horizontal layer, remove its edges to its vertical neighbors, and replace them with edges to nodes in the next layer down, with eg. Layer_1_Vertical being below Layer_0_Horizontal. Edges in Layer_2 won't be replaced. Do the same thing for Vertical layers / horizontal edges.
  3. Create a fake 'start' node, and connect it to the two Layer_0 nodes that represent that same grid-square with 0-weight edges. If your A* implementation only supports one goal-node, do the same with the goal.

If you want to prefer longer paths with less turns over shorter paths with more turns (is that even possible with only two turns??), give the edges between layers an extremely large weight.

Upvotes: 2

Related Questions