• Create Account

# Pathfinding for large units

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

19 replies to this topic

### #1Telanor  Members   -  Reputation: 1486

Like
4Likes
Like

Posted 17 June 2014 - 07:52 PM

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:

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.

### #2ApochPiQ  Moderators   -  Reputation: 21205

Like
3Likes
Like

Posted 17 June 2014 - 10:47 PM

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.

- 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.
Wielder of the Sacred Wands

### #3Ashaman73  Crossbones+   -  Reputation: 13587

Like
3Likes
Like

Posted 17 June 2014 - 11:06 PM

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 ?).

Ashaman

### #4Telanor  Members   -  Reputation: 1486

Like
4Likes
Like

Posted 18 June 2014 - 07:10 PM

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.

Edited by Telanor, 18 June 2014 - 07:16 PM.

### #5ApochPiQ  Moderators   -  Reputation: 21205

Like
5Likes
Like

Posted 18 June 2014 - 10:10 PM

POPULAR

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.
Wielder of the Sacred Wands

### #6Telanor  Members   -  Reputation: 1486

Like
0Likes
Like

Posted 21 June 2014 - 07:29 PM

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.

### #7ApochPiQ  Moderators   -  Reputation: 21205

Like
1Likes
Like

Posted 21 June 2014 - 11:26 PM

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.

 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.

Edited by ApochPiQ, 21 June 2014 - 11:28 PM.

Wielder of the Sacred Wands

### #8Telanor  Members   -  Reputation: 1486

Like
0Likes
Like

Posted 22 June 2014 - 10:58 AM

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.

### #9jefferytitan  Crossbones+   -  Reputation: 2508

Like
0Likes
Like

Posted 22 June 2014 - 06:28 PM

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.

### #10Telanor  Members   -  Reputation: 1486

Like
0Likes
Like

Posted 22 June 2014 - 07:10 PM

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

Edited by Telanor, 22 June 2014 - 07:10 PM.

### #11ApochPiQ  Moderators   -  Reputation: 21205

Like
1Likes
Like

Posted 22 June 2014 - 07:25 PM

Why do you think you need an actual graph data structure?

When you do your path search, you consider a cube-cube connection as passable if (besides your other checks) its distance score is at least the diameter of the unit you're searching for. Whether you model the edges in data or not is totally irrelevant.

