Tracking and moving Columns of Objects

Started by
7 comments, last by Waterlimon 10 years, 5 months ago

I'm working on the base of a game in which the object is to destroy as many blocks as possible. If connected, clicking a block will destroy it along with all blocks connected to it (cardinal directions only). The blocks above a destroyed section will fall down. If a column is empty, all columns to the right of it will shift left to occupy the empty space and ensure that the blocks are kept together.

My problem lies with just how I should go about tracking and shifting the columns to the right of an empty one. I use an associative array to keep track of the columns (1-10) and which blocks are located within them. Beyond that, I'm not too sure. I have had some success but run into problems when there is more than one empty column next to each other, between full columns.

Really, I'm unsure of how to work out how far I should move the columns. As you can see below, even my pseudo code is very vague. Any ideas on how to resolve this would be much appreciated.

Pseudo Code:

Loop through all columns
    if column is empty
        find all non-empty columns to the right
            move them left until there are no breaks betwen columns
Advertisement

I'm working on the base of a game in which the object is to destroy as many blocks as possible. If connected, clicking a block will destroy it along with all blocks connected to it (cardinal directions only). The blocks above a destroyed section will fall down. If a column is empty, all columns to the right of it will shift left to occupy the empty space and ensure that the blocks are kept together.

I am a bit confused: you said all the blocks above the clicked block will be destroyed yet you also said those same blocks will fall down. This sounds very contradictory if they fall down to me, they are still displayed in the game. Which one is it?

Assuming, the above blocks do get destroyed along with the clicked block, here are my thoughts:

for the destroy block implementation for cardinal direction(North): check what column of the block that was clicked and loop through every block above that block that clicked and remove them for each run of the loop. These blocks above the clicked bows are all located at the rows less than the row of the clicked block. Their column remains the same.

Say the block clicked was at row 5 and column 5, the blocks destroyed should be at the same column as the clicked block which is 5, but the rows of those destroyed are less than the column of the clicked block. These values are 0-4.

For the other cardinal directions, the approach is very similar. Try drawing what I said on paper and the implementations will be clear.


My problem lies with just how I should go about tracking and shifting the columns to the right of an empty one. I use an associative array to keep track of the columns (1-10) and which blocks are located within them. Beyond that, I'm not too sure. I have had some success but run into problems when there is more than one empty column next to each other, between full columns.

in terms of shifting these are just row and column offsets. If you are shifting blocks to the left, then check the column right after the empty column and offset row and column of those blocks in that column.

In terms of tracking, the block has only two information: their row and column represented the blocks position in the game. Arrays will do it.

This project reminds me of a Tetris and Bomberman game implementations.


I am a bit confused: you said all the blocks above the clicked block will be destroyed yet you also said those same blocks will fall down.

Yea, it would help if this was clarified.

+---------------------------------------------------------------------+

| Game Dev video tutorials -> http://www.youtube.com/goranmilovano | +---------------------------------------------------------------------+

Apologies, what I meant to say is that all blocks of the same colour that are connected will be destroyed. I'm at the point now where I can show an example of how it works (below). I've yet to create an efficient way of sliding the columns to the left to fill empty columns.

At the end of the gif below, you can see an empty column. The four columns to the right should all be moved to the left, leaving an empty column at the far right. I've had some success with this, though my efforts mess up when there is two or more empty columns to fill at once.

1JdcCQ1Q3PJQgf8sPV7ezqJclhws5h1.gif

Since you are using an associative array (is this C++, so a map?), remove the column when it is empty and add a new column which has ID rightmost columnID + 1, then just iterate over the columns in ascending order (which is what happens when you iterate a map anyway). This scales for multiple blank columns but does overflow when the column ID overflows (at a very large number though).

If the associative array is unordered, (e.g. a hash_map, unordered_map) you can't iterate the columns in order, using a linked list of ascending columns IDs which contain a list of tiles would work.

You probably want to keep the empty column still "active" (i.e. still drawn and animating etc.) until the board has fully closed the gap (using dummy tilIeIDs, e.g. negative values as a counter is an obvious way to do that).

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

Here's a small video that explains one possible algorithm:

Code:

Python demo (your mechanics, replicated, with the added feature): https://gist.github.com/GoranM/7049155#file-columnsquish-py

C demo (just the horizontal squish, in ASCII): https://gist.github.com/GoranM/7049155#file-columnsquish-c

Hope that helps.

+---------------------------------------------------------------------+

| Game Dev video tutorials -> http://www.youtube.com/goranmilovano | +---------------------------------------------------------------------+

Yay my post is a video star! (Even if you dismissed my advice straight away!).

I mentioned hash_map because the OP mentioned using an associative array to store the columns (not a 2D array). It looks like they are using a map though ordered by column number.

My suggestion involved never reusing column numbers, deleting them from the map when the column is cleared, which wouldn't work with an unordered map, since you need to iterate from the lowest to the highest column number in order, which you can't do as easily with a hash map.

EDIT: I didn't watch all of the video but it looks like you compact a 2D array by copying columns over. Do you do several passes if 2 or more columns are cleared simultaneously or have a "column to copy to" and "column to copy from" indices (which would also work).

With an associative array you don't need to do any copying of the columns you just keep incrementing the rightmost column number and delete entire empty columns from the container.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

I show the code at 4:02, so you can see it there (or you can just click the links, and read it).

It's a recursive approach (to facilitate animation between steps), using an array of rows as a base data structure. I didn't really care much about performance, but if I did, I would use an array of columns, so I could just do a memory move on an array of pointers, to "shift" the columns to the right, instead of swapping all the elements.

So, my "performance minded" implementation would look like this: https://github.com/GoranM/blocky/blob/master/blocky.c

blocky.gif

I don't see how a hash-map (a more complex data structure) would be more efficient in this context; direct array access is faster than having to go through the hash function, as far as I know.

Could you show me a quick code example? I probably misunderstood your algorithm.

+---------------------------------------------------------------------+

| Game Dev video tutorials -> http://www.youtube.com/goranmilovano | +---------------------------------------------------------------------+

You could have:

1) an array of columns [columns][height]

2) an array of ints (char would do in most sane cases) for column order [columns]

eg

a)

00101

10101

11101

11101

0,1,2,3,4 //you see that the last column has an entirely empty column ahead of it

b)

00101

10101

11101

11101

0,1,2,4,3 //swap the 2 last columns by swapping the indices

You can add the current amount of tiles in a column as a part of the column array (so each column is a class and can tell the amount of tiles it has) so you dont need to actually count them as long as you increment/decrement the counter when you add/remove tiles (functionality which can be encapsulated by the class)

This is clearly superior to making a "deep swap" (assuming the cost of some extra indirection is smaller than the cost of copying a large number of tiles. Lets assume your tiles are very bloated and moving columns is common) and you will thank me when you decide to run 100 000 games simultaneously on your router you hacked into a multiplayer server.

o3o

This topic is closed to new replies.

Advertisement