On Tuesday 27 February 2001 16:50, you wrote:
> your "ballremoving" routine was very nice, but actually I only want the
> balls to be removed, if there are 3 or more balls
> connected to eachother horizontally, vertically or diagonally.. (and if
> some of these balls have neighbours with the same
> color, they have to be removed too)
OK, it can be fixed.
The first step, calculating representants using union-find, is unmodified.
After this step you know all the groups. The group size is no longer
relevant, so the old second step is scrapped, as well as the old third step.
The new second step is to search for lines of 3 balls on a row, you can do
this easily by doing a linear search for every ball in 4 directions:
right-up, right, right-down, down (or 4 other directions, as long as they
represent the entire 8-direction star). You can do the search using a single
routine, with delta-x and delta-y as parameters.
Example: ("o" is the ball in question, "x" are balls searched, "-" are balls
not seached)
- - - - x
- - - x -
- - o x x
- - x x -
- - x - x
You don't have to search every direction because they are searched from the
ball on the other end of the line. (A line walked in the opposite direction
is still the same line, no need to check it twice.)
A simple trick is to use sentinels: mark the edge of the playing field with
balls of a color that doesn't occur in the game. Now you no longer have to
check for the coordinates being outside the playing field, instead you can
rely on the fact that no line will ever extend beyond the border of sentinel
balls.
Example: (this is the bottom part of a playing field)
9 1 2 2 3 4 9
9 2 1 2 4 3 9
9 2 2 1 4 1 9
9 9 9 9 9 9 9
Here the balls of color 9 are the sentinels. They also help in other places.
For example, gravity doesn't cause balls to fall out of the playing field,
because the lower line of sentinels will stop them (no coordinate checking
necessary). Also, the side walls form barriers when calculating whether a
sideways move (by the player) is possible.
If balls diagonally connected to a line of balls are neighbours, you only
have to search for lines of length 3. If balls are only considered neighbours
if they are horizontally or vertically next to a line, you should search for
the longest possible line.
All balls on the line are marked for removal, as well as all balls in the
same groups as these balls. An easy way to implement this is as follows:
Step 3a: for every ball on the line, mark its representant for removal.
Step 3b: for every ball, check if the representant is marked for removal, if
it is, mark the ball itself for removal as well.
There is a very useful optimization you can use: once you have all the
datastructures for the current game field, re-use them when the next balls
are dropped. You don't have to recalculate everything, you can apply the
group calculation and the line searching only for each of the new balls. Note
that in this case you do have to search lines in 8 directions, searching half
of them is no longer sufficient because there is no search initiated from the
balls on the other end of the line.
Whenever you remove balls, you will have to recalculate everything. However,
a game typically displays an animation when this happens, so you'll have some
spare CPU time to do the calculation.
Bye,
Maarten
--
For info, see http://www.stack.nl/~wynke/MSX/listinfo.html
