Category: A*

Updating A* for Multiple Agent Types of Pathfinding

digm520admin / / A*, AI, ArchitectureAIProject, Pathfinding

March 20, 2020

Updating A*

Different Pathfinding Logic for Different Agent Types

A* Current System

The A* Pathfinding currently performs the same calculations for every agent in order to determine its path. Every unit then takes the same path assuming they have the same starting and target positions. We are looking to adjust this so there are various types of agents which with different affinities to certain objects in the environment. This then needs to be incorporated in the path determination so different types of agents will takes different paths, even when using the same starting position and same target position.

Differentiating Pathfinding for Different Types of Agents

We want to add more parameters to the grid nodes besides flat cost that influence the agents’ paths. These parameters also need to be able to influence different agents’ paths differently (i.e. the parameters may give a node a cost of 10 for one agent, but 20 for another).

Approach

The initial needs for this system are the addition of parameters to the nodes of the A* grid and parameters that correlate with these on the agents themselves. With this in place, we are just going to add a reference pass of the individual agents themselves to the eventual path calculation so it can also factor in these additional values.
The actual steps for this concept are laid out here:

– Individual agents need to have data within them that determines how they act
– Pass the UnitSimple instance itself through PathRequestManagerSimple.RequestPath along with the current information (its position, its target position, and the OnPathFound method)
– In PathRequestManagerSimple script, add UnitSimple variable to the PathRequest struct
– Now, RequestPath with added UnitSimple parameter can also pass its UnitSimple reference to its newly created PathRequest object
– Then, TryProcessNext method is run
– Here, the UnitSimple reference can be passed on to PathfindingHeapSimple through the pathfinding.StartFindPath() method call
– Add UnitSimple parameter to StartFindPath method in PathfindingHeapSimple class along with existing parameter (start position of path request, target position of path request)
– PathfindingHeapSimple can now use variables and factors of UnitSimple when determining and calculating the path for that specific agent
– Finally, returns its determined path as a set of Vector3 waypoints to the agent (effectively stays the same process)

Next Steps

This is just a conceptual plan, so I still need to implement it to see if it works and how it runs. I will also be looking to add some parameters to the nodes and agents, so I can start differentiating various types of agents to test the system.

UnityLearn – AI For Beginners – Navigation Meshes – Pt.02 – Navigation Meshes

digm520admin / / A*, AI, Programming, Tutorial, TutorialList, UnityLearn
March 30, 2020

AI For Beginners

Navigation Meshes

Navigation Meshes


Beginner Programming: Unity Game Dev Courses

Unity Learn Course – AI For Beginners

Navigation Mesh Introduction

Nav Mesh: Unity function for making a navigable area for agents to traverse over.

There are 4 main tabs in the Navigation window:

  • Agents
  • Area
  • Bake
  • Object

Agents

Core Parameters: Radius, Height, Step Height, Max Slope

These dimensions determine where the agent can fit when navigating around obstacles, as well as how it can traverse elevation differences. Radius and height help limit where a character can go (cannot go between very small gaps or under objects very close to the ground) where step height is the elevation difference it can traverse in a single jump and max slope is how inclined the surface can be for the agent to travel on. The name allows you to save several types of agents, with various values for these 4 core parameters.

Area

How you define different costs for different types of areas (used in A* pathing).

Bake

Creates the Nav Mesh over your given series of meshes using their polygons. It does this using a template agent called the baked agent size. By default there is only a single mesh created for the default agent type, but there are additional tools that can allow you to create multiple meshes to help handle various sized/types of agents. The Generated Off Mesh Links parameters determine how far off the mesh an agent should be able to jump or drop to get to another mesh location.

Advanced Options (Under Bake):
  • Manual Voxel Size: lets you determine the voxel size used to generate the Nav Mesh; larger voxels are less detailed and follow the mesh less accurately; default is 3.00 voxels per agent radius; generally aiming for a value between 2 and 4
  • Min Region Area: Helps remove areas that are deemed navigable, but are too small to really be of use or will cause issues by existing
  • Height Mesh: bool to determine if Nav Mesh should average elevations to turn steps into slopes or not

Object

