4 - 8 - 16 Direction AStar Pathfinding

[DeathPhoenix22]

Hi @AlmasB ,

I've looked at the AStar pathfinding implementation and noticed that it's 4 directions restricted.
I looked at a way to adjust the current implementation and faced that fact (it's happening a lot, I must admit) that most of the Framework is Final protected.

As I can't use OO inheritance to extend behaviors, I need to redo the Pathfinding in my project or modify the existing Pathfinding directly in the Framework.

Should I do it in the Framework or redo it in my project? :( ? I also can't use inheritance to create extended Grid systems (I would normally have 3 classes, one for each type -> 4, 8 & 16 direction Grids where I would use inheritance to extend the "getNeighbors" for example, but inheritance doesn't seem to be a choice in that Framework as almost everything is Final)

Thanks for the guidance !
Jean-René

[DeathPhoenix22]

Hi @AlmasB,

I'm currently working on the Pathfinding side of things. I want to point out that I'm considering the extension of CellState to allow more states that would better fit multiple scenarios (mostly) related to RTS games. In certain games, you'll see units able to float over water (only) and/or be able to walk.

This means that the "AStarGrid" CellState system need to consider "acceptable states" to find a suitable path.

I'd love to "improve" the Engine and let everyone profit from these changes. I can't make any promises, but I think that I should work directly into the FXGL AStar section of the Framework.

Here are some items that I'll need to cover (required):

• At least 8 directions (Allow diagonal) -> Afterward, I'll look at 16 directions, but this one is trickier as certain cells are not "neighbors"
• Allow "custom" cell states to be used for Path searches -> e.g. certain units can cross water, but can't cross mountains, so a binary state isn't enough to differentiate units that can walk on ground from units that can cross water if we have units that can do both (of course, you can have 3 pathfinding grid, but is that Memory efficient?)
• An AStarCell should be defined by it's top-left corner OR by it's Center. Most of the time, you want to move the Anchor of an Entity to the "Anchor" (in this case the center) of a cell, not to it's top left corner.
• More to come...

[AlmasB]

Hi, @DeathPhoenix22 this sounds interesting. I would separate these into multiple separate PRs. I'm particularly interested in the 8 directional support being added first.

Once you have a high-level design of the changes, feel free to drop them in this thread and we'll go from there. My time is currently occupied elsewhere, but I'm keeping an eye on your developments.

[DeathPhoenix22]

@AlmasB #1338 (8 directions grid) PR submitted.

[DeathPhoenix22]

@AlmasB I'll submit the AStar changes today.
Could you kindly review this "todo" list so I can better target intended "Scopes" for my future PRs? (And if you think that you want it in FXL):

• Add 8 directions Support in AStarPathfinder
• Add Bi AStarPathfinding support (Bi-Directional search). This will fix a critical full-map read problem when the targeted cell is unreachable - e.g. a map with Isles
• Add 16 directions Support: I think that I have a viable solution for it. There are high chances that this change also boost performances some more.
• Find (elegant) ways to Optimize the search (time) - TBD. Right now, a single "full-map" read take, on average, 44 millis for a single unit. My goal is to reach less than 1 millis.

For the Optimization, I have a lot of strategies. My main goal is to keep the code clean as much as possible!
I know that the AStar[...] components are not yet ready to use these.

If you want me to add in something else let me know :)

[DeathPhoenix22]

@AlmasB #1339 PR is submitted.

[DeathPhoenix22]

@AlmasB ,

Now that I use the (not yet accepted) eight directions pathfinding, I realize that their are significant investment required on that field to allow RTS gaming pathfinding. I will need to end up with a highly performant and flexible pathfinding solution within the next 1-2 months. I'm currently heavily concerned about the capacity to have these changes integrated in the FXGL itself.

I'll do the directional support change. Then, I'll evaluate where the pathfinding improvements will be pushed.

[AlmasB]

@DeathPhoenix22 please see below

• Add 8 directions Support in AStarPathfinder

