How to make a freeform 2D platformer pathfinding system?

Help Navigation
, ,
1

Godot Version

4.7.1.stable

Question

Hi, it’s me again, working on the same project. It’s a 2D platformer that’s constrained to set planes in 3D. The entire physics and characters are in 2D space.

I’m trying to build a system that allows an enemy to track down the player and get in melee distance. It has to know where the platforms are, where it can jump to and from, and to consider when it can drop down a platform to reach a destination faster.

Also, as a part of translating the 2D to 3D, my characters have to teleport a lot in 2D space. It looks perfectly smooth in 3D, but the 2D logic needs to teleport in order to achieve the effect I want to produce.

The main problem I’m facing is that my game doesn’t use a tilemap, it’s a bunch of StaticBodyes thrown around with intention. On top of that, the player can press the down button to drop from the middle of a platform and phase through it, and I want the enemies to be able to do the same.

The best piece of study I found in the matter is this video, where a guy does most of what I want to do, but in Unity. The thing is, the video isn’t a tutorial, it’s more of a devlog. It does say what they did to achieve this goal, but not how they did it.

Complimentarily, I also found this series of videos, which shows just how to make the navmesh, but it’s entirely on a grid map, which my game isn’t constrained to. Should I just use a grid map with 2x2 px cells?

What I’m asking is just how to approach this problem. I can probably finish it after some advice, but I kinda don’t know where to start, again. Mostly, how do I simulate several frames ahead of physics, for the jumps, and how do I make a navmesh for this kind of game? How do I tie teleportation to that navmesh? I know the teleporters probably should have a weight of 0 on the A* algorith, as it’s just how entities move around in the game, no effort needed to do so, but I don’t know how to make them.

I appreciate anyone who even reads this post up to this point. I know I’ve been asking for a lot lately, but I’m here to learn, and I’ll try to learn as much as I can.

2

Build your own A* graph using Godot’s A* system.

3

Well, I figured that that’s what I have to do, just not how I do it, yet…

Any insights..?

I don’t even know how to link the graph nodes between each platform, or even to place them on top of each platform to begin with.

I’m not doing that manually for an entire metroidvania lol, I need a way to figure out where the platforms are and how to connect them, and how to refuse a connection if a character can’t jump that high…

4

In a side scrolling platformer the graph would depend on character’s jumping abilities. You want to put an A* node at the end of each platform and distribute more of them in regular intervals along the platform. Then iterate through nodes and establish connections with all nodes reachable by character’s movement abilities.

5

You could simplify further. If there are no obstacles on platforms you can only consider jumping to be the cost and represent each platform as a single A* node. Since figuring out movement on the platform is trivial, the pathfinding then boils down to reaching the wanted platform through the series of platforms. You’d need a bit of simple additional heuristic to determine the position span on each platform that guarantee a jump (or fall) can be performed to another platform.

6

I’m beginning to understand, but what about the physics calculation to determine if a character can jump to another platform or not? And how do I connect the platforms?

The way I understand currently, I can set each platform to one or two nodes, but how can I programmatically connect one node to another? Or do you suggest I do it by hand every time?

Edit: How do you suggest that I add each point to the AStar2D class, too? Can I pass Vector2.ZERO to every point’s position, and calculate their “distance” by where they’re connected to?

7

Just generate points along each platform and iterate through all pairs of points whose mutual distance is below some threshold. Make connections if point b is reachable from point a through a jump or fall or is on the same platform. Ditto for reverse direction of the same two points.

To determine if a point is reachable by jump - start with some simple heuristic like checking horizontal and vertical distance vs the jump height/reach. Later you can upgrade this to something more accurate.

8

I’m sorry, but I’m having quite the difficulty in visualizing how this would work. Do you have and more specific documentation I can read or watch to know more?

Like, I can spawn a node point (probably 2 would be better) for every platform, and link them to each other, but I’m having trouble in thinking how to place nodes below each platform and link them to the rest, for the dropping feature.

I can see how one node graph would work for multiple jump heights, tho, just keep weak links with a jump threshold in them, and only really link the nodes if the character has that jump height or more. Of course it’d be more complex than just that, in practice, but I can visualize this part, at least.

9

I don’t have any recipes, just tossing ideas on how to generally approach it. This type of thing would be very specific to your platforming system, including movement and platform geometry. Since you haven’t shared anything about it - it’s hard to get into specifics.

Start setting it up and adapt as you go. I’d start with using points relatively densely distributed along platforms and a simple naive connection heuristic. Do some testing, see how it behaves. Then refine (or simplify) further from there.

10

Just for curiosity sake, I’ll show more about the project here.

image
image1722×422 10.8 KB

My platforms are all StaticBodyes with simple rectangle shapes. They’re color coded for ease of level building: blue platforms are not droppable, white ones are droppable with the one_way_collisionvalue set to true, green and orange ones are teleporters, but behave differently internally, both teleport a character if they are above the platform for a single frame.

The player is a simple 2D capsule shape. No sprite, nothing else, because the rendering is all in 3D.

Currently, time is stretched thin between two projects, so I’m not working on this one as much as I would like. I should start actually coding the NPCs and enemies tomorrow, I think, so I’ll be thinking more about it until then.

You can ask me about the project if you want, although I don’t know why would you.

11

As I said, sprinkle A* nodes along platforms in a certain density, then establish connections between reachable pairs. You can always alter/upgrade the connection making heuristic. Experiment and see what works best in your specific use case. I suggest making a connection visualizer to check what your connecting algorithm is doing.

You’ll also need to maintain an additional data structure that keeps track of which A* connections represent jumps or falls so you can move the character along the path accordingly.