Generating a NavMesh / Point Graph for 2D Procedural Platformer Levels

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

 

[Klems]

- 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

 

We need an exemple of one of your levels and a size estimation (level size and maximum path length), otherwise we can't really help you.

Is the level made on a grid? Or with polygons? You can use octrees though.

 

It shouldn't be that hard though. There's no need for a navmesh, pointgraph is good enough for a platformer game, especially if this game is on a grid.

Generate enough points for each platforms and connect these points (= points are connected by walking). Once this is done, you connect adjacents platforms by finding out each pairs of points that are connected by jumping.

 

- 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 )

 

You gotta remember your physics/maths classes. You can deduce the general trajectory of any solid from his initial velocity/position + gravity. http://en.wikipedia.org/wiki/Trajectory_of_a_projectile

This trajectory can slightly change depending on how well you wrote your physic engine and on which numerical integration you used.

 

Basically, for any pair of nodes in your point graph that could be connected by jumping, you try to compute the optimal initial velocity to make the jump (some trajectories are faster than others). This velocity can't be higher than the base running/jumping speed of your IAs, obviously. You also need to trace along to check for any obstacles. Dropping down is a special kind of trajectory where the initial vertical speed is 0.

 

Once you know which points are connected and have the initial velocity needed to reach it, then there's nothing else to do. Once an IA reaches this point and wants to jump, then apply this velocity and that's it.

It will probably be too efficient at first, you can balance that by limiting the velocity, adding a cooldown/animation between each jumps by the IA, etc.

 

- How are cost / weight calculated ? ( Minor Problem )

 

Which ones? If you're talking about weights in a point graph then it's just a matter of being more or less proportionnal to the time it takes to traverse an edge.

[JekasG]

So this is how i generate my platforms;

 

This is the general idea;

First i make a forloop, defining how many platforms i want on the Y-Axis then make another forloop inside the first one and instantiate random amounts or defined amounts of platforms, as long as it doesnt reach the xDeadEndPos.

 

So this is the details;

These are all the variables i made

xStartPos - The very Left Position of the Platform

xMidPos - The Middle Position of the Platform

xEndPos - The very Right Position of the Platform

xDeadStartPos - Restricted Offset that Restricts Platforms from Starting

xDeadEndPos - Restricted Offset that Restricts Platforms from Ending

xSpacing - Spacing between each Platform, X - Axis

 

 

Since in Unity3D i dont know how to, define the Middle Position of the object and define the size and then evenly position that size of the gameObject on that position. In addition, it would cause some problems if i do it that way. So what i did was to have xStartPos, xMidPos, and xEndPos.

 

First i assign a variable which specifies the spacing of the Y-Axis

ySpacing - Spacing between each Platform, Y - Axis

I make a forloop which specifies how much i want on the Y-Axis

I then make another loop which either set or randomized of how many i want on the X-Axis, but doesnt exceed the Postition of xDeadEndPos

And this is how the platforms are calcuated

xStartPos - xDeadStartPos + xSpacing

xMidPos - ( xStartPos + xSpacing ) / 2

xEndPos - xStartPos + xSpacing

xDeadStartPos - new Vector3 ( 5 , this.transform.position , 0 )

xDeadEndPos - Random.Range ( 55 , this.transform.position, 0 )

xSpacing - Random.Range ( 3 - 5 )

 

Once this is done , I use these information to instantiate the platform

The process is looped

 

At the end of the second loop ySpacing = ySpacing + Random.Range ( 3 - 5 )

This ends the first loop

 

 

 

So this is the visual result

 

http://s29.postimg.org/6saka7vtj/Platform_Guideline_Complete.png