This should probably have an extra findPath() with NeighborFiltering options parameter that dictates how the algorithm is to pick up neighboring nodes. Would also be good to discuss how movement cost would work. I assume 1 diagonal is lower cost than 2 directional moves. I wonder if we should allow the user to change these as well, then we are removing this responsibility from ourselves. So something like:

.setDiagonal/DirectionalMovementCost(...), though the name needs a bit more formalisation.

• Add Bi AStarPathfinding support (Bi-Directional search). This will fix a critical full-map read problem when the targeted cell is unreachable - e.g. a map with Isles

Sorry, I am not sure what a bi-directional search is in this context. Does this mean, given cells A and B, we do a search from A to B and B to A at the same time? Is this a performance-only change?

• Add 16 directions Support: I think that I have a viable solution for it. There are high chances that this change also boost performances some more.

Could you clarify what these 16 directions are? In terms of the grid data structure, I can only visualise a cell having 4 directionally adjacent and 4 diagonally adjacent cells.

• Find (elegant) ways to Optimize the search (time) - TBD. Right now, a single "full-map" read take, on average, 44 millis for a single unit. My goal is to reach less than 1 millis.
  For the Optimization, I have a lot of strategies. My main goal is to keep the code clean as much as possible! I know that the AStar[...] components are not yet ready to use these.

I am not worried about optimisation at this stage, so I'd prefer to avoid any code that explicitly focuses on optimisation. Once we design the API and then implement its functionality, we can start looking at ways to optimise as a separate PR, if required.

[DeathPhoenix22]

Add 8 directions Support in AStarPathfinder
Noted for the findPath(). It'll be included there. This will also allow multiple "types" of units 4 vs 8 vs 16. Some may not have 16 angles where some have 8 (it's already the case for me).

For the .setDiagonal/DirectionalMovementCost(...), I think that we could refer to it's standard name: Heuristic. I'll include a way to specify nodes weights, while providing defaults (standard is Manhattan for 4 directions & Octile for diagonals. We can use Octile all the time, but Manhattan is soft for performances. Note that Manhattan isn't fit for diagonals)

Add Bi AStarPathfinding support (Bi-Directional search). This will fix a critical full-map read problem when the targeted cell is unreachable - e.g. a map with Isles

Bi StarPathfinding is, like you suggested, a search from both ends instead of a search from the start only. As soon as the search for A reaches the search for B, the path is reconstructed and returned. It's a form of Optimization, but it's also allowing quicker exit when A cannot reach B. While searching, if we can't find valid neighbors, we stop the search. Searching by both A & B will not only try to find the shortest path but will also, as soon as possible, identify that A cannot reach B as soon as we can. As soon as A or B doesn't find anymore Neighbors to explore, we return.

Add 16 directions Support: I think that I have a viable solution for it. There are high chances that this change also boost performances some more.

As you mentioned, conceptually, these wouldn't be immediate neighbors, but extended neighbors (at 1 cell distance). The extended neighbors would only be valid if the traversed cell to reach it is free. In short, to allow 16 direction pathfinding, we would need to add an extra concept of "Extended" neighbors. I've already added this concept in my game to retrieve "valid spawn cells" of a building. In the case of pathfinding, and for the sack of generalization, I would simply add a "dept" parameter to the requested "neighbors" to retrieve. So, if you need 16 directions, dept = 1. If you want 32 directions dept = 2, etc.

Find (elegant) ways to Optimize the search (time) - TBD. ...

I understand that you want the API part to be included first. I'll gladly do it in that order. I would simply add in the discussion that, currently, in my game, the Pathfinding is causing a lot of lag. There are many little things in the implementation that could be adjusted to boost it (without adding any complexity). I'll eventually need it because my game will include ... a LOT of units :D

Best regards

[DeathPhoenix22]

Hi @AlmasB ,
I've managed to greatly improve Pathfinding performances with a single really simple change. With some extra other changes, I was able to reduce pathfinding time by more than 100x. Let me know if you want some of them integrated in FXGL.

[AlmasB]

@DeathPhoenix22 This sounds good, though I understand the tpf issue is the priority for your project, so perhaps we should focus on integrating that first -- I've left some comments