On Tuesday 27 February 2001 15:33, you wrote:
> I have to make a ball disappearing routine just like in puyo
> puyo/klax/collumns
> and all those other games.
> for example, if I have this matrix (serie of ball's):
>
> 12436531
> 14312262
> 41222432
>
> it has to change in something like this one:
>
> 11011111
> 10110011
> 01000111
Exactly what is your disappearing rule?
It seems that groups of 3 or more balls of the same kind are removed. A group
is a set of balls that are connected horizontally, vertically or diagonally.
I think the union find algorithm works well for this problem. Union find is a
datastructure that devides a set into classes. In this case, the set consists
of all balls and the classes are the groups. Every class is denoted by a
special element, the representant, which is an element of that class.
Here is an implementation of union find in Java:
(excuses for the Dutch comments - this code is taken directly from the
standard algorithms library of our programming contest team)
===
class UnionFind
{
// Datatype waarmee je klassen kunt representeren.
// Ook handig om samenhangende deelgrafen te vinden.
int[] repr;
UnionFind(int nrElem)
{
repr = new int[nrElem];
for (int r=0; r<nrElem; r++) repr[r] = r;
}
int find(int elem)
{
// Zoek representant
int r = elem;
while (repr[r] != r) r = repr[r];
// Collapse path
while (elem != r) {
int h = repr[elem];
repr[elem] = r;
elem = h;
}
return r;
}
void union(int k1, int k2)
{
k1 = find(k1);
k2 = find(k2);
if (k1 != k2) repr[k1] = repr[k2];
}
}
class UnionFindTest
{
public static void main(String[] args)
{
UnionFind uf = new UnionFind(100);
uf.union(0, 1);
uf.union(1, 2);
uf.union(2, 3);
uf.union(1, 4);
System.out.println(uf.find(3) == uf.find(4));
System.out.println(uf.find(0) == uf.find(5));
System.out.println(uf.find(3) == uf.find(4));
}
}
===
You start with an empty data structure, that is where every ball is in a
group by itself. Then you iterate over every ball in the field and look at
all its neighbours. For every neighbour of the same color (you used the
numbers 1..6 for this, I'll call it color) you merge the groups with a
union(ball1,ball2) call. When you have done this for the entire field, you
have found all groups: for every ball the representant returned by the
find(ball) call is a ball number that uniquely represents the group that ball
is in.
Now you can count the number of balls in each group: take an array the size
of the number of balls on the screen and zero it out. Then iterate over every
ball, asks its group representant and increase the counter for that
representant. Once you have done this for all balls, the counters beloning to
representants contain the number of balls in that group and the counters
belonging to other balls are still zero.
Now iterate through the balls one last time, for every ball look up its
representant, then look up the group size in the counters array. If group
size >= 3, the ball should be removed.
I think it's best to program the algorithm in a language like Java, Pascal or
C first before you translate it into assembly. I think it's possible to merge
the first two iterations: the calculation of the representants and the
counting of the group size. If you need the performance, you can try that
optimization.
I hope I explained it well enough. It's not that complicated, but it's not
trivial either. If you have any questions, please ask.
Bye,
Maarten
--
For info, see http://www.stack.nl/~wynke/MSX/listinfo.html
