December 13, 2019
A* Tutorial Series
A* Pathfinding (E08: path smoothing 1/2)
A* Pathfinding (E08: path smoothing 1/2)
By: Sebastian Lague
A* Tutorial Series
A* Pathfinding (E09: path smoothing 2/2)
A* Pathfinding (E09: path smoothing 2/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 lineTurn 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.