2
\$\begingroup\$

I am looking forward to create a navigation volume to be utilized by AI actors.

The approach I am trying to tackle here is to first generate an octree and associate with respectable flags/data (type, what's contained for now). The octree is going to be fairly deep (up to 0.1 units).

This is the scene I am using for testing purposes: test level

results in 1947817 nodes in 9 levels. (22 x 9 x 22)

I am looking for an algorithm/concept/pseudo-code that would transform this octree into non-uniform, axis-aligned boxes derived from octants that match certain flags/data, that would, for instance, help me determine the navigation volume similar to what can be seen here (Havok):

simple nav volume, havok

With "I am looking for" - I have a feeling of such an algorithm/concept already existing, though, I am not sure. The feeling drives me towards this being a fairly mathematical problem that resides behind a common name.

The other approach would be to utilize a non-uniform grid (creates 4356000 cells) for the detailed shape to then be expanded (simplified) down to some boxes. Which my feeling tells, would utilize the same algorithm.

As for the "what have you tried part" - well... I have googled for some time with various combinations from keywords grid, merge, cell, flags, occupied, gamedev, octant, grow, largest space, adjacent and maybe some others to no avail. Well, before pushing the Post button, I did try some more keywords and ended up with this answer: https://gis.stackexchange.com/questions/23365/how-to-combine-adjacent-polygons-sharing-similar-trait-into-single-polygon which appears to be close to what I am looking for, except that it's 2D (though, I gave the keyword "polygon" for this query). Having learned that the process is called "dissolve", I made some more attempts with various combos with added word "dissolve". And through my findings some more searches and so on... Well... nothing.

If the answer wont yield any results, I know that I could attempt this by raying the hell out of the graph by starting at either corner and flooding through it all, basically, brute forcing my way.

So...

Is the common algorithm/concept already out there, that I could be pointed towards?;
or - what guidelines should I follow to produce such a product?

|improve this question
\$\endgroup\$
  • 1
    \$\begingroup\$ Just to double check: what you want to achieve is a nav-volume with less nodes, because the oct-tree ends up leaving you with too many due to it not allowing for asymmetric nodes, is that a correct assessment of your problem? If yes, I have a suggestion based on what I myself have implemented in the past \$\endgroup\$ – MAnd Feb 1 '16 at 22:35
  • \$\begingroup\$ Yeah, that's what I would look forward to ask if I were to bail this idea! Though, nav volume is one of the problems I am trying to solve. I know I could utilize this with other input data for other stuff (trigger zone generation). Basically, I am looking for a pre-processing tool that would - given some input, return some grouped volumetric output. \$\endgroup\$ – joltmode Feb 1 '16 at 22:41
1
\$\begingroup\$

If what you mean is that you need a nav-volume with fewer nodes because the oct-tree ends up leaving you with too many nodes, the main issue behind you problem is, of course, symmetry.

Or better said, the fact octrees do not allow for asymmetric nodes. The result of that is empty space ends up being wastefully divided - either in the within a given level, or worse, having to go down to more levels.

There are, of course, ways of just merging the boxes generated by octrees into arbitrary polyhedron. But I think that before going that route, what you are needing is the same I myself needed in a similar project: the correct spatial partition tool. In this case, KD-trees. These are much more appropriate than octrees for what you seem to be trying to achieve. The reason is that KD-trees are precisely spatial partitioning that allow for irregular (asymmetric) axis-aligned boxes.

In youtube you find some examples of 3D KD-trees: https://www.youtube.com/watch?v=_mzArAN7HYc

https://www.youtube.com/watch?v=NHoqyOJgzSg

https://www.youtube.com/watch?v=bHkaapcPyp0

More technical links are:

Introduction to kd-trees

Kd-trees and range trees

Specifically on navigation using nav-volumes, you can take a look at:

Getting off the NavMesh: Navigating in Fully 3D Environments

Efficient path-finding in free space

Practical motion planning for aerial-like virtual agents in Meta!Blast: A full and complex three dimensional virtual environment

http://web.archive.org/web/20110830022549/http://face2face.grandnotions.com/2011/08/pathfinding/

3D Pathfinding – Simulating Intelligent Navigation for Flying Creatures in Computer Games

Or see it in action here: https://www.youtube.com/watch?v=pq_nte8bVoE

https://www.youtube.com/watch?v=pegruZo4g6I

And for gentle introductions to the many spatial partitioning possibilities, see these two slide-shows: Acceleration: Spatial trees

CS 354 Acceleration Structures

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Damn, I looked at everything (octrees, bvh, bsp, uniform grids), but them mfckng kd's. Too much info on the net about octrees in this Minecraft'esque era. Say then... I can extract my desired exact "trigger zones" from KD-tree too, right? Just by popping the matching node(s). \$\endgroup\$ – joltmode Feb 1 '16 at 22:56
  • \$\begingroup\$ @joltmode Haha, it happens! I edited the answer with plenty material on KD-trees and also, in the end, two links with some introduction on spatial partitioning in general. With KD-trees, your trigger zones could be either one of the big boxes that represent the empty space, or you could even, of course, specify a specific area (say a custom box of yours) that lays inside one of the irregular nodes of the KD-tree. Than just check if position of object is inside the correct node of the tree. \$\endgroup\$ – MAnd Feb 1 '16 at 23:01
  • \$\begingroup\$ Sweet... Huge thanks (whenever huge + appreciation comes to mind..) for the materials! All those 4 nav-volume articles I am already familiar with - all have been stored offline and bookmarked. Haven't read through all of them with the greatest of detail (besides the Warframe, GDC one... octrees, you see?), though. \$\endgroup\$ – joltmode Feb 1 '16 at 23:15
  • \$\begingroup\$ Hmm, where you linked the KD examples, you have to links that are exactly the same - is it just a duplicate paste, or there had to be another link in the latter one? \$\endgroup\$ – joltmode Feb 2 '16 at 20:36
  • \$\begingroup\$ @joltmode oops, sorry for that, it was my mistake. I corrected it and even included both one more video there, as well as one more link elsewhere, which is this one: thomasdiewald.com/blog/?p=1488 \$\endgroup\$ – MAnd Feb 2 '16 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.