Category: AI

Coroutine Error Investigation in A* Tutorial Series – Path Smoothing – E09

digm520admin / / A*, AI, Debug, Pathfinding, Programming, Unity
December 13, 2019

A* Tutorial Series

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

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

Link – Tutorial

By: Sebastian Lague


Intro

I wanted to further my investigation on the issue I had with coroutines when dealing with updating the pathing of the A* units when following the A* tutorial series, specifically in episode 9. I have included the sections “Error with Updating Path” and “Fix for: Error with Updating Path” from my last post to keep them together, along with my updates for the investigation.

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.

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.

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.

Testing

The issue is that using StartCoroutine(“FollowPath”) and StopCoroutine(“FollowPath”) works completely fine, but replacing “FollowPath” with FollowPath() or followPathRoutine = FollowPath() does not work. There is some functional difference between these ways of referencing coroutines that I do not see. For matters of testing, I am trying to see if I can get the variable reference method to work (followPathRoutine = FollowPath()).

Test 1

The error was pointing to this line specifically:

while (path.turnBoundaries[pathIndex].HasCrossedLine(position2D))

So this line does make sense for a possible out of bounds index error when looking in the turnBoundaries array. My first test was to check what the pathIndex value is right before this while loop executes to see if it was being passed a weird value at some point. It turned out that I never got a weird pathIndex value when the error occurred (upon moving the target), so the pathIndex was not being changed or anything.

This was actually a bigger issue than I thought because pathIndex is specifically set to 0 at the beginning of this coroutine where this line is located, which indicates to me that the coroutine is not properly being terminated and reset. This supported my thought that maybe the coroutine was resuming immediately within the while loop. However, a more logical issue may be that the path is being updated, but not the pathIndex, so this new path has a different turnBoundaries array where that same pathIndex (since it isn’t properly being reset) gets an out of bounds error.

Test 2

I followed this test up with another quick debug log just outside of the entire while loop containing this while loop (so basically at the initialization of this coroutine) just to see if the coroutine was being executed more than once at all. As I expected, it was not even being restarted at any point while hitting this issue. Since the error is within the coroutine and happening when a new one should be started (but clearly isn’t), this made it fairly obvious something was wrong with how the coroutines were being stopped and started.

Test 3

I decided to split up the functionality to see if I could isolate the issue better. I simply added in an Update method to StopCoroutine when space was pressed to see specifically what just doing that would result in. I started the game and pressing space did indeed stop the unit from moving. I then furthered this test by moving the target now, knowing for sure that the coroutine had been stopped. This did allow the unit to reacquire the target and start moving towards it again. However, if I moved it several times, the error would come back again.

It is also very important to note that pressing space bar again when the unit was moving towards the newly acquired target did NOT stop it anymore. This suggests to me that my coroutine variable lost reference to the specific instance responsible for moving the unit. This would also make sense with the issues that I was having since it tries to start and stop the same exact instance of the coroutine.

Furthermore, my debug log of the path index was still running during these tests, and I could see specifically that the pathIndex was NOT reset when it reacquired the new target and starting moving in this setup. So pressing space stopped the coroutine, stopping the unit, but when it started moving again, the index was not updated. It actually kept the same pathIndex it had before pressing space, but was using it to move still.

The main difference between how it normally runs, and the “press space to stop” version work is that it normally gets a new path, then stops and starts the coroutine, where as the other version stops the coroutine, THEN gets the new path, then starts another coroutine. This difference is allowing the unit to at least somewhat reacquire the target and move again.

Test 4

To more accurately match the case with pressing spacebar since that seemed to work a bit more consistently, I moved the StopCoroutine before updating the path variable. I then also added a debug check here to output what the current number of waypoints were every time the path was updated. This would help confirm the indexing issue since if the number of waypoints were lower that the current pathIndex that does not seem to be updating, it would be pretty clear that this is indeed the issue.

Sure enough this proved my suspicions. I could now move the target some without the pathing breaking, but once I hit a point where a path had less waypoints than the pathIndex, the error came up and it stopped moving. So in this case, the coroutine is clearly not being reset properly.

Test 5: FIX

Since my followRoutine IEnumerator variable seemed to be losing reference to the current coroutine I needed access to, I decided to try and reset it values each time I needed to run a new coroutine. After stopping the coroutine with StopCoroutine(followRoutine), I then set followRoutine = FollowPath() again, before calling StartCoroutine(followRoutine). This approach actually worked perfectly! It was now stopping the correct coroutine instance and creating an entirely new one when starting on its new path. The pathIndex was properly being reset to 0 as that coroutine was properly called from its beginning each time.

Summary

The first big thing is that the different input types for StartCoroutine and StopCoroutine actually act differently just from these inputs. That is very important to know moving forward with those. It also appears that this method of setting an IEnumerator variable can work in these types of cases by making sure to set it equal to the IEnumerator again. This must have something to do with how coroutines can have multiple instances of themselves running, so this helps specificy which instance of the coroutine to stop and start.

Sebastian Lague A* Tutorial Series – Path Smoothing – Pt. 08 and Pt. 09

digm520admin / / A*, AI, Pathfinding, Programming, Tutorial, TutorialList, Unity
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.

Sebastian Lague A* Tutorial Series – Smooth Weights – Pt. 07

digm520admin / / A*, AI, Programming, Tutorial, TutorialList, Unity
December 10, 2019

A* Tutorial Series

Pt. 07 – Smooth Weights

A* Pathfinding (E07: smooth weights)

Link – Tutorial

By: Sebastian Lague


Intro:

This tutorial covers smoothing the movement penalty values out over an area, as opposed to the areas just directly being either one value or another. This will also be helpful for my uses as most cases when updating movement penalties in areas will not just want to update the single exact node where an important action happened. While that area should most likely have the largest impact on its weight, it will make sense to apply a light value change around that area as well. This seems to fit right in with smoothing or blending of weight values.

Theory

Box Blur: weight smoothing algorithm using averages of values within a kernel around a block in the grid

Kernel: a smaller grid sample within the overall grid; used here as the space to gather data from to create an average value with

The smoothing theory they look at is called Box Blur. In this case, each part of the grid represents an average value of the blocks around it. This smaller grid used for the averaging process is called a kernel. They intitially show this off by using a 3×3 kernel, which averages all 9 values in the kernel and places that value in another grid in the same relative location as the center of the kernel. This shows off the idea well, but they mention a more efficient way.

The more efficient way is to do a horizontal pass and a vertical pass separately. Representing the same overall 3×3 kernel as before, they start by doing the horizontal pass with a 1×3 sized kernel. This adds the 3 values in a row horizontally. This becomes more efficient because when they move to the next grid element, instead of searching for the next 3 elements, they simply keep tabs on the current sum and subtract the leftmost value (which is no longer in the kernel) and add the new rightmost value (which was just added to the kernel).

This is repeated over the entirety of the grid until they all received a horizontal pass (in all cases, values near edges of the grid are repeated if the kernel would go out of bounds). They then go through this new grid of summed horizontal values and do the same process, but vertically (so a 3×1 kernel). This gives the same exact resulting grid as the first method that averaged 9 values at once with the 3×3 kernels, but more efficiently.

AGrid

The approach here is actually pretty standard to what I would have guessed. They create 2 new grids with dimensions equal to the original pathing grid for each of the blurring passes, horizontal and vertical. They do the horizontal pass first, which grabs values from the original grid and sums them in kernels whose size is determined by the designer. The vertical pass then uses the values from the horizontal pass grid to create its own grid. These values are then passed in as the movement penalty values to the corresponding original grid nodes.

