next »

[JekasG]

Hi everyone,

I am trying to create an algorithm which handles a NavMesh / Point Graph Generation for 2D Procedural Platforms Level in Unity3D.
The reason why i say NavMesh / Point Graph is because i dont know for sure which one would be better for my 2D Procedural Platform Levels.

What i believe is that Point Graph would be better.

The major things i think i would have to face are;
- Navigating through the Platforms
- Jumping from a platform to another

I have read through the basics of Pathfinding;
- http://arongranberg.com/astar/features#
- http://www.redblobgames.com/

Although i have never made a Pathfinding System and my coding skills arent all that good, but i am willing to learn. Please, if possible could you guys reply with simple English. I dont understand the complicated terms. Thanks in advance for that.


So this is what i have in mind. SInce i know how to say it in theory i dont know how to put it in code. So please, give me advises, criticisms and most of all new theories. Since i already have a working Procedural Platform Generator, I plan to work from that.
From that Point Graph, I plan to generate Points above the Platforms, on each end. So the AI knows where it can navigate.
Once it can navigation from one end of the Platform to another. Its time to implement Jumping.
So to do so, i plan to Raycast some Math Trajectories. So when the Raycast has hit the next platform ( in some way , i havent figured out exactly how ) and it needs to jump to the next platform. Then it will jump.

Some slight problems i have right now are;
- Generating the Grid to do the Pathfinding ( Main Problem )
I know for normal Pathfinding, Normals Linear Grids are used. But i am certain that for my situation i cant use that.
So how can i generate my Graph ?
Please include some algorithms
- How is jumping done ? ( Major - Minor Problem )
Am i to program some code for the computer to input some buttons so the AI will jump ?
- How can i perfectly do the Trajectories ? ( Major - Minor Problem )
- How are cost / weight calculated ? ( Minor Problem )



Thank you so much. Your help is very much appreciated.

[Layl]

If you've never made a pathfinding algorithm start with something simple. Something like a simple top-down grid to navigate through with a point graph. First try to understand the way navigation graphs and A* work in isolation of any fluff. A good tutorial on that has been made by quill18 on his channel:



First understand the basics, then go on to more complex things.

[JekasG]

Yes i understand that i need to learn from the basics.
But after learning from the basics it still doesnt help me at all.
Especially using a Point Graph

[Zack Bell]

I think Layl's point is that you shouldn't run before you can walk, or even crawl. Pathfinding for procedurally generated platformer is complicated and as far as I know, hasn't ever been done well at all. Ever (correct me if I'm wrong.

That being said, "i have never made a Pathfinding System and my coding skills arent all that good" is a bad sign. Implementing the A* algorithm is going to be your first step whether you're looking at platformers or a top-down RPG. Start there.

I only replied because I started a series that hopes to be something similar to what your'e after.

Part 1: http://zackbellgames.com/2015/02/15/pathfinding-pt-1/


Part 2: http://zackbellgames.com/2015/02/16/pathfinding-pt-2/


Part 3 will hopefully be up tonight or tomorrow.

[Fallsburg]

Well, I'll just say that pathfinding for platformers (at least standard left->right Mario style platformers) is essentially a solved problem (see Robin Baumgarten's work

).  But in the scheme of crawl/walk/run that's running and you are at a crawl, so check out Zack's stuff (or any of the other countless A* tutorials).  A* is simply a graph search method (although I feel like it's commonly thought of as a grid search method in the indie game AI world) and is just about the best (although it typically requires a pretty tight heuristic to get good results, and doesn't do well with probabilistic or hidden information [see Monte Carlo Tree Search for work there]).

[BorisTheBrave]

The infinite mario thing doesn't look very far ahead. It couldn't pathfind through a whole level, I think.

[J-Snake]

If that only would be so simple for my Super Metroid Tournament...

[Fallsburg]

The infinite mario thing doesn't look very far ahead. It couldn't pathfind through a whole level, I think.

Well, it's a function of how the competition operated.  The AI was only given a local window (i.e. what it could "see" on the screen, although it wasn't doing any sort of vision).  Moreover, the infinite mario level generation is pretty simple and doesn't produce any dead ends.  That being said, it would be pretty trivial to include dead ends and a memory of what has been seen for more "global" level pathfinding.  Other than that, it's just an issue of time and memory (and the fidelity that one cares to model the pathfinding).  It does it's A* pathfinding at the frame level, which is probably overkill for most pathfinding, as one can typically do high level pathfinding and then rely on steering for low level motion.

[BorisTheBrave]

Well, precisely. The infinite mario frame-by-frame is only good for the local bits - you'd have to add in a high level path finding on top of it - in other words, it doesn't really tell you anything about how to efficiently path find for platfomers.