Category: Unity

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.

    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.

    UnityLearn – Beginner Programming – Swords and Shovels: Character Controller and AI – Pt. 01 – Overview and Character Controller

    digm520admin / / 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

    Overview and Character Controller

    Navigation and Animation Review

    This part of the tutorial just gets you familiar with the NavMesh setup they have and the animator they are using on the player character. Some of the items are a bit off since they are using an older Unity version (2017), like where the Navigation tab is located (it is now under Window -> AI).

    The player character animator has a blend tree that holds a speed parameter. This parameter appears to determine how much to blend between an idle animation and a running animation, as well as how fast the animation plays.

    Controlling Motion with C# and Unity Events

    This tutorial portion started with adding a NavMesh Agent component to the Hero character to have it interact with the baked NavMesh in the scene.

    The next step was to edit the MouseManager class to actually move the character according to its NavMesh Agent and the created NavMesh. This would require a reference to the NavMesh Agent component. They did not want to use a public field (as this creates a dependancy that can lead to issues down the road), so they turned to making an event.

    They needed to create this event, which they did so as a new class within the MouseManager script, but outside of the class. This was done in the following way:

    [System.Serializable]
    public class EventVector3 : UnityEvent { }

    The base class UnityEvent lets it send vector3 information through an event.
    They then created a public field of the type EventVector3 named OnClickEnvironment. This was then used to do the following:

    if (Input.GetMouseButtonDown(0))
    {
    OnClickEnvironment.Invoke(hit.point);
    }

    The public field created a box within the inspector similar to UI events in Unity. You could drag an object in as a reference, and select a component and method to call when that event happened. In this case they used the Hero object, and called the NavMeshAgent.destination method.

    Synchronizing Animation with Motion

    They start by simply referencing the NavMeshAgent speed and passing that value into the animator’s speed parameter. They then begin to alter the NavMeshAgent component’s properties to fine tune the movement to feel better to play with. They significantly increased the Speed, Angular Speed, and Acceleration, and turned off Auto Braking. This felt much better, but led to an issue where the player would run back and forth near their destination.

    The issue is caused by turning off Auto Braking and not having a Stopping Distance. I assume since the character has trouble “perfectly” reaching the value of its given destination, the Stopping Distance of 0 means it will keep trying to get there even though it cannot.

    Setting the Stopping Distance to 0.5 fixed this issue. This allows the agent to stop moving once it is within 0.5 units of the given destination. There was still a strange issue where the character would move slowly around stairs, but they said they would cover this issue.

    Handling the Passageway

    This portion deals with adding code to allow the character to traverse the special passageway section of the level. The passageways have unique colliders to inform the cursor that a different action should take place when they are clicked. These colliders also have direction, which will be used to determine which way to move the character through the hallway.

    They then go back to the MouseManager to show where the cursor is detecting the unique collider (currently just to swap the mouse icon with a new icon). This is where they add extra logic that if door is true (a doorway has been clicked) that they want to grab that object’s transform and move a fixed distance (10 in this case) in that object’s z-direction. This is why the collider’s orientation is important.

    This setup seems very bad to me. This only works for passageways that are all exactly the same distance since the value is hard coded in. You can still click on areas between the passageway entrances, so the character just gets awkwardly stuck in the middle with the camera pressed up against a wall. There is no limitation when taking a passageway, so the player can click again midpassage and alter their character trajectory which can be weird or buggy.

    I think I would prefer a system that somehow links the two passageway entrances so that no matter where they are, when the player clicks one they will enter it and come out of the other one (use their transform with some offset). Player input should also be limited somehow during the passage because there is no reason to do anything else within the passage, this only allows for more errors.

    Note:

    The MouseManager uses a lot of if/else conditional statements, and from the previous lessons, I think it could possibly benefit from having a small state machine setup. While I think it is just on the edge of being ok in its current setup, the Update method for the MouseManager is already looking a bit bloated and any more complexity may start to cause issues.

    SUMMARY

    I think this tutorial was mostly focused on just getting you used to finding and using some different features of Unity, such as NavMesh and the Animator. Nothing here seemed to be that deep or well done, so it felt very introductory. Getting a refresher on NavMesh agents was definitely useful at least, and working with animation never hurts.

    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”.

    digm520admin / / A*, AI, Pathfinding, Programming, Tutorial, TutorialList, Unity

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

    November 20, 2019

    A* Tutorial Series

    Pt. 01 – Algorithm Explanation

    A* Pathfinding (E01: algorithm explanation)

    Link – Tutorial

    By: Sebastian Lague


    Notes:

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

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

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

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

    Coding Approach

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

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

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

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

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

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

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

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

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