art with code

2010-12-26

The Space Campaign

Space Captain, First Galactic Baron, Royal Ring Knight, First Solar King and Third Moon Prince of the Space Planet New New Zealand, Second Master of the Holy Star Order, Imperial Great Lord of Space and Independent Space General, Sergeant Major Lieutenant Stanislaw Stanisgreat stood up from his space chair on the space deck to stare across the spacebow of the space ultrabattledestroyer HMS Stiff Upper Lip with his spacescope. There! In the distant depths of space, near the space planet of New South Macedonia, a blacker than black space cutter was cutting space towards the space merchant fleet sailing the space waves towards the space port of New North America. The weak, defenseless merchantmen were sitting in their space deckchairs just waiting to be picked off from space by the evil boat of space.

Space Captain Stanislaw cursed a terrible space curse under his space breath to no one in particular, which was just as well for there is no sound in space. He gave the order to turn the space wheel of the space ultrabattledestroyer towards the space cutter, hoist the main space sail to the space mast and blow the space horn to sound the space crew to readiness. The space sails billowed in the space wind and started the ultrabattledestroyer towards the nefarious space cutter at infinite velocity. Even at infinite velocity, Stanislaw knew he'd be too late to stop the space cutter from sinking the space merchantmen into the depths of space and feeding their space crews to the space fishes.

An endless instant later, the space ultrabattledestroyer closed to engagement range from the space cutter and turned its right side towards the dastardly space cutter. Stanislaw ordered a full thirty-fold space broadside alpha strike to be fired at the space cutter at his mark. Mark! The crewmen of the space cutter shouted in great alarm at the ultrabattledestroyer but their shouts were never heard in space before the report of the space guns of the ultrabattledestroyer drowned them out under a terrible booming fury of space.

Millions of space cannonballs flew across space in slow motion, tearing gaping space holes in the space sails of the space cutter. One space cannonball hit the cutter right in the middle and split it in two. The mangled space cutter turned its cowardly tail and tried to run across space to the space asteroid field in the middle of space to escape the space pursuit of the space ultrabattledestroyer.

Too bad for the space cutter, the ultrabattledestroyer had its space sensors deployed in space, giving them full knowledge of space. Space Captain Stanislaw set his magnificent space plan in motion and deployed a single space rowboat right in the space path of the space cutter. The space rowboat was carrying a deadly cargo of space gunpowder, which the spacemen aboard it set to explode with a slow-burning space fuse. The spacemen jumped to space off the space rowboat and space swam back to the welcoming space arms of the space ultrabattledestroyer.

The space captain of the space cutter, Shining Diamond Vizier Democratically Elected Big Cat Corporate Chief Communist Politruck Liberal Nazi Warlord Space President of Badmanistan, General Colonel of Three Stripes and One Star Badstar Badmanis noticed the space rowboat a mere picosecond too late. His bellowed order to space duck was cut short in space as the space rowboat exploded with thunderous space roar and shot three million nuclear space lightnings everywhere in space, shattering the space cutter into five trillion pieces. An endless shower of space blood colored the space red. That was one space cutter that would not cut space again, thought the entire space crew of the space ultrabattledestroyer in unison in space.

Space Captain Stanislaw Stanisgreat turned to face his space crew and congratulated them for a space job well done. His lily-white space suit and space tophat had been splattered crimson from the space blood and his visage was like that of a butchered space goat. The Space Admiral Peerless Thirty-fold Queen Emperor, Defender of Space, Attacker of the Realm, First Dame of Spacistan, Royala Bigshotikins climbed the ladder aboard the ultrabattledestroyer from her million-mile long gigaspacehyperdreadnoughtcarrier space flag ship and bestowed the space medal of Biggest Imperial Glory of Space upon the beaming Space Captain Stanislaw Stanisgreat. Stanislaw fought back a single space tear of infinite boundless space pride and saluted for hours at the Space Admiral.

THE END
THESE BOOKS MAKE ME ANGRY PUBLISHING, LTD.

2010-12-19

WebGL Orrery


I wrote a small WebGL orrery a month back or so, using planet and orbit data from Wikipedia. The orbits came out a bit wrong (planet positions on orbits are wrong, the planet rotation axis rotates along the orbit, planets velocities are constant, the orbits / axes may well be flipped somewhere), but it's a passably "realistic" orrery. Well, realistic apart from the whole having to scale down orbits by a factor of thousand to make the planets visible -thing. With 1:1 orbits, the planets are smaller than a pixel in size when viewed from other planets and the sun is about a pixel in diameter when viewed from Neptune.

It's quite extensible too, it should be possible to add in all the moons just by filling in their data. The coordinate system and z-buffer aren't accurate enough to do anything fancy like a spaceship sim with 1:1 orbits though :)

