New Stars Status

Oh Frabjous Day! Calooh! Callay!

Here we can see the fleet split dialog in action. The cool thing about Tcl, is the whole dialog and the logic behind it is 90 lines of code...

Here's the bulk of it:
for {set i 0} {$i < $numDesigns} {incr i} {
pack [frame .tSplitter.fTop.fRow$i] -side top

set shipName [newStars $::ns_planet $fid $::ns_design $i $::ns_getName]
pack [label .tSplitter.fTop.fRow$i.lL -text $shipName] -side left

set shipCt [newStars $::ns_planet $fid $::ns_design $i $::ns_getNumFleets]
pack [label .tSplitter.fTop.fRow$i.lLC -text $shipCt] -side left

pack [button .tSplitter.fTop.fRow$i.bL -text "<" -command "adjustSplitRes $i -1"] -side left
pack [button .tSplitter.fTop.fRow$i.bR -text ">" -command "adjustSplitRes $i 1"] -side left

pack [label .tSplitter.fTop.fRow$i.lRC -text 0] -side left

lappend ::splitRes [list $shipCt 0]
}
Hardly any < or >!

In English, it says:
foreach ship design in the fleet do
create a new frame (invisible GUI packing object)
pull the ship name via the C++ bridge, and make a text widget for it
pull the ship count via same, and make a widget for it
make 2 buttons, one < and one > which will call adjustSplitRes (described later)
make a text widget with "0"
append a list to the global variable splitRes (which holds the split counts for each design)

Like 9 or 10 lines of specific English, roughly the same in Tcl (plus whitespace)
Here's adjustSplitRes in its entirety:
proc adjustSplitRes {row val} {
set left [.tSplitter.fTop.fRow$row.lLC cget -text]
set rght [.tSplitter.fTop.fRow$row.lRC cget -text]

if {$left < $val} {return}
if {$rght < -$val} {return}

set left [expr $left - $val]
set rght [expr $rght + $val]

lset ::splitRes $row 0 $left
lset ::splitRes $row 1 $rght

.tSplitter.fTop.fRow$row.lLC configure -text $left
.tSplitter.fTop.fRow$row.lRC configure -text $rght
}

This pulls the text labels for the left and right, checks for underflow, then applies the new count (for now, we only support moving up or down 1, but I should be able to bind shift and control click to move more). I then update the splitRes list, and the GUI text.

The C++ bridge does not handle deleting the old fleet... that will probably need to be fixed, although we should have new tools for handling chaff mine sweeping, which was the main reason for shedding old fleet nums (otherwise, you never need to move out the last ship from a fleet).

I should be able to use much of this logic to build the fleet merge dialog.

Split all and Merge all should be easy, and aren't strictly needed for playing (merge fleets is needed).

Almost there!

Stuff I've read lately

"O is for Outlaw" (Sue Grafton)(audio) - Meh.

Black Hole Catalyzed Total Conversion

That has a nice ring to it. Kind of like "Laser Induced, Gravity Sustained Fusion Reactor".

Weird chain of events: a Slashdot article discussing the physics of space war. Leads me back to Project Rho, re-reading the sections on stealth and heat dissipation. Somehow, I ended up on stardestroyer.net, reading about the Death Star power system (I remember something about the importance of heat dissipation, and how Luke might not have had the impact he thought he did). Someone (maybe there, maybe elsewhere) mentioned the possibility of using black holes to convert matter to energy (this was in the context of a system failure not producing a tremendous boom, at least in comparison to the enormous power output before the failure [the Death Star is assumed to produce more power than Sol - blowing it up could easily wreck a solar system - that is, Yavin or Endor, places the heroes were supposed to be protecting]).

I decided to sit down and actually look at what it would be like to have a black hole around for energy conversion.

The idea is actually pretty simple, you feed matter into a black hole (presumably one already electrically charged so you can keep a handle on it). You then harness the Hawking radiation (HR) for energy.

There are several properties of black holes which make this not entirely unreasonable:

Power output (via HR) is inversely proportional to the square of the mass of the hole.