The key things to note were:

  • They wanted the kernel to always be an odd value so that it had a clear central location, so the input parameter of blursize was always multiplied by 2 and had 1 added for the kernel size. This mathematically ensures they are always working with an odd value.
  • To replicate the idea of “duplicating values at the boundaries outside of the grid” they used Mathf.Clamp when searching for grid elements to sum so that if it ever went out of bounds for a grid index, it used a clamped value at the edge instead (effectively grabbing the same value again in edge cases).
  • The core of the algorithm needs values to already exist, so there is some additional logic for the first pass just to make sure all the intial values are properly set first before the true process begins.

Visualization

This again is something I always like to learn more about, and this was exactly what I wanted with this type of system just to help truly see what is going on behind the scenes with all the pathfinding logic.

They did this in the way I would have approached it. As they set the penalty values, they have a simple check to figure out what the lowest and highest values in the whole grid are. They then use these values as the bounds for a Color.Lerp for the visualization between black and white. This gives the nodes a gray scale representing their cost, with black being the highest values, white the lowest, and shades of gray for the values between.

This did show an issue with the current code. The obstacles had a slight blur of lower penalties around them. This is because the code does not factor in penalty values for obstacle areas at all, so they currently have a penalty value of 0. This is generally not ideal.

Summary

This tutorial was again, a great step in the direction I am trying to take this A* pathfindin logic in for my project. Since I want to update the penalty values at real time based on events that take place within the grid, it will make sense to disperse some of that value updating out from the single node the events occur on.

Sebastian Lague A* Tutorial Series – Weights – Pt. 06

digm520admin / / A*, AI, Programming, Tutorial, TutorialList, Unity
December 9, 2019

A* Tutorial Series

Pt. 06 – Weights

A* Pathfinding (E06: weights)

Link – Tutorial

By: Sebastian Lague


Intro:

Weights are exactly what I am looking for to influence the intelligence of the units in my project. They are an additional factor for moving in certain areas to make them more or less “appealing” to the AI to further influence their movement. This makes their movement more interesting than the simple “point A to point B” shortest distance.

When importing the Road object, I had to scale mine up (x5) to fit my scene like the tutorial. Unsure if they changed the size of their scene at some point, so this may impact the way the units travel so it is important to keep in mind.

This system is going to have the grid use a bunch of raycasts to see what they collide with to determine what type of terrain is in which area. The ray will return information on what terrain was hit, and this will relay the penalty information back to that specific grid location.

Node

This class just had an int field added to it to hold the movement penalty value. While small, this is really the main piece of information that will allow everything else to work properly.

AGrid

They added a new class, TerrainType, to hold information for the various terrains. This included a LayerMask field and an int field for the penalty value. The AGrid class itself then holds an array for these TerrainType objects so that the type and its corresponding penalty can be set in the Inspector. They noted that the LayerMask field here can have multiple layers set as usual, but make sure to NOT do this currently as it will mess up the current code.

(Much more code can be added to handle this, but they just wanted to do the simple setup for now)

They wanted to create a single LayerMask variable that held all the values of the masks within the TerrainType array. Unity uses bit masks for their layer mask system, so doing this required some weird syntax:

foreach (TerrainType region in walkableRegions)
{
//walkableMask.value = walkableMask | region.terrainMask.value;
walkableMask.value |= region.terrainMask.value;
}

The commented out section is the general concept of what is happening, and the uncommented section is just a short hand notation of doing the same thing. It uses a bit-wise OR operator to “add” the values together into a single layer mask.

Finally, in an attempt to provide some optimization to this system, they created a dictionary to hold information on all of the layers in the walkable regions. As the TerrainType array was added to the overall walkableMask, they were also added into a dictionary where the first value is the layer number and the second value is the movement penalty. Then when the raycasts were run, they just had to check this dictionary with the layer number they received so they could return the proper movement penalty value.

Summary

While I am not sure if this is exactly how I will be looking to use weights in my own system, it was still very helpful to see one way of approaching it. This method focused on the movement penalty being an inherent property of the type of ground, where I am looking for something that can update in the same area over time depending on other factors (such as learned danger of an area). At the very least, the math for factoring in the new penalty costs will most likely remain pretty similar in most approaches.

