I mentioned originally doing a k-nearest-neighbor search when selecting points for joining the connected components of the navmesh in process; this can be especially critical when you need to support parallel travel of heavy volumes of agent traffic without artificial bottlenecking at mesh merge locations. In our particular situation this turned out to be far more important than I originally guessed, and in fact required revisiting the entire merge process to yield a more robust "stitching" of the meshes.
At the time I wrote the first article, I was using a kd-tree to accelerate the nearest-pair lookup and produce the final selection of points used in the connection algorithm. When it came time to adjust the code to produce more stitches, I encountered some severe performance issues - on the order of a 10-40x speed drop depending on the data being fed into the algorithm, for only an order of magnitude increase in the number of requested stitches.
To make a long and mostly dull story short, I eventually wound up dumping the entire stitching half of the algorithm and starting from scratch, doing a naive brute-force search for the nearest neighbors used in the stitching process. My initial logic looked something like this:
While there are more than one connected components in the graph Select an arbitrary pair of connected components, CC1 and CC2 For each node N1 in CC1 For each node N2 in CC2 Compute distance from N1 to N2 Insert the pair (N1, N2) into a list, sorted by the distance value While the list is larger than k elements Remove the furthest-sorted pair from the list For each pair in the final list Create a stitched edge Mark the two connected components as merged
Obviously this was painfully slow (on the order of many minutes to merge the test meshes) and has terrible overall performance characteristics. But what do you expect - it's a naive implementation, after all [wink]
My first observation was that this led to a lot of duplicate edges. I added a simple blacklist that prevented a node from being used in more than one stitch, which added a minor speed boost (only a few seconds - remember this was taking several minutes!) and improved the visual results substantially.
The second key observation followed from there: I was much more interested in prioritizing the blacklist than the actual distance constraint! In other words, it was primarily important that the stitches not end up all joining the same nodes; the actual distance between stitched nodes was largely irrelevant. I only cared about the distance as a sort of heuristic to try and keep really wildly disjoint nodes from being stitched together and creating paths through boring, empty space.
At this point, it was easy enough to realize that the entire idea of doing a k-nearest-neighbor search (or more accurately, a k-nearest-unique-pair search) was a total red herring. All I needed was a set of seed points that was relatively "close" together, and the stitching could proceed from there.
This led directly to the next refinement of the logic, which (with only minor tweaks) ended up being the final incarnation of the algorithm, which is currently slumbering safely in our version control repository:
While there are more than one connected components in the graph Construct a bounding box surrounding each connected component Find the two components C1 and C2 whose bounding box centers are closest Find the k1 number of points in C1 which lie closest to the center of C2's bounding box Find the k1 number of points in C2 which lie closest to the center of C1's bounding box Pair up each point in P1 with the corresponding point in P2 (based on index alone, no other criteria needed) Sort the pairs by their separation distance Select the k2 closest pairs, pruning pairs which create edges that intersect collision geometry Create edges for the selected k2 pairs Mark C1 and C2 as merged into a single connected component
This allows us to fine-tune the number of candidate pairings (k1) and then select the best from those (k2), which gives us a really easy switch for controlling how much time we trade off in the heuristic search phase (assembling the candidate pair list) with time spend actually stitching edges (connecting the k2 selected candidate pairs).
Net results? A mesh merge now runs in an average of ~0.55 seconds on our test data set, with a mere 0.22 seconds spent in the stitching phase. That means the majority of the time is actually spent shuffling storage around to hold the newly created, larger navigation mesh. With some tuning to our allocation strategy, we could probably drop this time even further - but for now, it's already a factor of 3 faster than the old method, and produces superior results.
I call that a pretty solid win.
