[gameprogrammer] Re: Let's play... Name That Algorithm! :)
- From: niyoto@xxxxxxxxxx
- To: gameprogrammer@xxxxxxxxxxxxx
- Date: Tue, 18 Aug 2009 05:16:13 -0700 (PDT)
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:
