Latest News

Well, it had to happen. I reached my fortieth birthday this week.

Given that my son is a year and change old, I don't have as much time for blogging as I once did.

They say parenthood changes your perspective on many things. Despite my best efforts, I am afraid that has happened to me too.

I launched two web services this year in the social media space: Nestor and Linksnest. While neither is wildly popular, these tools helped me learn the latest web design principals and tools.

Looking back at the start of the year, I see that I began with a stealth project for a friend that involved collaborative filtering and ajax. Need to get back to that at some point.

I sponsored a few kickstarter projects and contributed a prize to the Interactive Fiction Competition. I guess if I can't do stuff myself, I can at least help those who are.

I got a mole on my face removed, but am experiencing some blow-back. Stupid organic body.

I worked for three different companies this year, one of which I worked for twice. We got our house painted and traded in our cars for new ones. I tasted 30 year old Laphroaig. Materially, it was a better year than many others had and I know how lucky I am.

We lost a great old lady cat, Miss Lulu, this year. She will be missed.

I guess I'm not as reflective as I have been in the past. Not enough time.

Following on to yesterday's post about economics, I'd like to present this brief note about how to model role-playing game (RPG) style combat easily with math.

Anyone familiar with Dungeons and Dragons will recall the very tortured set of combat tables broken out by class and level. A simpler method for resolving combat is found in Freeciv.

Assuming a two party combat, you create two attributes for each member: an attack stat and a defense stat. In this system, the bigger the number, the better.

To determine the chance of an attacker hitting the defender, use the following formula:

P(hit) = Attacker->att/(Attacker->att + Defender->def)

This is to say, the chance of an attacker hitting a defender is the proportion of the attacker's 'attack' stat over the sum of the attacker's attack stat plus the defender's defense stat.

If the attack succeeds, some amount of damage is subtracted from the defender's health stat.

I like this formula because it is simple and scales well to opponents of wildly differing strengths.

Attack and defense stats must be greater than 0.

Hope this helps.

update: Removed magic scalar from supply and demand calculations.

This is more of a note to be expanded on later. However, I believe some will find it useful in this raw form.

Many interesting games, like M.U.L.E. and Trade Wars, involve the mechanic of supply and demand. To model this in code, where you calculate demand and supply to arrive at a price, can be done through the following forumlae.

Calculate demand: This is usually a simple count of your potential consumers. Perhaps the number of players will equal demand. This depends on the context of your game. This number will be referred to as 'd'.

Calculate supply: This is a simple count of the number of widgets available that are to be sold. Again, this is contextual. This will be called 's'.

Calculate relative demand: You will need to pick an arbitrary equilibrium number that presents the perfect balance between supply and demand. This number is going to be arbitrary, so let's use 100.

Relative Demand = (d / (100 + d))

Calculate relative supply: This looks a lot like demand:

Relative Supply = (s / 100 + s))

Calculate price: You will pick a price that represents the price at equilibrium. Here, that is 100 currency units. Your number will be different:

Price = 100 * (Relative Demand / Relative Supply)

You must code around the case where supply is 0. The price becomes not-a-number.

The result of these maths is that when demand is high and supply is low, the price increases over some baseline. When the supply is higher than demand, the price lowers. That's mostly how life works.

These formulae will give you a very linear relationship between supply and demand. You may need to tweak this for your game. Inverse logs might be more realistic or even exponential functions. This is most certainly an exercise for the reader.

Please note that this supply and demand model is far from perfect. Most economists will tell you that the variable to look at is price, which then controls supply and demand (this might be a "freshwater" bias). However, most games will want to compute a price rather than predict supply and demand.

Sometimes, you just want to generate mazes. The code presented here is a depth-first search.

A couple of notes about the code below. It works with vanilla, 2D grids, but these can be of varying sizes. The maze data is stored is a simple 2D array. Each room is presented as a hash. The algorithm needs to track which rooms have been visited (more on this later). Any room may also not have a south (bottom) wall or an east (right) wall.

The following code initializes the maze structure:

sub init_maze {
  my ($max_row, $max_col) = @_;

  my $maze = [];
  for (my $r=0; $r < $max_row; $r++) {
     for (my $c=0; $c < $max_col; $c++) {
        push @{$maze->[$r]}, {'visited' => 0,
			     'bottom'  => 1,
                             'right'   => 1,
                            };
     }
  }
  return $maze;
}

No surprises there.

The real work happens in the next bit of code, make_maze(). Given a starting point specified by a row and column coordinate in the 2D maze array, it marks the room as "visited". It then looks for neighboring rooms that have not yet been visited. It randomly selects one of these and knocks down the wall between them. It then recursively calls make_maze() with the new room.

Get it? No? That's OK. Recursive code takes a long time to trust.

