# Searching through huge arrays (without using a loop)

I want to make some sort of list or array of tens to hundreds of thousands of xyz int coords.
I then want to easily check if an xyz I have is in the xyz of occupied coords described above. Looping through something that large would take far to long as this is used in pathfinding and surely storing them like this will fill my memory.
Any help appreciated.

You could use a dictionary. System.Collections.Generic.Dictionary

These are indexed (or more accurately a hash table) and much faster for lookups. You could generate a key that combines the axis. eg, x1000000+y1000+z.

how much memory will a huge dictionary take up though>?

Iâve been getting a run out of memory error with my previous method is why I ask

I am assuming your design requires this amount of information to be stored for it to work. If you are looking for alternate methods to achieve what you want to achieve, with less memory overhead. Then you will need to provide more details on what you are doing.

Note: You can also create a custom comparer, if you want to store more complex objects in the dictionary:

If all youâre doing is storing a flag for occupied or not, and you need to keep the memory footprint down.

Each entry is just a bool flag.

Then flatten out your 3-space coordinate to an index in this. Youâll need to define a spacial size first. The area of which must be less than the max length a BitArray supports.

This can be the formula to calculate the flattened index of discrete 3-space coordinates with a constant width and depth (height can theoretically grow in thisâŚ but because BitArray requires defining its length on constructionâŚ itâll be constant as well).

index = (x + WIDTH * (y + DEPTH * z))

BitArray uses integers though for indexing, which gives you the limit of 2^31 in length (a cube of side length 1290). This is actually because the largest single object in .Net can only be 2 gigabytes in size. An array of bytes of length 2^28 (total bits being 2^31) is 2 gigabytes.

You could write your own âLargeBitArrayâ that spanned multiple arrays, and use âLongâ for indexing, to get a larger size. Which theoretically could be 1 exabyte in size.

I am using a 3d A* pathfinding, currently it creates a 3d world by creating a bool array of length width * height * depth and then accesses the points using the formula
index = (x + WIDTH * (y + DEPTH * z))

the a* algorithm uses the true false to establish weather it can travel through the point. Because however I am trying to do this on a 1km map it means it has to generate a world of 1000 x 1000 x 100(height) which is a billion. Thus obviously the memory for the array runs out and it all goes pear shaped. SO my idea is to just store points that are occupied rather than all of the 3d grid and simply assume a point is not occupied if there is no match from my list of occupied points.

Thus the question as to how I can check through a list or an array with potentially tens of thousands of entries for a match

actually because I am in a 1000 x 1000 x 100 grid (100 tall) which is a billion 3d points. I am actually only storing occupied slots and assuming all other points are not occupied. In order to do this I need a list that doesnât require
index = (x + WIDTH * (y + DEPTH * z))

In fact this question was quite specifically about how to access parts of a list that I cannot store in an ordered fashion. I am still a little confused as to weather I am going to be able to store such a large number of points because of the memory

Iâve actually been stuck for a week now trying to find an appropriate pathfinding solution. Gridâs are improper as my game involves multi-story rapid construction and constantly regenerating a grid is makes grids a weak choice. So I have been at quite a loss.

Here are a few places I have tried to find help

Why canât you store it in an ordered fashion?

If that wonât work. A HashTable wonât work either.

All a HashTable does (or a Dictionary) is it uses some formula (the hash) to calculate the index, so that it doesnât have to loop and compare.

What I suggested was effectively a hashtable where the hash is (x + WIDTH * (y + DEPTH * z)).

1000x1000x100 will easily fit in BitArray and only take up about 12 megabytes (which is 100 million points, not a billionâŚ). And have a rather efficient lookup based on coordinate. You set that bool value at that slot true IF occupied.

BasicallyâŚ youâre not storing occupied coordinates. You have an array of booleans for all possible coordinates, whose index represents a coordinate, and its value if itâs occupied.

Your class would look something like this:

``````using UnityEngine;
using System.Collections;

public class GridOccupationMap
{

#region Fields

private BitArray _bits;
private int _width;
private int _height;
private int _depth;

#endregion

#region CONSTRUCTOR

public GridOccupationMap(int w, int h, int d)
{
_width = w;
_height = h;
_depth = d;
_bits = new BitArray(_width * _height * _depth);
}

#endregion

#region Properties

public bool this[int x, int y, int z]
{
get
{
return this.GetCoordinateIsOccuppied(x, y, z);
}
set
{
this.SetCoorindateIsOccupied(x, y, z, value);
}
}

#endregion

#region Methods

public bool GetCoordinateIsOccuppied(int x, int y, int z)
{
return _bits.Get(x + _width * (y + _depth * z));
}

public void SetCoorindateIsOccupied(int x, int y, int z, bool bOccupied)
{
_bits.Set(x + _width * (y + _depth * z), bOccupied);
}

#endregion

}
``````

Youâd then use it like this:

``````var grid = new GridOccupationMap(1000, 100, 1000);

