• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
  • entries
  • comments
  • views

Followup: 6DOF Navigation Meshes

Sign in to follow this  
Followers 0


My last entry here talked about a method for merging multiple navigation meshes in 6-degree-of-freedom space for creating navigation environments from individual components. As is often the case with real software development, a couple of weeks worth of refinement has gone into the method, and some additional tidbits have come to light.

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.

Sign in to follow this  
Followers 0


There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now