I’m trying to implement an AStar2D pathfinding system with conditional connections between nodes. Basically, game agents have different movement capabilities, and I need the solver to ignore certain connections between nodes in the pathfinding graph, if the agent doesn’t have the necessary movement capabilities.
The game is in platformer perspective, and the connections represent types of movement necessary to reach a given node in the graph. That’s why I’m trying to implement conditional connections, instead of just enabling/disabling nodes before getting a path. I also can’t just override the cost calculation methods in a script, because some moves need to be impossible, and not just discouraged.
For reference, I’m going for something like this, with some connections being unusable for game agents without the appropriate abilities:
I’ve looked through the class definition and C++ source (“core/math/a_star.cpp” on the GitHub). Ideally, I’d like to modify the existing solver instead of writing an entirely new one from scratch, but I’m new to modifying Godot at this level, and don’t know where to start.
Things I’m considering (in order of preference):
Extend/modify the AStar2D class to conditionally ignore neighbors/connections. Is this even possible? Can it be done in GDScript, or is C++ the only option? Is this a GDExtension sort of problem? Roughly how would I do this?
Making unique AStar2D graphs for each movement capability, and each possible combination of movement abilities. Not ideal, because the navigation grid changes frequently during gameplay, which means recalculating lots of graphs/connections.
Manually break node connections in the AStar2D graph immediately before an agent needs to navigate the grid (if they lack the capabilities to use that connection), and reconnect them afterward. This seems silly and slow for a game with many pathfinding agents, but I know it’s possible.
As above, but just toggle specific nodes to be impassable before calculation, instead of modifying any connections. Probably faster, but would need to be redesigned around. Agents are meant to be able to enter any node; the connections represent things like having to climb up a ledge, or jump to cross between nodes.
Anyway, I’d appreciate any insight or suggestions on how to approach this. Thanks in advance!
there is probably a better way. but this is what i did.
have a grid of blocks you can walk on (brown). and a grid for A* blocks (green).
for each block you can walk on, add:
– an A* block above
– an A* block above & left
– an A* block above & right
these are the dark green blocks. if there is a brown block where a green block would go, don’t put a green block there
now iterate over your A* blocks. if the block beneath the green block is empty, add a light green block below it. rinse and repeat until the light green block encounters a dark green block.
use the green blocks for your A* map. in the picture below, you can see how START connects to FINISH
from there, implement short gaps, jumping or whatever.
You will need to override _compute_cost() and/or _estimate_cost() to “hack” into the solver by controlling travel cost calculations and estimations.
Inside these functions you will check what types of points are evaluated and compare it to some sort of “movement capabilities” of your agents to decide whether or not it is possible to make that move. If not, you can just return infinitely big number to discourage this path.
For that you will probably need to store our own collection of points with additional properties.
You will need to override _compute_cost() and/or _estimate_cost() to “hack” into the solver by controlling travel cost calculations and estimations.
This is a good approach when you need to discourage a path, but this system needs to make some connections fully impossible, so the solver ignores them entirely and returns that such a move is impossible. Even when the methods are overridden and set to INF, agents will still use this path if no others are available.
What I need to edit is the “_solver” function in “a_star.cpp”, which hasn’t been made virtual or overridable in GDScript. Unfortunately, I don’t know how to go about doing that.
This approach looks like it’d work well for platformer-style AStar, broadly speaking!
My issue is that some units using the navigation graph can’t jump, while others can; I need a way to toggle what connections should be ignored by the solver (or the connections themselves) on the backend. There’s no way to make conditional connections that I’m aware of.
My fallback method is to make multiple AStar graphs for different combinations of possible movement types, but since there are many and the world is editable in-game, this introduces a lot of AStar graphs that would need to be rebuilt regularly.
create multiple a stars. one where you can jump up a space. another for jumping up two spaces.
look into a star for platforms. doing an online search for “A* for platformers” i found this article:
try creating a simple A* from scratch to gain a deeper understanding. that is what i did. here is the tutorial that i used. it even has interactive sections you can experiment with.
I appreciate the suggestion and links, though I already understood your earlier example. Also, I am familiar with AStar techniques, and have made simple implementations on my own. I was just trying to avoid that, haha.
I’ve simplified the problem in my example, since it wasn’t the point; the issue is that I have a lot of conditional parameters that need to be taken into account for navigation, like many unit collision sizes (1x1, 1x2, 2x2, etc) multiple forms of jumping, wall climbing, swimming, free flight, and others. Making an AStar graph for every possible combination of traits would be roughly 25 separate graphs, possibly more. Since the game world is edited frequently, and would have to rebuild each of 25+ graphs constantly, node by node, this isn’t a viable solution. I need to keep separate graphs to a minimum.
I’m currently looking into making my own Conditional AStar solution via GDExtensions, or a completely custom solver in GDScript, since it seems there’s no easy way to override the built-in solver’s neighbor calculations. Was trying to avoid that, but it is what it is.
Regarding option 4 (setting nodes to be impassible), it should be doable without too much redesign by creating special “lock” nodes in between any two nodes that are connected conditionally. those nodes would always have just the two neighbors and would be the ones set to impassible, agents could then be updated to simply ignore them and continue to the next node while doing any actual movement or whatever.
Using an arbitrarily high value from _compute_cost could be an effective method, though the efficiency of A* would be hurt by the heuristic not really being able to take this into effect easily. The real downside is that it seems neither of the methods that return a path also return you the total cost of the final chosen path.
So knowing when an impossible path is the only one left must be determined separately, this could probably be done ahead of time using a simpler method or a combination of quick checks depending on what you can assume about your setup. In the case of only small areas ever being entirely blocked off conditionally you could run a maze solver from both the start and destination simultaneously and stop when either finds itself out of options. and in the case where there are a limited number of much larger areas that can’t be travelled between in certain cases, you could keep a collection of sets of nodes with the conditions needed to move from any set to any other, and use that to rule out the posibility in the case where points are in 2 different areas and the agent can’t take any of the bridging paths. Actually in a lot of cases I bet just checking along the path afterward would be more efficient.
Oh yeah and to answer the initial question, no you can’t hook into the AStar2D class’s internal methods any more than is provided by the exposed API and virtual methods. I believe that is also the case for GDExtension, so it would be either engine/module code, or re-implementation.
Oh yeah, I hadn’t considered using extra 0-cost nodes between nodes, to act as a conditional lock. That’s a solid approach! Directionality might not even be important, so I might be able to get away with adding a single extra “lock” node that all traffic into the tile routes through, which I could iterate over and conditionally disable before any moves by an agent were calculated. It’d roughly double the solver time, but that’s not nearly as bad as other things I was thinking, haha.
I’ll give that some thought, and see how it compares to making my own solution as a GDExtension. Thanks a bunch, and I appreciate the thorough answer!