Sebastian Lague A* Tutorial Series – Units – Pt. 05

digm520admin / / A*, AI, Pathfinding, Programming, Tutorial, TutorialList, Unity
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.

Sebastian Lague A* Tutorial Series – Heap Optimization – Pt. 04

digm520admin / / A*, AI, Pathfinding, Programming, Tutorial, TutorialList, Unity
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.

UnityLearn – Beginner Programming – Swords and Shovels: Character Controller and AI – Pt. 03 – Finalizing and Extending Systems

digm520admin / / AI, Programming, Tutorial, TutorialList, Unity, UnityLearn
Novemeber 21, 2019

Beginner Programming: Unity Game Dev Courses

Beginner Programming: Unity Game Dev Courses

Unity Learn Course – Beginner Programming

Finalizing and Extending Systems

Designing with NavMesh Obstacles

This section just showed how obstacles work with NavMesh. Objects with colliders can be given NavMeshObstacle components to work as obstacles within the NavMesh. The Carve bool lets you determine if they “carve out” parts of the NavMesh to make them inaccessible for agents with NavMesh driven AI.

Finishing the Patrol System

The InvokeRepeating method has a delay paramter as well. This can be given various values between different objects so they are not all on the exact same cycle. This was used to offset the waypoint traveling cycles of the goblin NPCs.

Fine Tuning the Agents and Animation

The logic that was making the player character awkwardly slow down around the stairs and other obstacles is found within the obstacle avoidance part of the NavMeshAgent component. The simple fix was to just turn off obstalce avoidance completely. This is done by setting the “Quality” of obstacle avoidance to “None”.

Conclusion and Extensions

They go back to working with the animator controller for the player character. Going back to the blend tree, they show the two parameters for the animation clips are: threshold and speed. The threshold is the value a parameter must hit to start a certain animation (here that parameter is another Speed). Since animations are being blended here, it changes the weights of the blending at various values of the parameter used to determining blending. Then the clip speed value simply changes how fast an animation clip is run.

They suggest using these animator controller parameters in concert with the NavMeshAgent parameters to keep your gameplay and animations synchronized. Using them together really helps fine tune things so that you can control gameplay exactly how you want, while also having characters and animation look proper.

They then simply show how to extend the level. It was as simple as copy/pasting some of the floor tiles, making sure they had generic colliders, and then rebaking the NavMesh.

SUMMARY

This tutorial section involved working with the NavMesh tools and Animators again. This was again not extremely detailed or involved, but extra experience with those systems are useful. Some of the work with the Animator involved generically good advice to sync blending and animator parameters with gameplay to help provide a nice game experience.

UnityLearn – Beginner Programming – Swords and Shovels: Character Controller and AI – Pt. 02 – NPC Controller

digm520admin / / AI, Programming, Tutorial, TutorialList, Unity, UnityLearn
Novemeber 21, 2019

Beginner Programming: Unity Game Dev Courses

Beginner Programming: Unity Game Dev Courses

Unity Learn Course – Beginner Programming

NPC Controller

Creating NPC Patrol

The NPC has two main states: it will patrol within a set of waypoints or it will pursue the player. They create two main methods to control the NPC behavior, Patrol and Tick.

Both of these are called in the Awake method of the NPCController through the use of the InvokeRepeating command. This is done because you can set a time value that needs to pass between each invocation, so basically they can perform these methods in a “slow Update” fashion. Tick is called every 0.5s, while Patrol is called every patrolTime, which was defaulted at 15s.

The Patrol method used an inline ternary method to set the value of index, which is something I am not used to seeing. The line was as such:

index = index == waypoints.Length – 1 ? 0 : index + 1;

