[gameprogrammer] Re: Let's play... Name That Algorithm! :)

Hi Kevin - thanks for your responses! I'm going to try your Working List / 
Completed List idea to see how it fits. :)

As for the combinations:

    0  1  2  3
0 [*, 1, 0, 1]
1 [*, *, 1, 
1]
2 [*, *, *, 0]
3 [*, *, *, *]


Using the same truth-table as before - the "truth" in this case is that unit 0 
is compatible with units 1 and 3. Unit 1 is compatible with units 2 and 3. My 
goal is to determine all possible combinations of units 0, 1, 2 and 3 where 
each unit is compatible with each other unit. Thus 0-1-2-3 is not a possibility 
because 0 and 2 are incompatible. As are 2 and 3.

My optimal solution would be a set of all combinations of the three - and 
thinking further, it's best that I also exclude any combinations which are 
simply sub-sets of longer combinations (ie. if I have 0-1-3  as a combination 
I'd prefer to exclude 0-1 and 0-3 as reported results).

For further reference, here's the approach I'm currently using - it's 
implemented in Java at the moment - I've gone through a few versions of the 
function trying to improve performance. :)

CALLING FUNCTION:
...

for (int x = 0; x < uIndex; x++)
{
treeArray[0] = x;
buildCombinationTree(x, 1);
}

...

CURRENT APPROACH:
private void buildCombinationTree(int startAt, int level) 
{
// atTheEnd indicates that we can't walk further along the current branch, so 
we store the current combination

boolean atTheEnd = true;
int check=startAt*uIndex;
int x=startAt+1;
// Based on the value we're currently looking at, skip all subsequent 
incompatible values

while(x<uIndex && incompatible[check+x])
x++;

// uIndex is the unit count
while (  x < uIndex )
{
/* Check the current element against previously identified members of the 
combination.

* If compatible, the current index will be stored in position 'level' - because 
of the "skip" while loop above, I know that

* this value will be compatible with the one at level-1. Thus I only need to 
start checking at level-1 down to 0 (I've tried

* both directions, and it seems to be faster when checking backwards)

*/

if (compatibleBackwards(x, level-2))
{
// Another 'observational optimization' - it seems faster to test the condition 
than it is to just assign the variable. Odd.

if (atTheEnd)
atTheEnd = false;
// Store the current index within the 'working tree' (defined globally)

treeArray[level] = x;
// Recurse

buildCombinationTree(x, level + 1);
}
// Finally, skip ahead to the next non-incompatible index 
for (x++; x<uIndex && incompatible[check+x]; x++);
}
// If no more compatible units were found, store the current combination and 
return
if (atTheEnd)
{
storeCombination();

}
}
private boolean compatibleBackwards(int newIndex, int level)
{
while(level>=0)
if (incompatible[treeArray[level]*uIndex+newIndex])
return false;
else
level--;
return true;
}




________________________________
From: Kevin Jenkins <gameprogrammer@xxxxxxxxxx>
To: gameprogrammer@xxxxxxxxxxxxx
Sent: Monday, August 17, 2009 11:59:16 PM
Subject: [gameprogrammer] Re: Let's play... Name That Algorithm! :)


> Now your final processing list sets are [0,1,3] and [2]
> 
> So take the combination sets of those, which are:
> 0-1-3, 0-1, 0-3, 1-3, and 2

Dang, hit enter too fast. Since you're including single vertices in the output, 
the actual combination set is

0,1,2,3 (everything connects to itself in this case)
0-1-3 (fully connected mesh, of 3 vertices)
0-1
0-3

Not sure why you excluded some of those cases. Maybe I misunderstand the 
problem.

---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts: