Flattening a quad tree to a 2D array

136 Views Asked by At

I'm trying to create a game that uses a quad tree.Block game. As shown in the picture, the blocks are elements of the tree and they can have either 0 or 4 children. The biggest block is at level 0 and its children is at level 1 and so on. For every game, there is a maxLevel at which you cannot subdivide the block any further. Let's call the blocks that cannot be divided unit cells. Only the leaves have colors while non-leaf elements have color equal to null.

Furthermore, the children of a block is stored in an array in this order [upperRight,upperLeft,lowerLeft,lowerRight]. My goal is to flatten the tree to a 2D array of colors (arr[i] represents the row and arr[i][j] represents the color of that unit cell at the corresponding position on the board). For example, the element at arr[0][0] should have the color of the unit cell at the upper left corner of the biggest block.

Here's what I got so far:

    private Color[][] flatten(Color[][] arr) {
  //base case
   if(this.children.length != 0 && this.level == maxDepth - 1) {
    for (int i = 0; i < arr.length; i++) {
     for (int j = 0; j < arr.length; j++) {

      //I don't know which indices to use. I tried doing some calculations to convert the           coordinates into indices but I coudn't do it.
      arr[?][?] = this.children[j].color;

     }
    }
   }

  //if the current block doesn't have children and it is at maxLevel-1

   else if(this.children.length==0 && this.level == maxDepth - 1){
    for(int i = 0; i < arr.length ; i++){
     for(int j = 0; j < arr.length; j++){

    //same indices problem here
      arr[?][?] = this.color;

     }
    }
   }
  //recursive step
  //I'm doing the recursive call in the order 1,0,2,3 because of the way the children are ordered
   else if(this.children.length != 0 && this.level != maxDepth - 1){
    this.children[1].flatten(arr);
    this.children[0].flatten(arr);
    this.children[2].flatten(arr);
    this.children[3].flatten(arr);
   }

  return arr;
}
0

There are 0 best solutions below