One Game A Month

I’m going to work on finishing projects this year with the help of motivation by joining the community over at OneGameAMonth.com (#1GAM). I don’t know if I’ll write anything more than the initial post so I setup a new tumblr just for this event. Assuming things go well, I’ll repost the articles over here.

I hope to finally start blogging again about development in conjunction with attempting to finish developing one project each month. The first will be Star Command assuming we at least submit it this month, and while there will be continued work on it throughout this year, once it’s finally out I plan to devote a bit more time to blogging and #1GAM projects.

I wrote an initial entry and will follow up with one more “overview” or “brainstorm” type post soon.

Random ‘Draw’ With Shuffle

While writing Naval Fight I wanted to have the easy computer opponent select a random position on the board grid every turn.

First I implemented a naive solution creating an array of all possible positions that would be randomly selected from, but after a selection was used it was removed from this array.

validPositions = gridPositions.clone();

// selection
position = validPositions[random() * validPositions.length];
validPositions.removeElement(position);

This solution was adequate, but there can always be improvements, and now that I am storing information in a second array, how can it be used more efficiently. Thinking about the problem further it became apparent that this was akin to listening to a playlist on shuffle. Which then gives the light bulb moment that instead of thinking about random selection with no repeats I should just shuffle the array of positions, just like having a deck of cards and removing a card for each turn, noting it’s value (ie: grid position).

After a little searching I came across the Fisher-Yates shuffle algorithm, and found an efficient and unbiased implementation:

// setup
int currentPosition = 0;

for (int i = gridPositions.length; i > 1; i--) {
  // Pick a random element to swap with the i-th element.
  int j = uniform_random() * i;
  // Swap elements.
  int tmp = gridPositions[j];
  gridPositions[j] = items[i-1];
  gridPositions[i-1] = tmp;
}

// selection on each turn
position = gridPositions[currentPosition++];

This solution generates an array of possible positions which are then shuffled, and finally an index into the array is stored where the next position can be read. Each time the position is accessed from the array this counter increases to always point at the next position. There are other solutions that would work, but this seems to be a good final solution for my problem.

</steve>