Monthly Archives: July 2006

Transactional Board Game

A few months ago, I wrote about an idea for a game based on transactional moves. I just played a board game tonight (something about vampires) at GameDev which used the lag effect well. It sparked that idea again, so I fleshed out the details and made a game. Namaste and I played a round of it, and it is pretty good in concept. It needs a few tweaks, and I will discuss the way we played it along with the tweaks I am considering. Overall it was a deep strategic game.

There are two players (I plan on generalizing to more) who play on a graph. The graph we used had about 45 nodes and 40 edges. Each edge was marked with a unique identifier (such that starting from any node, you could uniquely identify an edge connected to that node; I used numbers from 1 to 5, nothing higher was necessary). I wish I could show the board, but I don’t have a camera. Each player had three “supply centers” (a la Diplomacy) and three units. Supply centers were special nodes which lay at the coasts of the graph.

On each turn, a player could move one unit to a connected node. No two units can occupy the same node; moving in to a node where there is already a unit is illegal. You may move into supply centers that you own, but not that the opponent owns. In order to conquer a supply center, you must attack with strength greater than their defensive strength — Diplomacy style with support orders. I’ll cover the details of that in a bit.

The interesting twist: each player keeps a private pad of paper. On your turn you write down an order on your paper identifying a move (for example, I would write A3 which meant unit A moves over edge 3 connected to its current node). This represents a command in a “transaction”. After you have written down a move, you have the option of “committing” all the moves you have thus far written: you scratch them out on the paper and execute them all in a single turn, in order. However, if the opponent commits a transaction which involves (either enters or leaves) a node which your transaction involves, you scratch out all the moves in your transaction. You lose those turns. You may also voluntarily abort an entire transaction. Of course, a transaction which is just a single move and a commit need not be written down.

To attack a supply center which is defended with strength n (how that is done I wll say in a moment), you move n+1 (or more) of your units adjacent to it. Then, for all but one unit, you write a “support” order in a transaction (if this is committed before the final attack is made, the support orders do nothing). For example, “AS3″ meant “unit A supports the attack against the node over edge 3″. After all the support orders are complete, a move into that supply center may be issued into the transaction. When the transaction is committed, the move is made and the player who made the move takes control of that supply center.

The defensive strength of a supply center starts at 1. If there is a unit inside the supply center, add 1. For every unit belonging to the owner of the supply center adjacent to it (connected by exactly one edge), add 1.

A special case: when a player gets down to one supply center, he loses a unit and his opponent gains a unit. The player who has 1 center selects a unit, which will from now on be controlled by the opposite player. If the losing player gains another center, then the same unit switches back to his control.

That’s how Namaste and I played it. It might have been the level design (very important), but the game felt a little bit “rigid”. It was too easy to trap units, and it was too easy to hold choke points. So I plan to add the ability to dislodge units (a la Diplomacy again), and also to make all supports automatic. So all you have to do to take a supply center or dislodge a unit is to have more adjacent units than the opponent does. This will make it harder to hold choke points. I also plan to make the graph a bit more dense: a larger edge/node ratio. This will make it easier to navigate the map, since one of the problems is that it took so long to get from one side of the map to the other; however I would still like an interesting topological structure, as opposed to a simple lattice. I also plan to add more units and possibly supply centers, since one of the problems was that it felt like you needed to engage your entire (three-unit) army to take a supply center, leaving you defenseless.

I plan on a networked computer implementation pretty soon. It should be pretty easy to write.

Images no. 2

Here is my third large improvisational piece. This is the longest one yet, measuring at about 50 minutes. I performed it in two acts, each without stopping. I meant to portray images starting from space down into the Earth’s core, some realistic, some fictional.

I am always trying to challenge myself with technical improvisational challenges; for example, today’s daily improvisation which is another step toward autonomy of my two hands. However, I would also like artistic challenges like this one. I know this blog doesn’t have that many readers; nonetheless I am opening it up to requests. Send me a message (my email address can be found on my about page) with the title of a song. If the title paints a picture that I like, I will attempt to paint the same picture with an improvisation.

Without further ado, here is Images no. 2:

Act One

  1. Outer Space to the Stratosphere
  2. Clouds of Ice
  3. Thunderhead
  4. Sunshine Amid the Rain

Act Two

  1. Friday Night in the City
  2. The Coal Plant
  3. Descending the Rock Ceiling
  4. Chant of the Underground Beasts
  5. Song of the Earth

Two Dances

I haven’t been recording my improvs recently because my desktop’s hard drive feigned failure. That is, one day when I was working on it, my computer kept crashing. The third time it did this, a *click* sound came from the case. So I assumed that my hard drive was failing. And I don’t have any evidence to the contrary at the moment. However, my computer worked long enough today for me to record these improvs.

Today’s improv: ice dance, wood faerie dance.

Low-Overhead Weak Pointers

Abstract: The usual linked-backreference method of implementing weak pointers has awkward copying semantics and involves a linear time search whenever a pointer is deallocated. This entry describes a better weak pointer implementation method.

What is a weak pointer? Consider this C++ code:

    Foo* x = new Foo;
    Foo* y = x;
    delete x;
    cout << y;

This outputs the location at which a Foo was allocated, but that value is now as good as garbage, because that Foo was deallocated. It would be useful to have y automatically set to NULL so that code could check whether the object is still valid. A pointer that is set to NULL when its target is deallocated is called a weak pointer.

Weak pointers are usually implemented by storing a linked list in the target of locations that should be set to NULL when the object is deleted. Consider the bookkeeping of this implementation: whenever a pointer is copied, a new reference must be added to the list, and whenever a pointer is deallocated (eg. the pointer itself goes out of scope), the list must be searched in linear time to delete it from the list. That hurts. Obviously there are ways to speed it up, but the asymptotic bound is still there.

Here is my solution: First, set up a small object pool with entries that look like this:

    struct Entry {
        unsigned int age;
        union {
            void* ptr;
            int next;

Which is just the typical small object pool entry with an extra field: age, which is initialized to zero when the pool is created. If you don’t know what a small object pool is, then the next paragraph is for you!

A small object pool is a way of quickly allocating memory of predefined size. Most allocators today use this method for sufficiently small objects (say 64 bytes or less). You implement it by allocating a big array of Entrys, and initializing them to form a sort of linked list. That is, pool[0].next = 1; pool[1].next = 2; etc. This linked list forms a “free list”, a list of unallocated space. The pool also keeps track of the first free entry in the list (call it head), in this case 0. Then when it is asked to allocate some space, it allocates head, and then sets head to the next entry in the linked list: pool[head].next. When it is asked to deallocate a location, it sets that location’s .next to head and head in turn to that location. It’s just standard linked list calculations with a slightly clever twist, which gives you minimal space overhead and constant time allocate and delete.

Okay, so about this age field. A weak pointer, instead of storing a location in memory, stores an index into this pointer pool. A weak pointer also has an age field which refers to the age of the cell it is pointing to when the pointer was created. To access what the pointer is pointing to, you look up that index in the pool. To see whether the object has been destroyed, you check the pointer’s age against the cell’s age. If the two ages are equal, then the pointer is valid, otherwise the object has been destroyed while the pointer was referring to it.

To allocate a weak pointer to an object, first allocate a space in the pool. Set that space’s ptr field to the object, set the pointer’s index to the index of the new space, and set the pointer’s age to the new space’s age. When you delete the object, free it from the pool and increment that cell’s age field. If a new object is allocated there in the future, it will have a greater age so that the pointers to the old object won’t be fooled into thinking the new one is the old one.

This scheme is only guaranteed to work as long as you don’t allocate 2sizeof(int) times in the same location. While that is a huge number and it is unlikely that any real application would do that, it may be more likely than you think. If the weak pointers follow a cycle of alloc, delete, alloc, delete, then the same space is used over and over again and the rest of the pool is untouched. It is conceivable that you could do that four billion times. A solution is to check on deallocation whether an increment would rollover, and if so, invalidate that pool entry—never use it again. This creates a memory leak, however it would be so gradual (in the worst case, 8 bytes every 4 billion allocations on 32 bit machines) that it would be neglegible. I feel silly even addressing the memory leak issue.

If you’re writing this in C++ as I am, you’ll want to hide all this behind a pointer wrapper class. Either that or you’ll want to use the one I wrote. I will post a link as soon as I write it.

Jam with The Moment

Nolan recruited a new drummer, whose name I don’t recall. He has experience with trance, as one can definitely tell from these recordings. I like them a lot; however, as usual, they lack focus (our dynamic range is getting better though). Tonight was entirely improvisation, though we found ourselves doing some songs accidentally :-). I think we should continue doing heyholes and other such games in order to improve improvisational focus. Josh the bassist wasn’t present, so we all took turns being the bass. I’m the one that sounds like an upright. The last four tracks (which are continual play broken up into tracks) are very driven, and if you need some dance music, they wouldn’t be a poor choice.