12,761,826 members (41,588 online)
alternative version

#### Stats

15K views
25 bookmarked
Posted 23 Oct 2012

, 31 Oct 2012 CPOL
 Rate this:
Tree representation for a 2D space allowing for infinite expansion

## Introduction

If you've ever had the desire for an infinite 2D array, but realize that the implementation of such is impossible with a fixed 2D array, this is the solution solution. The implementation here is done in C# using generics (or templates).

What is meant by Quadrant Map is that you are able to represent the full 4 Quadrants of the typical euclidean coordinate system, instead of being restricted to just positive integers. This means that you can have negative x and y indices as you might expect with a full Field of data.

The method by which this is implemented also allows for sparse input and data retrieval. If no data value has been set, its value is the default of T.

## Purpose

A Quadrant Map allows for a 2D infinite array in all directions without costly re-sizing or poor scaling that is described below.

## Other Methods

There are many methods by which you could implement an infinite 2D array. This section describes some of my previous attempts and failures.

This section will also be referring to a `Chunk`, which is a class that holds a 2D array with an offset.

```class Chunk<T>
{
public static int Size = 16;
public int OffsetX, OffsetY;
public T[,] Data = new T[Size, Size];

public Chunk(int x, int y)
{
OffsetX = x;
OffsetY = y;
}

public T this[int x, int y]
{
get
{
x %= Size;
y %= Size;
return Data[x, y];
}
set
{
x %= Size;
y %= Size;
Data[x, y] = value;
}
}
}  ```

### List

A potential solution, that is easier to implement, is creating a `List<Chunk>`. Whenever you search for a specific location in the 2D space, you must instead search the list, for the Chunk offset, and then index into that Chunk's array.

This is a valid solution so long as your List stays relatively small. The longer the list, the slower the search.

Example of how to search the list:

```class ListMap<T>
{
List<Chunk<T>> Chunks = new List<Chunk<T>>();

public T this[int x, int y]
{
get
{
//find chunk offset
int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
Chunk<T> found = FindChunk(xm, ym);

//if chunk doesn't exist, return default value for T
if (found == null) return default(T);

//otherwise return T
return found[x, y];
}
set
{
int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
Chunk<T> found = FindChunk(xm, ym);

//if chunk doesn't exist, make it
if (found == null)
{
found = new Chunk<T>(xm, ym);
}

//otherwise return T
found[x, y] = value;
}
}

public Chunk<T> FindChunk(int x, int y)
{
return Chunks.Find(
delegate(Chunk<T> query)
{
return query.OffsetX == x && query.OffsetY == y;
}
);
}
} ```

### Dictionary

The second approach might be using a `Dictionary<string, Chunk>`, where the key is a unique string based on its offset. This works much better, but it is still a hash table, and there is the difficulty of making and constantly constructing the hash each time you want to retrieve a Chunk.

This is a valid solution that can handle much larger sizes, more efficiently than the list, but you need a good quick unique hash method, If you ever have a collision, this system will fail. When you fail this way you will either overwrite or read existing data, when you expect new data to be created.

```class DictionaryMap<T>
{
Dictionary<string, Chunk<T>> Chunks = new Dictionary<string, Chunk<T>>();

public T this[int x, int y]
{
get
{
//find chunk offset
int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
string key = xm + ":" + ym;

//if chunk doesn't exist, return default value for T
if (!Chunks.ContainsKey(key)) return default(T);

//otherwise return T
return Chunks[key][x, y];
}
set
{
int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
string key = xm + ":" + ym;

//if chunk doesn't exist, make it
if (!Chunks.ContainsKey(key))
{
}

//otherwise return T
Chunks[key][x, y] = value;
}
}
} ```

## Overview

So, how to solve this problem? Well no doubt this is done before, but the this solution uses a system similar to a binary search tree.

### Binary Search Trees

If you know how binary search trees work, skip past this section. Although I will be describing a special kind of Binary Search Tree (BST).

To understand how a quad tree works in 2D space we must first analyze a BST. A BST has a Root Node, with two pointers, Left and Right. The Left and Right pointers both may point to null or another Node. This is similar to a List, however, we can store many Nodes, with a shorter path (or equal) from the Root to any other node (this is true if the tree is balanced).

Example

```        ()
/    \
()      ()
/       /    \
()      ()      ()
```