2010-12-01

A deck of cards

If not for the order property, you could cram a deck of cards into a 64-bit int. Though if you had a RNG cyclical in full_deck_size, that'd work to preserve the order property. Which would be enough for poker and other stackless or write-only stack card games.

With the cyclical RNG you could pop a card off a full deck in O(1). With incomplete decks (that is, a deck with non-RNG-generated cards removed) you'd need to go through random cards until the generated card is in the deck. The worst-case time-complexity for popping all cards off an incomplete deck would be O(full_deck_size) and the average complexity for popping one card off an incomplete deck would be O(full_deck_size/incomplete_deck_size). Anyhow, incomplete decks would be as fast or slow as full decks, with an extra existence check slowing them down a bit further. The RNG would need a seed with log2(fac(full_deck_size)) bits, so log2(52!) = 226 bits for a deck without jokers.

A naive version of the RNG would be to generate a random number between 0 and 52!-1, then convert the number into 52 digits in factorial base. Divide first by 51!, the result is the first card. Divide the remainder by 50!, the result is the second card (note that you have to remove the first card from consideration for the second card index). Continue dividing the remainders until you have 52 cards. Or just generate a shuffled 52 element array of numbers and go through that :P

... I should get back to work now.

Source

#include <inttypes.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef int64_t card_mask;
typedef int8_t card;

typedef struct deck {
card cards[55];
int8_t length;
card_mask mask;
} deck_t;

#define suit_size 13

static const card_mask hearts = suit_size*0;
static const card_mask spades = suit_size*1;
static const card_mask clubs = suit_size*2;
static const card_mask diamonds = suit_size*3;
static const card_mask jokers = suit_size*4;

static const char* suits[5] = {"Hearts", "Spades", "Clubs", "Diamonds", "Jokers"};
static const char* ranks[13] = {
"Ace", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
"Jack", "Queen", "King"
};

card_mask remove_cards_from_mask(card_mask deck, card_mask cards)
{
return deck & ~cards;
}

card_mask add_cards_to_mask(card_mask deck, card_mask cards)
{
return deck | cards;
}

card_mask query_mask(card_mask deck, card_mask cards)
{
return deck & cards;
}

card_mask mask_of_card(card c)
{
return (card_mask)1 << (card_mask)c;
}

card card_for_suit_and_rank(card_mask suit, card_mask rank)
{
return suit + rank;
}

int deck_initialize(deck_t *deck, int jokers)
{
card c = 0;
if (jokers < 0 || jokers > 3)
return 0;
deck->length = 52 + jokers;
deck->mask = ((card_mask)1 << (card_mask)deck->length)-1;
for (c=0; c<deck->length; c++) {
deck->cards[c] = c;
}
return 1;
}

void deck_clear(deck_t *deck)
{
deck->length = 0;
deck->mask = 0;
}

void deck_shuffle(deck_t *deck)
{
int8_t i,j;
card tmp;
for (i=deck->length-1; i>0; i--) {
j = rand() % (i+1);
tmp = deck->cards[j];
deck->cards[j] = deck->cards[i];
deck->cards[i] = tmp;
}
}

card_mask deck_query_mask(deck_t *deck, card_mask m)
{
return query_mask(deck->mask, m);
}

card_mask deck_query_card(deck_t *deck, card c)
{
return deck_query_mask(deck, mask_of_card(c));
}

card_mask deck_query_deck(deck_t *deck, deck_t *deck2)
{
return deck_query_mask(deck, deck2->mask);
}

int deck_add(deck_t *deck, card c)
{
card_mask m = mask_of_card(c);
if (query_mask(deck->mask, m)) {
return 0;
} else {
deck->mask = add_cards_to_mask(deck->mask, m);
deck->cards[deck->length] = c;
deck->length++;
return 1;
}
}

int deck_remove(deck_t *deck, card c)
{
int8_t i=0, j=0;
card_mask m = mask_of_card(c);
if (!query_mask(deck->mask, m)) {
return 0;
} else {
deck->mask = remove_cards_from_mask(deck->mask, m);
for (i=0,j=0; i<deck->length; i++) {
if (deck->cards[i] != c) {
deck->cards[j] = deck->cards[i];
j++;
}
}
deck->length = j;
return 1;
}
}

card deck_pop(deck_t *deck)
{
card c;
if (deck->length < 1) {
return -1;
} else {
deck->length--;
c = deck->cards[deck->length];
deck->mask = remove_cards_from_mask(deck->mask, mask_of_card(c));
return c;
}
}

const char* suit_string(card s)
{
if (s >= suit_size*5)
return "Invalid";
return suits[s / suit_size];
}

