Lately, I’ve been investigating the Anya pathfinding algorithm.
Anya is an optimum any-angle pathfinding algorithm.
Nonetheless, it really works solely with discrete factors on the grid.
Right here is an excerpt from the paper “Optimum Any-Angle Pathfinding In Follow” by the inventor of the algorithm (Daniel Harabor):
Lastly, the any-angle pathfinding downside is one which requires as
enter a pair of discrete factors, s and t, and asks for an anyangle
path connecting them. The purpose s designates the supply
(equivalently, begin) location whereas the purpose t designates the goal
(equivalently, aim) location.
This confirms what I see within the instance code offered.
I applied a GUI to showcase some issues.
The darkish gray cells signify blocked cells.
The white cells signify walkable cells.
The beginning place is displayed in inexperienced and the goal place is displayed in purple.
For this software, I truncate decimal locations of the X and Y coordinates of the supply and goal positions.
The rationale is that positions from n.00 as much as n.999 lie inside cell n, so I have to respect whether or not cell n is blocked or walkable.
(If there’s a greater different to truncation, let me know!)
Within the first instance, solely the trail discovered by anya, which immediately leads from (2,2) to (4,2), is drawn.
To get the precise path the agent ought to take, I join the beginning place and goal place to the calculated path.
Clearly, that’s not the optimum path.
Right here, one can nonetheless apply comparatively commonplace path smoothing rules, e.g., as a substitute of beginning with the primary discovered level, carry out line-of-sight checks from the beginning place of the unit to the a number of factors of the primary phase of the trail and choose the furthest level that also has a line-of-sight to the beginning place.
Doing so (relying on the quantity of line-of-sight checks) may result in a improved path like proven right here:
So, on this case, path will be discovered.
However that’s not the case for all inputs.
Take into account the subsequent instance, right here the beginning and goal positions of the unit are extra in the direction of the underside of the cell.
Right here, clearly pathing across the backside aspect of the impediment would result in the shortest path.
Nonetheless, because the X and Y coordinates of the beginning place are nonetheless truncated to the identical discrete X and Y values.
Thus, anya will get the identical enter knowledge as within the earlier instance and consequently discover the identical path.
Sadly, the line-of-sight examine smoothing can not assist right here to search out the shortest path, as the trail returned by anya traverses the impediment on the fallacious aspect (prime as a substitute of backside).
Subsequently, my query is how can I resolve this downside whereas nonetheless utilizing the anya pathfinding algorithm. (and never switching to navmeshes)
Considering of it, would not different grid-based pathfinding algorithms have the identical downside?
Are there any actual and environment friendly options for different algorithms?
Or is that this one of many instances, that most individuals simply dwell with the practically optimum path?
Which appears bizarre to simply accept, when particularly making use of a optimum, any-angle pathfinding algorithm.