Where you can align specific area types to different parts of the mesh, which parts of your mesh you want to generate nav meshes for, and helps create mesh links, which help travel from one nav mesh to another by jumping or falling.

From Waypoints to NavMesh

Introduction of Unity NavMesh, where they introduce the concept of baking the Nav Mesh with use of static game objects and adding the NavMeshAgent component to the AI agents you want to follow the Nav Mesh.

NavMeshAgents

They setup a new scene and project with a Nav Mesh. Nav Mesh specifically looks for “Navigation Static” game objects to build around when baking. They showed that selecting a gameObject before going into play mode with the Nav Mesh active helped visualize how the Nav Mesh was determining their paths.

Areas and Costs

The Areas tab in the Navigation Window lets you set different parts of the mesh as different types of areas. When selecting the polygons or meshes to use for these different areas, select the desired polygons and go to the Object tab. Here you can select which Area to apply to those specific polygons. These areas can then be used to tell agents where they can and cannot go. This is done by going to the NavMeshAgent component of the agent and changing the Area Mask of the Path Finding for that agent. By turning an Area type on or off, you designate which meshes it can travel on at all.

In the Areas tab, you can assign different Cost values to these different areas. This can make them more or less appealing for the agents to traverse across (higher values for cost mean the agents are less likely to use that path).

Following a Player on a NavMesh and Setting Up Off-Mesh Links

This tutorial setup another scene in another project, this time with the basis of following the player around. This was as simple as using the SetDestination method within the NavMeshAgent component to the player’s position in Update.

Off Mesh Links

Off Mesh Links: used if you have gaps in your NavMesh that you want an agent to cross

To create the Mesh Links, select the polygons of interest that you want to link over a gap and go to the Object tab. Here you can select “Generate Mesh Links”. Then go to the Bake tab, set the “Drop Height” and/or “Jump Distance” under the “Generated Off Mesh Links” section, and bake the mesh again to incorporate these links. They will be visually shown as circles between the meshes. Jump Distance is good for crossing horizontal disconnects, where Drop Height is good for crossing significant vertical disconnects. Setting drop links is similar, in that you select the two main groups of meshes in question and generate the mesh links.

Summary

After doing a lot of work with A*, building a path finding system with it from scratch, a lot of the tuning factors and parameters for Nav Mesh made a lot of sense with how A* works. This was good to know there was so much overlap, so I can learn a lot from what they use to work with Nav Mesh to give my A* system effective modifiable parameters to tweak it for designing needs.

Nav Mesh does seem powerful and very easy to get running, but I would have to work with it more to see just how controllable it is. I still like having my own A* system that I know the insides well to tweak exactly how I want it, but the Nav Mesh does offer a lot of similar features I am looking to add so I may need to explore it more to see how easy it is to work with.

A* Architecture Project – Spawning Agents and Area of Influence Objects

digm520admin / / A*, AI, ArchitectureAIProject, Pathfinding, Programming, Unity
March 25, 2020

Updating A*

Spawn and Area of Influence Objects

Spawning Agents

Goal: Ability to spawn agents in that would be able to use the A* grid for pathing. Should have options to spawn in different locations and all use grid properly.

This was rather straight forward to implement, but I did run into a completely unrelated issue. I created an AgentSpawnManager class which simply holds a prefab reference for the agents to spawn, a transform for the target to pass on to the agents, and an array of possibl spawn points (for incorporating the option of several spawn locations). This class creates new gameObjects based on the prefab reference, and then sets their target to that determined by the spawner. This was something worth tracking since sometimes there can be issues with Awake and Start methods when setting values after instantiation.

This was all simple enough, but the agents were spawning without moving at all. It turns out the issue was that the spawn location was above a surface that was above an obstacle (the obstacle was below the terrain, but entirely obstructed). This was an issue with how my ray detection and node grid was setup.

Editing the Grid Creation Raycast

The node and grid creation for the A* system uses a raycast to detect obstacles, as well as types of terrain to inform the nodes of their costs or if they are usable at all. Since it is very common to use large scale planes or surfaces as general terrain, and place obstacles on this, uses a full ray check would almost always pick up walkable terrain, even if it hit an obstacle as well.

To get around this, I simply had it check for obstacles first, and if it detected one, mark this node unwalkable and move on. This created an issue however in the reverse case, if an obstacle went a bit past the terrain into other nodes below the surface, they would be picked up as false obstacles, or in this case, it was picking up obstacles that were entirely located below the surface.

I was using a distance raycast in Unity, which just checks for everything over a set distance. I looked into switching this to a system that just detects the first collider the ray hits and simply use that information. I found that using the hit information of the raycast does this.

Unfortunately I am using a layer setup for walkable and unwalkable (obstacle) terrain, so I needed to incorporate that into my hit check. Checking layers is just weird and unreadable in Unity scripting, since I am currently just use the hardcoded integer value for the current layer number that is unwalkable when doing my check for obstacles. This does at least suffice to let the system work properly for now.

Influence Area with Objects

I wanted to be able to create objects which could influence the overall cost of nodes around them in an area significantly larger than the objects themselves. The idea is that a small but visible or detectable objects could influence the appeal of nodes around them to draw or push agents away from them.

For a base test, I created a simple class called Influence to place on these objects. The first value they needed was an influence int to determine how much to alter the cost of the nodes they reached with their influence. Then, to determine the influence range, I gave them an int each for the x and z direction to create dimensions for a rectangle of influence in units of nodes. I also added some get only variables to help calculate values from x and z to help center these influence areas in the future.

I then added an Influence array to the AGrid class which contains all the logic on initializing the grid of nodes and setting their values at start up. After setting up the grid, it goes through this array of Influence objects and uses their center transform positions to determine what node they are centered on, then finds all the nodes around it according to the x and z dimensions given to that influence object, and modifies their cost values with the influence value of the Influence object. Everything worked pretty nicely for this.

As a final touch just to help with visualization, I added a DrawGizmos method that draws yellow wire cubes around the influence objects to match their area of influence. Since the dimensions are mainly in node units, but the draw wire cube wants true Unity units, I simply multiplied the x and z node dimensions for the influence by the nodeDiamater (which is the real world size of each node) to convert it to units that made sense.

I have two sample images to show the influence objects in effect below. The small purple squares are the influence objects, and the yellow wire frame cubes around them show their estimated area of influence. The first image shows the paths of the agents when the influence of all squares is set to 0 (no influence), and the second shows the paths when the influence is set to 200 (makes nodes around them much more costly and less appealing to travel over).

Paths with Influence Set to 0


Paths with Influence Set to 200

Summary

The raycast and layer system for detecting the terrain and initializing the grid could use some work to perform more cleanly and safely, especially for future updates. The spawning seems to have no issues at all, so that should be good to work with and edit moving forward. The basic implementation of the influence objects has been promising so far, I will look into using that as a higher level parent class or an interface moving forward as this will be a large part of the project and their may be many objects that use this same core logic by want special twists on it (such as different area of influence shapes, or various calculations for how influence should be applied).

Updating A* to Move Units in 3D for Elevations (Cont.)

digm520admin / / A*, AI, ArchitectureAIProject, Pathfinding, Programming
March 12, 2020

Updating A*

Adding 3D Movement (Elevations)

A* Current System and Notes

Now the A* system can deal with moving units along the y-axis according to the terrain, but it is still off with the advanced path smoothing functionality since this only cares about points where the unit is turning according to the xz-plane. To keep the system more simplified for now, I am looking to roll back some of the more advanced functionality from the Sebastian Lague tutorial I followed to incorporate the y-axis movement into a more simplified pathing system.

I want to ignore the SimplifyPath method for now (which narrows down the full list of nodes for a path down to only those which turn the agent, and only uses these as waypoints), which also causes problems if I have path smoothing as well. This is another reason to remove path smoothing temporarily.

A* Update

I wanted to keep the advanced path smoothing options available in the project, while looking to use the simplified version for now (with updates to continue having the y-axis movement). To do this, I identified which scripts dealt with path smoothing specifically which led me to the chain of these scripts:

  • PathFindingHeap
  • Unit
  • PathRequestManager