const char* rank_string(card s)
{
return ranks[s % suit_size];
}

void print_card(card c)
{
printf("%s of %s\n", rank_string(c), suit_string(c));
}

void print_deck(deck_t *deck)
{
int8_t i;
printf("Deck %p:\n", (void*)deck);
for (i=0; i<deck->length; i++) {
print_card(deck->cards[i]);
}
}

void print_mask(card_mask m)
{
int i;
const char* symbols[5] = {"♥", "♠", "♣", "♦", "☻"};
for (i=0; i<64; i++) {
if (i%suit_size == 0) printf(" %s", symbols[i/suit_size]);
if ((m>>i) & 1) putchar('#');
else putchar('.');
}
putchar('\n');
}

int main()
{
int i=0;
deck_t deck, hand;
card c;
srand(time(NULL));
deck_initialize(&deck,2);
deck_initialize(&hand,0);
deck_clear(&hand);
deck_shuffle(&deck);
printf("Deck %p has %d cards and mask %ld.\n", (void*)&deck, deck.length, deck.mask);
print_mask(deck.mask);
for (c=0; c<54; c++) {
if (!deck_query_card(&deck, c)) {
printf("Error: Deck doesn't have a card.\n");
print_card(c);
}
}
printf("Hand %p has %d cards and mask %ld.\n", (void*)&hand, hand.length, hand.mask);
print_mask(hand.mask);
for (c=0; c<54; c++) {
if (deck_query_card(&hand, c)) {
printf("Error: Hand has a card it shouldn't have.\n");
print_card(c);
}
}
deck_remove(&deck, hearts);
if (deck_query_card(&hand, hearts))
{ printf("Error: Hand has a card it shouldn't have.\n"); print_card(hearts); }
deck_remove(&deck, spades);
if (deck_query_card(&hand, spades))
{ printf("Error: Hand has a card it shouldn't have.\n"); print_card(spades); }
deck_remove(&deck, clubs);
if (deck_query_card(&hand, clubs))
{ printf("Error: Hand has a card it shouldn't have.\n"); print_card(clubs); }
deck_remove(&deck, diamonds);
if (deck_query_card(&hand, diamonds))
{ printf("Error: Hand has a card it shouldn't have.\n"); print_card(diamonds); }
printf("Deck %p has %d cards and mask %ld.\n", (void*)&deck, deck.length, deck.mask);
print_mask(deck.mask);
for (i=0; i<5; i++) {
c = deck_pop(&deck);
print_card(c);
deck_add(&hand, c);
}
printf("Deck %p has %d cards and mask %ld.\n", (void*)&deck, deck.length, deck.mask);
print_mask(deck.mask);
printf("Hand %p has %d cards and mask %ld.\n", (void*)&hand, hand.length, hand.mask);
print_mask(hand.mask);
print_deck(&hand);
if (deck_query_deck(&deck, &hand) || deck_query_deck(&hand, &deck)) {
printf("Error: Deck and Hand intersect.\n");
} else {
printf("Deck and Hand are disjoint.\n");
}
for (i=0; i<hand.length; i++) {
if (deck_query_card(&deck, hand.cards[i])) {
printf("ERROR ");
} else {
printf("OK ");
}
}
printf("\n");
for (i=0; i<deck.length; i++) {
if (deck_query_card(&hand, deck.cards[i])) {
printf("Error: Found a card in Deck that is in Hand.\n");
print_card(deck.cards[i]);
}
}
print_card(suit_size*5);
return 0;
}

Output

$ ./a.out
Deck 0x7fff98907250 has 54 cards and mask 18014398509481983.
♥############# ♠############# ♣############# ♦############# ☻##..........
Hand 0x7fff98907210 has 0 cards and mask 0.
♥............. ♠............. ♣............. ♦............. ☻............
Deck 0x7fff98907250 has 50 cards and mask 18013848686551038.
♥.############ ♠.############ ♣.############ ♦.############ ☻##..........
Eight of Hearts
Seven of Clubs
Ten of Diamonds
Six of Diamonds
Nine of Hearts
Deck 0x7fff98907250 has 45 cards and mask 17714777228828286.
♥.######..#### ♠.############ ♣.#####.###### ♦.####.###.### ☻##..........
Hand 0x7fff98907210 has 5 cards and mask 299071457722752.
♥.......##.... ♠............. ♣......#...... ♦.....#...#... ☻............
Deck 0x7fff98907210:
Eight of Hearts
Seven of Clubs
Ten of Diamonds
Six of Diamonds
Nine of Hearts
Deck and Hand are disjoint.
OK OK OK OK OK
Ace of Invalid

Blog Archive