An important feature of BSTs is that Nodes are placed in the tree based on their data. This means the data is inserted based on some function that allows you to find it faster in the future. A default BST has data at each node, and places all data on the Left that compares to be left from the data at the current Node, and all data on the Right that compares to be right from the data. This comparison is done recursively so that you may, for example, place a Node down the path Left, Left, Right, Left, Right.

Example with data

```       (5)
/   \
(3)    (8)
/      /   \
(1)   (6)    (9)
```

However, I want to discuss a different kind of BST. Instead of each node containing data. Instead data can only be contained at the lowest level of the BST. Each node contains information as to what ranges of data are contained below it. Now all the data is lined up at the bottom. However there is difficulty with this. We need to have a 3rd pointer, that is only used when the Node is a leaf node. This pointer points to the data.

```        (0-7)
/     \
(0-3)    (4-7)
/    \        \
(0-1) (2-3)      (6-7)
/     /          /   \
(0)   (2)        (6)  (7)
```

Also we have the problem that we no longer can just wantonly insert data. Instead if we need to insert data that is beyond the range of the Root Node, we have to make a new Root Node, doubling the range, and placing the previous Root under the new Root. You may also note there is more Nodes created than in the previous example, and I'm only storing 4 bits of data.

Lets take a look at the example of what this tree would look like after inserting the value 8 (which exceeds the Root's range of [0-7]).

```                  (0-15)
/          \
(0-7)              (8-15)
/     \             /
(0-3)    (4-7)        (8-11)
/    \       \         /
(0-1) (2-3)    (6-7)    (8-9)
/     /        /   \    /
(0)   (2)       (6) (7)  (8)
```

Notice, that we create a new Root Node, with double the range of the previous Root. Then as we decent to the location where 8 will be placed, we create nodes along the way, each time reducing the range by half.

Also note, that as you decent the Tree, the range is halved at each step, until you reach a Leaf node, at which point it can point to 0, 1 or 2 points of data. Also the Node representing (4-5) doesn't exist. We didn't need to create it because there is no data down that path.

Now everyone who knows BSTs well, is going to be yelling at me, but that is okay. This is a feature that is required for moving on to my solution the Quadrant Map

We are going to use this modified BST to store our Quadrant Map (QM) except that each Node has 4 pointers down, to represent the 4 main quadrants.

Example with 1 Root node, and 4 locations stored (-1,-1), (0,-1), (-1,0) and (0,0). "<>" indicates a value and "[]" indicates a Node:

```<(-1,-1)>              <( 0,-1)>
\                      /
[(-1,-1) to ( 0, 0)]
/                      \
<(-1, 0)>              <( 0, 0)>  ```

It gets more complicated the deeper you go, but as you want to store a value at (1,1) you need to push down and double the range of the Root node, so it would represent ranges from (-2, -2) to (1, 1). This is important as you keep expanding the map, you only push down when you need new space, and then only allocate nodes along the tree till you get to the leaf level when adding new nodes.

After 1 push down, and adding value (1, 1).

```[(-2,-2) to (-1,-1)]              [( 0,-2) to (1,-1)]
\   \                /  /
\ <(-1,-1)>  <(0,-1)> /
[(-2,-2) to ( 1, 1)]
/ <(-1,0)>   <(0,0)> \
/   /               \  \
[(-2, 0) to (-1, 1)]              [( 0, 0) to ( 1, 1)]
\
<(1,1)> ```

This push down in a Quadrant Map is a bit more complicated. You must create 4 new child Nodes, and each one then gains 1 element from the previous Root Node. Then the Root Node is replaced by a new Root with twice the range. Finally, the (1,1) data point is added to the tree down the appropriate chain.

## Code

The theory above is simplified in the code. The important difference is that the Root node is the only one aware of the negative values. And subsequently, all children nodes are 0 indexed.

To determine the size of each node `Height` variable is used to compute its Size in the form of 2Height. Thus a Leaf Node has a Height of 1, and is of size 2. Thus each time a push down is performed a the new Root node has twice the Height of the previous Root, allowing for it to be twice the Size.

The Node Class:

```class QuadrantNode<T>
{
//an indicator if the node is at the leaf height
public bool IsLeaf { get { return Height == 1; } }
public int Height { get; protected set; }
public int Size { get; protected set; }
public int SizeOver2 { get; protected set; }

//pointers to other nodes if not a leaf
//pointers to data if is a leaf
T[,] ChildrenTs;

{
Height = height;
//determin size of node
Size = (int)Math.Pow(2, height);
SizeOver2 = Size / 2;

//allocate pointer arrays depending on node type
if (IsLeaf)
{
ChildrenTs = new T[2, 2];
}
else
{
}
}

//and sets them back into the out values
public void GetQuadrant(int x, int y, out int qx, out int qy)
{
qx = (int)Math.Floor((double)x / SizeOver2);
qy = (int)Math.Floor((double)y / SizeOver2);
}

//getter for leaf values
public bool GetT(int x, int y, out T leafValue)
{
leafValue = default(T);
if (!IsLeaf) return false;
int qx, qy;
GetQuadrant(x, y, out qx, out qy);
leafValue = ChildrenTs[qx, qy];
return true;
}

//settter for leaf values
public bool SetT(int x, int y, T leafValue)
{
if (!IsLeaf) return false;
int qx, qy;
GetQuadrant(x, y, out qx, out qy);
ChildrenTs[qx, qy] = leafValue;
return true;
}

//getter for node values
public bool GetNode(int x, int y, out QuadrantNode<T> node)
{
node = null;
if (IsLeaf) return false;
int qx, qy;
GetQuadrant(x, y, out qx, out qy);
node = ChildrenNodes[qx, qy];
return true;
}

//setter for node values
public bool SetNode(int x, int y, QuadrantNode<T> node)
{
if (IsLeaf) return false;
int qx, qy;
GetQuadrant(x, y, out qx, out qy);
ChildrenNodes[qx, qy] = node;
return true;
}
}```

The Map class:

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

{
{
//gets height of the root (ie how tall is entire tree)
public int Height { get { return Root.Height; } }

{
//set root to leaf node
}

public bool InMap(int x, int y, out int qx, out int qy)
{
Root.GetQuadrant(x, y, out qx, out qy);

//this is different from the node quadrent check, because
//we allow negative values thus cover the full x & y field
if (qx >= -1 && qx <= 0 && qy >= -1 && qy <= 0) return true;
return false;
}

public void PushDown()
{
//create a new node 1 taller than the previous (will double size)

//set the children of the new root to nodes

//if the root is a leaf node, then the children are, so copy T
if (Root.IsLeaf)
{
T tempChild;
newRoot.GetNode(0, 0, out tempNode);
Root.GetT(0, 0, out tempChild);
tempNode.SetT(tempNode.SizeOver2, tempNode.SizeOver2, tempChild);

newRoot.GetNode(0, newRoot.SizeOver2, out tempNode);
Root.GetT(0, Root.SizeOver2, out tempChild);
tempNode.SetT(tempNode.SizeOver2, 0, tempChild);

newRoot.GetNode(newRoot.SizeOver2, 0, out tempNode);
Root.GetT(Root.SizeOver2, 0, out tempChild);
tempNode.SetT(0, tempNode.SizeOver2, tempChild);

newRoot.GetNode(newRoot.SizeOver2, newRoot.SizeOver2, out tempNode);
Root.GetT(Root.SizeOver2, Root.SizeOver2, out tempChild);
tempNode.SetT(0, 0, tempChild);
}
//root is not a leaf node, so copy quad nodes
else
{
newRoot.GetNode(0, 0, out tempNode);
Root.GetNode(0, 0, out tempChild);
tempNode.SetNode(tempNode.SizeOver2, tempNode.SizeOver2, tempChild);

newRoot.GetNode(0, newRoot.SizeOver2, out tempNode);
Root.GetNode(0, Root.SizeOver2, out tempChild);
tempNode.SetNode(tempNode.SizeOver2, 0, tempChild);

newRoot.GetNode(newRoot.SizeOver2, 0, out tempNode);
Root.GetNode(Root.SizeOver2, 0, out tempChild);
tempNode.SetNode(0, tempNode.SizeOver2, tempChild);

newRoot.GetNode(newRoot.SizeOver2, newRoot.SizeOver2, out tempNode);
Root.GetNode(Root.SizeOver2, Root.SizeOver2, out tempChild);
tempNode.SetNode(0, 0, tempChild);
}

//overwrite root
Root = newRoot;
}

public T this[int x, int y]
{
get
{
int qx, qy;
if (!InMap(x, y, out qx, out qy)) return default(T);

//shift x and y to use normal corrdinate systems
x += Root.SizeOver2;
y += Root.SizeOver2;

while (current != null && current.IsLeaf == false)
{
current.GetQuadrant(x, y, out qx, out qy);

//shift x and y according to the quadrant values
int sx, sy;
sx = qx * current.SizeOver2;
sy = qy * current.SizeOver2;

//get the node
current.GetNode(x, y, out current);

//shift the x and y down
x -= sx;
y -= sy;
}

if (current == null) return default(T);

T value;
current.GetT(x, y, out value);
return value;
}
set
{
int qx, qy;

while (!InMap(x, y, out qx, out qy)) PushDown();

//shift x and y to use normal corrdinate systems
x += Root.SizeOver2;
y += Root.SizeOver2;

while (current.IsLeaf == false)
{
current.GetQuadrant(x, y, out qx, out qy);

//shift x and y according to the quadrant values
int sx, sy;
sx = qx * current.SizeOver2;
sy = qy * current.SizeOver2;

//get the node
current.GetNode(x, y, out deeper);

//if next node down is empty, make a new one
if (deeper == null)
{
deeper = new QuadrantNode<T>(current.Height - 1);
current.SetNode(x, y, deeper);
}
current = deeper;

//shift the x and y down
x -= sx;
y -= sy;
}

//save the value
current.SetT(x, y, value);
}
}
}
} ```

## Using the code

The code comes wrapped in a class two classes `QuadrantMap<T>` and `QuadrantNode<T>` ready to be exported as a DLL with only `QuadrantMap<T> public`.

Usage:

```QuadrantMap<string> map = new QuadrantMap<string>();
map[4, 5] = "hello";
map[4, 6] = "world";

Console.WriteLine(map[4, 5] + map[4, 6]);```

## Deficiencies and Errors

If you notice any deficiencies or errors, please comment with corrections.

## Change Log

31 Oct 2012 - Fixed several Bugs in QuadrantMap<T>.PushDown()

## Share

 Software Developer Microsoft United States
No Biography provided

## You may also be interested in...

 First Prev Next
 What is it for? Guirec Le Bars31-Oct-12 17:39 Guirec Le Bars 31-Oct-12 17:39
 Re: What is it for? ohmusama31-Oct-12 17:51 ohmusama 31-Oct-12 17:51
 Re: What is it for? Guirec Le Bars31-Oct-12 18:15 Guirec Le Bars 31-Oct-12 18:15
 Re: What is it for? ohmusama31-Oct-12 18:26 ohmusama 31-Oct-12 18:26
 Re: What is it for? Guirec Le Bars31-Oct-12 18:28 Guirec Le Bars 31-Oct-12 18:28
 Memory space improvement Suggestion AndyHo30-Oct-12 3:49 AndyHo 30-Oct-12 3:49
 Re: Memory space improvement Suggestion ohmusama30-Oct-12 7:06 ohmusama 30-Oct-12 7:06
 Re: Memory space improvement Suggestion AndyHo30-Oct-12 7:58 AndyHo 30-Oct-12 7:58
 Re: Memory space improvement Suggestion ohmusama30-Oct-12 10:54 ohmusama 30-Oct-12 10:54
 Interesting _groo_24-Oct-12 2:53 _groo_ 24-Oct-12 2:53
 Re: Interesting ohmusama24-Oct-12 6:31 ohmusama 24-Oct-12 6:31
 Re: Interesting _groo_24-Oct-12 8:17 _groo_ 24-Oct-12 8:17
 Re: Interesting ohmusama24-Oct-12 9:55 ohmusama 24-Oct-12 9:55
 Re: Interesting _groo_28-Oct-12 4:02 _groo_ 28-Oct-12 4:02
 Re: Interesting ohmusama28-Oct-12 16:10 ohmusama 28-Oct-12 16:10
 Re: Interesting simbos22-Nov-13 1:01 simbos 22-Nov-13 1:01
 Re: Interesting ohmusama22-Nov-13 5:14 ohmusama 22-Nov-13 5:14
 Last Visit: 31-Dec-99 19:00     Last Update: 26-Feb-17 18:14 Refresh 1