I believe this checks if index is equal to (waypoints.Length – 1), then if that is true, it sets the value of index to 0, and if it is false, it sets the value of index to (index + 1) (or index++). This is actually pretty basic waypoint logic, the syntax was just unusual.

This system has some flaws as well already. The InvokeRepeating calls start their timer countdowns immediately upon calling the method. So even though the NPC takes time to travel between waypoints, the countdown to move to the next waypoint has already started as soon as they start moving. This means their travel time must be taken into consideration when setting this value as if it is too low they will start moving to the next waypoint before they have even reached the current one as a destination.

Synchronizing Animation and Creating the Pursue Behavior

This tutorial starts similarly to synchronizing the player character’s speed with its animation. They simply pass the NavMeshAgent component’s speed value into the Animator controller’s speed parameter to alter animation as the character’s speed changes.

To create the pursue behavior, they added extra logic to the Tick method in the NPCController class. They added an if conditional to check if the player was within the aggroRange of the NPC, and if so, it would add the player’s position as the NavMeshAgent destination value and increase its speed.

SUMMARY

While the NPC logic was not very interesting, some of the programming syntax used was new and interesting. The use of InvokeRepeating without any coroutines or anything was also a neat way to just get a quick prototype system setup when you want something to run many times but Update is overkill.

Sebastian Lague A* Tutorial Series – Algorithm Implementation – Pt. 03

digm520admin / / A*, AI, Programming, Tutorial, TutorialList, Unity
November 20, 2019

A* Tutorial Series

Pt. 03 – Algorithm Implementation

A* Pathfinding (E03: algorithm implementation)

Link – Tutorial

By: Sebastian Lague


Intro:

Since these sections are very coding intensive, I just setup a breakdown into the different classes that are worked on. I try to discuss anything done within the class in that class’s section here. As should be expected, they do not continuosly do a single section and move to the next, they jump back and forth so that the references and fields make more sense for why they exist, so I try to mention that if needed.

Pathfinding

This class begins to implement the psuedo code logic for the actual A* algorithm. It starts with a method, FindPath, that takes in two Vector3 values, one for the starting position and one for the target position. It then uses our NodeFromWorldPoint method in AGrid to determine which nodes those positions are associated with so we can do all the work with our node system.

It then creates a List of nodes for the openSet and a HashSet of nodes for the closed set, as seen in the psuedo code. It is around here that they begin to update the Node class since it will need to hold more information.

The next part is the meat of the algorithm, where it searches through the entire openSet to determine which node to explore further (by using the logic of finding the one with the lowest fCost, and in the case of ties, that with the lowest hCost). Once found, it removes this node from the openSet and adds it to the closedSet. It is mentioned that this is very unoptimized, but it is one of the simplest ways of setting it up initially (they return to this for optimization in future tutorials).

Continuing to follow the psuedo code, they go through the list of neighbors for the currentNode and check to see if any are walkable and not already in the closedSet to determine which to further explore.

Here they create the distance calculating method that will serve as the foundation for finding the gCost and hCost. This method, named GetDistance, takes two nodes and returns the total distance between them in terms of the grid system. Just to reiterate, it returns an approximated and scaled integer distance value between two nodes. Orthogonal moves have a normalized distance of 1, where diagonal moves are then relatively the sqrt(2), which is approximately 1.4. These values are then multiplied by 10 to give their respective values of 10 and 14 for ease of use and readability.

If it is determined that the neighbor node should be evaluated, it calculates the gCost of that neighbor from the current node by adding the distance to the neighbor from the currentNode to the currentNode gCost. It then checks if this is lower than the neighbor node’s current gCost (so they found a cheaper route to the same node) or if neighbor is not in the openSet (which means it has never been evaluated, so has no gCost to compare). If these criteria are met, it sets the gCost of the neighbor to this determined value, and calculates the hCost using the new GetDistance method created between the neighbor node and the targetNode.

It finally sets that neighbor node’s parent as the currentNode, and checks if the neighbor was already in the openSet. If not, it adds this node to the openSet.

