Dev Blog

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.

HFFWS Scenario Building System

digm520admin / / HFFWS, Programming, Unity
December 12, 2019

HFFWS Generation System Design

Scenario and Create Class Interaction

Detail on Scenario-Create Interaction

My first pass on deciding on how to have the Scenario classes and Create classes interact uses the following flow:

  • Scenario holds all parameter ranges
  • Scenario picks random values within ranges
  • Scenario holds these values in various fields (read only)
  • Scenario calls overall creation method within each Create class
  • Scenario passes parameters to Create class through this Create method

The overall idea here is that the Scenario class can hold all the parameters necessary for all its Create classes, as well as the Inspector interface for setting the ranges for these parameters (so the designer can design the scenario from this single class object). As the Create classes determine their varied values within the sets of parameters, they can feed information back to the Scenario class to update how the other Create class parameter ranges are set. So if the variation chosen for a certain Create class does not work with certain values in another Create class anymore, that range will be updated to ensure all the Create classes work together properly no matter the values selected as it goes along.

Next Step

Create Scenario Gameobject Hierarchies

I want each generated scenario to be childed to an overall newly generated gameobject. Each scenario should create an empty gameobject overall that acts as the parent for each full, individual scenario. I am hoping the positioning of this object will also serve as an easy way to space out the various scenarios with the DemoManager. This will just help with overall organization when demoing the project in Unity.

Creating New Scenario Objects

Currently the system has a single instance of each ScenarioManager object that has its values updated to create a single scenario, then they get overwritten to make another scenario instance. It may make more sense to create a new instance of that ScenarioManager class everytime a scenario is created so that the data is conserved for me to check later. This will also make sense as I add seeding to the random generation as well.

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.

Issues with Intellisense in Visual Studio in Unity

digm520admin / / Programming, Unity
December 10, 2019

Unity and Visual Studio

Intellisense Issues

Good Solution Options for Unity / Visual Code Intellisence Issues

Link – Possible Solutions

For some reason Visual Studio 2019 does not want to use Intellisense properly on the HFFWS project when using Unity commands. It still autocompletes some general stuff that I assume is more generally C# focused, but methods like Start, Awake, OnCollisionEnter that are Unity specific do not complete. They still work and run fine, but the autocomplete feature is missing.

I tried circumventing this by going back to Visual Studio 2017 as the code editor and it worked totally fine. This points to it being a VS 2019 issue directly, but it could also be how it interacts with Unity in general. I have to use an older version of Unity (2017.4.13f1) so maybe that has something to do with the issues that come up.

People run into this issue all the time for various reasons, and I have tried a lot of their solutions to no avail.

Moving the Script into the Project (Out of Miscellaneous Files)

Sometimes when you create a new C# script, it gets sent to Miscellaneous Files intstead of into your actual project. This completely removes its connection to Unity, so the intellisence autocomplete tends to break here. I have fixed this and the files were either moved back to the C Sharp Assembly or are now automatically put there again, so that is not my current issue.

Have the Unity Dev Tools Installed in VS

It should be a given I have this since I have used VS 2019 on other projects before and recently without issue, but I double checked that I have this installed as well. This is indeed still there, even found when using it for the HFFWS project which it is not working for.

Nuget Packages

This is something I was unclear with and do not think I was successfully able to even implement this as a recovery method. I never directly dealt with them initially to setup VS with Unity, so I was unsure if this would even be helpful for me when I have these issues later down the road.

Delete Visual Studio Generated Files

I went to the root folder of my Unity project to find the Visual Studio generated files to delete them. These are the .csproj, .sln, and .user files found there. I only had 2, the general solution file and a single .csproj file. I deleted both of those and restarted Unity and VS but it had not changed.

Reimporting Files

The easiest way to attempt this large scale is to just reimport the entire project. For bigger projects, such as this HFFWS project though, this can take a pretty long time. I tried a smaller scale approach by just reimporting my scripts folder but this gave me no results either.

Unloading/Reloading the Project Files

I tried unloading the C Sharp Assembly file and reloading it. I also tried unloading and reloading a few of the individual scripts themselves. This can sometimes fix the connection, but this also did not work here.

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.

HFFWS Generation System Overview Update

digm520admin / / HFFWS, Programming, Thesis, Unity
December 5, 2019

HFFWS Generation System

Overview Update

General System Overview

I have updated my thoughts on setting up the overall system to fit the demands for my thesis as well as to keep everything more organized and readable. I am sure as I go through building this I will find ways to cut out levels of inheritance or add scripts for readability, but this is the most recent view on everything. I want the highest level to be very general (DemoManager), the middle level should be where the majority of parameter ranges and interactive placement between objects should be (ScenarioManager’s), and the lowest level will be in charge of putting together the needed objects within the bounds dictated by the higher levels (Create classes).

This image just shows the general idea of the overall hierarchy (the actual number of ScenarioManagers and Create classes is not accurate). The DemoManager holds references to all of the ScenarioManagers, but only chooses one ScenarioManager at a time to develop its scenario. Each ScenarioManager is connected to specific Create classes within a large pool of Create classes, which will be the objects that specific scenario will actually possibly need to create. The Create classes referenced to can overlap as some objects will be used in multiple scenarios.

DemoManager (change to GenerationManager)

The name of GenerationManager was changed to DemoManager to fit its purpose better. Since the system will be mainly used for demonstration purposes, it will focus its functionality on generating any varied number of scenarios and allowing for real time resetting.

Goal:

Passes down highest level information to ScenarioManager level. This will include puzzle type, variation types within that puzzle type, and any other high level information such as overall positioning or how many scenarios in total to generate.

Needs:
  • Number of scenarios to generate
  • List to hold information on all scenario options
    • Customizable in editor to pin point certain scenarios if wanted
    • ScenarioManager level objects should be same type of object to help with this listing
  • Scenario spacing
  • Input to reset generation in real time
  • Seed information (may be better in scenario manager level)
Notes:
  • Will have some bool list of scenario types to include in its random generation
  • For testing, have “GenerateSpecific” bool to allow for creating a single specific scenario

    • ScenarioManager

    I think it makes sense to commit to setting up an internal hierarchy setup within the ScenarioManager level at this point. This allows the DemoManager to just deal with ScenarioManager type objects, but I can break each scenario type down into its own class to help keep the scripts manageable and more organized.

    Goal:

    Will take DemoManager information and use it to determine which “Create” type classes will need to be used (or have the option of being used), how many times to use each, and what other information needs to be passed on to them (the “Create” type classes) to properly build out the desired scenario.

    Needs:
    • Hold Parameter Ranges
      • will need to be moved over from current Create classes
    • References to Create type classes
    Example for Possible Inheritance Pattern
    • ScenarioManager
      • PulleyScenarioManager
        • HeaveyDoorPulley
        • PlatformPulley
        • HookPulley
    • Information for all general scenarios
      • Information for a general type of scenario
        • Specific information for a specific type of puzzle in a specific type of scenario

    This shows the inheritance setup within the ScenarioManager level from the overall system setup.

    Create Classes

    I have not worked with these enough yet to fully update them, but I am looking at creating a base Create class that holds general data that any of those classes will need. Then each type of object will have its own Create type class that derives from this class detailing all of the specifics for altering the parameters of that overall object.

    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.