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