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

    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.

    Quote from JekasG

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


    Quote from JekasG

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


    Quote from JekasG

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

    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/Plat…ne_Complete.png

Participate now!

Don’t have an account yet? Register yourself now and be a part of our community!

Register Yourself Login