Hi all. I want to briefly share my thoughts and hear your comments about pathfinding in 3d space in games. So, in the process of working on the path search in 3D coordinates, I came to the conclusion that some of these problems can be solved by the behavior of agents, or 2D path search. That is, the tasks of the behavior of agents under water or in space can be solved by simply avoiding obstacles when moving to the destination point.

For example, on YouTube, Sebastian Lague has an implementation of this behavior along with the boids model. Looks amazing.

Also, some of the tasks of 3D path search can be solved by 2D path search, for example, using multi-level 2D maps.

You can also set the height of agents on a 2d map, while the height itself can be adjusted by behavior and not by planning.

Let me explain by behavior, I understand the processing by an agent of a meeting with such an obstacle on an event, and planning is laying a route.

What examples or ideas of games can you give where you really need a path search in 3D space, that is, route planning? Let's discuss please.

Or maybe you have already encountered such a problem. It is very interesting.

I plan to do 3D pathfinding. In my case my world is built as a sparse voxel octree. Given my voxels have shared walls it's easy enough to add a couple back pointers, which gives me adjacency information. In fact I have it now as a debugging option I can turn on. After that it should be a matter of using A* or some variant of it.

Summary of my nav-data: built from 3D world grid as maps are already built on a grid (it's X-COM'ish), then merged into largest area bounding boxes (if two boxes can't merge, check if they could former a larger volume if merged were the remainder cut away), cells know if they're adjacent to “sky” in which case they can path to any other “sky” touching cell like an off-mesh connection in any other nav-mesh, and when stuff gets blown up the merge routines get called a bunch of times.

Primary jank is that if things have cell masking rules then those are different nav-meshes - so far there's only 1 of those, for cells big monsters can just bulldoze through unbothered, but it's probably going to become a problem as more things come along for “I can go through here, but I have to pop a nova first to level the place.”

Biggest headache for me has been convincing flight motion with regards to queueing at chokepoints. As my system is grid based to the design grid there's also the added bit that the aperture of actual passage is not assured to be the size of a cell, but could be a small window with varying traits (barred, glass, broken) that a CrocoBat can fit through but a straight up dragon can't do diddly.

I deal with queueing (flyers need to circle like vultures if they can't hover) by refitting a collection of curves to the nav cell placed at the top of it. Flyers will head up and circle in these stacks of curves until their turn. The nav-cells know if they're attached to open-sky, in which case this circling behaviour continues outside of the map area and in the “sky” area, which is outside the map-grid. They enter their curve by boids'n it up along a path through the center of the curves, causes them to swoop low, up, and out like a mushroom cloud. Right now I've just got a timing control on a flyer-type basis that controls how tight the queue delay is, so CrocoBats will basically swarm right on through as fast as they can while GatorSkyEels (eh … it flies … IDK … RIP my naming sense) putz for a bit as they are chonk. This gets reused for idle behaviour, so the fliers will go into circling mode.

Those curves do get moved around, as undulating flyers have different spacing requirements and there's some room for some noise vertically. The fitment to the cube is XZ (Y is Up) done as Laplacian deform with Eigen to fit the box. Curves were a nice solution here as I can … like look at them and roughly understand WTF is going to happen as well as use them for the entry and exit strategy of this state.

I would really like to ditch having the separate box network for flyers and work with grid itself, but I feel I would end up having it anyways just to have the information required to setup the circling layouts. There are non-grid maps, but those are like classic DOOM maps in that they're sectors with height and they get detailed with various lofts and tessellations - so there's just a merge of sectors whose ceilings levels are the same with limitations on height difference - also, flyers are strongly avoided on those maps outside of gimmick rooms that will lock you in with them and a battle situation just makes them boids.

For the boids'ing everybody reports their flight corridor accounting for their undulation ranges and how far a boids looks depth-wise into connected cells depends on the volume of the cell. Things are allowed to go crazy, if need be, but everbody is rocking that front-line repulse like leader-following (though I use a cone). Rules applied vary on the flyer, CrocoBats swarm and thus gather, GatorSkyEels are basically Rookie slaying machines and do their own thing that all lesser boids avoid which creates a nice scatter and you can actually see “ahhh, damn, here comes the big one.”

Dealing with erroneous situations has basically been a content problem. Right now I'm just using some key poses with some inertialization and a few other parameters for interpolating these shock response poses with some wiggle bone dynamics on wing joints. Unsure how tractable that will be moving forward into final art - jank may shape what's acceptable for the final look.

---

Flyers have definitely been easier than serpentine navigators, though I do admit to copping-out and pulling some MonsterHunter jank with flyers. Serpentine has me losing hair fast enough to consider scrapping it, but I'd sooner scrap complicated interiors than the gigantic snakes. There are swimmers … it's fake knee-high FX water (or oops … you're dead, lava) … those were easy.

Nowhere near done, still have to visit ambush behaviours both in regards to introductions of a flyer and as part of that navigation leaping from sky-touching-cell to sky-touching-cell.

@Gnollrunner Oh, without a doubt. A-star can work in any dimensions, it's just that it is often given in 2D. Although in fact the algorithm is about nodes. But I think you already know this. Where can I read about your svo project?

@Sprue It is very interesting. I will indeed be re-reading your post several times. It looks like you've done a great job.

@MaximSnd I have a blog on this website, but I haven't touched it in a LONG time. I've made a lot of mostly internal changes since then. For instance, it's in DirectX12 now. I also have JIT (Just In Time) collision, which builds the physics model around the player has moves. This is necessary since my planets can be large and are procedurally generated and refined at run time so there is no way to have a permanent physics mesh. Finally I included Dear IMGUI as a temporary GUI.

There are many other internal changes but since that stuff isn't really interesting to most people I haven't really been keeping up with the blog. Right now I'm working on procedural trees so I can make planets that look like something, rather than a barren landscape. After that I'll probably continue with the blog.

@gnollrunner It's always very interesting. Of course, write to your blog, it is very motivating for everyone else. Of particular interest is your experience with the sparse voxel octree implementation.

Shortcuts like collapsing the map to 2D or not searching globally that solve “some problems” cheaply aren't really good if you need general pathfinding anyway for some important difficult cases.

Do you plan to have large or complex obstacles that might cause bad pathfinding with local obstacle avoidance? For example, fish in the sea are unlikely to need global pathfinding if they only avoid other fish of similar size, but if they have to swim through ramified caves or around a mountain that's comparable in size to the whole game level they might act unreasonably or get stuck in a major cul-de-sac because they used a “stupid” local heuristic.

Managing choke points by queuing up or by preferring other routes is another complication that depends very strongly on level design: can you simply use only wide passages and moderate unit counts? How crowded can the choke points be in the worst case? Do you actually want crowds?