Simulated Evolution

At the height of self-isolation during the COVID-19 pandemic, one might hope that this would give me more time to focus on my hobby projects, to keep myself sane if nothing else. No such luck. The project I’d been hoping to work on—an artificial-life simulation from 1989—stalled out pretty aggressively, and I had very little motivation to work on it directly.

I did still want to investigate the simulation, though, so I gave up on the “retrocoding” part of it and implemented it directly in C. This both let me validate the design and explore some of the space it suggested. Fixing up the design to be more friendly to modern implementations also ended up being interesting.

So today, let’s look at taking a very old design and bringing it a bit into the modern world.

The Original Design

The original program I’m cloning and modifying here was a program named Simulated Evolution, created in the late 1980s by a high school teacher named Michael Palmiter. This program was written up by A.K. Dewdney in is column Computer Recreations, and the column in which he did so was published in the May 1989 issue of Scientific American. That column was republished, with some extended detail, in his collection The Magic Machine: a Handbook of Computer Sorcery. This collection is where I first encountered the program.

The basic idea is pretty simple; there is a 150×100 “primordial soup”. Plankton randomly appear in the soup at a steady rate. Bugs swim around the soup, eating any plankton they come across. Plankton lives forever unless eaten, but bugs will starve to death if they don’t eat for long enough. Bugs that eat well and live long enough will fission into two bugs.

Where things get interesting is that bug motion is determined by their genome. Each bug carries with it a weighted set of probabilities determining what it will do each time unit; each time unit it will turn some multiple of 60 degrees and then advance one unit. When a bug divides, a random one of the six possibilities will end up weighted twice as heavily, and the other will have a (possibly different) random option weighted half as heavily.

The starting conditions include 100 plankton and ten bugs with random genomes and a nutrition level consistent with having consumed a single plankton. This means that bugs begin by just kind of twitching in place, more or less, and as the simulation continues selection pressure produces bugs that move in more directed ways.

The article doesn’t specify exactly how it works, but it also mentioned that Palmiter’s original program had a “garden” setting that would set aside a small part of the soup to receive much more plankton than the rest, and that doing this could encourage speciation amongst the bugs, with the “cruisers” being supplemented with “orbiters” that would turn tight circles within the garden.

I have successfully replicated that result in my own system:

I’ve uploaded the source code to the Bumbershoot Github. The full program requires SDL2, but it should build with “make” alone on any system where that’s immediately available – so, any Linux-like system, or macOS running Brew, or Windows running MSYS2.

Fixed-Point: When Integers Aren’t Integers

My latest retro project, such as it is, is the resurrection of an old scientific simulation program in a way that should let it run properly on the 8-bit home computers that are my usual focus here. I’m not yet sure this is a viable project—the original assumed about ten times the memory and the speed and also was tuned to 16-bit systems—but it doesn’t look like the port would have to make many compromises.

Even if it doesn’t work out, though, there’s some fun or useful stuff that’s falling out along the way. Here’s the first.

Flat Random Distributions

Part of the simulation requires a lot of random integers evenly or reasonably-evenly distributed across relatively small ranges. In my projects to date I hvae mostly gotten away with making sure that all of my random ranges were powers of two, which meant I could simply use a bitmask to get the random numbers I actually wanted. I can no longer get away with this.

How does this help us? Well, I’m using a 16-bit RNG for my simulation, and it is relatively good at picking a random number between 0 and 65535 with equal probability. If I want to convert that to a random integer between 0 and N, non-exclusive, and spread out the error as evenly as I can, the most direct way to do this would be to divide it by some number, so that 65535 yields N and 0 yields 0. There are two problems with this: one of them is that division is very painful on the 6502, and the other is that if our number isn’t exactly right, we risk disaster. Dividing by a number that’s too large results in the largest number being underrepresented in our random results, which isn’t great, but dividing by a number that is too small introduces a small but real chance that we end up returning values larger than N. If these are going to be used as array indices, this risks severe data corruption.

So, we’ll need to be exact. We’re looking for a divisor k such that:

• All values are in range: 65535/k = N after we round down.
• All possible values appear as much as they can: 65536/k = N+1 after we round down.

Ideally, k should be such that we don’t have to do any rounding on that second test. And that makes this a very easy equation to solve: k=65536/(N+1). That’s still rather inconvenient to work out, and we certainly cannot do it in advance with the precision we want.

But dividing by a rational number is simply multiplying by its reciprocal. If we do that, this means we take our random number, multiply it by (N+1), and then divide by 65536. And dividing by 65536 is so easy it is literally free—it would normally be shifting a value 16 bits right, but on an 8-bit system we may accomplish this simply by only paying attention to the top 16 bits of our multiplication!

We’ve seen this trick before, too. When I implemented the Xorshift-Star PRNG, which required 64-bit math on 32-bit chips. These had an internal state of 64 bits, and each tim we advanced the RNG that state was shuffled, and then it was multiplied by a 64-bit constant, and then the top 32 bits were returned as the random integer. The C implementation needed to do 64-bit math and then shift right by 32 bits; the assembly-lnaguage implementations simply returned the high 32 bits as a core value directly.

A Caveat

Since (N+1) here probably doesn’t evenly divide 65536—and if it does, you can just use N as a bitmask to get your random number—some values are going to be more probable than others. As long as N is much, much less than 65536, this will not be a very large problem, but as it grows, the amount of error gets more drastic. Once you get past 32,768, some numbers will end up being twice as common as others. Even that may not be a great problem if you are interpolating points along some function, but if you are using these numbers to select entries out of a dictionary or something, it could very unpleasantly skew your results.

In cases like this, I would generally recommend restricting the result to the closest larger power of two, and then rerolling any RNG results that are out of range. That makes the generation take an indeterminate amount of time, but once a value is decided upon all values will be equally probable.

Having Fun With It

As written, this a mathematical trick; some algebra that lets us have fewer headaches when providing an extremely basic capability. Let’s do something fun with the technique.

Suppose we’re writing a 2D game with a physics engine of some kind. We’d like to have gravity or something like it, and the smallest “normal” acceleration we could give it would be 1 pixel per frame per frame. The problem is, this is way too fast. Here’s the longest I can keep a ball in the air on a C64-sized screen:

This is a reasonable amount of time but our jump ends up taking the entire screen. It doesn’t generalize well to the kinds of physics we normally see in 2D platforming games, even ones from the era with similar screen sizes.

The general shape of the solution is obvious: don’t use pixels as the fundamental unit of your world physics, because they are too large. However, floating point is completely out of the question for these systems, even though it’s normal once you enter the 3D world. The solution is to have an extra byte for your coordinates to serve as the subpixel value. After that, the lowest byte may be ignored when placing sprites and the like.

This turns out to be an implementation of fixed-point math, the counterpart to floating point. It’s a good choice when you’re dealing with something with a true fractional value but which needs to be represented exactly, or where you need the speed and precision of integer math but can’t rely on integers all the way through the system.

Our random number algorithm can also be thought of as a fixed-point system as well; we can treat the “decimal point” as being between the low and high 16-bit values, and thus our RNG is returning a value that is greater than or equal to zero 0 and strictly less than 1. We then multiply that fraction to get a number larger than one and ignore the fraction in the product.

2019 Compilation

As is now traditional, I have collected my various Bumbershoot Software projects from the previous year into a single zip file for convenient download.

Most of my work for this blog last year was in the form of long essays or analyses of programs, but there’s still a modest collection:

• A partial machine-language port of Mark Charlton’s Wallpaper program for the ZX81, improving the speed and regularity of the display.
• A complete machine-language port, with enhancements, of the uncredited Mandala/Chopper Checkers program for the ZX81/Timex Sinclair 1000. I suspect it may have been written by Tim Hartnell (who edited the book it was collected in). This merges the two programs it was presented into into one, with a main menu to select the variation, drastically improves the speed of play and display, properly enforces the rules of play, and improves the UI for entering moves.
• An implementation of the SHA-256 hash algorithm for the Commodore 64 (and by extension any 6502-based system).
• A native GUI port of the Lights-Out Puzzle to Win32.
• A previously uncollected 256-byte Atari 2600 program composed in an impromptu code jam at MagWest 2019. A very simple logo animation, but it was a thing I wrote.

2020 has begun with me staring down a much larger set of tasks I wish to take on in modern Open-Source projects. If interesting things happen there, I’ll probably write them up here. With luck I’ll get some retrocoding time too, though.

Raw Win32: Dialog Boxes

The Lights-Out application is basically complete. However, it is not really representative of period Windows applications, because we aren’t actually using any widgets. We have a menu, a window, and a completely OS-managed pop-up message box, but everything else is a custom-painted window canvas. To really get a sense of the intended development model, we’ll want to make at least some use of standard widgets and controls.

The obvious thing to add is a custom dialog box for the credits, under the Help menu:

This isn’t too hard to do, but it also ends up highlighting why the raw Win32 GUI APIs aren’t really fit for purpose anymore.

How Dialog Boxes Work in Raw Win32

Dialog boxes are a kind of window but the do no work quite the same way. They have a window procedure like usual, but it has a different return value and there is a more defined relationship between it and its component controls. The change in return value is simple enough—since dialog boxes aren’t quite windows, we are not permitted to call DefWndProc. Instead, we return zero to indicate that we did not handle the message ourselves, or nonzero to signify that we have done the necessary work. A return value of zero effectively results in a call to the equivalent of the default window procedure.

The connection to component controls are more interesting. Dialog boxes are generally specified in the resource file as a dialog template, which lays out the component controls and assigns identifiers to them. Here is the dialog template for our About dialog:

IDD_ABOUT DIALOGEX 10, 10, 150, 44
CAPTION "About Lights-Out!"
STYLE WS_POPUP | WS_BORDER | WS_DLGFRAME
{
        ICON 1, 0x501, 12, 6, 0, 0, SS_ICON
        CTEXT "Lights Out!\r\nBumbershoot Software, 2019", 0x0502, 36, 6, 106, 18
        DEFPUSHBUTTON "OK", 0x503, 102, 30, 40, 12
}

Each of the items in this dialog box gets a line in the specification: an icon, some centered static text, and a default pushbutton. Each of these is a window in its own right, and it is assigned a dialog control ID to uniquely identify it. I use hex numbers increasing from 0x501 to identify each control in the dialog. At run time, given some instance of a dialog box, the GetDlgItem and GetDlgCtrlID functions can convert between window handles of the controls in that dialog box and their corresponding dialog control IDs. Controls that represent a value, like text boxes or sliders, may be interrogated with the GetDlgItemInt and GetDlgItemText functions.

Since they are also windows, SendMessage and related functions will also work.

The first argument for each control here is also some basic configuration information—the text for the labels and buttons, or the icon number for the icon we wish to display. The last argument for the icon is a style value, which is also basically harmless.

Where things begin to get deeply unpleasant is every other number in the resource template. These represent locations and sizes of controls in absolute units. As written, Windows dialog boxes have a completely static layout. This is no longer acceptable behavior in a modern GUI application, and addressing it requires implementing sensible behavior in response to WM_SIZE messages that, in this day and age, we expect to be part of the basic widget design and layout itself. Searching around a bit I found a project from 2011 for retrofitting a “spring and strut”-like system into the resource code, but it doesn’t actually work all the way back to Win9x and does not seem to have been standard practice at any point.

So let’s be clear: the fifteen megabytes of space you pay to use something like Qt to manage your UI elements is unquestionably worth it for contemporary C/C++ desktop software development. We’re only working in raw Win32 here to prove a point, and we’ve already hit the barrier where we’re better off using a pre-existing third-party solution, just for access to a reasonable automatic layout engine.

That said, for this project, we’ll just have our About dialog not be resizable. Below the jump, we’ll work through the necessary code to make this happen.

Raw Win32: Icons and Resource Files

With the work of gameplay and basic display done, our main goal now is to improve its appearance. Our first task there—and our goal in this article—is to add an icon visible from the File Explorer.

