Pete Holland <petehollandjr@xxxxxxxxx> wrote:
>The computer needs to keep track of, among other things, what all the
>cards are in the deck of cards, the discard deck, the four stacks you
>start with the aces, and the seven stacks you start the game with.
>Take the last stack, the one with seven cards, one up, six down at the
>start. I'm thinking I'll need a pair of memory cells for each card,
>one to tell the denomination, the other to tell what suit it is.
Erik Mooney gave some good advice, some things that hadn't occurred
even to me, but I'm not sure I followed his math...
So, here's a scheme that I THINK only uses 69 bytes -- it's a little
wasteful, but doesn't require much "dynamic" adjustment. If you're a
little more wasteful you can still do it in 85 bytes...
Basically, since there are only four suits, you only need two bits
to represent them. Example:
00 = hearts
01 = diamonds
10 = clubs
11 = spades
Note that the first bit gives you the color, which might come in handy
later.
You've only got 13 cards per suit, so there's another four bits you need:
0001 = Ace
0010 = 2
...
1001 = 9
1010 = 10
1100 = Jack
1101 = Queen
1110 = King
Each card is in the form SSNNNN (suit, number), which requires only
6 bits per card to uniquely identify it.
Note that I've done some weird things here as far as the encoding...
But, this way, you know a card is a face card if the first two bits
are both 1s, and the number cards have values which are the actual
numeric values. (Hmm, actually, this would work better for black-
jack, wouldn't it?).
So, we've wasted 3 combos (0000, 1011 and 1111 -- but we can use
these later), and we've wasted two bits out of each byte (if we
don't waste them we move from 85 bytes required down to 69), but
we're far ahead of using two bytes per card!
Now it comes to how to use the shortened space... (Erik gave some
GREAT ideas about unseen cards).
First, though it's a little wasteful, why not start out by writing
the whole deck into memory randomly so we have a shuffled deck?
The good thing is, this preserves the shuffled order for later.
This uses either 52 bytes, or if we compress via the scheme below
only 39 bytes:
As we only need 6 bits of every byte, we can overlap the cards in
memory, every four cards in three bytes:
AAAAAABB BBBBCCCC CCDDDDDD EEEEEEFF FFFFGGGG GGHHHHHH
IIIIIIJJ JJJJKKKK KKLLLLLL MMMMMMNN NNNNOOOO OOPPPPPP
QQQQQQRR RRRRSSSS SSTTTTTT UUUUUUVV VVVVWWWW WWXXXXXX
YYYYYYZZ ZZZZaaaa aabbbbbb ccccccdd ddddeeee eeffffff
gggggghh hhhhiiii iijjjjjj kkkkkkll llllmmmm mmnnnnnn
oooooopp ppppqqqq qqrrrrrr sssssstt ttttuuuu uuvvvvvv
wwwwwwxx xxxxyyyy yyzzzzzz
Once we've actually used a card from the pile, write back a 000000
to indicate an empty spot (i.e. no card). (If we're wasting space
we can use the leading bit to indicate card or no card, so we'd
write 11001110 for the King of Hearts (KH) and 00000000 for an
empty slot). We can skip these spots when going through the deck.
If need be, you could compress the deck later on to save traversal
time with a low number of cards in the deck, but it's probably
unnecessary.
Similarly, we need to keep 4 bytes for the ace piles, and
we can comress this into 3 bytes if we desire:
HHHHHHCC CCCCDDDD DDSSSSSS
Actually, we can compress this to 2 bytes if you need the extra
by merely making each pile in order represent a particular suit
to begin with:
(HH CC DD SS)
HHHHCCCC DDDDSSSS
Remember, this takes advantage of the fact that you ONLY have to
keep track of the top card in each pile (or a 000000 if it's still
empty) -- the cards below are out of play, and if you put in a
cheat that allows the user to put the top card back into play, you
KNOW what the card underneath it will be, so you don't have to
store it.
For the build piles, Erik pointed out that you can draw these out
randomly from the deck at the point they are uncovered, instead of
actually tracking them all along... This is sound thinking. Once
they're drawn out of the deck, they're replaced by a 000000 there
anyway, so they don't screw up the draw order.
Now, we still need to keep track of the up cards... Another trick
Erik mentioned was that we only need to keep track of the SUITS of
the cards underneath the top. So, we need 7 bytes for the top
cards if we waste space (only 6 bytes if we don't), and a further
21 bytes (as I'll describe below) for the rest of the up cards.
The seven build piles are:
11111122 22223333 33444444 55555566 66667777 77XXXXXXX
The Xs show that we've again wasted some space, but in truth, we're
going to be using that somehow anyway. I would either use that
space (or another byte in the uncompressed scheme) to be a pointer
into the deck to indicate the card on top (if XXXXXX = 000000, there
are no more cards in the draw pile and no more build pile down cards,
so you can stop going through the deck anymore).
Now, as to the up cards below the top... The largest a stack can ever
be is 13 cards, and since we're already tracking the top card separately,
we only need to store 12 suits underneath. Though it's more wasteful
than doing this dynamically, let's just use 3 bytes for each stack.
We go in order and terminate with a duplicated suit, or for a max stack,
when we're at the end of those 3 bytes.
For instance, if our stack was 7C, 6H, 5S, 4D, we have 010100 in the
build pile top card array above, and an associated list of 11001010
(that's SHCC, the CC -- clubs duplicated -- means you're at the bottom
up card).
The maximum stack KH, QS, JD, 10C, 9H, 8C, 7D, 6S, 5D, 4C, 3H, 2C, AH
has 000001 in the build pile top card array, and a suit list of:
00110110 00100111 01100010
If you put the ace on the ace pile, then it must be adjusted to have
100010 in the build pile top card array, and a suit list of:
00110110 00100111 01100000
In this case, we've duplicated the 3H suit so we know that the list
ends there. Let's say we now add the AD to the 2C. We change the
top card to 100001 and we traverse our suit list until we come across
the duplicated value and write the 2C back there (from the top card
position) to give us:
00110110 00100111 01100010
This assumes we've checked that it's a valid move first, of course...
So, our byte counts are:
wasteful compressed
draw pile 52 39
ace piles 4 3
build piles 7 + 21 + 1 6 + 21
---------- ----------
total bytes 85 69
Not too bad, eh?
I think either scheme gives plenty of room for other variables and
a stack if we need it... Plus, all of our memory used in these
schemes is static, so there's no need to waste cycles updating it
dynamically.
>That's the problem for Solitaire, and it gets more complicated
>with a game like Columns. To make a long idea short, I am envisioning
>a series of 208 registers, two spots for each square in the 8 by 13
>well. One of the pair would tell if there is a jewel there, the other
>will denote it's color.
Won't go into much detail here, but as Erik pointed out, there's no
need to waste memory to have a separate flag that a spot is empty --
use a 0 color value to indicate there' no jewel there. How many colors
are there in Columns anyway? If there are only 6, plus the flashing
jewels, you can encode like this:
000 - empty
001 - blue
010 - red
011 - green
100 - yellow
101 - white
110 - purple
111 - flash
You MAY have to go to 4 bits if you use more colors, but that's still
two jewels per byte, so for a well of 8x13, we can do it in 104 spots =
52 bytes, or if 6x13 the way others have recollected, 78 spots = 39
bytes; if you can encode the colors in 3 bits, you can compress further,
similarly to the cards above, only this time 8 spots into 3 bytes, so
our counts above would be 8x13 in 39 bytes, or 6x13 in <30 bytes:
AAABBBCC CDDDEEEF FFGGGHHH
...
(Hmm, 8 spots in three bytes... that's a 3 x 13 byte array, which makes
bookkeeping mildly easy for the 8-spot-wide well; with 4-bit color, it
doesn't matter if it's 6 or 8 spots wide, we can make a nice N x 13 array
no matter what).
Note that you'd keep track of the falling piece separately; this scheme
only covers what's static in the well. Since the flashing jewels basically
take out colors as a "wild card", you probably don't need to encode the
flash state in the scheme above, giving you an extra color if you need it.
(To be more clear, the flash picks a color around it randomly when it
stops, and at THAT point would have a real color value rather than the
flash state).
>Since the idea is to match the colors in three in a row or more, all I
>can imagine is the computer comparing each individual square in each of
>four directions by it (Starting with the left jewel on the row, it would
>move right, comparing the jewel on the immediate right, right-down, down,
>and down-left.) If it registers a match, it will check the next one in
>that line to see if there are three of more in a row.
> This has me concerned that it will slow the computer down as it
>checks all the jewels.
Yeah, that could be a slight bugger, though when a piece stops falling,
at first you ONLY have to check (in eight directions) all the spots around
it, not the whole board, as Erik also mentioned (though after that you do
need to update it all; er, not quite... see below).
>I'm also wondering how I would get the computer to keep it's directions
>straight ("No, no! Go to the next in line, don't change direction!")
This shouldn't be TOO hard...
>and how it would tell what spots had matching jewels that need to be
>removed.
This is a little tougher... I think you'd make a list (on the stack)
of all locations that need to be removed, and perhaps a second list of
jewels left hanging (again by location). Start at the dropped piece's
top jewel, and look up two locations (since if there were three, they'd
be gone by now; also this is a trivial case, since we know there can't
be anything above the top of the dropped piece, but it makes things
easier later). If the second and first, or just first, match the dropped
color, you'll need to note that and keep looking for more jewels of the
same color; if the count is right, add them to the list of jewels to be
deleted. Do this for upper-left, left, and lower-left; then repeat for
the middle and bottom jewels in the dropped piece. Then erase all the
pieces on the list (i.e. change their color values to 000 for empty).
If you made a list of pieces left hanging, you can know drop all of
these now and then do the "dropped piece" check for each of them. In
this way you might not have to check the entire board -- it'll save
some time when there are few pieces stranded, but it will possibly
take MORE time with the list keeping when a lot of pieces are stranded.
>I can't just blank those memory locations, because the scoring is
>different if six jewels are removed (two sets of three) or six jewels
>are removed (six of the same color).
I think the scheme above let's you account for this, though I'm not
giving much help as far as an actual implementation goes...
>Of course, once those are removed, it checks for matches once the
>jewels fall to fill in the holes.
As above.
>I'm having trouble seeing how to make this work for the Atari without
>slowing it down, screwing up the count, whatever.
Well, screwing up the count is a bug, slowing it down is a design issue.
Slightly different issues.
>Is this the best, most efficient way to do it?
Well, most efficient isn't ALWAYS the best, since if the efficient route
uses too much RAM, it'll never be best.
>If not, what is?
I don't know if we've come up with a really good way to do it yet or not,
but you've got some more hints. Any more questions?
//*================================================================++
|| Russ Perry Jr 2175 S Tonne Dr #105 Arlington Hts IL 60005 ||
|| 847-952-9729 slapdash@xxxxxxxxxxxx VIDEOGAME COLLECTOR! ||
++================================================================*//
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
