I'm not entirely sure if this is the right section for this, but here's my problem: I have a 3D voxel world, similar to minecraft, and I'm using A* to do pathfinding for the NPCs. Since the world is laid out in a grid of blocks, I use that same grid for the pathfinding nodes. When the AI follows the path, for units wider than a single grid unit, it gets stuck a lot of times.

The first issue it has is when it comes to a ledge that it needs to drop down from, as shown in my crappy drawing:
[attachment=22189:diagram.png]

The AI gets to the node above the ledge, but can't fall down to the next 3 nodes without moving forwards more.

The other issue is things like doorways, where its physically impossible for the unit to go through due to the size. It would need the pathfinder to path around and find another, larger, opening.

I've tried a bit to make the A* pathfinding work for larger units but the code quickly became a mess and each node check started to require checking a good 15 or so surrounding nodes. Is this the right way to go about it or is there a better solution? Keep in mind its a dynamic world, so precomputed solutions won't work.

There's generally no need to have each node look at its neighbors for every single path search. In other words, marking up your path graph to tell you what edges are "too close to geometry" for a given unit is something you can cache/precompute. You simply need to update that information when the voxel set changes.

Keep in mind that you can store more edges than are actually usable by a given unit. Some small units might be able to take advantage of edges that a larger unit can't. If you store that markup information alongside the edge data, and cache it as mentioned, you can modify the path search to simply compare the unit's "radius" with the markup of a given edge, and immediately know if that unit can traverse that particular edge or not.

If your maximum unit radius is N voxels:

- Initialize the "clearance" score of each voxel to 0 for blocked voxels, and 1 for everything else
- For each cell with a value >= 1, look at its neighbors. Take the lowest adjacent clearance score, add 1, update that cell
- Repeat this procedure (increasing your minimum threshold each time) until you hit N repetitions

This should propagate a score of how close a given voxel is to the nearest geometry. You can use that cached score to dynamically prune edges during path search, as mentioned.

There are some ways to ease this issues, one approach (influence map like) has been mentioned already by apochPiQ. You can althought try to work on different voxel resolutions (2x2x2 block is considered as single block for medium creatures, 4x4x4 for large etc.), you can work with predefined voxel representations and build a graph (a cone voxel).

But I would re-think my physics/movement/pathfinding approach in a modifiable voxel world. If you really intent to move large entities in a more or less realistic way through a voxel world, then you will encounter lot of issues (getting stuck most often) and modifing the world will result in breaking stuff really quickly. Eg it would be much easier, if every entity would be the size of one voxel, this will result in lot of clipping, but getting rid of clipping will be extremly hard. Separating the movement phyiscs representation from the visuals and optional hit-boxes, have lot of benefits (minecraft do it this way ?).

So if I'm following you correctly, I'd store an extra set of data for each voxel that is basically a measure of how far away it is from the nearest impassable voxel. I suppose if I only search horizontally when computing that number (since my units aren't always going to be cube shaped), the pathfinding can do a simpler vertical search based on the unit's height.

One thing I don't understand is this step: "For each cell with a value >= 1, look at its neighbors. Take the lowest adjacent clearance score, add 1, update that cell". In order for that to work, it seems like you'd have to process things by starting at the voxels marked 0 and moving outwards. In other words, if you had this: 0 1 1 1 1 1 0, moving from left to right, you'd end up with:

0 & 1 -> select 0, store 1 -> 0 1 1 1 1 1 0
1 & 1 -> select 1, store 2 -> 0 1 2 1 1 1 0

2 & 1 -> select 1, store 2 -> 0 1 2 2 1 1 0 <- should have been 3

2 & 1 -> select 1, store 2 -> 0 1 2 2 2 1 0

2 & 0 -> select 0, store 1 -> 0 1 2 2 2 1 0

The only way I can think of to fix that is to do N passes through the entire set of voxel data, which could take a significant amount of time.

Edit: Actually, having re-read your post, that's exactly what your suggesting. I guess I can give that a try, but it seems like it would take a while to compute that for the several million voxels that get loaded.

You only need to compute the entire world once. After that, all you have to recompute is the area within the bounding volume of a geometry change.

Well I gave it a try, and it ends up taking around 4 minutes to compute for the initially loaded area for N = 5. Not the best, but not terrible either. I'm not sure how I'm supposed to use the data though. For example, an area like this: 0 1 2 2 1 0 could fit up to a 2 radius unit, but the waypoint has to be placed between the 2 voxels. With an odd number of spaces, you get: 0 1 2 3 2 1 0 which can fit up to a 2.5 radius unit (not 3 as the number indicates) and the waypoint would be in the middle.

Four minutes? Are you simulating an entire solar system or something? :-P


I described how the data works earlier. You assign the edges between voxel nodes those numbers. If an edge has a number that is smaller than a unit's radius, the edge is not pathable for that unit. This is literally two lines of code in your A* implementation.


[edit] The more I think about it, the more I wonder if I really want to say "diameter" instead of "radius" at a few points in my earlier post. Shouldn't be too hard to figure out.

Well the regions are 32x128x32 voxels, and there's 400 regions loaded around the player. Each voxel needs to look at 8 neighboring voxels when computing its value. And it does that 5 times, plus the initial seeding of 1/0s. So that's about 2.1 billion checks it has to do. Also I ran it on background threads set to low priority so it wouldn't slow down the main loading threads, so that contributed to some of the slow down.

I guess I misunderstood you. I went and took a look at some pathfinding articles and I think I understand what your referring to with the edges now. I guess normally you'd build a graph with all the edges between the nodes and their weight values. Thing is, I don't have that in my implementation. I have a large, 3d array of voxel 'type ids' and the pathfinding searches through that to build a path. It calculates the weights and determines what is and isn't walkable on the fly. The voxel array alone takes up about 200MB for a single player. If I were to make a graph storing the radius values for the 4 connections of each node, that'd be another 200MB. It might be fine for 1 player, but if you have 10 players all spread out in different areas, now you're looking at something like 4GB of ram usage just for those 2 sets of data.

So I'm not sure it's a feasible solution given the storage requirements.

Do you have your voxels stored in an octree or similar structure? If a large chunk is solid, that would at least allow you to ignore a lot of voxels when calculating your distance metric. Plus if you have a reasonable maximum unit size, a large enough empty space could be generally marked as passable.

No it's just stored in an array. We tried using an octree before but ran into problems. I forget what the issue was. Earthmark made a post on here a while ago about it but we never did get it working right