This poses a problem: so far in this project we’ve been building our UI elements programmatically—each element is constructed and configured based on instructions executed when the program is run. How can we get UI information—an icon, in this case—where Windows can see it without running us?

This problem is, of course, not unique to Windows, and different operating systems solve it in different ways. Modern macOS and iOS, as well as the RISC OS from the Acorn Archimedes and its descendants, both make applications be entire directories instead of files, and put the icon file inside that directory. The classic Mac OS divides files into a “data fork” and a “resource fork”, with the latter being an OS-imposed asset database that may include, among other things, the necessary icons.

The Windows approach is a bit more like the classic Mac OS. Files are not bifurcated into resources vs data, but the executable format is structured such that it exists as a set of self-describing segments. Normally the segments we care about as programmers are the ones that correspond to program code, or the initial state of the data the code works on. But there are many other chunks in an executable file, incorporating linking information, hardware requirements, and other things we normally don’t think about directly. One of the chunks is a “resource chunk”, and it works in a way very similar to a resource fork. This is where we’ll put our icon.

First, of course, we’ll need an icon. Icons are ultimately just a collection of bitmap images of various sizes and depths, and most paint programs can export to that format. If you don’t have a paint program, though, Visual Studio includes a basic one that is sufficient for our needs:

We need a 16×16 image for the smallest icon and then we can include larger and fancier ones for display in other contexts. We’ll just stick with a 32×32 image, which should look fine in most Explorer contexts as well as the taskbar. Now we just need to get it into a resource chunk.

Creating a Resource Chunk

Resource chunks are linked into executables as if they were object files, and like object files they’re compiled from source code. This is done with a special resource description language and then compiled with a program called a resource compiler. If all we want to do is add an icon, the resource file is very simple:

1 ICON WinLights.ico

We put that line in a file named WinLights.rc.

What we need to do after that depends on whether we are using the MSVC toolchain or the MSYS2/MinGW one.

Compiling and Linking Resources on MSVC

The resource compiler is named rc and it’s pretty simple to use:

rc WinLights.rc

This produces a file named WinLights.res, and we may list it in our link command alongside WinLights.obj, the product of our assembler.

Compiling and Linking Resources with MinGW

This is a bit nastier, because the MinGW toolchain doesn’t have a special object type for resources, which also means we can’t use the same base name for our files. Fortunately, windres, the MinGW resource compiler, lets us specify custom output the same way the compiler does:

windres -o WinLights-res.o WinLights.rc

The resulting object file may then be linked in to the final file in the usual way.

Making the Icon Appear

The 1 before the ICON directive gives the resource identifier of the icon. The File Explorer will extract the icon with the lowest resource identifier and use that for the program’s overall icon. That does not, however, give us an icon for the application window or the taskbar itself. To do that, we’ll need to associate the icon with the window itself. That’s simple enough; the LoadIcon function will extract an icon resource from a module, and the WNDCLASSEX structure we use to register the class has an hIcon field. During initialization we wait until we initialize the hInstance field (which takes the value from EAX) and turn that instance value into the icon:

        push    dword 1
        push    eax
        call    _LoadIconA@8
        mov     [ebx+WNDCLASSEX.hIcon], eax

Now we have a proper window icon, too:

This gets us what we want, but we can go further. Resource files can hold much more than just icons.

Raw Win32: A Properly Resizable Custom Widget

Five updates in, and our custom display still just gets cut off when we resize the window. We’re long past due to rework our drawing code so that the board rescales itself to fit in whatever size window we provide. We’ve been putting it off so that we could add more basic Windows functionality—GUI programs have a lot more machinery in them than usually goes into our programs here—but we’re officially out of excuses now. Let’s get to work.

The Problem

When calling either paint_grid or hit_test, we’ve been just feeding it a series of constants so far:

        xor     eax, eax
        mov     al, 70
        push    eax
        mov     al, 60
        push    eax
        mov     al, 10
        push    eax
        push    eax

These are pushing down, in order, the distance between the center of each circle, the diameter of the circle, and then the upper-left corner of the first circle. We want, instead, to compute values for all of these based on the current size of the window.

