A* Pathfinding for Procedural Platformer Levels

This is quite an interesting problem.

I don't have time to look into it but I did some quick thinking.

First, have you experience with A* PathFinding? I programmed myself A* Pathfinding that deals with the sales man problem for an iPhone app.

I think a good start would be to start with just getting a A* algorithm to work cause that is just the basics.

Also I think you will get much better answers if you ask on http://gamedev.stackexchange.com/ .

1.

This might be a start but I didn't think long for this problem! (weeks of programming can save hours of thinking).

I only thought of the jumping problem.

Find for every platform the left and the right end (see squares).

Find other platforms (below) within the maximum jump range (see arcs).

If it intersects with a platform below then the intersection might be a good start as a jumping point (purple).

However, the idea above doesn't deal with a lot of situations.

2.

While writing above I got a new idea. The pathfinder should be aware of the acceleration, speed, direction etc.

You have a certain amount of "fuel" for a jump, i call this 'J'.

Let's say 'J' is 10 by default (meaning you could jump 10 units up).

You allow access to access isolated white cells, as if it is a RTS game seen from above. However, accessing a white cell in the up direction decreases J. If J == 0 then you no longer can go up, so the next nodes to look for are down (gravity).

While writing above:

Instead of 'J' for jump it should be related to upwards acceleration. So on the start of a jump the acceleration in an upward direction get's added. (And some boolean canJump will be set to false until you hit the ground again).

That's it for now. I might have more time in like a few weeks from now. I really love to solve those problems.

It would be nice if it could also take time into consideration to deal with moving platforms.

O yeah, about F = G + H. Last week I did a quick test where I reversed an array that had the best options for the next node sorted. By adding one line of code I had an algorithm that was almost taking the longest path possible

I'd make a navmesh algorithm that would scan new procedural sections of the level before they get visible to the player, then append them to an already existing navmesh.

I think you just need to add a couple extra conditions to your valid path check for jump height etc. You wouldn't have to change too much.

The fact that it is a sidescroller might be confusing you. But you can implement the pathfinding algorithm in a similar manner as you would for a top-down game (I assume this is what you mean by 'normal' pathfinding), it's still 2D space after all, and the world can be split into a grid of sorts (and you can avoid evaluating a lot of grid nodes if you only have NPCs which walk on the platforms and don't float/fly/etc). But you'll need to think of extra conditions which will apply to your game, as Alex mentioned (which will probably involve taking your gravity values and movement behaviours into account).

A couple of additional resources for A* - not specifically about platformers or procedural environments, but they might still be useful:

http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.redblobgames.com/pathfinding/a-…troduction.html

It also depend on how perfect you want it.

If it's just jumping up straight and going to the left/right at the last moment then things become a lot simpler.

Curiously I think the biggest challenge here is to make it work with platforms that might be underneath/above each other...

I started on a pathfinder from scratch last week. I got the nodes based one working. I almost have the tile based one working as well.

Anyway, I was watching some youtube. Saw this one:

It's not that good but I liked it anyway.

Also there where some pathfinding tutorials for unity on youtube. Maybe they help you.

I will post more later.

Quote from JekasG

I am just wondering . . What kind of grid would i be using for my situation ?

A graph is a graph, there are probably some more optimal solutions though yes.

Quote from clankill3r

I started on a pathfinder from scratch last week. I got the nodes based one working. I almost have the tile based one working as well.

Anyway, I was watching some youtube. Saw this one:

External Content www.youtube.com

Content embedded from external sources will not be displayed without your consent.

Display content once Display all external content

Through the activation of external content, you agree that personal data may be transferred to third party platforms. We have provided more information on this in our privacy policy.

It's not that good but I liked it anyway.

Also there where some pathfinding tutorials for unity on youtube. Maybe they help you.

I will post more later.

Display More

This is an excellent yet simple example on how to do it.