How can I do pathfinding on octree kind of map?

[lucky6969b 1333]

Is it possible to do pathfinding on an octree?

When I anticipate, I thought A* on an octree would open 9*2 + 8 = 26 neighbor nodes over each iteration,

if the agent can either go up or down.

What approach can I take to achieve this?

Thanks

Jack

Edited June 21, 2016 by lucky6969b

[Nanoha 2682]

Does it make sense to use the octree nodes as the nodes in your pathing graph? It might not be the most suitable thing to do but only you can decide that. As long as you can have nodes and edges in a graph you can probably use A* just fine.

 

With an octree, your entity will start by being in one of the leaf nodes, then they will have to traverse up the tree until they come to a shared parent and then traverse back down to the desired leaf node. They would presumably move towards the centre of each node until they are in that nodes volume. It does sound possible and it very likely is but I'm not sure it's the best option. I tried this on paper using a quad tree and I find that usually the best path ends up being more or less a straight line which may well be blocked if you have other objects in the scene and if you don't then you don't need to path anyway.

 

Personally I think you shouldn't use the octree as a pathing graph and instead should create a more appropriate graph. Is your graph going to be big enough that you would need to partition the actual graph itself? If so there are probably better methods of achieving that than using a generic octree but I don't know enough to make a recommendation, hopefully someone with more experience can offer up better advice.

 

What is your world like? How big is it? How open is it etc?

[samoth 9831]

Personally I think you shouldn't use the octree as a pathing graph and instead should create a more appropriate graph.

I agree. It is without any doubt possible, but the question should really be "does it make sense, is it the best thing?".

Pushing back the question wheter an octree is very suitable at all for a moment...

Do you strictly need 3D pathfinding at all? Most people do well enough with "2D and some", and not few even only do 2D at all (without the "and some"). Plain 2D is sometimes a bit poor with flying units that cannot cross water and such, but still "and some" is normally good enough, you rarely need real 3D. Adding a node that is for flying units only usually does the trick. Most units don't move in 3D anyway, and if they do, they don't truly move in 3D if you take the ground as a reference, or hardly.

The only things I could ad hoc think of that really need true 3D pathfinding would be a dungeon maze with several levels, aerial combat simulation, or space games. Everything else either walks on the ground, or has some flying abilities, but still mostly-walks-on-ground for practical purposes.

Mazes are not normally large enough to justify an octree. Also, in a maze, agents usually don't need to pathfind from the bottom to the top. It's the player's task to do that, and monsters are usually per-level 2D beasts... If monsters are able to track the player up the next stairway, that's already almost revolutionary (how many games do that!) -- and this can be easily done with one extra node over the stairway.

Airplanes really only need to care about not flying into a mountain or tower, the rest is more or less "straight line through mostly empty space", so that would be "2D plus". Shoot at enemy airplane? Draw a line.
Yes, in real life you have flight levels and corridors, but that's a different thing, and it isn't a pathfinding problem either. There's a well-defined course and altitude which you must follow, and you have no questions to ask or think of a better route (flight control tells you exactly what to do).

Similar for space sim. Most of the universe is empty, and "draw a straight line" works 99% fine. And when it doesn't work, you just have to "bend" your path ever so little so you don't fly through a star. So basically, draw a straight line, and see if it collides with the bounding sphere of something of planetar size. Unless you want something like navigate fully automatically through a narrow passage between two hostile territories, I don't see how there's large demands on path finding there.

There's that "hierarchical pathfinding" thing of course, or the "hierarchical AI" thing in general. Which has its merits. But an octree (or let's say quadtree) still doesn't seem like the necessarily best approach. I'm using a "somewhat hierarchical" regular grid representation for the world myself (with three levels alltogether) because I like the idea that you can just stop simulating what no player can see, and I'm cheap. But pathfinding itself is in fact embarrassingly poor, yet it works entirely satisfyingly (indeed, it being poor accounts for the fact that units are not omniscient, which is desired).

That hierarchic stuff is not a free lunch alltogether anyway, there is a point where things turn around, and it's hard to predict where and when. After finding a path within high-level nodes, you still have to pathfind within each high-level node, and if these are huge, they contain a lot of child (grand child, grand-grand child, ...) nodes, which are added to the sub-search again. It still prunes a lot away, but it's not a free lunch alltogether, and infinitely. Plus, unless you put a lot of extra work into it, there is a good chance of getting a rather sub-optimal path (which is not always undesirable, more perfect is not always more good).

I haven't ever tried the octree approach, so everything here is just guesstimate. But the mere added complexity paired with the uncertainity whether it really adds a lot turns me away.

