I'm generating nav meshes for a rasterized game world and I'm at a point where I need to decide on an approach with hope that I can maybe save some guessing time :).

Basically, the two solutions I can think of both take advantage of some version of flood-filling, except that one generates information for holes and the other one should be able to generate a simple polygon that wraps around holes directly. Decomposition of polygons with holes isn't so much an issue as it's a potential bottleneck if the number of holes is considerable (eg they're small).

The algorithm should be able to update a region in near-realtime.

1) the first approach basically scans the work area for a boundary pixel and starts a marching squares run until it reaches the origin. The interior of this shape is then scanned for unaccounted for boundary pixels, which are marched independently and stored as a set of holes. The process is repeated until there are no more boundary pixels in the work area, at which point the boundary regions and their respective holes are simplified for good measure and finally decomposed into convex polygons.

By limiting the work are to a reasonable clip space (eg 256x256 pixels) I should be guaranteed to first hit a space (eg not a hole) when flood-filling from an edge or a corner. It should also be reasonably fast, but can still return polygons with a fair number of vertices.

2) using flood-fill directly. This seems like a better idea at first glance, because by using something like a memory-based flood-fill should return a simple polygon that wraps around any holes and generates stitches automatically. By memory-based I mean populating the fill region with time indexes instead of flags: if the fill wraps back on itself after a certain number of iterations, it no longer attempts to merge, but rather generates an edge as if it encountered a boundary pixel. The downside is that these interior edges may well be very jaggy (eg consist of a lot of vertices) and would require a lot of look-up time later on to optimize.

That being said, perhaps there's a third approach I'm not thinking of :).

I'd appreciate some thoughts and/or ideas before setting out to write the code, so if anyone has any - bring them on!

By "simple polygon" you mean something you can easily work with (I assume triangles are okay, right? ... or do you want just monotone polygons, just convex polygons? ... actually if we break everything into triangles it might be the best - they are monotone and they are convex).

Actually, by Simple polygon I literally mean the the technical term, which essentially describes a concave non self-intersecting polygon (the precise definition is a bit more involved). I already have my ear clipping as well as convex decomposition routines down, so getting a near-optimal convex representation is not the issue. I think the inclusion of holes elevates the term to something like "weakly-in-simple", although I'm not sure if that's official lingo or not. My current objective is to first either directly generate these concave polygons so that they wrap around holes, or find a way to extract hole data and extend my convex decomposer to handle them (which isn't really all that difficult, to be honest, seeing as getting the hole information in the first place is a considerably costlier affair).

You might also want to do 3rd step here, and that is merging some triangles into convex polygons (it really depends on your navmesh algorithm, mine is built on top of triangle nodes only, which makes a lot of things easier).

As mentioned, I'm already doing convex decomposition from concave polygons, so no triangles involved at all . As post-processing I also do single-pass merging of this convex set to further optimize the results. So far this has resulted in pretty much an optimal final set in 99% of the cases (at least according to visual assessment).

Is it possible to construct a quadtree (or similar) for the binary map to quickly determine boundary pixels? Maybe the process that generates or modifies the binary map can help with this.

I think merging/optimizing the line segments afterwards shouldn't be to much of an issue since the number of line segments only scales linearly with the area size, whereas the number of pixels scales quadratically.

Using an acceleration structure is a great idea! I think I can fairly easily add pixel counts to subregions of each work area, although it feels like in this case a quad tree is a bit of an overkill. A regular grid of something like 32x32 pixels will avoid a bunch of pixel lookups.




Anyhoo - I dabbled with the code a bit last night, which gave me a couple of ideas:


For starters I decided to try out a somewhat optimized flood-fill method, which should generate a single fairly optimal polygon per cavity in a single fill. I haven't finished and hence timed it yet, but the idea goes roughly like this:

- a polygon is always extruded around a pixel or a set of pixels (eg a pixel has dimensions) - this is to get around potential dead ends that are one pixel wide.
- the algorithm starts breadth-first by scanning from the top left until it finds an valid starting point. This is guaranteed to be a boundary pixel. It then extends the row to the right until it encounters another boundary pixel. A quad is (eg four edges/vertices are) constructed surrounding the row.
- it then checks if any of the new edges is a closed boundary segment (eg it lies on the edge of the work area or is completely walled in on the outside, forming a boundary edge). Any edge that isn't a boundary segment is added to an "open list". All edges are also stored as vertices in a linked list.
- instead of flood-filling pixel by pixel, the algorithm then iterates over edges in the open list and scans a row or column along the boundary the edge, extruding the polygon in that direction
- if an edge cannot be fully extruded, it is split and any gaps that can be extruded generate new vertices
- a look-up table of consumed pixels needs to be maintained, though, since the polygon can wrap back on itself
- this is repeated until there are no more edges in the open list

This idea probably exists as a flood-fill algorithm, but as best I can tell, it should be pretty fast for generating a polygon with both the least number of interior edges and an optimal number of boundary edges. A pre-existing acceleration structure would also allow fast expansion if a tile is empty, which would initially generate extra vertices; nevertheless, removing these can be done while the algorithm is still running.

Here's the beautiful thing: using vertex caches, insertion can be done dirt cheap since the list is doubly linked and, more importantly, the cost of traversal will be limited to a cache-friendly lookup from a short linear array, instead of memory hopping along the boundary list itself. In fact, the boundary only needs to be traversed once after the algorithm finishes to retrieve the outline (and once more as part of the simplification step).

One thing I still haven't quite thought through yet is how to handle diagonals (eg one-pixel "corners"). As far as I can tell, segments that connect at a 45 degree angles can easily be connected and will always form boundary edges. The smoothing/simplification pass will therefore foremost need to handle cases where the scan returns a series of interleaved short diagonal and orthogonal segments. Simplifying these should be as easy as merging segments until a notch (a reflex vertex) is encountered or the minimum desired length is achieved. For regular polygons this could be potentially costly, but there are two simple thing I didn't quite realize before: all segments are classified as either axis-aligned or diagonal. In both cases the length of the minimum size segment is fixed, which completely does away with any conventional distance checking to calculate segment length (in fact the length can be updated by the algorithm itself during flood-fill). Also, since the number of directions in which lines can go is precisely eight, determining whether a vertex is reflex boils down to doing a trivial lookup instead of calculating the dot product (which even in 2D is 5 subtractions and 2 multiplys).