Category: Tutorial

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.