Back to General and Gameplay Programming

Puzzle game woes

General and Gameplay Programming Programming

Started by defster April 29, 2002 07:56 AM

5 comments, last by defster 21 years, 11 months ago

defster

122

Author

April 29, 2002 07:56 AM

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

- defster

hpox

122

April 29, 2002 08:26 AM

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]

...

coelurus

259

April 29, 2002 09:44 AM

Note that Puzzle Bobble used a hexagon-tiles! I don''t know whether you want that or not.

defster

122

Author

April 29, 2002 09:52 AM

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.

- defster

parklife

132

April 29, 2002 10:38 AM

use recursion/backtracking to solve this.

Anonymous

April 29, 2002 04:47 PM

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:

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.

changed = false

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 rightfor 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;

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)

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.