grid[52,83,99] = true;//someone currently occupies coord <52,83,99>

if(grid[99,99,99])
{
//if someone occupies <99,99,99> do something
}
``````

If you need more data stored in each coordinate. For instance like in Minecraft, each 3d coordinate stores what kind of cube is there. You use a byte array, if the byte value is 0 itâs not occupied, if itâs greater than 0, then the numeric value is associated with the kind of thing is occupying it.

1 = dirt
2 = water
3 = wood
4 = rock
5 = coal ore
âŚ etc

This of course would limit your overall length of the array, and overall size of the grid. Which then of course could be grown again by splitting across a couple arrays. Remembering that full byte array takes about 2 gigs memory.

1 Like

Currently my world looks like this

``````using UnityEngine;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Tests
{
/// <summary>
/// Author: Roy Triesscheijn (http://www.roy-t.nl)
/// Sample World class that only provides 'is free or not' information on a node
/// </summary>
public class World
{
private int sx;
private int sy;
private int sz;
private int offsetIdx;
private bool[] worldBlocked; //extremely simple world where each node can be free or blocked: true=blocked

//Note: we use Y as height and Z as depth here!
public int Left { get { return 0; } }
public int Right { get { return sx - 2; } }
public int Bottom { get { return 0; } }
public int Top { get { return sy - 2; } }
public int Front { get { return 0; } }
public int Back { get { return sz - 2; } }

/// <summary>
/// Creates a 2D world
/// </summary>
public World(int width, int height)
: this(width, height, 1)
{ }

/// <summary>
/// Creates a 3D world
/// </summary>
public World(int width, int height, int depth)
{
// add 2 to compensate for the solid border around the world
sx = width + 2;
sy = height + 2;
sz = depth + 2;
offsetIdx = (0 + 1) + ((0 + 1) + (0 + 1) * sy) * sx;
//offsetIdx = -250;
worldBlocked = new Boolean[sx * sy * sz];

for (int x = 0; x < sx; ++x)
for (int y = 0; y < sy; ++y)
{
MarkPositionEx(new Point3D(x, y, 0), true);
MarkPositionEx(new Point3D(x, y, sz - 1), true);
}

for (int y = 0; y < sy; ++y)
for (int z = 0; z < sz; ++z)
{
MarkPositionEx(new Point3D(0, y, z), true);
MarkPositionEx(new Point3D(sx - 1, y, z), true);
}

for (int z = 0; z < sz; ++z)
for (int x = 0; x < sx; ++x)
{
MarkPositionEx(new Point3D(x, 0, z), true);
MarkPositionEx(new Point3D(x, sy - 1, z), true);
}
}

/// <summary>
/// Mark positions in the world als blocked (true) or unblocked (false)
/// </summary>
/// <param name="value">use true if you wan't to block the value</param>
public void MarkPosition(Point3D position, bool value)
{
worldBlocked[offsetIdx + position.X + (position.Y + position.Z * sy) * sx] = value;
}

private void MarkPositionEx(Point3D position, bool value)
{
worldBlocked[position.X + (position.Y + position.Z * sy) * sx] = value;
}

/// <summary>
/// Checks if a position is free or marked (and legal)
/// </summary>
/// <returns>true if the position is free</returns>
public bool PositionIsFree(Point3D position)
{
return
!worldBlocked[offsetIdx + position.X + (position.Y + position.Z * sy) * sx];
}

public bool PositionIsGrounded(Point3D position){
//return GameObject.Find ("GridManager").GetComponent<SetupGrid> ().isGrounded (position.X, position.Y, position.Z);
return
worldBlocked[offsetIdx + position.X + (position.Y - 1 + position.Z * sy) * sx];
}
}
}
``````