That means every (log) step down in mass, you go up two steps in the power of your reactor! Smaller holes give more power! It also means the black hole will likely not fail-big, but rather fail-evaporate (giving off a huge amount of energy). A small hole (2e10 kg) would produce about 1e11 W. Making it a little smaller (2e8 kg) would yield 1e15 W (probably too much to get rid of...)

Size is proportional to mass

This has good and bad points. A small hole is really small. 2e10 kg being about 3e-20 m (3e-11 of 1 nm) This means you won't accidentally fall in. But it also means you have to try very hard to get matter into the thing to keep it going.

Lifetime is proportional to mass cubed

This is kind of annoying, but the constants make it ok. A small hole (2e10 kg) would have a lifetime of about 21 million years. It does mean that your initial hole (unless you have a really big accelerator) is going to decay fast.

Actually, with a lifetime like that, it's effectively a battery, with no fuel input. A super small hole (2e6 kg, only two million kilograms!) would have a lifetime of 662 seconds! Definitely a problem, especially considering it is giving off a constant 1e19 W! Don't get burned!

People worrying about the Large Hadron Collider producing black holes shouldn't worry. The energy levels are way too low to produce a hole with any meaningful lifetime. It also means we will need a much larger collider (or better production methods - huge lasers?) to produce commercial black holes.

Civ Sequels

Of course, a game as successful as Civ is going to be followed by a lot of hangers-on (both products from the original designers, and imitators).

There was the natural progression: Civ-Net, Civ 2 (with a lot of variants, like Test of Time), Civ 3, and Civ 4.

There were clones: Civ Call to Power and Free Civ.

And in-spirit successors: Master of Orion (were you start with one planet and one colony ship), and Alpha Centauri (where you play the descendants of the original colony ship from Civ). Also, Colonization: a Civ-like specialized to a particular time.

---

The natural sequels were actually very disappointing.

Civ-Net: largely a Windows port (there may have been a Civ-Win). The network play had sequential (basically, hot-seat on different computers), or simultaneous. This really didn't work out, as a battle between two catapults could be decided by who was quickest with the keys.

Civ 2: Civ plus-plus. More of everything. More tech, more units, even more for settlers to do (double irrigation, anyone?). Of course, more is not necessarily better. The micro-management hassle of Civ became that much more in Civ 2. With more city improvements and more engineers needed, you built more cities. And the tedium of terraforming became just that much more. I largely play Civ 2 now, only because the old DOS Civ is a little buggy (some sort of weird memory corruption).

Civ 3: A good disaster. Introduced a lot of new concepts (culture, armies, a focus on fewer/better cities). I'm not sure what went wrong, had to be not enough play testing. Armies were way to powerful, culture didn't work quite right, the corruption in big empires was just crippling and small empires couldn't win.

Civ 4: Another hit. Largely made possible by the failures of Civ 3. Now culture is working right, the combat model is a lot better, and small empires really work. They also managed to fix the terraforming problem, where there is an actual choice to be made (not just, road-irrigate-railroad / next!). I'd play this more, except the graphics requirements are really steep.

The Life of the Game Designer

is not an easy one.

You have to spend hours thinking about (i.e. reminiscing) about all the great old games. Maybe talking with friends, or on rec.games.design, or even just alone.

Then, you have to go and play all sorts of games (for, you know, "research").

In that spirit, I have been playing some of the Facebook games (which a lot of people say are really bad).

They are really bad.

I will break out the how and why in (one or more) separate posts.

The Civ Legacy

I've been wanting to do some discussion of game design, and no better place to start than Civ.

Sid Meier's Civilization will always be remembered as a classic. You might say it is just Empire on steroids, or a translation of the board game - but millions of people don't play Empire and most have never heard of the board game.

Sid perfected "Just one more turn". Not only for Civ, but also in the less successful Alpha Centauri (lovingly known as SMAC).

The main advantage Civ had over Empire was splitting attack and defense (along with a more complex city model). This allowed specialization of units.

Civ also covered a much longer (and therefore more "epic") time scale.

The biggest failing of Civ was the old "phalanx beats tank" scenario. This comes from the simple unit progression (after the most basic unit - Militia 1/1):
Defensive

Phalanx	1	2
Musketeer	2	3
Rifleman	3	5
Mechanized Infantry	6	6

This is from memory, so I may be a little off. The general progression was just to add one or two to the attack and defense.

Offensive

Horseman	2	1
Legion	3	1
Chariot	4	1
Catapult	6	1
Cannon	9	1
Tank	10	5
Artillery	12	?

Sorry, I can't remember the artillery defense at all. It was less than the tank, making them very specialized (they could ignore city walls). Some of the offensive units could move at 2 (Tank may be 3, that has changed some in Civ, Civ 2, Civ 3, Civ 4).

The combat system was dead simple:

Chance of win = attack / (attack + defense)

So, a horseman attacking a phalanx has a 50% chance of winning. Of course, as a military option, a 50% chance isn't very attractive. I'm going to need an equal number of attackers as defenders, and defenders get an advantage for terrain and digging in ("fortifying").

I will cover naval combat in another post.

This is actually very easy to fix, although it didn't get fixed until Civ 4 (which, ironically, went back to a single strength number, although they did it very well).

Make the units improve by more than 1 per step! I mean, you've got at least a byte for strength and defense, that's 255 (or even 127 if signed).
In Civ 4, the "Modern Armor" unit is, like, strength 40. Plenty of firepower to crush that old phalanx.

New Stars Status

I hacked in a simple fix for the case I can check. I will need more code once I can check more cases...


Now we can build multiple ships, and split them out one by one. The Tcl/C++ interface has everything we need (I created this case from the command line). I need to update the GUI to present it nicely.

Sorry

I was going to do some New Stars stuff. But I was cleaning out my projects directory, and found some old code a friend sent me.

Of course, I had about three different versions from hard drive back ups and new computers, so I was reconciling them all and putting my changes into CVS (had to reformat all the code, you know).

I also fixed a bug due to wrap around, and added an alternate viewing mode.

Here is the normal view (it shows biomes - like desert, forest, etc):


Here is the alternate view (based solely on altitude):


Of course, all this map gen stuff made me want to play Civ. So I lost the day to Civ 2. Mmm, Civ 2.

New Stars Status

This is a particularly tricky set of code. I need to split off individual ships into a new fleet, and make sure the fuel and cargo are transferred proportionately.

Here we can see the 2 Toms have been split, but the fuel was left behind (as would the cargo)...

Stuff I've read lately

"P is for Peril" (Sue Grafton)(audio) - Choosing an audio book from the library is always hard. There tends to only be popular fiction, and I can't always concentrate on audio (with all the crazy Maryland drivers). So, I don't even want to choose "good" stuff.

This is the second Grafton book I've read (listened to). I wasn't at all happy with this one.

First, the red herring. Totally didn't fool me, not for a minute. In fact, I thought it was so overdone that it was actually the reverse. I figured the guy was being set up, and the main character's total hatred of him (after her initial liking him) would turn out to be misplaced. Nah, he was just evil.

The ending made no sense.

We had a lot of suspects to choose from:

1. The ex-wife.
• Gained $1e6 after his death
• Significant circumstantial evidence
• Spite against current wife
2. The business partners
• Protect their multi-million dollar business (blame him after he's dead)
• He was going to the FBI (they might not have known)
  
3. The step daughter
• Conceal her drug habit
• Conceal her theft of $30k
• Escape her "constricted" lifestyle
  

The ending isn't totally clear (I listened to it three times, and I'm still not sure). You can sort of convince yourself that it was the step daughter, but I think the author intended to finger the current wife...

• Gains nothing (life insurance went to ex-wife)
• Loses the father of her two year old
• Couldn't have wanted to get away (he was old and a workaholic)

Boo!

New Stars Status

I've been doing more work on the Linux side, as bugs come in and because I don't trust my XP regression (without comparing it to Vista).

This means I get my first Linux screen shot! (Which confused me for a second, I thought I would need to scp it back!)


Twm rulez!

The other advantage of working on Linux is that I need a new regression. That means I can use a disposable game, where everyone is not acting optimally.

Here, I have changed player two to build two scouts, instead of one.

That allows me to update the build logic to group new ships into fleets by design, rather than putting every ship in its own fleet.

This will allow me to work on the split fleet code.

Prime Directive

Let's see how D and C++ stack up when it comes time to maintain and expand our code.

