Create a navmesh from scratch


May be i’m off on a tangent, but my game has no ‘terrain’ or anything of the sorts. I place enemies, obstacles and goals in the scene, and want to have the enemies move towards the goal, avoiding the obstacles. I’m beginning with simple steering mechanism (seek, avoid etc. from tuts+), but at some point it would be nice to be able to do Theta* or A* for their pathfinding. Without any terrain to use as base for navmesh - where do I start? Do I use a ‘blank’ terrain and go from there, or is there any way to do this starting from a blank navmesh…

My game is only 2d (top-down).

The idea would be to subtract the obstacles from the navmesh ‘walkable’ area every time obstacles are placed. Does that make sense?

Looking for any help or directions to sources that deal with ‘not having any terrain to base it off’ :slight_smile:

kind regards

I would have 1x1 tiles and the tile information would be 1 for path and 0 for wall (or obstacle). You then could even have 0.5 if it is water or so. If you have those tiles the A* implementation is straight forward. No clue if you can organize your game “terrain” in tiles :slight_smile:

I did this for one of my game (which I didn’t finish as creating the game content for my game idea was hmmmm too much for one person :wink:). If you have multiplayer game this is even a very server friendly way to do it. And doing it with for example Zay-ES would be pretty easy … (I had a pathfinding system as far I can remember).

Hope this helps.

For a dynamic 2D polygonal pathfinding you might take a look at jWalkable.
It’s a very thin layer on top of [hxDaedalus] (GitHub - hxDaedalus/hxDaedalus: Daedalus-lib Haxe version) to provide an easy to setup 2D polygonal pathfinding.

You can watch some demos here :

Hope this helps.

That’s probably the way to go. My obstacles can be placed at any position, so I would just have to figure out which tiles are obstructed by the obstacles and mark them in the grid as unavailable. Depending on granularity of grid, it could result in fine pathfinding (though the grid size would then get pretty large…).

I will certainly have a look. Thanks.