Jump to content
  • Advertisement

Archived

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

capn_midnight

Blocky Puzzle Game Algorithms

This topic is 6010 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i''m currently working on a puzzle game similar to Yahoo Collapse (for those of you unfamiliar with the game, you click groups of 3 or more blocks to destroy them as more blocks rise up from the bottom. If you let the blocks get all the way to the top, you lose.) Everything is going good. The problem is the popping algorthim. I can make it pop in a cross pattern, but I can''t make it pop whole groups of blocks. for example, say I have a grid of blocks like this: 11111111 11221111 11222111 11111111 I want to pop all of the #2''s with one click, but I can''t quite figure it out. What I have now pops every matching block directly out from the top, right, bottom, and left in straight lines. I tried making a recursive function called pop (in pseudo code): 1.pop (x,y) 1.1. gird point (x,y) = 0 (removes tile) 1.2. check top (x,y-1) 1.2.1. if matches, pop (x,y-1) 1.3. check left (x-1,y) 1.4. check right (x+1,y) 1.5. check bottom (x,y+1) so now the function is recursive and will check the top, right, bottom, and left of each matching tile around the first tile... MAJOR STACK OVERFLOW!!! what do I do? please help! I''m so tired because I stayed up all night working on this and might stay up all night tonight. AOL, so easy to use, no wonder it''s nothing but a bunch of retards Spyder''s Web Games

Share this post


Link to post
Share on other sites
Advertisement
Better publish the source code. The algorithm seems to be Ok but maybe it is a problem with the implementation. The algorithm, though, is not very detailed and may be interpreted in varios ways.

Share this post


Link to post
Share on other sites
I was doing something similar early last year, the problem is your recursive function is not stopping. I''d guess that the blocks are not begin =0''d properly, so then your algorithm is getting into an infinite circle. Are you checking against X,Y for a match or against a set value ? (as you are zero''ing X,Y).

I''d have to see the code to be sure but this is exactly the same thing I had to overcome (almost).

,Jay

Share this post


Link to post
Share on other sites
Sorry, this doesn''t really help you out, but I really hate that game, heh. Personally, I think it takes no skill whatsoever, it''s all mindless clicking..

I''ve never lost the game before, all I do is click really fast all over the bottom line, and the game never seems to end, or get challenging.

Share this post


Link to post
Share on other sites
A couple of things...

First check that the tile you are trying to pop isn't already zero. If it is zero then return immediately. You see, if it is zero then there is a possibility that you may begin checking the surrounding area for matching tile (more zeros). When you're playing with an empty screen then it's full of zeros. This could cause a lot of recursion, although this may not be your problem and if you post the code then I may find you've already put this check in. Sorry if that's the case.

Secondly, yes there is indeed the possibility that you are causing a lot of recursion when a large area is 'popped'. Try increasing your stack size for a quick fix, but better still try considering developing something that doesn't use recursion as already suggested. Why is this better? It's not, necessarily. Actually increasing your stack size is possibly a valid solution, yet wasteful of course. You might like to try the alternatives as a mere programming exercise.

Thirdly...when you check surrounding tiles, make sure what you are checking is part of your board. Without the code we can't see what your data structure is, so it's possible that if you check the border tile you may then begin to check a tile beyond the border that doesn't actually existing, but is actually just some arbitrary area of memory. In this case, anything could happen. Always bounds check the (x,y) to check it's a tile.

Finally, I can recommend also dumping out your conversion of mouse co-ordinates (or whatever picking method you are using) and just checking that it's being coverted into the correct position on your game board. Again, bounds checking would likely show this up but if the conversion is wrong you may be creating (x,y) values that are ridiculous and indexing into something unknown.

I hope that helps, to some extent at least.

[edited by - freakchild on June 2, 2002 2:02:50 AM]

Share this post


Link to post
Share on other sites
uhm, will you hate me if I say I''m making the game in VB?
Actually, I think I know what the problem may be (besides VB). Once you pop a block the blocks above it fall down to fill the gap. I think I''m implementing the fall too soon. I''ll have to rewrite the section of code.

Thanks for the hints.

Share this post


Link to post
Share on other sites
quote:
Original post by freakchild
A couple of things...

First check that the tile you are trying to pop isn''t already zero. If it is zero then return immediately. You see, if it is zero then there is a possibility that you may begin checking the surrounding area for matching tile (more zeros). When you''re playing with an empty screen then it''s full of zeros. This could cause a lot of recursion, although this may not be your problem and if you post the code then I may find you''ve already put this check in. Sorry if that''s the case.


Nope, cut that out from the beginning.

quote:

Secondly, yes there is indeed the possibility that you are causing a lot of recursion when a large area is ''popped''. Try increasing your stack size for a quick fix, but better still try considering developing something that doesn''t use recursion as already suggested. Why is this better? It''s not, necessarily. Actually increasing your stack size is possibly a valid solution, yet wasteful of course. You might like to try the alternatives as a mere programming exercise.


Going with an alternative will probably be my best bet. I''m not sure how you would increase the stack size in VB.

quote:

Thirdly...when you check surrounding tiles, make sure what you are checking is part of your board. Without the code we can''t see what your data structure is, so it''s possible that if you check the border tile you may then begin to check a tile beyond the border that doesn''t actually existing, but is actually just some arbitrary area of memory. In this case, anything could happen. Always bounds check the (x,y) to check it''s a tile.


Got that too, as soon as I reallized that it was checking on the opposite side of the board.

quote:

Finally, I can recommend also dumping out your conversion of mouse co-ordinates (or whatever picking method you are using) and just checking that it''s being coverted into the correct position on your game board. Again, bounds checking would likely show this up but if the conversion is wrong you may be creating (x,y) values that are ridiculous and indexing into something unknown.


Actually, I''m not using (x,y) mouse coordinates. I''m using the VB Picture element in a large one-dimensional array (about 270). When the click event for the picture is executed, the pictures array index is passed to the sub. At this point I still don''t need to convert to (x,y) coords because the math is simple enough to do in one dimension, x+1=index+1, y+1=index+gridWidth.

thanks for the help

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Puzzler183
The porblem is that it check tons of tiles. Try not to make it recursive.


Recursion looks like a clean, natural way to express this algorithm. Your stack overflow is very likely to be cased because the recursion isn''t ending when it should and possibly going over and over the same tiles. Unless you have thousands of tiles (unlikely), you shouldn''t be getting stack overflows.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!