Languages
» Pathfinding algorithms in Unity
Here you will find information about pathfinding algorithms. If you need visualization to better understand how they work, below I provide a link to the application 🙂
Aplikacja
Whole application with the video tutorial and music was made entirely by me.
Colors explanation
I’m posting an explanation of the colors used in the application here. As soon as I finish the settings panel, you’ll be able to change them freely within the program.
Nodes:
Sea – default
Green – start
Pink – target
Black – blocked
Markers:
Yellow – ready to check (opened)
Green – checked (closed)
Blue – path
Algorithms
Assumptions for explanations:
- Nodes colors are like in the description above.
- Permitted directions and order is as follows: up, down, left, right.
- Blocked nodes and ones previously added to the collection (already opened) are ommited.
First two steps in my implementation are the same regardless of the algorithm type:
1. Check if the starting node is the ending node and close it. If so, draw the path. If not, proceed further.
2. Add all neighboring nodes for inspection according to the assumed direction order. If any node has been already added, skip it. In the BFS and especially the DFS the speed of finding the correct path depends on the order in which subsequent nodes are added.
Breadth first search
As the name suggests, this is breadth-first search (breadth = width), meaning that starting from the initial node, the algorithm first checks all nodes around it (the order can be determined), then all nodes around those checked, and so on. Depending on which side we start from, the result may vary (more or fewer moves may be needed to reach the goal).
3. Check the next node from the collection of open nodes and close it. Nodes are sorted according to the FIFO rule (First In First Out), so the next node should be that one opened at the earliest (not closed yet). Because our order is: up, down, left, right and the upper node is blocked, algorithm moves to the bottom one.
4. Repeat points 2 and 3 until you find the ending node or check all possible nodes for inspection. Nodes next in the queue are left and then the right one.
5. If the cursor has found the ending node, draw the path from the starting position to the destination position.
Depth first search
As the name suggests, this algorithm chooses one corridor, checks nodes proceeding towards chosen direction until that corridor ends. Here direction order has a great impact on the total time needed to find the path. Also we are not ensured, that found path is the shortest path.
3. Check the next node from the collection of open nodes and close it. Nodes are sorted according to the LIFO rule (Last In First Out), so the next node should be that one opened at the latest (not closed yet). Because our order is: up, down, left, right, algorithm moves to the right (right node has been added at the latest).
4. Repeat points 2 and 3 until you find the ending node or check all possible nodes for inspection. Since the latest added node is the right one, algorithm continues checking in the right direction until it hits the end of maze. Then moves back to the previously opened corridor.
5. If the cursor has found the ending node, draw the path from the starting position to the destination position.
A*
A* is a little more complicated algorithm, but not so much. Its difference in reference to previous ones is in having some sort of specified criteria of open nodes collection sorting, so the order of nodes prepared to check changes dynamically while algorithm is working.
Every node must have specified 3 values commonlty named:
- H = cost to the goal
- G = cost from the start
- F = H + G (score)
Cost to the goal (H) can be measured in plane distance from the specified node to the destination one, calculated using the Pythagoras Theorem or calculated in another way (e.g. number of moves in the horizontal and vertical directions, which algorithm needs to do in order to reach the destination).
Cost from the start (G) can be simply set as the number of moves that algorithm had to do to reach specified node. You can also add a special restrictions to the diagonal movement, if You want to.
Score (F) is a sum of the above values. Algorithm determines next node to check by this score value. According to the specified node, the lower score has, the earlier will be chosen.
3. Check the next node from the collection of open nodes and close it. Nodes are sorted according to the score (F) value explained above. Every node opened so far has the same cost from the start (G), but with a naked eye we can notice, that the right one has the shortest distance to the destination node (ommitting blocked nodes – in a straight line). Therefore the right one is chosen.
4. Repeat points 2 and 3 until you find the ending node or check all possible nodes for inspection. At this stage distance of every next specified node is short so much, so their scores are still lower than the scores of the other ones left behind (despite still increasing value of the cost from start – G).
5. If the cursor has found the ending node, draw the path from the starting position to the destination position.
It is much more difficult to judge oneself than to judge others. If you succeed in judging yourself rightly, then you are indeed a man of true wisdom.
-- Little Prince --