There's that thing called cache, too. Octrees are one of those structures which look awesome, and perform awesome -- on paper, looking at complexity numbers, and also in some real-life situations. And then they fail miserably in other situations, solely because the way you access them doesn't play well with the hardware. There are some access patterns (and I am afraid A* might exactly be one of them!) which are catastrophic worst-case to an octree (unless the whole octree fits into cache, and in that case it's so small that it's pointless).
I remember (unrelated to pathfinding) an article some 4-5 years ago analyzing Minecraft-like engines which concluded that although octree is what everybody intuitively jumps onto, it fails performance-wise because of iteration being the main operation.

[ferrous 6161]

I could see it being mildly useful for checking if you need to break down and do pathfinding.  Doing a raycast versus an octree to see if you hit anything with a solid in it, then breakdown and do pathfinding from there.  With possibly just doing a pathfind within the smallest octree, though I'm not sure how nice the paths generated would look.

[samoth 9831]

With possibly just doing a pathfind within the smallest octree, though I'm not sure how nice the paths generated would look.

That would probably be a straight line since the smallest octree is just one node. Neither the highest level nor the lowest level really makes a lot of sense optimization-wise in an octree. One contains "nothing" and the other contains the entire world.

 

But generally the "find sumthin' coarse, then pathfind inside the small area" approach gives very nice results, in my opinion. It does with a somewhat-hierarchical-grid anyway. The results are rarely perfect, but they come close (in any case almost always acceptable) and they very ingeniously (inadvertedly, but anyway!) simulate the way real life humans and animals pathfind.

 

You look ahead and see mountains blocking your path, so you decide to go right where you see nothing blocking your way. After walking 3 kilometers, it turns out there is a tunnel going through the mountain, and a river blocking you on the right with the next bridge two kilometers away. But you could not see either of these when you looked! Too bad for you!

 

That's just what the coarse-first-then-pathfind approach does in some situations (not always), too. Which is admittedly not so great if you are strictly searching for the optimal path, but who wants the optimal path anyway! Almost nobody does. Indeed, most people put a lot of effort into their AI to make it not-too-perfect. Nobody wants to play against a computer and lose every time.

 

An AI that works close to perfect 80% of the time, but has 1% epic fails (but eventually still finds its goal) is just great. And it does that on its own, without you even trying. Computers are only humans, too  :D

Edited June 22, 2016 by samoth

[ferrous 6161]

Yeah, sorry, wasn't clear, I meant, do the raycast, hit a leaf, back up one to it's parent, and pathfind around that leaf.  I'm spitballing since I haven't worked with an octree.  And I agree, most optimal paths aren't really needed.  I make all sorts of fairly brutal shortcuts in my pathfinder, and the paths are good enough.  I see some wonky paths occasionally, but for the 90% general use case, the paths are fine, and that's good enough for me.

[lucky6969b 1333]

I've changed my mind to use inclined quads now,

and let octree does other stuff.

when comparing the geometry with the current quad,

I use this...

if (triangle[0].y - m_boundingBox[0].y < m_tree->m_fMinHeight
            || triangle[1].y - m_boundingBox[0].y < m_tree->m_fMinHeight
            || triangle[2].y - m_boundingBox[0].y < m_tree->m_fMinHeight)
        {
            // project the triangle onto a 2D plane
            quad::vec2* projectedTris = new quad::vec2[3];
            projectedTris[0].x = triangle[0].x;
            projectedTris[0].y = triangle[0].z;
            projectedTris[1].x = triangle[1].x;
            projectedTris[1].y = triangle[1].z;
            projectedTris[2].x = triangle[2].x;
            projectedTris[2].y = triangle[2].z;
            addTriangleToRegion(projectedTris, startIdx);
        }

The problem is I can either compare with the maximum height or minimum height,

when the quad is inclined, I have no way to tell which y to compare with.

 

Update:

I think I should use the maximum height, because on a flat quad, the y's would be equal anyways....

Any ideas?

Thanks

Jack

Edited July 1, 2016 by lucky6969b

[frob 45503]

I think I should use the maximum height, because on a flat quad, the y's would be equal anyways....

 

 

That depends on your game.

 

As mentioned above, many games operate on the idea of a footprint that is navigated in 2D with a planar spatial system. For a human walking around even though a table has a usable top surface and space underneath the space is typically considered blocked for travel.

 

You can extend that with a height element as part of traversal.  You'll need to establish your own rules on what it means to change height since an opening at the top of one location may not connect to the bottom of another location.

If your game truly is volumetric and doesn't naturally reduce to 2D representations then it is appropriate for volumetric pathfinding.  As many people who talk about volumetric worlds tend to be thinking about minecraft clones, A* still works as the heuristic means the tool still makes a direct line for the target. Adding a cost to the heuristic for distance above ground could encourage staying at or near the ground while not eliminating aerial motion.

 

 

I would recommend you let your world builders generate large connected patches rather than using the common (yet expensive) solution of a uniform grid. Reducing the number of elements to search helps dramatically, and adding a dimension adds a big cost to an expensive algorithm.