Category: A*

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.

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.

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

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