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

[ivan.moony]

I'm aware of a method for path finding, but I don't know if I can put it in simple words...

Let's say that we have infinite size chess board and a horse on it. We have to find how to drag a horse in multiple moves from its starting position to specified place. The trick is that we have to grow a tree of every possible move from starting position. Starting position then gets 8 possible new positions after first move. Each of that 8 position then gets its new possible 8 positions for a second move and so on. With each branch we check is specified ending place equal to any of new places. Once we get ending place inside some branch, we forget all other branches and memorize branch that canonically led to ending place.

Analogically, with each platform, I guess you should enumerate platforms to which you can jump or fall to. Then you start building tree from the current platform and check for ending platform. At the end, you'll get an ordered list of platforms which you have to pass to get to the ending platform. Jumping/falling complicates things a little bit, but I think it should be sufficient to store information about direction of jump or fall when enumerating possible movements.

Sounds complicated, but once you get it, it is really simple thing.

[Korrelan]

Being as your just starting out with AI I suggest you start with a simple vision system.  You have the right idea for casting rays.

If you scan from Mario’s eye level out into the game space you’ll end up with very basic idea of the layout in front of your character.  Then use simple pattern matching between the degree of the ray and the distance until it encounters an object, note the main colour of the hit surface (use an averaged colour block).  The patterns can easily be stored in an array and checked for the next best appropriate move. 

Gaps (red triangle) and jumps (blue triangle) can easily be detected this way.

Without the use of genetic algorithms you would have to play the game while the system learns to play.

I know it’s very basic but you got to start somewhere