sub make_maze {
  my ($maze, $row, $col) = @_;

  $maze->[$row]->[$col]->{'visited'} = 1;

  while (my $unvisited = get_unvisited($maze, $row, $col)) {
    last unless @$unvisited;

    # Randomly select a neighbor
    my $choice = $unvisited->[ rand(@$unvisited) ];

    # Knock down the wall between them
    remove_wall($maze, [$row, $col], $choice);

    # move to this new cell
    make_maze($maze, $choice->[0], $choice->[1]);
  }
}

There are two details worth investigating. The first is how unvisited neighbors are selected. The second is how to figure out which wall to remove. Here's the unvisited neighbor code:

sub get_unvisited {
  my ($maze, $row, $col) = @_;
  my @found;

  # look for neighbors in cardinal directions;
  # be mindful of maze bounderies
  if ($row == 0) {
    push @found, [$row + 1, $col] unless $maze->[$row + 1]->[$col]{'visited'};
  } elsif ($row == @$maze - 1) {
    push @found, [$row - 1, $col] unless $maze->[$row - 1]->[$col]->{'visited'};
  } else {
    if ($row + 1 < @$maze) {
      push @found, [$row + 1, $col] unless $maze->[$row + 1]->[$col]->{'visited'};
    }
    push @found, [$row - 1, $col] unless $maze->[$row - 1]->[$col]->{'visited'};
  }

  if ($col == 0) {
    push @found, [$row, $col + 1] unless $maze->[$row]->[$col + 1]->{'visited'};
  } elsif ($col == (@{$maze->[0]} - 1)) {
    push @found, [$row, $col - 1] unless $maze->[$row]->[$col - 1]->{'visited'};
  } else {
    if ($col + 1 < @{$maze->[0]}) {
      push @found, [$row, $col + 1] unless $maze->[$row]->[$col + 1]->{'visited'};
    }
    push @found, [$row, $col - 1] unless $maze->[$row]->[$col - 1]->{'visited'};
  }

  return \@found;
}

This code is pretty straight-forward. It observes the boundary rooms and makes sure that these rooms have not yet been visited. There are clever ways of reducing this code, but this is easier to understand, I think.

Removing the right wall is simply a matter of looking at two rooms and figuring out if the rooms are joined horizontally or vertically. It is then pretty easy to remove the right or bottom of wall of the correct room.

sub remove_wall {
  my ($maze, $r1, $r2) = @_;
  my $selected;

  if ( $r1->[0] == $r2->[0] ) {
    # Rows are equal, must be East/West neighbors
    $selected = ($r1->[1] < $r2->[1]) ? $r1 : $r2;
    $maze->[ $selected->[0] ]->[ $selected->[1] ]->{'right'} = 0;

   } elsif ( $r1->[1] == $r2->[1] ) {
     # Columns are the same, must be North/South neighbors
     $selected = ($r1->[0] < $r2->[0]) ? $r1 : $r2;
     $maze->[ $selected->[0] ]->[ $selected->[1] ]->{'bottom'} = 0;
   } else {
     die("ERROR: bad neighbors ($r1->[0], $r1->[1]) and ($r2->[0], $r2->[1])\n");
   }
   return;
}

It would be useful to print out a bird's eye view of the maze and that's done (admittedly awkwardly) in the following routine.

sub print_maze {
   my ($maze) = @_;
   my $screen = [];

   my $screen_row = 0;
   for (my $r=0; $r < @$maze; $r++) {
     if ($r == 0) {
       # Top border
       push @{$screen->[$r]}, '+';
       for (@{$maze->[0]}) {
	 push @{$screen->[$r]}, '--', '+';
       }
     }

     for (my $c=0; $c < @{$maze->[0]}; $c++) {
       my @middle;
       if ($c == 0) {
	 push @middle, "|";
       }

       push @middle, "  "; # room center
       if ($maze->[$r]->[$c]->{'right'}) {
	 push @middle, "|";
       } else {
	 push @middle, " ";
       }
       push @{$screen->[$screen_row + 1]}, @middle;

       my @bottom;
       if ($c == 0) {
	 push @bottom, "+";
       }

       if ($maze->[$r]->[$c]->{'bottom'}) {
	 push @bottom, "--";
       } else {
	 push @bottom, "  ";
       }
       push @bottom, "+";
       push @{$screen->[$screen_row + 2]}, @bottom;
     }
     $screen_row += 2;
   }

   for (my $r=0; $r < @$screen; $r++) {
     for (my $c=0; $c < @{$screen->[0]}; $c++) {
       print $screen->[$r]->[$c];
     }
     print "\n";
   }
   print "\n";
}

Finally, here's the main line:

my $dimension = $ARGV[0] || 5;
my $maze = init_maze($dimension, $dimension);

my ($startRow, $startCol) = (int(rand($dimension)), int(rand($dimension)));
make_maze($maze, $startRow, $startCol, undef);

print_maze($maze);

Hope this helps get you started in the wonderful world of maze building!

Linksnest is a new web tool I have developed to help you collect and manage URLs mentioned by you or your friends on social media sites, like Twitter or LinkedIn.

You can even see your latest collected links as an RSS feed.

It's free to use and I think pretty easy to understand. Please give it a try and tell me what you think.