[gameprogrammer] Let's play... Name That Algorithm! :)
- From: "Mike Gillissie" <Niyoto@xxxxxxxxxx>
- To: <gameprogrammer@xxxxxxxxxxxxx>
- Date: Mon, 17 Aug 2009 20:03:49 -0400
(Note - I may have accidentally sent this early - probably a key combination
that hates me... trying again...)
Hi folks!
I'm in the middle of a situation - I have a problem I'm trying to solve, and it
looks like the sort of problem that has a very nice algorithm named after some
fine studious person. Here's the skinny:
At this point in my code I have a square boolean array that's used to indicate
"compatibilities" - so if I have 5 units and I calculate each one's
compatibility with each other unit (as either a Yes or a No), I might have
values something like:
compat[0][1]=true;
compat[0][3]=true;
compat[1][2]=true;
compat[1][3]=true;
compat[1][4]=true;
compat[2][4]=true;
compat[3][4]=true;
A couple of design notes - I'm showing this as a 2-dimensional array for
clarity - it's actually a one-dimensional array, but is easier to describe this
way. Second note - I only ever work "upwords" in my indexes - so while [0][1]
is true, indicating that unit 0 and unit 1 are compatible, I never set [1][0]
to true.
My end goal is to build an array/collection of ALL possible compatible
combinations from this array. So from the above, I'd expect to be returned
something like:
0 1 3
0 3
1 2
1 3
1 4
2 4
3 4
(ie. 0 1 3 because all three are mutually compatible).
So my question is, has anybody come across a common algorithm that describes
this problem? I've got a recursive approach that works, but my current
"nightmare" scenario contains over 5000 units, and takes a solid hour to
calculate - clearly not fun... ;)
Thanks in advance, and let me know if I wasn't clear in my description, which
is quite likely...
-Mike
Other related posts:
