Archived

This topic is now archived and is closed to further replies.

defster

Puzzle game woes

Recommended Posts

I''m working on a simple puzzle game, similar to puzzle bobble and the rest of them, where you line up blocks and then blow them away when there are many enough of them lined up. The problem is that i''m having a hard time figuring out which blocks are connected to each other. Imagine you got this grid of blocks. 22222442 46422222 42444242 42242242 Ofcourse the grid is much larger, and there are many different colored block. Say that the number 4 represents all red blocks. How do i figure out which of the red blocks are connected to eachother, if 6 is the starting point? I want them to disappear only if there are 4 or or more red blocks connected, which means that i cant just wipe the grid of all 4s. I cant think of any ways to do this It should be similar to the good old "fill" routine used in the Paint program. Can anyone help me find a solution to this? I''ve been staring at the wall the last few hours. Thanks

Share this post


Link to post
Share on other sites

Actual Board Mask Board

22222442 00000000
46422222 00000000
42444242 00000000
42242242 00000000
^ 00010000
4


When the entity hit, you must check if there is the same entity stuck to it and it must not have been checked before.

The best is to create a recursive function that will check in four directions all the possible path and end when the pointer is back to its original position. The Mask Board is used to represent which entities were checked as valid.


[edited by - hpox on April 29, 2002 9:27:21 AM]

Share this post


Link to post
Share on other sites
No, i dont use hexagonal grids. But puzzle bobble was the first puzzle game that entered my minds. Bad example.

Thanks for the help hpox, i managed to fix my problem now, using a recursive routine.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Ok, this is a simple algorithm and is by no means the fastest way to do it, but it's quite quick as long as your grid isn't huge, it's easy to understand, and it won't result in a stack overflow error:


  1. let c = the colour we're flooding over (e.g. 4)
    let f be a unique number that is not used as a colour (e.g. 255, -1, ...); we will use this 'colour' to mark out the area filled.
    set the starting points colour to b.


  2. changed = false


  3. s say your grid is 1 .. width by 1 .. height. Then you want to do something like this:


    // this part floods down and to the right
    for x := 1 to width - 1
    for y := 1 to height - 1
    if (colour[x, y] == f) then
    if (colour[x + 1, y] == c) then
    colour[x + 1, y] = f;
    changed = true;
    end;
    if (colour[x, y + 1] == c) then
    colour[x, y + 1] = f;
    changed = true;
    end;
    end;
    end;
    end;

    // this part floods up and to the left
    // the loop goes the opposite way, because it is likely to
    // fill quicker as a result.
    for x := width downto 2
    for y := height downto 2
    if (colour[x, y] == f) then
    if (colour[x - 1, y] == c) then
    colour[x - 1, y] = f;
    changed = true;
    end;
    if (colour[x, y - 1] == c) then
    colour[x, y - 1] = f;
    changed = true;
    end;
    end;
    end;
    end;


  4. though this algorithm will fill squares relatively quickly, it won't get round every corner; so we iterate:

    if changed then (repeat steps from 2 onwards)


  5. we get past step 4, changed = false, so from the last pass we know we've got 'em all. Count them, to determine if there are the number you require. If there are, delete them. If there aren't, change every f on the grid back into a c.


  6. Hope that's more-or-less what you wanted



    [Edit: Enabled formatting.]

    [edited by - Oluseyi on April 29, 2002 7:17:41 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Sorry, the indenting appears to have been lost

I should have looked up the tags for monospaced text.

Share this post


Link to post
Share on other sites