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.

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.

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.

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();

	if(region.RegionState != Region.States.Loaded)
		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.

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.

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.

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.

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.

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.

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