Generating subsets

I’ve been reading “The Algorithm Design Manual” (Steven S. Skiena) recently and I have to share with you one of the chapters, just because it’s too cool.

In “The Witcher” we have the following problem: we’ve plenty of attack animations, most of them dynamic (ie, the character is moving forward) and not so many damage animations. Most of the attack consist of multiple hits. The problem is with synchronizing damage and attack animations (so that our opponent moves back roughly at same pace and similar distance as we move forward, playing his damage animations at the same time). Imagine animation with 3 hits, we can choose from 8 possible configurations of damage animations for that (not playing at all, playing for each hit, playing for hit 0 & 1, 0 &2, 1&2, 0, 1, 2). Basically, what we have to do here is generate all the possible subsets for given number of hits. I think that originally we simply played it for every hit. I’ve been experimenting with better system late night before some E3. I fixed all my bugs and couldnt be arsed to go home because testers could report back any minute. In the meantime I decided to tweak the combat and came up with this “subset” system. I couldnt find a way to generate subsets in an elegant way, tho. Finally, we ended with brute-force solution and subsets precalculated for max possible number of hits. Two years later I finally find an ultimate solution for this problem. The genius of this approach is that it looks at the problem from totally different angle. It doesnt try to “solve” it in some smart analytical way, it just exploits bit masks. We just count from 0 to 2^n-1 (n = number of hits). For each value we create mask and compose a subset of the items corresponding to “enabled” bits. Example solution:

void CollectSubsets(int n, std::vector<std::vector<rde::uint32_t> > &subsets)
{
    const rde::uint32_t maxMask = 1 << n;
    subsets.resize(maxMask - 1);
    int subset(0);
    for (rde::uint32_t mask = 1; mask < maxMask; ++mask, ++subset)
    {
        for (int i = 0; i < n; ++i)
        {
            if ((mask & (1 << i)))
                 subsets[subset].push_back(i);
        }
    }
}

Old comments

Mikola Lysenko 2008-06-03 21:44:10

There is a really neat extension to this idea. If you want to generate all of the subsets of a subset - such as the subsets of say, {0, 1, 3, 5} in {0 .. 7}, you can use a similar counting trick:
int m = set_to_bit_mask(s);
for(int x=m; x>0; x = (x - 1) & m)
{
visit(bit_mask_to_set(x));
}
visit(empty_set);
Where the function set_to_bit_mask converts a subset into a bit mask the function bit_mask_to_set does the opposite. The key idea is to use the effect of borrowing in subtraction to automatically toggle the next bit in the set.

therealremi 2008-05-28 14:23:50

“Basically, what we have to do here is generate all the possible subsets for given number of hits.”
Why? For a given number of hits (M) can’t you just randomly pick the number N of damage animations to play? And then for each damage animation pick the unique hit it is assigned to?

admin 2008-05-28 14:43:53

I knew I missed something :) Later I analyzed those configurations and chose set that looked the best (according to deviation from “natural” animation timings and displacements). Picking them randomly would look quite awful.
HarrierR: indeed, it’s similar. It’s funny because I’ve been using it as well in the past and never noticed it can be used for other problems as well (perhaps because it was always kinda “hardcoded” for 8 vertices for me).

HarrieR 2008-05-28 09:25:14

I’ve been using a variation of above for generating cube vertices:
for( int i=0; i<8; ++i )
{
cubeVertex[i].x = ( i & 1 ) ? bboxMin.x : bboxMax.x;
cubeVertex[i].y = ( i & 2 ) ? bboxMin.y : bboxMax.y;
cubeVertex[i].z = ( i & 4 ) ? bboxMin.z : bboxMax.z;
}
// yeah, my first comment on your blog ;-)