This poses a problem; we now have a function that returns four values. How best to arrange this? In C, we would have pass four pointer arguments and then write through them. It would be simple enough to do this in assembly language as well—a pointer argument in C is just an address in assembly language, and we can create those just by adding values to the stack or frame pointer—but why bother going through extra pointers when we can just reach into our caller’s stack frame directly by way of the frame pointer?

This sounds like an ugly hack, but this is really just working around some limitations in C’s expressiveness. The real trick is in modifying the function call ABI so that this doesn’t end up being horrible for us. Here is how I end up doing that:

• The basic operation matches __stdcall. Functions push their input arguments onto the stack from right to left, and returning from the function puts the return value in EAX and clears out all the input arguments.
• However, in addition to input arguments, functions are allowed to declare output arguments. These come after all input arguments, and are not removed from the stack on function return.
• Calling the function will assign values to all output arguments, resulting in values that may be used directly, popped into registers, or recycled as arguments into a subsequent function call.

This notion of having the function write into the caller’s stack frame is new to us here at Bumbershoot software, but it’s not tremendously uncommon. When returning a value too large to fit into a register, most ABIs have some way of passing in a way for the function to write a pre-allocated structure. The ABI for the original Macintosh wrote return values into preallocated space on the caller’s stack even when the result would have fit into a register; it just didn’t use registers for this.

That’s the theory and the context. What’s the practice like?

• Our function will be called size_board.
• It will take one input argument—the handle to the window we’re trying to fit into.
• It will take four output arguments, which correspond exactly to the x, y, size, stride arguments to both paint_grid and hit_test. They are all write-only and do not require initial values.
• The function otherwise “returns void”: all useful data is returned in the output arguments, and EAX is just trashed.

This lets us replace our eight instructions hardcoding arguments in the window procedure with three:

        sub     esp, 16
        push    dword [ebp+8]
        call    size_board

Once the function returns, we can then immediately call the function we were preparing for. This is quite nice for us.

Now we have to actually implement size_board. Let’s get to work.

Raw Win32: Menus

Our game is playable now, but it isn’t very polite about it. The only way to get a new game is to quit and restart, and it’s up to us to notice that we’ve won. Until we make the program itself smart enough to referee for us, this is a toy, not a game.

The user experience we want will look a great deal like the old Windows 3.1 games like Reversi or Solitaire. Normally you have a game in progress, but you can start a new game at any time from the menu or with a hotkey. Once you do win, a small dialog box pops up reporting the result and asking if you wish to immediately begin a new game. If you do, this is just like starting a new game any other way, and otherwise the game screen goes unresponsive in the finished state until the program is quit or a new game is started.

Our general solution here will look, under the hood, a lot like the Finite State Machine that we designed for the Atari 2600. We’ll have states for “in-game,” “game has been won but we haven’t reported this fact yet,” and “game has been won and the user has decided to make the game go idle.” (The machine still has three states, but the game flow from the Atari is a bit different, because we’ll start in PLAYING and we have a special state for ENDING instead of STARTING.) Menus and simple dialog boxes will be handled using standard Windows system calls.

Breaking this down into its component parts yields a few changes so small we can write the code needed down within the spec, and then a few other parts that are more work:

• Reserve an extra byte in the .bss segment for gameState. Easily managed with a line gameState: RESB 1 near the other uninitialized data. Put it last so there aren’t alignment problems.
• After zeroing out EAX in initPuzzle, also reset the game state to “game in progress” with the instruction MOV [gameState], AL.
• Ignore clicks if we aren’t in the “game in progress” state.
• Change the game state to “solved” if a move solves the puzzle.
• If the player won, prompt for a new game, and either create a new puzzle (resetting to “game in progress”) or transition into “idle” depending on reply.
• Add a menu bar to the application with a “Game” menu, which lets us select “New Game” or “Quit” at any time.
• Make the menu bar accept keyboard shortcuts; G, N, or Q for the Game menu, the new game, and the quit option, with F2 or Alt-F4 working anywhere for new game or quit.

Once we do all these things, the end result starts improving:

Below the cut, we’ll finish the implementation from our work.