Since those were the scripts that dealt with applying path smoothing, I looked for versions of the project I saved as stepping stones of the tutorial that were before path smoothing (around episode 8 of the tutorials). From these projects, I grabbed their respective versions of these scripts to copy into this working project. To keep them as unique but separate options, I appended “Simple” to these versions of the scripts.

With these scripts, I could build out a scene (named SimpleTest) for the purposes of testing the y-axis movement with this simpler movement logic. While it is less aesthetically pleasing, it is in a way more accurate and representative of the core information the system is working with, so I wanted to get back to this state to have a better idea of what I was working with. This new scene has PathFindingHeapSimple and PathRequestManagerSimple on its A* gameobject, and each of the Seekers use the UnitSimple script instead.

With all of these in place to effectively remove path smoothing for now, I could effectively remove the SimplifyPath method from PathFindingHeap (and PathFindingHeapSimple as well for this case). This ensures the agents will travel to each individual position designated by every node along its path. This helps me see exactly every point of data that the agents are working with when moving. This is helpful to make sure the agents are properly receiving the right elevation data throughout the entirety of their paths.

With all of this done, I got the desired results I expected. The units immediately fly down into their starting position and move along the terrain properly, regardless of elevation. They effectively move up and down inclined surfaces, and can properly navigate up and down bumps and ramps in the terrain. They also show every single node point as a gizmo they are using as a path for movement, which clearly shows their paths following the terrain. I have included a video link for a quick demonstration of the agents in motion.

Vimeo – A* Movement in 3D Edit

AI Agents Moving in 3D with Path Highlighted

Next Steps

This simplified system appears to work exactly how I need it to, and I think this may be the preferred approach moving forward for now since it will be used to represent and show theoretical data. This may make it more practical to show the exact pathing information given as opposed to the skewed pathing created by the path smoothing operations.

The next step will be looking into creating objects which can influence the cost of a number nodes around them (as opposed to just those they are directly on, which is somewhat covered in the behavior of obstacles). This way different objects can influence the likelihood of an agent moving towards/around them.

I am looking at starting with a simple area of effect approach where the grid detects the object on a certain node and then alters the cost of all the nodes around it to some degree (the simpler approach, and mimics the blur effect already present from the tutorial followed). This blur effect makes it so the cost additions of the grass and road are blurred some around where they meet. The future advancement of this topic would be to allow objects to influence the cost of nodes based on line of sight, which is a much more variable amount of nodes to influence, making it a bit more difficult to implement.

Updating A* to Move Units in 3D for Elevations

digm520admin / / A*, AI, Pathfinding, Programming
March 11, 2020

Updating A*

Adding 3D Movement (Elevations)

A* Current System

The current A* system I am using solely works on a 2D plane (on the x-axis and z-axis). It creates a grid on this 2D plane and then allows agents to move specifically along this 2D plane, with no regard for heights. It is currently casting rays from above these grid nodes to detect the layer of the terrain the node is on. Each node also casts a small sphere the same size as it to detect collision for obstacles to determine if a node is traversable or not.

A* Update

Since the system already uses raycasts to detect the terrain type, I edited this to detect the height information from the terrain as well. Using RaycastHit.point, the raycast can return information on the exact point it hits, so I can pass the y-axis information from here to the node. I just do this along with the terrain detection, and pass this to the world position data of the node.

Since this update is specifically targeted at working with various elevations, I do not like using the collision spheres on the nodes to detect obstacles. Since I already have raycast incorporated, I thought it made sense to have it detect obstacles as well. Because there are layers involved for obstacles and terrain, I have the raycast check first if it can detect an obstacle (unwalkable terrain), and then if it does not find one, then check for walkable terrain and what type it is.

Finally, just to clean up, I added an extra variable to account for the unit heights when assigning elevation positions. This can be changed in the editor, but it adds a bit of elevation to the exact value from the terrain so the unit’s positioning as it moves along is a bit above the ground (so it is not in or below the ground).

Next Steps

These changes worked pretty well to get close to the desired effects. The units will move along altered elevation terrains to some degree. The current testing was done with a further simplified waypoint system after grabbing all of the nodes, so only the position data of points where the unit needs to turn is really taken into account for movement. This results in weird issues since the unit will not move up and down to account for elevation if it is moving in a straight line according to the xz-plane. It only accounts for elevation if the specific waypoints end up on varied elevation points (this is why it looks pretty proper on just a slanted plane).

