I’ve been diving into the Anya pathfinding algorithm recently, which is super cool because it’s designed for optimal any-angle pathfinding. However, I’ve hit a bit of a snag: Anya only works with discrete start and target points, and I’m trying to figure out how to use it with non-discrete positions without losing that optimality factor.
Here’s what I’ve been doing: I set up a GUI where I can visualize the grid with blocked and walkable cells. My start position is in green and my target position is in red. To handle the non-discrete nature of the start and target positions, I’ve been truncating the decimal parts of their coordinates. The logic is that any position between n.00 and n.999 still belongs to cell n, and I want to ensure I’m respecting whether that cell is blocked or not. But I can’t help but feel there might be a better way to approach this.
I’ve implemented the default pathfinding and found that sometimes it leads to suboptimal paths. For instance, I drew a path from the start to the target, and while it’s functional, it’s definitely not optimal. In one of my tests, Anya took a direct route that was clearly not the best option. I tried using line-of-sight checks to smooth the path out, which improved things slightly. But in some scenarios, like when both the start and target are towards the bottom of their respective cells, the optimal path turns out to be on the opposite side of the obstacle! Since Anya uses truncated coordinates, it just doesn’t connect the dots correctly for those cases.
So, I’m wondering if there’s a more effective way to adapt the Anya algorithm for non-discrete positions while still keeping it optimal. Have you faced a similar issue with other grid-based algorithms, or is this a common hurdle in pathfinding? Are there any clever tricks or techniques you could share that might help me navigate this challenge? It feels frustrating to think that I might have to settle for “almost optimal” paths when I’m aiming for the best!
It sounds like you’re doing some cool work with the Anya algorithm! I totally get where you’re coming from with the whole start and target position issue. It’s tricky when you’re dealing with non-discrete positions, especially since Anya was originally designed for discrete cells.
Your approach to truncate the decimal parts makes sense for keeping the algorithm in line with the grid system. But I wonder if instead of just truncating, you might try to utilize interpolation or snapping. Maybe you could look into snapping the positions to the nearest walkable vertex rather than just the grid cell. This way, even if your start and target are decimal, you’d still be able to work with them more precisely.
Another idea could be using the concept of local minima. If you’re finding that certain paths are suboptimal, consider running a simple local optimization after Anya has generated a path. Basically, check specific segments of the path to see if they could be straightened out based on line-of-sight checks. There are also some smoothing techniques where you iteratively adjust the path to minimize distance while checking if the new segment can still be traversed.
On a different note, you might want to implement a secondary pathfinding run after you get the initial result from Anya. Like, after you get the path, take the start and target points and run a different algorithm (maybe A* or Dijkstra’s) specifically around those non-discrete points, which might give you a smoother path.
And hey, don’t feel too frustrated! Many people face similar challenges with grid-based algorithms, especially when trying to adapt them for more complex scenarios. Just keep experimenting and iterating on your ideas; that’s the best part of programming!
The challenge you’re facing is common when adapting Anya’s discrete-cell assumption for non-discrete start or target positions. Truncating coordinates naturally introduces inaccuracies when positions lie close to cell boundaries, causing Anya to potentially overlook optimal paths. To preserve optimality, one effective approach is to handle your start and goal positions as “floating” points by explicitly considering the geometry around cell boundaries. Instead of truncation, you can introduce additional temporary nodes precisely at your non-discrete start and target positions and link them to reachable adjacent visibility points at the boundaries of their cells, taking into account actual collision geometry. This technique typically involves performing an initial visibility check from the precise start or target positions to potential pivot points on neighboring cells, fitting nicely within Anya’s method of propagating intervals rather than discrete points.
Moreover, rather than directly truncating coordinates, another established practice for addressing this scenario is to preprocess grid intersections or cell corners, creating interval sets that your start and target can directly access through visibility checks. This approach leverages Anya’s native handling of visibility intervals, maintaining its optimal any-angle property rather than relying on post-hoc smoothing steps. Such preprocessing, coupled with online visibility checks, allows Anya to efficiently bridge from arbitrary continuous start and target positions into discrete grid intervals, overcoming the limitations you faced with truncation and resulting in truly optimal pathfinding outcomes.