and my pathfinder like this

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Tests
{
/// <summary>
/// Author: Roy Triesscheijn (http://www.roy-t.nl)
/// Class providing 3D pathfinding capabilities using A*.
/// Heaviliy optimized for speed therefore uses slightly more memory
/// On rare cases finds the 'almost optimal' path instead of the perfect path
/// this is because we immediately return when we find the exit instead of finishing
/// 'neighbour' loop.
/// </summary>
public static class PathFinder
{
/// <summary>
/// Method that switfly finds the best path from start to end.
/// </summary>
/// <returns>The starting breadcrumb traversable via .next to the end or null if there is no path</returns>
public static SearchNode FindPath(World world, Point3D start, Point3D end)
{
//note we just flip start and end here so you don't have to.
return FindPathReversed(world, end, start);
}

/// <summary>
/// Method that switfly finds the best path from start to end. Doesn't reverse outcome
/// </summary>
/// <returns>The end breadcrump where each .next is a step back)</returns>
private static SearchNode FindPathReversed(World world, Point3D start, Point3D end)
{
SearchNode startNode = new SearchNode(start, 0, 0, null);

MinHeap openList = new MinHeap();

int sx = world.Right;
int sy = world.Top;
int sz = world.Back;
bool[] brWorld = new bool[sx * sy * sz];
brWorld[start.X + (start.Y + start.Z * sy) * sx] = true;

while (openList.HasNext())
{
SearchNode current = openList.ExtractFirst();

if (current.position.GetDistanceSquared(end) <= 3)
{
return new SearchNode(end, current.pathCost + 1, current.cost + 1, current);
}

for (int i = 0; i < surrounding.Length; i++)
{
Surr surr = surrounding[i];
Point3D tmp = new Point3D(current.position, surr.Point);
int brWorldIdx = tmp.X + (tmp.Y + tmp.Z * sy) * sx;

if (world.PositionIsFree(tmp) && brWorld[brWorldIdx] == false && world.PositionIsGrounded(tmp))
{
brWorld[brWorldIdx] = true;
int pathCost = current.pathCost + surr.Cost;
int cost = pathCost + tmp.GetDistanceSquared(end);
SearchNode node = new SearchNode(tmp, cost, pathCost, current);
}
}
}
return null; //no path found
}

class Surr
{
public Surr(int x, int y, int z)
{
Point = new Point3D(x, y, z);
Cost = x * x + y * y + z * z;
}

public Point3D Point;
public int Cost;
}

//Neighbour options 3D, diagonals

private static Surr[] surrounding = new Surr[]{
//Top slice (Y=1)
new Surr(-1,1,1), new Surr(0,1,1), new Surr(1,1,1),
new Surr(-1,1,0), new Surr(0,1,0), new Surr(1,1,0),
new Surr(-1,1,-1), new Surr(0,1,-1), new Surr(1,1,-1),
//Middle slice (Y=0)
new Surr(-1,0,1), new Surr(0,0,1), new Surr(1,0,1),
new Surr(-1,0,0), new Surr(1,0,0), //(0,0,0) is self
new Surr(-1,0,-1), new Surr(0,0,-1), new Surr(1,0,-1),
//Bottom slice (Y=-1)
new Surr(-1,-1,1), new Surr(0,-1,1), new Surr(1,-1,1),
new Surr(-1,-1,0), new Surr(0,-1,0), new Surr(1,-1,0),
new Surr(-1,-1,-1), new Surr(0,-1,-1), new Surr(1,-1,-1)
};

/*
//Neighbour options 3D // 4 dirs
private static Surr[] surrounding = new Surr[]{
//Top slice (Y=1)
//new Surr(0,1,1),
//new Surr(-1,1,0),
new Surr(0,1,0),
//, new Surr(1,1,0),
//new Surr(0,1,-1),
//Middle slice (Y=0)
new Surr(0,0,1),
new Surr(-1,0,0), new Surr(1,0,0), //(0,0,0) is self
new Surr(0,0,-1),
//Bottom slice (Y=-1)
//new Surr(0,-1,1),
//new Surr(-1,-1,0),
new Surr(0,-1,0)
//, new Surr(1,-1,0),
//new Surr(0,-1,-1)
};*/

// 2D
/*
private static Surr[] surrounding = new Surr[]{
new Surr(0,-1,0),
new Surr(1,0,0),
new Surr(0,1,0),
new Surr(-1,0,0)
};*/

}
}
``````

OK.

This doesnât explain why you canât store what coordinates are occupied in an ordered fashion.

I just presumed there wouldnât be a way to store all the occupied and unoccupied points when I needed a 1km x 1km maps

trying to work out a way to bring in the class you just showed me with the ones I posted above

If you remain 100 meters high, you could get around 4600 meters by 4600 meters square with 1 meter intervals.

In my opinion, you have too many points that you are trying to handle discretely. I think that it would be more efficient to save the occupied areas as ranges. I expect in your world you will have areas that are blocked and areas not blocked. You could have a class like this that represents a cube area to track the areas that are blocked:

``````Class Occupied
{

public Occupied(Vector3 A, Vector3 B, Vector3 C)
{
this.PointA = A;
this.PointB = B;
this.PointC = C;
}
Vector3 PointA { get; set; }
Vector3 PointB {get; set; }
Vector3 PointC {get; set; }

public bool IsIn(Vector3 checkPoint)
{
....
}
}
``````

The IsIn method could be written to check if a point is within this occupied block.

In your code, when you create the solid border. This could now be stored in four instances of the Occupied object. eg: one border would by:
Occupied border1 = new Occupied( new Vector3(0, 0, 0), new Vector3(sx, 0, 0), new Vector3(sx, sy, 0));

You would need to come up with an efficient method to check if a point is occupied. that is, you donât want to iterate through the entire list of occupied sections. So you could break your world into 100x100 metre subsections and then store in these subsections the occupied ranges. This should be reasonably low on memory and still fast to determine if any block is occupied.

The map is not separated into 100 by 100 areas. That seems tricky because what if I want to find a path to another section. Can you be more specific? what is the issue with having one area.

I suppose I would need a way to find a path across multiple areas

I was considering only running the pathfinder for blocks that are less than 100m