I will look into reverting the simplified system to see if the standard system going to every single node works first. After I get that working again in all 3 dimensions, I will look to adjust back to the simplified waypoints system.

A* Pathfinding: Debugging Special Cases

digm520admin / / A*, AI, Debug, Pathfinding, Programming
December 19, 2019

A* Pathfinding

Debugging Special Cases

ISSUES

Getting an Index Out of Bounds Error in EnemyBasicMovement Script

Error happening on this line:

Vector3 direction = (path.lookPoints[0] – transform.position).normalized;

Suggests that the very first point in a path does not exist, so somehow empty paths are being passed through the system.

Test 1: Increase A* Grid Size to Cover Entire Play Area and Spawn Points

Some of the spawn points are a bit off of the normal play area, so I made sure to cover anywhere the units could possibly exist with the A* grid so they always had a node to latch onto (even though I believe the clamping should cover this error). This did not end up being the issue as the error persisted.

Test 2: Increase Size of Walkable Plane Over Entire Play Area

Similar to the logic of Test 1, I just wanted to make sure the nodes were not not being created because the units were missing some usual piece of information they would have to make them. Turns out this was not the issue either.

Test 3: Make Sure Target is Set Before Instantiating the Enemy

I thought maybe a path was being created before the unit had a target, which could make sense for creating a path with size 0. I did this by having the pathing script disabled initially, and making sure the spawner passed in the target information BEFORE it activated the script. The error continued though.

Test 4: Do Not Move the Target to See if Error Exists

It seemed like most spawns didn’t get errors if the player did not move, so I moved the one spawn that basically did not have to move to reach the player’s x position and tested what happened without the player moving (The X position counted as “very close” to the player at this time since I still had some of the issues with converting between 3D and 2D coordinates). There were no errors at all when not moving the target during the game.

DETERMINED ISSUE

Something about the paths updating later in the units’ lives was creating these size 0 paths.

Test 5: Is Spawning Causing the Issue

I was not sure if spawning the units was somehow causing the problems still, so I just placed 4 of the unit prefabs randomly about into the scene initially and stopped the spawners. This did not get rid of the error, and had the units return to moving in big circles still.

Further Info

This was giving me a lot of trouble, so I went back to following the path of logic to see why it would be producing these 0 count paths.

  • OnPathFound method in EnemyBasicMovement is being passed an empty array of Vector3[] waypoints
  • PathRequestManager class calls this method through its own FinishedProcessingPath method
  • OnPathFound is the method assigned to the callback Action for the PathRequest object
  • PathFindingHeap is creating an empty waypoints array somehow

The zero count path is being created in PathFindingHeap somehow. This should be impossible as every path should at the very least have the start node and the target node, which would be a count of 2.

    Within PathFindingHeap

  • RetracePath takes in a startNode and endNode to create the entire path of nodes between them
  • In the problem case, a new path has been created when the target is only a single node away from the pathfinding unit’s current position
  • there is a while loop that runs until it hits the startNode, so in this case, it only runs a single time (since the only nodes are the startNode and the endNode), creating a single waypoint
  • this creates a path with a count of 1
  • then the SimplifyPath method takes in this path
  • SimplifyPath creates a new List of Vector3 to fill with only necessary waypoints
  • it does this by taking points from the passed in path, but it looks through this with a for loop which starts at i = 1 and ends at i < path.Count, because it needs a previous point to compare to since it is doing a directional check
  • since the path.Count is only 1 here, the for loop never runs, and we return an empty set of waypoints
  • Can possibly solve with a special case since a path of 1 node is also a most simplified case

Test 6: Add Case In Simplify Path to Deal with Receiving One Node

I just added a check case before the normal logic that if the input path for SimplifyPath was only 1 node, it would just use that node as the path. This reduces the number of errors significantly, but there are cases where even the base path passed into SimplifyPath has 0 nodes.

DETERMINED ISSUE

