Falling Tiles Java Question

[namarino]

So I have a grid of numbers (an array) and some of them can be removed. Open spaces are filled when other tiles fall into place. 

So essentially like this. The tiles are removed and then the other tiles fall into place. Does anyone have any idea how to do this??? I'm really stuck here....thanks so much.

//     0  1  2  3  4
  //   ---------------
  // 0|  4     4      
  // 1|  9  1  6     2
  // 2|  6  5  1     9
  // 3|  2  5  5  x  x
  // 4|  5  9  x  x  x
  //
  // Calling doRemovals() should first remove them from the board
  // creating gaps.
  //
  //     0  1  2  3  4
  //   ---------------
  // 0|  4     4      
  // 1|  9  1  6     2
  // 2|  6  5  1     9
  // 3|  2  5  5      
  // 4|  5  9         
  //
  // Gems should then fall downward.
  //
  //     0  1  2  3  4
  //   ---------------
  // 0|  4           
  // 1|  9  1  4     
  // 2|  6  5  6      
  // 3|  2  5  1     2
  // 4|  5  9  5     9 

[Ryoutarou97]

I'm not sure if I quite understand what is supposed to be happening here, but if I do, here would be my solution. Start at the bottom row and iterate across until you find an empty space (I assume empty == 0 and 1-9 are gems) then go up that row until you either hit a gem or the top of the row and drop down the gem or create a new one at the top and drop it down. Then start back at where you left off moving up the rows.

If it's a 2d array made by nesting an array within an array, the pseudo-code would be as follows:

 

//these could also be for loops, but I don't remember the syntax for those

int y = 0;
int x = 0;

while (y <= arrayHeight)
{
	while(x <= arrayWidth)
	{
		//the next line assumes 0 is empty, but use whatever condition you have for empty in there
		if(getTileID(x, y) == 0)
		{
			int tempY = y;
			
			while(getTileID(x, tempY) == 0 && tempY < arrayHeight)
			{
				tempY++
			}
			
			if(tempY == arrayHeight)
			{
				setTileID(x, tempY, rand.nextInt())                                                 
			}else{
				dropTile(x, tempY)
			}

		}//end of the part that happens if you hit an empty tile
		x++; //move over to next tile
	}
	y++; //move up one row
    x = 0; //start at the beginning of the next row
	
	
}

 

Whoops, that wasn't pseudocode and there are a lot of newlines at the end. Anyways, how does that look?

[Nuluvius]

So it's essentially Tetris?

 

What specifically are you struggling with? Try to break the problem down into components and list out what you think you need to accomplish.

 

4 hours ago, Ryoutarou97 said:

 

Anyways, how does that look?

Upon first glance; too much going on in one place and far too much nesting/cyclomatic complexity.

[voldelord]

You could make the columns ArrayLists, then removing an element would also remove the gap.  

 

Otherwise you could iterate through each column until you encounter a gap, lower each element above the gap, then continue your search.

[Nineshadow]

You find the cells you want to delete , probably with a flood/fill algorithm if I understand what you want to do, then delete them.

 

As far as the falling part goes, it's basically Tetris. Except entirely with column chapes. If you want to do it the Tetris way :

The Idea

Define the set of frozen objects inductively as follows:

    An object touching the bottom is frozen.

    An object lying on a frozen object is frozen.

Intuitively, exactly the frozen objects have reached their final place. Call the non-frozen objects active.

Claim: All active objects can fall one unit downwards simultaneously.

Proof: Of course, an active object will not hit another active object, since their relative position with respect to each other does not change. An active object will also not hit a frozen object. If that was so, then the active object was, in fact, frozen, because it was lying on a a frozen object. This contradicts our assumption.

Our algorithm's very high-level pseudo-code would be as follows:

while (there are active objects):
    move active objects downwards simultaneously until one of them hits a frozen object
    update the status (active/frozen) of each object

Notice that at least one object becomes frozen in each iteration of the while loop. Also, every object becomes frozen exactly once. These observations would be used while analyzing the run-time complexity of the actual algorithm.
The Algorithm

We use the concept of time to improve the efficiency of most operations. The time is measured starting from 0, and every unit movement of the active objects take 1 unit time. Observe that, when we are at time t, the displacement of all the objects currently active at time t, is exactly t units downward.

Note that in each column, the relative ordering of each cell is fixed. One of the implications of this is that each cell can directly stop at most one other cell from falling. This observation could be used to efficiently predict the time of the next collision. We can also get away with 'processing' every cell at most once.

We index the columns starting from 1 and increasing from left to right; and the rows with height starting from 1. For ease of implementation, introduce a new object called bottom - which is the only object which is initially frozen and consists of all the cells at height 0.

Data Structures For an efficient implementation, we maintain the following data structures:

    An associative array A containing the final displacement of each cell. If a cell is active, its entry should be, say, -1.

    For each column k, we maintain the set S_k of the initial row numbers of active cells in column k. We need to be able to support successor queries and deletions on this set. We could use a Van Emde Boas tree, and answer every query in O(log log H); where H is the height of the grid. Or, we could use a balanced binary search tree which can perform these operations in O(log N); where N is the number of cells in column k.

    A priority queue Q which will store the the active cells with its key as the expected time of its future collision. Again, we could go for either a vEB tree for a query time of O(log log H) or a priority queue with O(log N) time per operation.

Implementation

The detailed pseudo-code of the algorithm follows:

Populate the S_k's with active cells
Initialize Q to be an empty priority queue

For every cell b in bottom:
    Push Q[b] = 0

while (Q is not empty):
    (x,t) = Q.extract_min()     // the active cell x collides at time t
    Object O = parent_object(x)
    For every cell y in O:
        A[y] = t                // freeze cell y at displacement t
        k = column(y)           
        S_k.delete(y)
        a = S_k.successor(y)    // find the only active cell that can collide with y
        if(a != nil):
            // find the expected time of the collision between a and y
            // note that both their positions are currently t + (their original height) 
            coll_t = t + height(a) - height(y) - 1
            Push/update Q[a] = coll_t

The final position of any object can be obtained by querying A for the displacement of any cell belonging to that object.
Running Time

We process and freeze every cell exactly once. We perform a constant number of lookups while freezing every cell. We assume parent_object lookup can be done in constant time. The complexity of the whole algorithm is O(N log N) or O(N log log H) depending on the data structures we use. Here, N is the total number of cells across all objects.

 

Of course it can be made a lot simpler, since you aren't dealing with shapes of any kind here.

Let's take this column :

1
4
2
0
0
2
1

We have already deleted what we had to delete. In those cells we have values of 0 now. We know the one with the highest index is 4 (counting from 0), and we know there's 2 of empty cells. We then shift the column from that position by the amount of empty cells to the bottom.

Should look something like this :

int n = 7, v[7] = {1, 4, 2, 0, 0, 2, 1},k=0,p;

    //find no. empty cells and right/bottom-most empty cell
    for(int i = 0; i < n; ++i)
    {
        if(v[i]==0)
        {
            ++k;
            p = i;
        }
    }
    //shift the array from that position by k units to the right/bottom.
    for(int i = p; i>=0+k; --i)
    {
        v[i] = v[i-k];
        v[i-k] = 0;
    }

To make it a little more efficient we can calculate how many cells we delete for each array and the highest index of a deleted cell on each column and store it into some data structure of some kind.

So the complexity would be O(delete) + O(shifts).

O(delete) = k.

O(shifts) ~= m*O(shift).

O(shift) is worst case n. (or n-1, whatever)

Worst case complexity : O(k+m*n).

 

I'm pretty sure you could also solve it using graphs. Probably some topological sort.