Category: Programming

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.