The PathFindingHeap RetracePath method is creating paths with 0 nodes when Unit is close to target. As a result, SimplifyPath also makes 0 count paths. The only way this can be the case is if the startNode == endNode, so this must be happening when a new path is being created even though the unit and its target are already considered to be on the same node. This leads me to believe it is an issue with the difference between the node size and the distance the target has to move before looking for a new path (pathUpdateMoveThreshold in EnemyBasicMovement).

Test 7: Reduce NodeRadius to Half (or Less) of Update Path Threshold

Originally the values for pathUpdateMoveThreshold and the nodeRadius were both 0.5, which lead to a overall node size (nodeDiamater) of 1.0. I reduced the nodeRadius to 0.25 (which gives them a total nodeDiameter of 0.5), so this was at or below the threshold.

SOLVED

This completely removed the errors from happening (I add mostly because I am unsure if there exists a case where having the nodeDiameter exactly equal the threshold could cause an error).

SUMMARY

There was a lot of going back and forth to figure out where this error was coming from, and it was even harder since I was having some other issues since I had not fully converted the 3D system to the 2D system. As far as I can tell, this should cover most of the strange cases the pathing should run into even with an updating target (which should mostly be extra for my purposes anyway). I should add a check between the node size and the update threshold to make sure that issue does not happen again.

A* Pathfinding: Edit for 2D

digm520admin / / A*, AI, Pathfinding, Programming, Unity
December 19, 2019

A* Pathfinding

2D Conversion

ISSUES

Pathing In Circles Away from Target

They move in a large circle around the entire game area. They go in a half circle consistenly then stop in about the same place everytime (either directly above or below the middle of the play area).

Test 1: Tone Values Down

I tried toning all their numbers down since my game area is relatively small in case they were just constantly over shooting node targets, but this did not change the behavior.

I think the direction I am aiming and moving them must be incorrect with how I changed the Vector math from 3D to 2D.

DETERMINED ISSUE

They can only respond to the player’s X position. If the player moves, the properly oriented ones will move slightly to keep at the same X value, whereas those facing the other direction will travel in a large circle to reach the same X value (since I guess they cannot rotate very easily).

Test 2: Edit Rotation Calculation

I just needed to remove an extra (-90) that was being applied to the rotation vectors for aiming them at the target. This completely fixed the issue for their initial movement, but they only move in the x direction after that initial reaching of the target now.

DETERMINED ISSUE

The target position is not changing its Y value for some reason, only its X value.

Next Steps

Either their rotation is messed up (so moving right only moves them along x axis) or the overall translation is messed up and is only moving them left and right. It could be another z/y conversion error somewhere.

Test 3: Change NodeFromWorldPoint Method to Use worldPosition.y instead of z

It looks like PathFindingHeap was using AGrid NodeFromWorldPoint function to determine the proper node from world points, but this was using the z value of the Vector3 input as to determine the y coordinate in the overall grid. This is why it was constantly hovering at the same low Y value, because those were the nodes that correlated with a z input of 0.

SOLVED

These combined edits fixed the pathfinding logic completely. They now constantly followed the target position properly and it updated accordingly.

Sebastian Lague A* Tutorial Series – Threading – Pt. 10

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

A* Tutorial Series

A* Pathfinding (E10: threading)

A* Pathfinding (E10: threading)

Link – Tutorial

By: Sebastian Lague


Intro:

This tutorial gets into the idea of threading to help relieve some of the burden on processing caused by the pathfinding logic. Threading is not something I understand very well, so I will have to look into this more in the future, but I wanted to cover this tutorial just for completions sake.

Tutorial

This setup usese another namespace, the System.Threading namespace. This lets them use the ThreadStart delegate type and the lock keyword. ThreadStart can be assigned the value of some other delegate, with in this case contained the FindPath method from PathfindingHeap. I then looked up the lock keyword here:

https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/lock-statement

While this sort of threading setup has some unique syntax, it is an otherwise simple setup. There is a queue of PathResults that are just checked paths that are waiting to be called for the movement of units. The paths get created and checked to make sure they can hit the target, and once this is satisfied, it gets added to the queue.

Summary

I would need to have a better understanding of threading and how to utilize it to assess how useful this tutorial really was. I know the general idea behind it is to help distribute the processing load, but I do not know how well this new setup accomplishes that.

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.