By the way: 2.1 billion compare/update operations comes out to something in the handful-of-seconds range on a modern CPU. If you use SIMD (why aren't you using SIMD?) you can quarter that, or better if you're willing to target only more recent hardware.

Throw in the optimizations of ignoring known large empty volumes, and you should be able to easily build this thing at map load time and maintain it in realtime as the geometry changes.

Edited by ApochPiQ, 22 June 2014 - 07:30 PM.

Wielder of the Sacred Wands

### #12jefferytitan  Crossbones+   -  Reputation: 2508

Like
0Likes
Like

Posted 22 June 2014 - 07:29 PM

Hmm, that's a shame. I believe you had trouble rendering voxel octrees. You could create an octree purely for collisions and pathing, although it's a little bit of a waste using it only for that.

### #13Álvaro  Crossbones+   -  Reputation: 19900

Like
1Likes
Like

Posted 22 June 2014 - 08:26 PM

I wrote some code that computes the size of the largest square that fits, in a 2D situation (because I am not entirely sure how your 3D world works). What I compute exactly is, for each cell, the size of the largest square that has its lower-right corner at this spot and doesn't include any walls. I think that's what I would use if I wanted to do pathfinding with large units.

The code takes only about 12 milliseconds to run on my laptop for a 2048x2048 grid. I only show a small fraction of the map, but the computation is for the whole grid.

#include <iostream>
#include <cstdlib>
#include <algorithm>

int const height = 2048;
int const width = 2048;

int map[height][width];

int main() {
for (int i=0; i<height; ++i) {
for (int j=0; j<width; ++j)
map[i][j] = (std::rand() % 100) < 80;
}

for (int i=0; i<20; ++i) {
for (int j=0; j<20; ++j)
std::cout << (int) map[i][j] << ' ';
std::cout << '\n';
}

std::cout << "***************\n";

for (int i=1; i<height; ++i) {
for (int j=1; j<width; ++j) {
if (map[i][j] > 0)
map[i][j] = std::min(std::min(map[i-1][j-1], map[i-1][j]), map[i][j-1]) + 1;
}
}

for (int i=0; i<20; ++i) {
for (int j=0; j<20; ++j)
std::cout << (int) map[i][j] << ' ';
std::cout << '\n';
}
}

I am sure you can adapt that code for your 3D case, and it should be very very fast.

### #14Telanor  Members   -  Reputation: 1486

Like
0Likes
Like

Posted 22 June 2014 - 08:54 PM

Why do you think you need an actual graph data structure?

When you do your path search, you consider a cube-cube connection as passable if (besides your other checks) its distance score is at least the diameter of the unit you're searching for. Whether you model the edges in data or not is totally irrelevant.

I'm not sure if you're suggesting I compute it as needed and save the results, or if it should still be precomputed. If it is precomputed, its quite a bit of data to store.

By the way: 2.1 billion compare/update operations comes out to something in the handful-of-seconds range on a modern CPU. If you use SIMD (why aren't you using SIMD?) you can quarter that, or better if you're willing to target only more recent hardware.

Throw in the optimizations of ignoring known large empty volumes, and you should be able to easily build this thing at map load time and maintain it in realtime as the geometry changes.

I'm not using SIMD because C# doesn't (yet) support it . I'm not sure how I'd know where large empty volumes are without an octree. You can take a look at my code if you like, maybe I'm doing something terribly inefficiently.

private static void BuildPathingData(object o)
{
var region = (Region) o;
var sw = System.Diagnostics.Stopwatch.StartNew();

return;

for(var i = 0; i < Region.SizeX * Region.SizeY * Region.SizeZ; i++)
{
var type = region[i];

if(BlockInformation.IsWalkable(type))
region.PathingInfo[i] = 1;
else
region.PathingInfo[i] = 0;
}

for(var i = 0; i < MaxUnitSize; i++)
{
for(var index = 0; index < Region.SizeX * Region.SizeY * Region.SizeZ; index++)
{
var value = region.PathingInfo[index];

if(value > 0 && value < MaxUnitSize)
{
byte smallest = MaxUnitSize;
var index3D = new RegionIndex(index);
var pos = region.GetVectorPosition(index3D);

foreach(var direction in directions)
{
var neighborPos = pos + direction;
var r = new RegionPosition(neighborPos, region.World);
var pathValue = r.SelectedRegion.PathingInfo[r.Index];

if(pathValue < smallest)
smallest = pathValue;
}

region.PathingInfo[index] = (byte) Math.Min(smallest + 1, MaxUnitSize);
}
}
}

sw.Stop();
Core.Log("Path building took {0}", sw.Elapsed.TotalMilliseconds);
}

RegionIndex and RegionPosition are both structs, so neither of those 'new's are actually allocating anything.

### #15Telanor  Members   -  Reputation: 1486

Like
0Likes
Like

Posted 22 June 2014 - 09:12 PM

Hmm, that's a shame. I believe you had trouble rendering voxel octrees. You could create an octree purely for collisions and pathing, although it's a little bit of a waste using it only for that.

Yea, something like that. Its something I'll have to look into again at some point.

I wrote some code that computes the size of the largest square that fits, in a 2D situation (because I am not entirely sure how your 3D world works). What I compute exactly is, for each cell, the size of the largest square that has its lower-right corner at this spot and doesn't include any walls. I think that's what I would use if I wanted to do pathfinding with large units.

The code takes only about 12 milliseconds to run on my laptop for a 2048x2048 grid. I only show a small fraction of the map, but the computation is for the whole grid.

Interesting. But when building a path from that, wouldn't the path for large units end up being placed along the right most wall, rather than through the middle? The large NPCs wouldn't be able to reach the waypoints if they're all up against the wall like that. Also since my map is essentially infinite, the top and left edges will all be 0/1 for each subdivision (regions as I call them) which would prevent large units from moving along region boundaries. Actually now that I think about it, my implementation of Apoch's suggestion probably has that same issue... I'm not sure how to deal with that.

### #16Álvaro  Crossbones+   -  Reputation: 19900

Like
0Likes
Like

Posted 22 June 2014 - 09:32 PM

I wrote some code that computes the size of the largest square that fits, in a 2D situation (because I am not entirely sure how your 3D world works). What I compute exactly is, for each cell, the size of the largest square that has its lower-right corner at this spot and doesn't include any walls. I think that's what I would use if I wanted to do pathfinding with large units.

The code takes only about 12 milliseconds to run on my laptop for a 2048x2048 grid. I only show a small fraction of the map, but the computation is for the whole grid.

Interesting. But when building a path from that, wouldn't the path for large units end up being placed along the right most wall, rather than through the middle? The large NPCs wouldn't be able to reach the waypoints if they're all up against the wall like that.

No, it just means that in order to determine whether a unit fits at a particular location or not, you need to query the map at the lower-right corner. This has nothing to do with the path; it's just a low-level detail of the implementation, which should not have any high-level observable consequences.

Also since my map is essentially infinite, the top and left edges will all be 0/1 for each subdivision (regions as I call them) which would prevent large units from moving along region boundaries. Actually now that I think about it, my implementation of Apoch's suggestion probably has that same issue... I'm not sure how to deal with that.

I am not sure what you mean by "essentially infinite", but I suggest you avoid complicating things beyond what you can handle. It looks like you have a hard enough time making this work on reasonably-sized finite maps, so I wouldn't try to go beyond that.

### #17ApochPiQ  Moderators   -  Reputation: 21205

Like
0Likes
Like

Posted 22 June 2014 - 10:01 PM

It's hard to say for sure without disassembling the IR for your code, but my two guesses for your worst performance hits would be (A) doing a lot of redundant work when calculating indices into your voxel arrays; and (B) that inner foreach doing something weird, which I can't see for sure without knowing what the definition of the "directions" variable looks like.

Also, note that casting a byte to a double to call Math.Min() and re-cast to a byte is a really painful operation. Just write out the code longhand for the min check, it'll probably be faster.
Wielder of the Sacred Wands

### #18Telanor  Members   -  Reputation: 1486

Like
0Likes
Like

Posted 22 June 2014 - 11:15 PM

It's hard to say for sure without disassembling the IR for your code, but my two guesses for your worst performance hits would be (A) doing a lot of redundant work when calculating indices into your voxel arrays; and (B) that inner foreach doing something weird, which I can't see for sure without knowing what the definition of the "directions" variable looks like.

Also, note that casting a byte to a double to call Math.Min() and re-cast to a byte is a really painful operation. Just write out the code longhand for the min check, it'll probably be faster.

The directions variable is just a small array of 8 Vector3 offsets. The casting is actually going to happen no matter what because C# doesn't support addition of bytes. It always casts them up to an int32. I'll try replacing the Math.Min call with an if statement though and maybe see if I can do something about the index calculations.

### #19Telanor  Members   -  Reputation: 1486

Like
0Likes
Like

Posted 25 June 2014 - 03:29 PM

So I fiddled around with the code a bit, made some of the supporting code a bit more efficient. The time is down to about 15s now. Not exactly sure what I changed that made such a big difference, since I got nothing useful out of the profiler and I had to change a lot of things all at once.

In any case, the storage requirements are still an issue if I need to store multiple edge values for each block. Using a dictionary to store only non-zero values doesn't help in the least bit since there end up being around 90k entries and apparently each entry costs around 20 bytes.

I suppose the next thing I could try is to compute it on the fly and store only a small subset.

### #20ApochPiQ  Moderators   -  Reputation: 21205

Like
0Likes
Like

Posted 25 June 2014 - 06:42 PM

You shouldn't need more than 1 byte per voxel, assuming your units are no bigger than 255 voxels across. :-)
Wielder of the Sacred Wands

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS