Multidimensional array vs dictionary performance

[Ackior]

I am building a voxel based pathfinding system. One of the important parts is being able to mark blocks as being clear to walk on.

I made an array to hold the bool walkable using the x,y,z integer coordinates as a key:

bool[,,] worldWalkable = new bool[1000,1000,1000];

The thing is, there tends to be a lot of wasted space(non walkable blocks) and it uses a ton of memory as the map size goes up.

I thought a dictionary might be a better choice, so I made this:

Dictionary<Vector3Int, bool> worldTrav = new Dictionary<Vector3Int, bool>();

I only store true values to save memory. Everything else is assumed false.

Vector3Int is a struct that holds the x,y,z integers so I can use it as a key for the dictionary.

Like this:

using UnityEngine;
using System.Collections;

//makes a Vector3 of integers
public struct Vector3Int
{
	public int x,y,z;
	
	public Vector3Int(int x, int y, int z)
	{
		this.x =x;
		this.y=y;
		this.z=z;
	}
    	    
	//checks for equality
	public static bool operator ==(Vector3Int a, Vector3Int b)
	{
		return a.x==b.x && a.y ==b.y && a.z ==b.z;
	}

	public override bool Equals(object obj)
	{
		return obj is Vector3Int && this == (Vector3Int)obj;
	}

	public override int GetHashCode ()
	{
		return x.GetHashCode() ^ y.GetHashCode() ^ z.GetHashCode();
	}

	
	public static bool operator !=(Vector3Int a, Vector3Int b)
	{
		return !(a==b);
	}
}

The thing is, when I use the dictionary, it is slooooow. Even though my array has about a billion indexes and the dictionary has 7000, the dictionary access with Vector3Int as key is much slower. Like 30-100 times slower.

Is there a better way to contain the boolean information? I will be loading and unloading chunks, so a dictionary seems much more flexible. The lookup needs to be much faster than the dictionary seems to be.

Thanks.

Edit: Turns out that I needed to implement IEquatable.
Good link on how to do it is here.

After implementing, time to calculate dropped from 225+ms to 2-8ms. The speed increase appears to be from preventing boxing/unboxing while using the dictionary.

New code:

using UnityEngine;
using System.Collections;
using System;
using System.Collections.Generic;

//makes a Vector3 of integers
public struct Vector3Int : IEquatable<Vector3Int>
{
	public int x,y,z;
	
	public Vector3Int(int x, int y, int z)
	{
		this.x =x;
		this.y=y;
		this.z=z;
	}
	
	public static Vector3Int operator +(Vector3Int a, Vector3Int b)
	{
		Vector3Int temp = new Vector3Int();
		temp.x = a.x +b.x;
		temp.y = a.y +b.y;
		temp.z = a.z +b.z;
		return temp;
	}

	public bool Equals(Vector3Int other)
	{
		return other.x==this.x && other.y==this.y && other.z==this.z;
	}
	
	public static bool operator ==(Vector3Int a, Vector3Int b)
	{
		return a.Equals(b);
	}

	public override bool Equals(object obj)
	{
		if(obj==null || !(obj is Vector3Int))
			return false;

		return Equals((Vector3Int)obj);
	}

	public override int GetHashCode ()
	{
		return x ^ (y<<10) ^ (z<<10);
	}

	public override string ToString ()
	{
		return string.Format ("("+x+", "+y+", "+z+")");
	}
	
	public static bool operator !=(Vector3Int a, Vector3Int b)
	{
		return !(a==b);
	}
}

[JinJin]

When accessing the dictionary, you are searching for one object out of 7000

when accessing the array, there is no searching at all:

• from a 3 dimensional array you select one 2 dimensional array from 1000 arrays
• from the selected 2 dimensional array you select a 1 dimensional array from 1000 arrays
• you select one object from 1000 objects in the 1 dimensional array

getting an element from an array is very, VERY fast - much faster than getting a hashcode and accessing the dictionary

if your main problem is memory usage, I would suggest splitting your 3D array

make a tree with sub-trees, like when you make a “k-d tree”

public class SmallNode
{
   public bool[,,] walkable = new bool[10,10,10];
}

public class AverageNode
{
   public SmallNode[,,] small = new SmallNode[10,10,10];
}

public class LargeNode
{
   public AverageNode[,,] average = new AverageNode[10,10,10];
}

public class MyGame
{
   LargeNode large = new LargeNode();

   void Setup()
   {
      // initialize large - some of the elements in average[,,] can be "null", saving memory

      // initialize all elements in average - some of the elements in small[,,] can be "null", saving memory

      // initialize all elements in small - here you must assign all bool values
   }

   bool isWorldWalkable(int x, int y, int z)
   {
      // change x from [0,1000] to [0,10]
      int averagex = x / 100;
      int averagey = y / 100;
      int averagez = z / 100;

      AverageNode average = large.average[averagex,averagey,averagez];

      if(average != null)
      {
         // get the x interval between 0-100, 100-200, etc...
         int smallx = (x - averagex * 100) / 10;
         int smally = (y - averagey * 100) / 10;
         int smallz = (z - averagez * 100) / 10;

         SmallNode small = average.small[smallx,smally,smallz];

         if(small != null)
         {
            int walkablex = (x - averagex * 100 - smallx * 10);
            int walkabley = (y - averagey * 100 - smally * 10);
            int walkablez = (z - averagez * 100 - smallz * 10);

            return small.walkable[walkablex,walkabley,walkablez];
         }
      }

      return false;
   }
}

[mezzostatic]

I’d agree, an array of 1bn booleans is 1gb, 2.47bn is the upper limit for a single array, it’s instant lookup of memory address, whereas other methods are a loop through thousands of array entries to compare one of them.