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.

#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';
  }
}

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.

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

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.

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.

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.