🔒 Locked

Columns Algorithm

Started by Xorcist Sep 29, 2001 at 1:58 AM 7 replies 650+ views

Original Post

Sep 29, 2001 at 1:58 AM

Okay, just thought I''d throw this out in the open before I got started to see if anyone had any interesting or unique ideas about solving the task at hand. For those of you that don''t know Columns is a Tetris like game but all the game pieces are 1x3 and formed of colored crystals. When 3 or more of the same colored crystals line up (horizontally, vertically, or diagonally) they are destroyed and any crystals that may have been above the destroyed ones fall. The process is repeated until no crystals line up, and then the next piece drops into play. I''m about to attempt to map this algorithm for use in a game of my own creation, but if someone already has a decent one premade or feels like creating one just for the fun of it, it would help me out a lot. The board is basically a two dimensional array 6x13 and each time a piece lands a check needs to be done. I''m not sure where I''ll eventually start, but I''d like to end up with a highly optimized algorithm (in case I decide to increase the size of the board). I guess my first step would be to perform a check based on every element in the array and branch if a matching color is found (incrementing as I go). Hmmmm I wonder if I can use a variant of A* to solve this. Well let''s see how far I get... at the very least this should prove to be an interesting undertaking. {Comments, Questions, and Suggestions are all welcome.}

c_wraith

Sep 29, 2001 at 5:00 AM

Here''s a few thoughts.

First, don''t waste your time scanning the whole board. Only a few places have changed. Only scan those places. That will make the speed of the algorithm essentially independent of the board size, although not completely because the potential size of chain reactions increases.

Second, this algorithm doesn''t need to be fast. It''s run once every time the set of pieces changes. Even if it takes 30 ms (and there''s no way it should take even 1% of that much time), the user won''t really notice it.

Third, it shouldn''t be that hard of algorithm to just write. Even the least clever algorithm that takes my first thought into account should run VERY fast.

Ace17

Sep 29, 2001 at 5:06 AM

Don''t bother with high-optimisation!
I programmed this game with a larger board on a calculator...
A simple A* algorythm should work fine
Anyway, I hope you''re checking all the board every frame;
Check it only when a ball arrives on the stack

Jedyte

Sep 29, 2001 at 5:43 AM

Ah yes,

I made something similar recently... I made a clone of Panel de Pon, also known as Tetris Attack (or Pokemon Attack, I heard they made that flavour too, now).
You have al these colored blocks that rise up and a cursor that can switch two blocks, and you just have to match up three blocks of the same color so they dissapear.

I wrote an algoritm and let it stew for a day or so to think over all the degenerate cases, and was surpised to see when I implemented it to it all worked perfectly. So just write something good on paper, then try it. Don''t rush, and it''ll work

Xorcist

Author

Xorcist

Oct 8, 2001 at 4:47 AM

Okay I worked up a prototype in Delphi to check out my basic algorithm, I''m hoping someone here might check my code for me and maybe give some extra insight. Here are the basic structures I''m using:

  
TYPE
  TCoord = record
    X: Integer;
    Y: Integer;
  end;
  TState = (Empty, Red, Green, Blue, Destroy);
  TBoard = array[1..13,1..6] of TState; //ROW major


CONST
  North: TCoord = (X: 0; Y: -1);
  South: TCoord = (X: 0; Y: 1);
  East: TCoord = (X: 1; Y: 0);
  West: TCoord = (X: -1; Y: 0);
  North_East: TCoord = (X: 1; Y: -1);
  North_West: TCoord = (X: -1; Y: -1);
  South_East: TCoord = (X: 1; Y: 1);
  South_West: TCoord = (X: -1; Y: 1);

and I''ve setup my algorithm with the premise I would rotate through the directional checks based on any "single" given grid coordinate, and would extrapolate afterwards, given that a playing piece could be composed of any number of verticle tiles (although I only plan to go as high as 3). Basically I used a recursive function to check (moving in a single direction) whether or not a series of the same colored tiles exist, and if so if that number of tiles is greater than or equal to 3. If so they should all get marked for destruction. (did any of that make sense...) Well anyways here''s my code:

  
PROCEDURE Check(Var Grid: TBoard; StartPos: TCoord; Direction: TCoord);
  Const
    MarkON: Boolean = False; //Static Variable

    Count: Integer = 1; //Static Variable

  Var
    Next: TCoord; //Next Grid Coorinate to Move to


  Begin //Check


    Next.X := StartPos.X + Direction.X;
    Next.Y := StartPos.Y + Direction.Y;

  { Check Current Grid Position''s Color Against The Next In Line }
    if (Grid[StartPos.Y, StartPos.X] = Grid[Next.Y, Next.X]) then begin
      Count := Count + 1;
      Check(Grid, Next, Direction);
    end else begin
      if (MarkON = False) then begin
        if (Count >= 3) then begin
          MarkON := True;
        end;
      end;
    end;

  { Mark Grid Coordinates }
    if MarkON then begin
      Grid[StartPos.Y, StartPos.X] := Destroy;
    end;

  { Reset Counter / Marker }
    Count := Count - 1;
    if (Count = 0) then begin
      Count := 1;
      MarkON := False;
    end;

  End; //Check

Soo... what do we all think? Can it be improved? Optimized? Does it cover what the initial rule set states? Are there any cases in which the function fails? Of course I am testing all this myself, but it never hurts to have a second mind at work...

{Any input would be greatly appreciated}

Xorcist

Author

Xorcist

Oct 8, 2001 at 5:07 AM

P.S. Any ideas on what would be the best way to handle cascading? I mean after a series of tiles are destroyed should I attempt to set all tiles above the destroyed ones to "new" pieces? I''m thinking that would be the best approach, because then all I need to do is get a tile count for each newly created piece and loop through my check function, and repeat until no tiles are set for destruction? Of course I''m sure the implementation will be a little more complex than what I''ve stated, but it makes sense right?

SkatMan

Oct 8, 2001 at 5:24 AM

I think your algorithm fails for inputs where a cell is common between lines of 3 same colored crystals:

For example:


(the column 1
            1
            3 is added on the left)

000       100
011   ->  111
021   ->  321
232       232

( top-left = (0,0) )

Now the ''1'' on (1,1) is common to both a diagonal and a horizontal structure of clipped ''1''s.
If you run ''check'' for each of the new cells separately, you''ll miss the second line you''ll check that contains the common cell (1,1).

Correct me if I''m wrong.
And of I''m not, tell me if you don''t have a solution.

Oren.

http://qsoft.cjb.net

Xorcist

Author

Xorcist

Oct 8, 2001 at 5:44 AM

Not sure if I totally understand what you''re getting at, but I do see a problem (since I mark the actual grid inside check). Basically if I check in the order North, North_East, East, South_East, South, South_West, North_West and I test from bottom up (in this case 0,2 followed by 0,1 and finally 0,0) what will end up happening is that I mark the horizontal 111 so when I get to the diagonal South_East check on 0,0 111 is actually 444 and since 4 <> 1 the check fails. Damnit! Now the question is how the hell to get around this...

I guess I could fill an array of TCoords with coordinates that need to be destroyed rather than modifying the actual grid. Then after my initial set of checks if the array in not "empty", parse through it and actually do the destroys. This way I won''t run into the aforementioned case, and if multiple sets of the same coordinates arise there won''t be any conflicts.

P.S. Was the the error case you where refering to? and thanks

SkatMan

Oct 8, 2001 at 6:07 AM

Yes, you got me right.
And your solution should work.

About cascading: Yes, do it. Check out Xixit (1995) for a very kewl Columns game.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.