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, x*1000000+y*1000+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

 

Check out this this article to calculate memory: http://www.dotnetperls.com/dictionary-memory

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:
http://www.dotnetperls.com/iequalitycomparer

 

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

How about a bitarray:
http://msdn.microsoft.com/en-us/library/system.collections.bitarray(v=vs.90).aspx

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
http://forum.unity3d.com/threads/voxel-pathfinding.276442/#post-1827115
http://unitycoder.com/blog/2013/04/09/a-pathfinder-2d-3d/

 

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:

Code (csharp):

1.  
2. using UnityEngine;
3. using System.Collections;
4.  
5. public class GridOccupationMap
6. {
7.  
8.     #region Fields
9.  
10.     private BitArray _bits;
11.     private int _width;
12.     private int _height;
13.     private int _depth;
14.  
15.     #endregion
16.  
17.     #region CONSTRUCTOR
18.  
19.     public GridOccupationMap(int w, int h, int d)
20.     {
21.         _width = w;
22.         _height = h;
23.         _depth = d;
24.         _bits = new BitArray(_width * _height * _depth);
25.     }
26.  
27.     #endregion
28.  
29.     #region Properties
30.  
31.     public bool this[int x, int y, int z]
32.     {
33.         get
34.         {
35.             return this.GetCoordinateIsOccuppied(x, y, z);
36.         }
37.         set
38.         {
39.             this.SetCoorindateIsOccupied(x, y, z, value);
40.         }
41.     }
42.  
43.     #endregion
44.  
45.     #region Methods
46.  
47.     public bool GetCoordinateIsOccuppied(int x, int y, int z)
48.     {
49.         return _bits.Get(x + _width * (y + _depth * z));
50.     }
51.  
52.     public void SetCoorindateIsOccupied(int x, int y, int z, bool bOccupied)
53.     {
54.         _bits.Set(x + _width * (y + _depth * z), bOccupied);
55.     }
56.  
57.     #endregion
58.  
59. }
60.  

You'd then use it like this:

Code (csharp):

1.  
2. var grid = new GridOccupationMap(1000, 100, 1000);
3.  
4. grid[52,83,99] = true;//someone currently occupies coord <52,83,99>
5.  
6. if(grid[99,99,99])
7. {
8.      //if someone occupies <99,99,99> do something
9. }
10.  

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.

 

Currently my world looks like this

Code (CSharp):

