[gameprogrammer] Re: Let's play... Name That Algorithm! :)
- From: "Mike Gillissie" <Niyoto@xxxxxxxxxx>
- To: <gameprogrammer@xxxxxxxxxxxxx>
- Date: Mon, 17 Aug 2009 22:09:38 -0400
I did just an excellent job of not completing my first attempt at an email -
hopefully my second attempt came though to completion... ;)
The Karnaugh Map thingie looks pretty interesting, though admittedly I'm going
to have to take a closer look at its scalability to 5000-ish values
(squared-ish)... thanks for sharing! :)
My ultimate goal is to determine all combinations of mutually compatible units
based on the truth table.
From Vince's example,
0 1 2 3
0 [1, 1, 0, 1]
1 [1, 1, 1, 1]
2 [0, 1, 1, 0]
3 [1, 1, 0, 1]
In this case, starting with element 0, I'm currently building a tree using a
recursive function. I see that 0 and 1 are compatible - I recurse down one
level and see if 0-1 is compatible with 3 (the next compatible element to 0) -
since all three are mutually compatible (0-1, 0-3 and 1-3) my first "stored"
combination is 0-1-3.
From 1, I look at 1-2. I recurse down to see if 1-2-3 is compatible - I find
that it's not since 2-3 are not compatible. So I end up storing the
combinations 1-2 and 1-3.
Finally, since 2-3 is not compatible, I end up storing 2 and 3 as separate
"combinations" (albeit combinations of 1 element).
My final set from the Vince-List:
0-1-3
1-2
1-3
2
3
My code actually eliminates the "south-west" portion of the matrix, since I
will only compare against higher-value indexes from my starting point. Well
said, Mike... yeesh... ;)
0 1 2 3
0 [*, 1, 0, 1]
1 [*, *, 1, 1]
2 [*, *, *, 0]
3 [*, *, *, *]
While slightly complicating my indexing, it more than doubles my capacity.
Looking at this, even considering a 5000x5000 truth table (stored as a
4999+4998+4997...3+2+1 one-dimensional array), it just looks like something
that a more experienced algorithmagician must have solved nicely in the past...
;)
My apologies for the half-email that I started this with - Outlook Express
probably does a send when you hit some combination of Control/Shift/Enter, or
if you're trying to impress your betters... =/
Thanks guys! :)
-Mike
----- Original Message -----
From: Alan Wolfe
To: gameprogrammer@xxxxxxxxxxxxx
Sent: Monday, August 17, 2009 8:24 PM
Subject: [gameprogrammer] Re: Let's play... Name That Algorithm! :)
I'm not sure 100% what you are trying to achieve but Karnaugh maps might help
you
http://en.wikipedia.org/wiki/Karnaugh_map
they let you take an array of bools and simplify it into groups. They are
used on 2d arrays mostly to take boolean output and try to come up with the
simplified boolean equation to make that output, but i think they could work
for what you want too, and they deffinately work on both 1d and 3d arrays (and
higher) as well :P
On Mon, Aug 17, 2009 at 5:13 PM, Vince <uberneen@xxxxxxxxx> wrote:
--- On Mon, 8/17/09, Mike Gillissie <Niyoto@xxxxxxxxxx> wrote:
> From: Mike Gillissie <Niyoto@xxxxxxxxxx>
> Subject: [gameprogrammer] Let's play... Name That Algorithm! :)
> To: gameprogrammer@xxxxxxxxxxxxx
> Date: Monday, August 17, 2009, 11:57 PM
>
>
>
>
>
>
>
> 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][1]=true;
>
> compat[0][1]=true;
>
> compat[0][1]=true;
>
>
I'm looking three redundant statements here.
If I'm reading your description correctly, compat might look more like
this: (adjust 0, 1 for true, false if you please)
0 1 2 3
0 [1, 1, 0, 1]
1 [1, 1, 1, 1]
2 [0, 1, 1, 0]
3 [1, 1, 0, 1]
If you're testing to see if something along X is compatible with something
along Y, you could
#define OPTION1 0
#define OPTION2 1
and so on, then you could check with any pair like so :
iscompat = compat[OPTION1][OPTION2]
Is that what you're after?
Vince~
---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html
Other related posts:
