Category: Pathfinding

December 16, 2019

A* Tutorial Series

A* Pathfinding (E10: threading)

A* Pathfinding (E10: threading)

Link – Tutorial

By: Sebastian Lague

Intro:

This tutorial gets into the idea of threading to help relieve some of the burden on processing caused by the pathfinding logic. Threading is not something I understand very well, so I will have to look into this more in the future, but I wanted to cover this tutorial just for completions sake.

Tutorial

This setup usese another namespace, the System.Threading namespace. This lets them use the ThreadStart delegate type and the lock keyword. ThreadStart can be assigned the value of some other delegate, with in this case contained the FindPath method from PathfindingHeap. I then looked up the lock keyword here:

https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/lock-statement

While this sort of threading setup has some unique syntax, it is an otherwise simple setup. There is a queue of PathResults that are just checked paths that are waiting to be called for the movement of units. The paths get created and checked to make sure they can hit the target, and once this is satisfied, it gets added to the queue.

Summary

I would need to have a better understanding of threading and how to utilize it to assess how useful this tutorial really was. I know the general idea behind it is to help distribute the processing load, but I do not know how well this new setup accomplishes that.

December 13, 2019

A* Tutorial Series

A* Pathfinding (E08: path smoothing 1/2)

A* Pathfinding (E08: path smoothing 1/2)

Link – Tutorial 1

By: Sebastian Lague

A* Tutorial Series

A* Pathfinding (E09: path smoothing 2/2)

A* Pathfinding (E09: path smoothing 2/2)

Link – Tutorial 2

By: Sebastian Lague

A* Pathfinding (E08: path smoothing 1/2)

Intro:

These tutorials both covered the same general topic of smoothing the path of the unit.

Theory

Currently the units follow the path by making a straight line from one point to the next, which looks unnatural. To remedy this, they suggest a path smoothing technique.

This system starts with each point having a small line pointing directly to the previous point, whose length is called the “turn distance”. This line then has a perpendicular line emanating from the end, called the “turn boundary”. Once the unit passes this turn boundary, it will start to turn towards the next point in the path (instead of making direct contact with its current point destination). The only difference on any of the points is that the end point just has the turn boundary placed directly on itself (instead of at the turn distance). A turning speed value is also attributed to the unit to complete the parameters for controlling the amount of smoothing.

Turn Distance: distance away from a waypoint destination a pathing unit starts to turn towards the next waypoint in line

Turn Boundary: the actual line where the unit begins to turn towards its next destination

Programming

This was a very heavy math programming section that just had to do with drawing perpendicular lines accurately at a certain distance away from each waypoint along the path. To do so, they created a new struct named Line, and a new class named Path.

Line

This struct is responsible for all the heavy math behind building these lines perpendicular to the path properly. The names for the input parameters were misleading, as they named them “pointOnLine” and “pointPerpendicularToLine”, but the second is actually a point perpendicular to the perpendicular line it is making (so it’s actually just another point in line with the normal path line). It then uses these two points to build a line and figure out the line perpendicular to them, which is what is needed with this method.

This also deals with helping determine which side of the point the unit is approaching it from. This will be important for determining which way to start turning the unit to properly aim for the next waypoint.

Path

This class is mostly responsible for taking in the waypoints we have already determined and using those to position the turn boundaries. This just uses a directional vector between a waypoint and its next waypoint to position the turn boundary a bit before it (using the turn distance value). Then it just places Lines at these points.

A* Pathfinding (E09: path smoothing 2/2)

Intro

This follow up is to actually use what was created in smoothing the paths in the last video to actually have the unit move and follow this new pathing method.

Unit

This class was significantly modified, especially the FollowPath method, to work with the new pathing behavior. It was generally straight forward though, as it is still following waypoints for the most part. It just has additional behavior to start moving towards the next waypoint when it crosses a turn boundary.

Issues with Pathing System

There was an interesting part where they covered issues with very high speed units. Basically they could pass multiple waypoints in a single frame with high enough speeds, which can cause very weird behavior as it tries to come back to hit the next waypoint in its logic (even if it is now several waypoints ahead positionally).

They fixed this by changing the if statement for “crossing the line” to a while statement. This ensures that even at high speeds, it will stay within this loop of updating its waypoints until it reaches one that is has not crossed yet before changing its trajectory. It still behaves weirdly, but it at least reaches the destination very quickly, as it should.

Updating Path at Run Time

They basically just moved the PathRequestManager.RequestPath method into a coroutine. They added some conditions to update the path so it was not happening constantly. These were based on time and distance. The target needed to at least move a reasonable amount before updating, and a small amount of time needed to pass before each update. These were just to keep it from updating every single frame.

Error with Updating Path

For some reason my version was not working properly. The path was updating fine, as I could see with the visualization, but the unit would stop moving and never move toward the target again. I was getting an index out of bounds error, some I have some issue with one of my arrays somewhere, but not sure where. It was running fine in the tutorial, so I must have missed something.

Slowing Down the Unit Near the End

They wanted to add an extra feature where the unit slows down as it gets close to the end of its path. They added an extra method in the Line struct to find the distance between a point and the finish line (line going through the final point/destination). They wanted to use this to determine when to slow the unit down. This however has an issue with some paths where the finish line crosses through other parts of the path, as the unit would slow down at weird times.

To fix that, they used the stopping distance (the distance before the end to start slowing the unit) to go backwards from the end point to identify which waypoint the unit should start slowing down after. This was done by basically adding up the distance between each waypoint from the end backwards until that total distance was greater than the stopping distance.

Fix for: Error with Updating Path

I have no idea how this works, but I saw it in the comments of the tutorial. For some reason, in the OnPathFound method in the Unit class, if you pass the IEnumerator FollowPath into the StopCoroutine and StartCoroutine methods as “FollowPath” instead of FollowPath() or using an IEnumerator variable, the updating works.

This makes no sense to me, as it works completely fine the other ways when doing a single initial path, but as soon as you move the target and it tries to update, only one way works for some reason.

I think it may have to do with how coroutines are handled in Unity. My guess is that the quotations form is the only one that is properly stopping the correct “FollowPath” coroutine and then starting a new one. The other approaches might not be stopping it properly, which is leading to a weird issue where the coroutines are stacking on top of each other.

My other guess is that somehow these other techniques stop the coroutine but keep track of where it is stopped, and then start back up where they started. This could possibly be what is leading to an index out of bounds issue since a value might not be updated as it should after changing the path.

Overall Summary

There are a lot of interesting ideas going on here, and it will take some time parsing out the useful bits for myself. The path smoothing is definitely a nice touch to help keep the moving units from looking extremely robotic in their movements, and there are probably a lot of other ways to look into to achieve this as well.

Updating the paths at run time is a huge feature I would like to understand better and explore more as it may be very useful to me in some cases. I was having some weird trouble with they way they implemented it in this tutorial, so I would like to understand those issues or find another way to use such a feature.

Slowing the units down before they reach the end is not particularly useful to me, but this general concept of controlling the unit’s speed throughout its pathing could possibly be interesting. This will be something good to just keep in mind as an option.

December 4, 2019

A* Tutorial Series

Pt. 05 – Units

A* Pathfinding (E05: units)

Link – Tutorial

By: Sebastian Lague

Intro:

This tutorial focuses on passing the Pathfinding information to units so that they can actually use it to move.

PathRequestManager and Updating Old Classes

Having many units use this logic at once would be a bit too costly and could cause slow downs, so this needs to be managed and spread out in order to keep the game from slowing down or stopping.

This was done by creating the PathRequestManager class. This was created to ensure only one request would be processed at a time. Requests were added to a queue, which are then popped off one at a time to fulfill. A simple bool check was used to ensure one request was being done at a time (isProcessingPath).

A new struct named PathRequest was created within this class as well to make managing the data much easier. These PathRequest objects would hold a Vector3 for the start position, another Vector3 for the end position, and then a bool named callback. This just helps keep all the data together in a nice package when processing through the request manager.

Once this was setup, the Pathfinding class (PathfindingHeap) needed updated to work with this. As I expected, the FindPath method was changed to a coroutine, and a method was added within PathfindingHeap simply to start this coroutine (as well as pass in the needed parameters for starting and ending positions). Next was getting a unit to actually use all of this to inform its movements.

All of the nodes used for the path are effectively used as waypoints for an object to move through. Bigger and higher resolution grids would be creating a lot of waypoints this way, so to reduce this they created a SimplifyPath method that only creates waypoints at nodes where the direction changes. A Unit class was then created for the actual moving objects that simply requests a path and then follows the waypoints generated by the path.

Visualization

Finally for visualization purposes, they used some more OnDrawGizmos methods. They drew a cube at each waypoint, and then drew a line between each of these waypoints. The lines were then removed as the unit traversed them to show their remaining path. This was a really neat and effective way to show their pathing logic.

Summary

This setup for a request manager seems very simple, but effective enough for lower scale cases. I think some of my recent work with overall event systems in Unity could be used to really improve this overall system. The visualization was a nice touch and worked really well. This is definitely something I want to look into more to help show how logic behind the scenes works to others.

December 2, 2019

A* Tutorial Series

Pt. 04 – Heap Optimization

A* Pathfinding (E04: heap optimization)

Link – Tutorial

By: Sebastian Lague

Intro:

This tutorial focused on converting the pathfinding setup over to a heap system to help speed up the process, especially for larger scaled environments and node grids. There is some useful theory at the beginning, and then it gets into heavier code work, so I again break down the classes later in the tutorial.

General Heap Theory

One of the first places to optimize this A* pathfinding is in the Pathfinding class where it searches through the entire open set every time it tries to determine the next lowest F cost node. Heap optimization will be used here to reduce the load of the process.

A heap is basically a binary tree where each node branches out to two more nodes. The general rule of this tree is that the parent value is less than that of the children nodes. When placing a new node, it is placed at the end (on a “leaf of a branch”) initially. It is then checked with its parent and if it is less, it swaps positions with that parent. This continues until it reaches a parent with a lower value, or the node moves all the way to the top.

For the A*’s needs it will constantly be removing the node with the lowest value. This will always be the node found at the top of the heap. To fill the space when that is removed, they take the last value added to the tree and place it in the opening (at the top). They then compare this with the children nodes and swap it with whichever value is lower. This continues until it reaches a point where none of the children are lower value (or it has reached the end of a branch).

Some basic integer math can be used to locate the array index of an element that is the parent or a child of any given node. A parent can be found for any index with the formula:

parentIndex = (index – 1) /2

This works with both children as “half” values will round down in integer math.

Then this can similarly be used to get the children of a node, with the minor caveat that each child has its own unique formula. The formulas for these are:

leftChildIndex = 2 * index + 1
rightChildIndex = 2 * index + 2

Heap Class

They created an entirely new class named Heap. This was a generic class that would take in a type, T, so that it could also be generically used for various different types of objects. This started with some basic fields for an array of items (of type T) and an int for currentItemCount. There was then a constructor that simply took in an int as a parameter which dicated the size of the items array.

They then created a new interface, IHeapItem, within this same script. It implemented the interface IComparable (which is part of the System namespace). It was initially created with just an int named HeapIndex, which will be used to hold the index value of that item within the heap. This was important to note as the Heap class then used a “where” keyword to dictate that T implemented the IHeapItem interface. I assume this means that the type T used for the Heap class MUST implement the IHeapItem interface.

They create a few key methods here in the Heap class. The Add method takes an item of type T and adds it to the heap by setting its heapIndex to the currentItemCount and then adding it into the items array at the end (in index currentItemCount). It then uses the SortUp method to properly position that element in the heap, and increases the currentItemCount.

SortUp is the basic logic for continuosly comparing a new element to its parent until it is properly positioned. It uses the CompareTo method within to compare the items with their parents, which can return a value of 1, 0, or -1 depending on how the comparison priority is determined.

Then a simple Swap method was created to properly swap the items in two index array positions. It also has to separately change their heapIndex values to match their new index positions. This is done by also swapping the two items heapIndex values.

Then a method is also needed to remove items from the heap. This was named RemoveFirst. It returned the top element of the heap (items[0]), and then replaced it with the last element in the heap, with index (currentItemCount – 1). It then has to run a similar sorting algorithm to properly place this newly moved item.

The method to sort this newly moved item was named SortDown. This took an item as a parameter and constantly compared it with its children items and swapped their positions until it either reached the bottom of the heap or did not find children with higher priority than the actively sorted item. It checked if there were any children, then which child had higher priority, than compared the higher priority child to the current item. If the child was higher priority, they swapped. Otherwise, end the loop.

Update Node Class

They then move to the Node class to update it with the new Heap class. This starts by implementing the new IHeapItem with type Node. Because of this implementation, they need to add an int field for HeapIndex, and because of that interface implementing IComparable, they also need a method named CompareTo.

HeapIndex just gets and sets the value of heapIndex. CompareTo uses compareTo methods to compare the fCost and Hcost values to determine which node has higher priority. Integers can use the CompareTo method as well, and will similarly return 1 if the value it is compared to is greater, 0 if they are the same (equal), and -1 if it is lower.

So their approach creates an int named compare that is set equal to the CompareTo value between the fCosts of both nodes. Then, if it is 0 (which means they are equal), it sets compare equal to the compareTo value between the hCost values of the nodes. Finally, it returns the opposite value of compare (-compare), since they want it to represent higher priority, which actually corresponds with the lower cost values in this case.

Finally they just needed to update the Pathfinding class to use the heap instead of a list. I made a separate class called PathfindingHeap just to archive both versions of the code for myself. They then showed how to use the System.Diagnostics namespace to create a StopWatch to keep track of time as a measure of performance. This helped show that the new heap method is much faster for larger scale searching and grids.

Summary:

The heap optimization clearly appears to work from the several tests I ran and they ran in the tutorial video, especially as you scale up the environment. While this is clearly very useful for pathfinding, the general theory behind heaps also just seems to be useful knowledge for generic programming practices. This makes it very nice that the tutorial sets it up in a very generic way, so I can possibly use this for other logic later on.

Check:

I need to look into the syntax used for the Heap class setup. The initial line for the class is:

public class Heap where T : IHeapItem

This is syntax I have not come across before. I assume this means that the type of objects used for the Heap MUST implement the interface IHeapItem, but I want to look into this just to make sure.

Sebastian Lague A* Tutorial Series – Algorithm Explanation – Pt. 01

November 20, 2019

A* Tutorial Series

Pt. 01 – Algorithm Explanation

A* Pathfinding (E01: algorithm explanation)

Link – Tutorial

By: Sebastian Lague

Notes:

G cost = distance from starting node H cost (heuristic) = distance from the end node F cost = G cost + H cost

A* starts by creating a grid of an area. There is a starting node (initial position) and an end node (destination). Generally, you can move orthogonally (which is normalized as a distance of 1) or diagonally (which would then be a value of sqrt of 2, which is approx. 1.4). Just to make it look nicer and easier to read, it is standard to multiply these distances by 10 so that moving orthogonally has a value of 10, and diagonally has a value of 14.

The A* algorithm starts by generating the G cost and H cost of all 8 squares around the starting point (in a 2D example for ease of understanding). These are then used to calculate the F cost for each square. It starts by searching for the lowest F cost and then expanding the calculations to every square in contact with it (orthogonally and diagonally). Recalculations may be necessary if a certain path finds a way to reach the same square with a lower F cost. If multiple squares have the same F cost, it prioritizes the one with the lowest H cost (closest to the end node). And if there is still a tie, it basically can just pick one at random.

It is worth reiterating that the costs of a square can be updated through a single pathfinding event. This however only occurs, if the resulting F cost would be lower than what is already found in that square. This is actually very important as the search can lead to strange paths to certain squares giving them higher F costs than they should have when there is a much more direct way to reach that same square from the starting node.

Coding Approach

Psuedo Code (directly from tutorial):
OPEN //the set of nodes to be evaluated
CLOSED //the set of nodes already evaluated
add the start node to OPEN

loop
current = node in OPEN with the lowest f_cost
remove current from OPEN
add current to CLOSED

if current is the target node //path has been found
return

foreach neighbour of the current node
if neighbour is not traversable OR neighbour is in CLOSED
skip to the next neighbour

if new path to neighbour is shorter OR neighbour is not in OPEN
set f_cost of neighbour
set parent of neighbour to current
if neighbour is not in OPEN
add neighbour to OPEN

There are two lists of nodes: OPEN and CLOSED. The OPEN list are those nodes selected to be evaluated, and the CLOSED list are nodes that have already been evaluated. It starts by finding the node in the OPEN list with the lowest F cost. They then move this node from the OPEN list to the CLOSED list.

If that current node is the target node, it can be assumed the path has been determined so it can end right there. Otherwise, it checks each neighbour of the current node. If that neighbour is not traversable (an obstacle) or it is in the CLOSED list, it just skips to check the next neighbour.

Once it finds a neighbour to check, it checks that it is either not in the OPEN list (so this neighbour is a completely unchecked node since it is in no list since we also just checked to make sure it was not in the CLOSED list) or there is a new path to this neighbour that is shorter (which is done by calculating the current F cost of that neighbour, since it could be different now). If either of these are met it sets the calculated F cost as the actual F cost of this neighbour (since it is either lower or has never been calculated), and then sets the current node as a parent of this neighbour node. Finally, if neighbour was not in the OPEN list, it is added to the OPEN list.

Setting the current node as the parent of the neighbour in the last part of the psuedo code is helpful for keeping track of the full path. This gives some indication of where a node “came from”, so that when you reach the end you have some reference of which nodes to traverse.