The RetracePath method was created, which determines the path of nodes to follow once the target has finally been reached. Starting with the endNode (target position), it cycles through each node’s parent by continually changing the checked node to the current node’s parent until it gets back to the startNode, and adds them to a list named path. Finally, it reverses the list so they are in the proper order matching the actual object’s traversal path (since doing it this way effectively gives you the list of nodes backwards, starting with the end).

Node

They add the gCost, hCost, and fCost as public ints here finally. The fCost is actually just a getter function that returns gCost + hCost. This is a nice setup that provides some extra encapsulation as fCost will never be anything else so it may as well only return that sum whenever it is called.

Later they also add ints gridX and gridY, which are references to their indices in the overall grid array. This helps locate them, as well as their neighbors, more easily in later code.

A field is created of the type Node named parent to hold a reference to a parent node. This serves as the link between nodes to give a path to follow once the final destination has been reached. As the lowest fCost nodes are found, they will create a chain of parent nodes which can be followed. This is done with the RetracePath method in Pathfinding.

AGrid

They added the GetNeighbors method here. It takes in a node, then returns a list of nodes that are its neighbors. It effectively checks the 8 potential areas around the node with simple for loops spanning -/+ 1 in the x and y axes relative to the given node. It skips the node itself by ignoring the check when x and y are both 0. It also makes sure any potential locations to check exist within the grid borders (so it does not look for nodes outside of the grid for nodes on the edges for example).

Sebastian Lague A* Tutorial Series – Node Grid – Pt. 02

digm520admin / / A*, AI, Programming, Tutorial, TutorialList, Unity
November 20, 2019

A* Tutorial Series

Pt. 02 – Node Grid

A* Pathfinding (E02: node grid)

Link – Tutorial

By: Sebastian Lague


Intro:

This started by creating the overall Node class to contain valuable information for each individual node, and the Grid class that would be dealing with the overall grid of all the nodes (I rename this to AGrid to avoid errors in Unity).

Node

For now, this simply holds a bool walkable, which represents whether this node contains an obstacle or not, and a Vector3 worldPosition, which contains data on its Unity real world position.

AGrid

This class has a couple parameters that influence the coverage and resolution of the overall A* system. The gridWorldSize represents the two dimensions covered by the entire grid (so 30, 30 will cover a 30 by 30 area in Unity units). The nodeRadius is half the dimension of a node square, which will be used to fill the entire grid. The lower the nodeRadius, the more nodes (so higher resolution, but more computing cost).

The intial setup is a lot of work that simply breaks down whatever the overall area being covered by the grid into int size chunks to use as indices to work with a 2D array containing all the nodes. The NodeFromWorldPoint method is also created, which is a nice method that takes in a Vector3 value and returns the node encompassing that point. I like the extra step of clamping the values here to reduce possible errors in the future.

Unity Feature Notes:

Clamp Example:

// Clamped to prevent values from going out of bounds (will never be less than 0 or greater than 1)
percentX = Mathf.Clamp01(percentX);
percentY = Mathf.Clamp01(percentY);

Mathf.Clamp01 clamps a value within the bounds of 0 and 1. This percent value should never be outside of those for the purposes of the grid anyway (they help determine basically what percentage away a node is on the x and y axes separately relative to the bottom left node). So in error cases, this will simply give a node that is at least on the border of the grid.

The CreateGrid method in the AGrid script uses a Physics.CheckSphere method to determine if a node is traversable or not. This simply creates a collision sphere of a determined radius that returns information on anything it collides with.

Gizmos:

They use the DrawWireCube Gizmos, which just lets you create a wire cube outline with defined dimensions. This is very nifty for conveying the general area covered by something visually in your editor.

Warning:

Unity had an issue with naming the one script “Grid”, as they already something named Grid built into the system. It gave me a warning that I would not be able to use components with this object. Just to make sure I did not run into any future issues, I renamed it “AGrid”.