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
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
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
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?
I agree. It is without any doubt possible, but the question should really be "does it make sense, is it the best thing?".Personally I think you shouldn't use the octree as a pathing graph and instead should create a more appropriate graph.
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.
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
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.
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
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.