top of page

A* Pathfinding

About

This project is dedicated to implementation of A* algorithm. I implemented priority queue using Binary search algorithm that is used by A*. In addition to that I made custom window editor where I can build different maps to try out the algorithm.

Project Info

  • Role: Tools and System programmer

  • Time: 3 weeks

  • Team Size: 1

  • Engine: Unity

  • Engine Experience: 13 months

  • Programming Experience: 13 months

Priority Queue and Binary heap

Why priority queue?

That was my third time implementing A* pathfinding and I wanted to make it more optimised. After doing some research, I realised that priority queue is used in A* algorithm.

​

There was a problem however, unity didn't have built-in priority queue, therefore I had to make it myself.

Binary-heap

Initially I wanted to implement Fibonacci heap as it is more efficient, but it was taking me too long to understand and make something out of. Instead I programmed binary-heap in order to program the priority queue. 

Visualisation

In this video, I generate random numbers and then use max binary search to arrange things in the array. The visible result is the largest number gets to the top

In the video to the right, I generate random numbers, then use min-binary search to arrange them in the array immitating priority queue.

A* Pathfinding

What is A* pathfinding

  1. Cost from start (S)- What is the cost to reach to this Node from start

  2. Heuristic cost (H) - Estimated guess about how much will it cost to get to desination. Esimated means we don't take into consideration things like terrain and walls.

  3. Combined cost (C)- Two previous costs put together

Here you can see that the node that is picked next for evaluation is always the one with lost "C" cost.

Costs Math

In order to calculate costs we use following formulas:

  1. S = S[previousNode] + TerrainCost From this node to ajdecent one + Walking Cost from this node to adjecent;

  2. H = WalkingCost from this Node to Destination Node

  3. C = S+H

    •  Walking Cost = StraightMove - 10 ; Diagonal - 14;

Here is another visualization, I added some walls(Black tile) that are not walkable and water. Water(Blue Tile) has 8 times the walking cost of the road(Yellow)

Playtime

Now we can play a little game, I made a long tonnel with different terrains. Which path do you think is going to be the fastests?

  1. Zig-zag road

  2. Straight but only water

  3. Random Forests and mountain(most expensive) terrains

Tools

EditorWindow

In addition to implementing pathfinding, I decided to try to get into a little bit more advanced tool development. I made a custom Editor Window to help me visualize A* algorithm.

The window has a few responsiblities. First of all, it ensures that the grid is created by creating it itself if it's not present. Secondly, it allows interractions with the grid by changing tile types and the size of the grid.

In the video, you can see how you can interract with the editor to change the properties of the map.

Workflow example

bottom of page