I created a bash script to run the programs a lot (so we can check performance).

#!/usr/bin/bash
for i in {1..100}
do
./d_prime.exe > /dev/null
done

This isn't the greatest (generating more primes would be good too), but it should suffice...

On my Pentium 4, 2.4 GHz, D gives:
real 0m12.865s
user 0m3.888s
sys 0m10.450s

While C++ gives:
real 0m13.325s
user 0m4.128s
sys 0m10.667s

I won't be comparing the speeds directly, as much of that is a compiler issue (and I would need to evaluate turning on optimizations, which is a big headache). I am most interested in algorithmic improvements, and how hard they are to code.

The obvious thing is that the code is O(n^2), or at least O(n*p) where p is the current number of primes. We don't need to check primes that are larger than sqrt(n). So, how can we encode this?

The D code is an easy change:
We add:

uint ct = 0;
uint sqr = 4;
if( i >= sqr )
{
ct++;
sqr = primes[ct] * primes[ct];
}

And change:

if( isPrime(i, primes[0..ct+1]) )

This makes use of D's "slice syntax". That is, we can create a subarray just by specifying the elements we desire. The slice is a reference, so there is no copying.

real 0m12.915s
user 0m3.923s
sys 0m10.507s

The new time isn't any better, probably because the time is dwarfed by system (/dev/null doesn't seem any faster under Cygwin). But we have introduced a new algorithm that is potentially twice as fast with little effort.

When I come to the C++ version, I realize I've made a terrible error... the isPrime function takes a reference to a vector. But I only want to pass in part of my current vector. Now I have to come up with a slice class which is derived from vector, or change my function to use iterators (Note: I did not plan this to make C++ look bad!).

Iterators are ugly, but not as ugly as trying to implement my own slice class!

The new prototype is:

bool isPrime(unsigned n, const std::vector<unsigned>::const_iterator b,
const std::vector<unsigned>::const_iterator e)

and the for loop becomes:

for(std::vector<unsigned>::const_iterator i = b; i != e; ++i)

while the call point is:

if( isPrime(i, primes.begin(), primes.begin()+ct+1) )

Again the time isn't any better:
real 0m13.561s
user 0m4.097s
sys 0m10.855s

Of course, iterator addition is pretty unusual. It might give someone pause. And make them think about how it is just as ugly as normal iterator usage!

Now imagine I've had to edit header files and caused a dependency chain reaction which forces everything to rebuild. Or worse, altered a public API, which drives a version change. Maybe implementing that slice class wouldn't be so bad...

D Code

I had a little time, and started playing with primes again (something fascinating about primes).

Good chance for a little D code:

import std.stdio;

bool isPrime(uint n, uint[] curPrimes)
{
  foreach(i; curPrimes)
  {
    if( n % i == 0 )
    {
       return false;
    }
  }
  return true;
}

void main(char[][] args)
{
  uint[] primes;
  primes ~= 2;

  uint i = 3;
  while( i < 1000 )
  {
     if( isPrime(i, primes) )
     {
        primes ~= i;
     }
     i += 2;
  }

  writefln(primes.length);
  writefln(1);
  foreach(j; primes)
  {
     writefln(j);
  }
}

The C++ code is very similar (except with lots more editing for HTML, with &gt; and &lt;):

#include <iostream>
#include <vector>

bool isPrime(unsigned n, const std::vector<unsigned> &curPrimes)
{
for(std::vector<unsigned>::const_iterator i = curPrimes.begin();
   i != curPrimes.end(); ++i)
{
  if( n % *i == 0 )
  {
     return false;
  }
}
return true;
}

int main(int argc, char **argv)
{
std::vector<unsigned> primes;
primes.push_back(2);

unsigned i = 3;
while( i < 1000 )
{
  if( isPrime(i, primes) )
  {
     primes.push_back(i);
  }
  i += 2;
}

std::cout << primes.size() << std::endl;
std::cout << 1 << std::endl;
for(std::vector<unsigned>::const_iterator i = primes.begin();
   i != primes.end(); ++i)
{
  std::cout << *i << std::endl;
}

return 0;
}

I've already complained about hideous iterator syntax. But I will post more on some D goodness, when it comes time to make improvements to the algorithm.