Jon Foster

Jon Foster

  • NA
  • 7
  • 0

Quad Tree Algorithm

Jul 13 2007 8:53 AM
Hi,

I am working on a simple 2d tile generation algoritm and thought it might be a good oppotunity to teach myself some recursive programming. (I am quite new to C# and havn't really coded in ernest before recently...)

I ended up with what seems to be called a "quadtree" algoritm. Like a binary tree but with 4 branches on each node. However i have so far failed to implement it.

So far i have something like :

int base_height = Constants.LOWLAND;
int lengthX = Constants.MAP_WIDTH;
int lengthY = Constants.MAP_HEIGHT;
int OriginX = 0;
int OriginY = 0;
int gradient = 20;

Set_Height(OriginX, OriginY,lengthX,lengthY,gradient);

Draw_It();

 

 

public void Set_Height(int OriginX, int OriginY, int lengthX, int lengthY, int gradient)
{
int Ox = OriginX;
int Oy = OriginY;
int X = lengthX;
int Y = lengthY;
int grad = gradient;

if (X > 2 && Y > 2) // create new variable instead of "2"
{
Set_Height(Ox,Oy,(X/2),(Y/2),(grad/2));
Set_Height((Ox+X),(Oy),(X/2),(Y/2),(grad/2));
Set_Height(Ox,(Oy+Y),(X/2),(Y/2),(grad/2));
Set_Height((Ox+X),(Oy+Y),(X/2),(Y/2),(grad/2));

for(int y = 0; y < Y; y++)
  for (int x = 0; x < X; x++)
  {
mapgrid[x, y] = (mapgrid[x,y]+grad);
  }
}

--------

It run successfully but only ever services the first of the Set_Height calls. I believe this is because
X and Y end up at 2 when this part of the tree gets down to it's deepest. Can anyone give me a clue as to how I can re-write this so the entire tree gets created?

Thanks

Jon.


Answers (1)