1. using UnityEngine;
2. using System;
3. using System.Collections.Generic;
4. using System.Linq;
5. using System.Text;
6.  
7. namespace Tests
8. {
9.     /// <summary>
10.     /// Author: Roy Triesscheijn (http://www.roy-t.nl)
11.     /// Sample World class that only provides 'is free or not' information on a node
12.     /// </summary>
13.     public class World
14.     {
15.         private int sx;
16.         private int sy;
17.         private int sz;
18.         private int offsetIdx;
19.         private bool[] worldBlocked; //extremely simple world where each node can be free or blocked: true=blocked      
20.  
21.         //Note: we use Y as height and Z as depth here!
22.         public int Left { get { return 0; } }
23.         public int Right { get { return sx - 2; } }
24.         public int Bottom { get { return 0; } }
25.         public int Top { get { return sy - 2; } }
26.         public int Front { get { return 0; } }
27.         public int Back { get { return sz - 2; } }
28.  
29.         /// <summary>
30.         /// Creates a 2D world
31.         /// </summary>      
32.         public World(int width, int height)
33.             : this(width, height, 1)
34.         { }
35.  
36.         /// <summary>
37.         /// Creates a 3D world
38.         /// </summary>      
39.         public World(int width, int height, int depth)
40.         {
41.             // add 2 to compensate for the solid border around the world
42.             sx = width + 2;
43.             sy = height + 2;
44.             sz = depth + 2;
45.             offsetIdx = (0 + 1) + ((0 + 1) + (0 + 1) * sy) * sx;
46.             //offsetIdx = -250;
47.             worldBlocked = new Boolean[sx * sy * sz];
48.  
49.             // add solid border
50.             for (int x = 0; x < sx; ++x)
51.                 for (int y = 0; y < sy; ++y)
52.                 {
53.                     MarkPositionEx(new Point3D(x, y, 0), true);
54.                     MarkPositionEx(new Point3D(x, y, sz - 1), true);
55.                 }
56.  
57.             for (int y = 0; y < sy; ++y)
58.                 for (int z = 0; z < sz; ++z)
59.                 {
60.                     MarkPositionEx(new Point3D(0, y, z), true);
61.                     MarkPositionEx(new Point3D(sx - 1, y, z), true);
62.                 }
63.  
64.             for (int z = 0; z < sz; ++z)
65.                 for (int x = 0; x < sx; ++x)
66.                 {
67.                     MarkPositionEx(new Point3D(x, 0, z), true);
68.                     MarkPositionEx(new Point3D(x, sy - 1, z), true);
69.                 }
70.         }
71.  
72.         /// <summary>
73.         /// Mark positions in the world als blocked (true) or unblocked (false)
74.         /// </summary>
75.         /// <param name="value">use true if you wan't to block the value</param>
76.         public void MarkPosition(Point3D position, bool value)
77.         {
78.             worldBlocked[offsetIdx + position.X + (position.Y + position.Z * sy) * sx] = value;
79.         }
80.  
81.         private void MarkPositionEx(Point3D position, bool value)
82.         {
83.             worldBlocked[position.X + (position.Y + position.Z * sy) * sx] = value;
84.         }
85.  
86.         /// <summary>
87.         /// Checks if a position is free or marked (and legal)
88.         /// </summary>      
89.         /// <returns>true if the position is free</returns>
90.         public bool PositionIsFree(Point3D position)
91.         {
92.             return
93.                 !worldBlocked[offsetIdx + position.X + (position.Y + position.Z * sy) * sx];
94.         }
95.  
96.         public bool PositionIsGrounded(Point3D position){
97.             //return GameObject.Find ("GridManager").GetComponent<SetupGrid> ().isGrounded (position.X, position.Y, position.Z);
98.             return
99.                 worldBlocked[offsetIdx + position.X + (position.Y - 1 + position.Z * sy) * sx];
100.         }
101.     }
102. }
103.  

and my pathfinder like this

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using System.Text;
5.  
6. namespace Tests
7. {  
8.     /// <summary>
9.     /// Author: Roy Triesscheijn (http://www.roy-t.nl)
10.     /// Class providing 3D pathfinding capabilities using A*.
11.     /// Heaviliy optimized for speed therefore uses slightly more memory
12.     /// On rare cases finds the 'almost optimal' path instead of the perfect path
13.     /// this is because we immediately return when we find the exit instead of finishing
14.     /// 'neighbour' loop.
15.     /// </summary>
16.     public static class PathFinder
17.     {                  
18.         /// <summary>
19.         /// Method that switfly finds the best path from start to end.
20.         /// </summary>
21.         /// <returns>The starting breadcrumb traversable via .next to the end or null if there is no path</returns>      
22.         public static SearchNode FindPath(World world, Point3D start, Point3D end)
23.         {
24.             //note we just flip start and end here so you don't have to.          
25.             return FindPathReversed(world, end, start);
26.         }      
27.  
28.         /// <summary>
29.         /// Method that switfly finds the best path from start to end. Doesn't reverse outcome
30.         /// </summary>
31.         /// <returns>The end breadcrump where each .next is a step back)</returns>
32.         private static SearchNode FindPathReversed(World world, Point3D start, Point3D end)
33.         {
34.             SearchNode startNode = new SearchNode(start, 0, 0, null);
35.  
36.             MinHeap openList = new MinHeap();          
37.             openList.Add(startNode);
38.  
39.             int sx = world.Right;
40.             int sy = world.Top;
41.             int sz = world.Back;
42.             bool[] brWorld = new bool[sx * sy * sz];
43.             brWorld[start.X + (start.Y + start.Z * sy) * sx] = true;
44.  
45.             while (openList.HasNext())
46.             {              
47.                 SearchNode current = openList.ExtractFirst();
48.  
49.                 if (current.position.GetDistanceSquared(end) <= 3)
50.                 {
51.                     return new SearchNode(end, current.pathCost + 1, current.cost + 1, current);
52.                 }
53.  
54.                 for (int i = 0; i < surrounding.Length; i++)
55.                 {
56.                     Surr surr = surrounding[i];
57.                     Point3D tmp = new Point3D(current.position, surr.Point);
58.                     int brWorldIdx = tmp.X + (tmp.Y + tmp.Z * sy) * sx;
59.  
60.                     if (world.PositionIsFree(tmp) && brWorld[brWorldIdx] == false && world.PositionIsGrounded(tmp))
61.                     {
62.                         brWorld[brWorldIdx] = true;
63.                         int pathCost = current.pathCost + surr.Cost;
64.                         int cost = pathCost + tmp.GetDistanceSquared(end);
65.                         SearchNode node = new SearchNode(tmp, cost, pathCost, current);
66.                         openList.Add(node);
67.                     }
68.                 }
69.             }
70.             return null; //no path found
71.         }
72.  
73.         class Surr
74.         {
75.             public Surr(int x, int y, int z)
76.             {
77.                 Point = new Point3D(x, y, z);
78.                 Cost = x * x + y * y + z * z;
79.             }
80.  
81.             public Point3D Point;
82.             public int Cost;
83.         }
84.  
85.         //Neighbour options 3D, diagonals
86.  
87.         private static Surr[] surrounding = new Surr[]{                      
88.             //Top slice (Y=1)
89.             new Surr(-1,1,1), new Surr(0,1,1), new Surr(1,1,1),
90.             new Surr(-1,1,0), new Surr(0,1,0), new Surr(1,1,0),
91.             new Surr(-1,1,-1), new Surr(0,1,-1), new Surr(1,1,-1),
92.             //Middle slice (Y=0)
93.             new Surr(-1,0,1), new Surr(0,0,1), new Surr(1,0,1),
94.             new Surr(-1,0,0), new Surr(1,0,0), //(0,0,0) is self
95.             new Surr(-1,0,-1), new Surr(0,0,-1), new Surr(1,0,-1),
96.             //Bottom slice (Y=-1)
97.             new Surr(-1,-1,1), new Surr(0,-1,1), new Surr(1,-1,1),
98.             new Surr(-1,-1,0), new Surr(0,-1,0), new Surr(1,-1,0),
99.             new Surr(-1,-1,-1), new Surr(0,-1,-1), new Surr(1,-1,-1)          
100.         };
101.        
102.         /*
103.         //Neighbour options 3D // 4 dirs
104.         private static Surr[] surrounding = new Surr[]{                      
105.             //Top slice (Y=1)
106.                                      //new Surr(0,1,1),
107.             //new Surr(-1,1,0),
108.             new Surr(0,1,0),
109.             //, new Surr(1,1,0),
110.                                    //new Surr(0,1,-1),
111.             //Middle slice (Y=0)
112.                         new Surr(0,0,1),
113.             new Surr(-1,0,0), new Surr(1,0,0), //(0,0,0) is self
114.                         new Surr(0,0,-1),
115.             //Bottom slice (Y=-1)
116.                                        //new Surr(0,-1,1),
117.             //new Surr(-1,-1,0),
118.             new Surr(0,-1,0)
119.             //, new Surr(1,-1,0),
120.                                        //new Surr(0,-1,-1)
121.         };*/
122.        
123.         // 2D
124.         /*
125.         private static Surr[] surrounding = new Surr[]{
126.             new Surr(0,-1,0),
127.             new Surr(1,0,0),
128.             new Surr(0,1,0),
129.             new Surr(-1,0,0)
130.         };*/
131.        
132.        
133.     }          
134. }
135.  

 

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:

Code (CSharp):

1. Class Occupied
2. {
3.  
4.   public Occupied(Vector3 A, Vector3 B, Vector3 C)
5. {
6. this.PointA = A;
7. this.PointB = B;
8. this.PointC = C;
9. }
10.      Vector3 PointA { get; set; }
11.      Vector3 PointB {get; set; }
12.      Vector3 PointC {get; set; }
13.  
14.     public bool IsIn(Vector3 checkPoint)
15.     {
16.         ....
17.     }
18. }

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

 

For such a large area to be pathfind'ed, you should probably not be using A* in a grid, maybe navmeshes, or grouping blobs of space into nodes, then solving with something like dijkstra

 

