Leave a comment

>Nav meshes


I’m finally getting back to what I need to do: AI.

A necessity of any AI is good pathfinding. I had a basic point-based pathfinding system working long ago, but didn’t have proper steering algorithms (as proper as they could be for a point-based system). Overall it was not very convincing, despite it (usually) getting from point A to point B.

More recently, I investigated navigation meshes and decided I would like to try implementing them. The basic A* algorithm I have will still work here (they are just another graph after all), but I need to actually create these meshes somehow.

In the interest of saving time (and allowing for the possibility of users creating their own mazes), I investigated automatic generation of the meshes. I basically start with a rectangle, and subtract additional polygons from it (each polygon representing a wall I add). I used an algorithm for subtracting one polygon from another (not really trivial) and another for generating the “minimum decomposition” of an arbtrary polygon into a series of convex polygons (convex polygons are a necessity for navigation meshes). Some pretty heavy and boring math here, and I could never get it all to work.

What stopped me were floating point inaccuracies. When two convex polygons are adjacent and floating point precision comes into play, one of the polygons may no longer be technically convex. The algorithms I was using did not like that. After a week of trying to get things working, I (temporarily) gave up, decided it was not worth it.

I’m now back to creating nav meshes manually. As an aid, I auto-generate points based on the wall positions that will be useful for creating the polygons.

At the top of this post is an example of a completed nav mesh using the in game maze editor.
One benefit to creating them manually is that I get control over how they are positioned. I may want the individual polygons to be evenly distributed in terms of size/position if I end up using polygon-level conditions (e.g. an enemy is in this polygon, so increase the cost of moving through this polygon).


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Just another WordPress site

Just another WordPress.com site

Harebrained Schemes

Developer's blog for IceFall Games

kosmonaut's blog

3d GFX and more


Turn up the rez!

bitsquid: development blog

Developer's blog for IceFall Games

Game Development by Sean

Developer's blog for IceFall Games

Lost Garden

Developer's blog for IceFall Games


Developer's blog for IceFall Games

Casey Muratori's Blog

Developer's blog for IceFall Games


Developer's blog for IceFall Games

Rendering Evolution

Developer's blog for IceFall Games

Simon schreibt.

Developer's blog for IceFall Games

Dev & Techno-phage

Do Computers Dream of Electric Developper?

- Woolfe -

Developer's blog for IceFall Games

Fabio Ferrara

Game Developer

Clone of Duty: Stonehenge

First Person Shooter coming soon to the XBOX 360

Low Tide Productions

Games and other artsy stuff...


Just another WordPress.com site

Sipty's Writing

Take a look inside the mind of a game developer.

%d bloggers like this: