hi all~ there's a game named "Super Puzzle Fighter 2" presented by Capcom, who had ever played it be4 will know its rules: 1. gems have colors(blue, green, yellow and so on); 2. if several gems with same color consists a rectangle those gems will be changed into a huge one, which is called a combo gem; my question is, when 2 gems get down, how to search and decide which gems could be considered to be a combo one ? i thought recursion as a solution for a few seconds, but soon i realized that recursion has less efficiency caz' we dont know how far we must search, and it is hard to debug once there's a problem within, so any good idea for it(searching) ?

Quote:Original post by Sneftel
It's a trivial enough problem that the algorithm doesn't need too much intelligence. For each gem, check for whether the gems around it are the same color. If they are, combine them into one gem. Search the entire playfield after each change.

tks for quick reply. i'd say that it seems to be a simple problem but it is not that simple indeed, caz' there may be many situations when 2 gems dropped down to the bottom. i'll explain why in details.

for 2 common gems(and it will always be 2 at the same time) dropped down there will be a few possibilities like examples below:

// Use customized matrix to describe those situations:
// 0 for empty cells;
// 1 for common gems(all in same color say, blue at the moment);
// 2 for comb gems(in blue color as well);
// ? are where two gems dropped down finally.


example 1:
00000000
00000000
000?0000
000?0000

in this case no comb gems will be generated and just ignore.

example 2:
00000000
000?0000
000?1000
00011000
or
000000000
000??0000
000111000
000000000

no doubt that either case there will be a comb comes out like this:

00000000
00010000
00022000
00022000
or
000000000
000220000
000221000
000000000

example 3:
00000000
0?222000
0?222000
00000000
or
00??10000
000220000
000220000
000000000
or
00?00000
01?22000
01122000
00000000

caz' we prefer retangle(combo gem) not square, so this must be what we get:
00000000
02222000
02222000
00000000
or
001220000
000220000
000220000
000000000
or
00100000
02222000
02222000
00000000

example 4:
00011000
01??1000
01111000
00000000
or
000122000
01??22000
022000000
022000000

we may expect such cases will be eventually converted like this:
00011000
02222000
02222000
00000000
or
000222000(wor double combo gems all at once cheers~ :D)
022222000
022000000
022000000


so good so far. and what we worry about when 2 gems dropped down are:
1. check if there's some gems around with which we could make a new comb one;
(1) if not, ignore and go next turn(example 1).
(2) if any, just combine them(example 2 and 3);
2. if there's already a comb gem around, try to make a bigger comb one(example 4);


if anyone has good idea to sort both problems above pls let us know in details, tks.

[Edited by - blackgame on May 30, 2006 2:17:22 AM]

Quote:Original post by Sneftel
In terms of preferring larger gems, you can simply try to grow the largest gems in the field first. IIRC, though, Super Puzzle Fighter was not always optimal in the way it grew gems. It would sometimes leave orphans it didn't have to, or make gems that didn't provide the best powerup. Basically, don't look at it in terms of gems dropped, but purely in terms of what's currently on the playing field. That's particularly important when dealing with situations like blocker gems, where the counter runs out and many gems are simultaneously added.

u mean to check every gem inside the playing field ? and that's right the solution Capcom used anyway ?

Quote:Original post by Sneftel
I couldn't say whether that's the solution Capcom used, but they may as well have. The playfield can't contain more than about 200 gems, so checking each one is trivial.

u're right, that must be the easiest way, and one thing, how can we avoid checking gems which has already been checked ?

eg. we may first check a gem at second row and second column ie.(1, 1), gems aound it are (0, 1), (2, 1), (1, 0) and (1, 2), that's fine but if next time if we try to check a gem next to it that will be a waste, caz' probably its neighbors has already been checked, so how do we make a better solution for this ?

tks.

say you have a grid of gems 10x20y

that can be green or blue doesn't matter:



just run this every update of Gem_Grid[][]

Quote:Original post by speedie
say you have a grid of gems 10x20y

that can be green or blue doesn't matter:

*** Source Snippet Removed ***

just run this every update of Gem_Grid[][]

i think i know what u mean, it really helps, tks for it man !