As I say I plan to only pathfind within 100m of the grid and translate anything longer distance into steps of 100

 

So I had a go at setting up a bit array here is my class

Code (CSharp):

1.  
2. using UnityEngine;
3. using System;
4. using System.Collections;
5. using System.Collections.Generic;
6. using System.Linq;
7. using System.Text;
8.  
9. namespace Tests
10. {
11.     /// <summary>
12.     /// Author: Roy Triesscheijn (http://www.roy-t.nl)
13.     /// Sample World class that only provides 'is free or not' information on a node
14.     /// </summary>
15.     public class World
16.     {
17.         private BitArray _bits;
18.         private int _width;
19.         private int _height;
20.         private int _depth;
21.  
22.         //Note: we use Y as height and Z as depth here!
23.         public int Left { get { return 0; } }
24.         public int Right { get { return _width; } }
25.         public int Bottom { get { return 0; } }
26.         public int Top { get { return _height; } }
27.         public int Front { get { return 0; } }
28.         public int Back { get { return _depth; } }
29.  
30.         /// <summary>
31.         /// Creates a 3D world
32.         /// </summary>    
33.  
34.         public World(int w, int h, int d)
35.         {
36.             _width = w;
37.             _height = h;
38.             _depth = d;
39.             _bits = new BitArray(_width * _height * _depth);
40.         }
41.  
42.         public bool this[int x, int y, int z]
43.         {
44.             get
45.             {
46.                 return this.GetCoordinateIsOccuppied(x, y, z);
47.             }
48.             set
49.             {
50.                 this.MarkPosition(x, y, z, value);
51.             }
52.         }
53.  
54.         #region Methods
55.        
56.         public bool GetCoordinateIsOccuppied(int x, int y, int z)
57.         {
58.             return _bits.Get(x + _width * (y + _depth * z));
59.         }
60.        
61.         public bool GetCoordinateIsOccuppied(Point3D point)
62.         {
63.             return _bits.Get(point.X + _width * (point.Y + _depth * point.Z));
64.         }
65.        
66.         public bool PosFree(Point3D point)
67.         {
68.             return _bits.Get(point.X + _width * (point.Y + _depth * point.Z));
69.         }
70.        
71.         public void MarkPosition(int x, int y, int z, bool bOccupied)
72.         {
73.             _bits.Set(x + _width * (y + _depth * z), bOccupied);
74.         }
75.        
76.         public void MarkPosition(Point3D point, bool bOccupied)
77.         {
78.             _bits.Set(point.X + _width * (point.Y + _depth * point.Z), bOccupied);
79.         }
80.        
81.         #endregion
82.        
83.         public void IsGrounded(int x, int y, int z)
84.         {
85.             return _bits.Get(x + _width * (y - 1 + _depth * z));
86.         }
87.        
88.         public void IsOpenabove(int x, int y, int z)
89.         {
90.             return _bits.Get(x + _width * (y + 1 + _depth * z));
91.         }
92.        
93.         public void IsGrounded(Point3D point)
94.         {
95.             return _bits.Get(point.X + _width * (point.Y - 1 + _depth * point.Z));
96.         }
97.        
98.         public void IsOpenabove(Point3D point)
99.         {
100.             return _bits.Get(point.X + _width * (point.Y + 1 + _depth * point.Z));
101.         }
102.     }
103. }
104.  

however i get the following errors
`Tests.World.IsGrounded(int, int, int)': A return keyword must not be followed by any expression when method returns void

help would be appreciated thanks for all of done so far

 

Any function that returns a value cannot be void, should be the same type as that which is returned (bool in this case [all 4 will give the error])

 

But the functions don't return void how would I fix ot

 

oh gosh my bad I see it now the return type

 

Hey I am having slight trouble with the simple formula for the index
index = (x + WIDTH * (y + DEPTH * z))

when I have the map _depth _width _height
all the same value it works perfectly! and my pathfinder is kicking ass!
however when I make the _height less than _depth & _width I have an issue

The array returns out of index when I am at an x pos and z pos greater than the height value.

So when I am in x less than 100 y less than 100 and z less than 100 everything is fine

when I am in y less than 100 and x OR z greater than 100 it still works but if x AND z are greater than 100 it breaks.