A* Pathfinding for Procedural Platformer Levels

[JekasG]

Im trying to write code a my Procedural Platformer Game , but i have no idea where to start.

Ive looked up A* Pathfinding in general, but i cant seem to find A* Pathfinding with Procedural Platformer Levels. That is, jumping from platform to platform.

So would anyone give me some pointers as to how to approach this problem ?
That is, taking into the account of the:

 - Enemies Physics ( Gravity , Acceleration, Speed )
 - Enemies jumping from platform to platform

How would i be coding it different for a normal A* Pathfinding and a Procedural Level.

Link for A* Pathfinding Tutorial

 - https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW

Link for Procedural Level

 - http://ashblue.github.io/pathfinding-platformer/

[clankill3r]

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

[Sentura]

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.

[AlexM]

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. 

[spence]

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-star/introduction.html

[clankill3r]

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.

[Sentura]

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

[JekasG]

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

[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:

 

 

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.

[AtsEst]

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.

[JAL]

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.

 

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