A digression on recreating a higher res logo

This isn't a post about my compiler project. I haven't touched that in a while - I've been thinking about what my reference semantics are going to be, and I think that I've got stuff making sense in my head, but it'll take a bit of time to get it working. Time and uninterrupted attention, which I haven't carved out lately. I've got some vacation time coming up.

No, this is about some goofing around I did with some different approaches to solve a problem that isn't super important. You know, fun.

Many years ago, I decided I needed a stylized logo for Big Dice Games, something that'd capture some of the idea of old school gaming, in a way that'd reproduce on letterhead, or business cards, or whatnot.

So, I sat down and doodled this in Inkscape, I think:

Well, something like that, anyway. I generated a SVG, because I wanted nice crisp edges, and SVGs are good at that.

And I made business cards. And I got a local company to embroider it onto a sweatshirt. I love that sweatshirt.

And I put it as a title screen on a bunch of tiny games.

Somewhere along the way, though, I misplaced the SVG, and just have a PNG of it. And those business cards. And the sweatshirt.

So, I decided I'd try to recover, or recreate, the vector description of the logo. That's what this post is about.

Stab #1 - Genetic Algorithm
I love me some good genetic algorithms. They're fun to implement, fun to watch as they lurch around with their hilariously unfit attempts, and slowly converging on... something. And then, they're frustrating as they plateau, and no progress gets made, and then you turn your machine off, and you tell yourself you weren't interested in the project to begin with.

Or, you make some good progress, and you realize that you forgot to have the output saved somewhere, or the output isn't in a useful format, and you only realize that several hours of GA searchtime later.

Or, your computer turns off in the middle of a search, and, you didn't save the population, so you could start over, but... is it worth it?

I think those roughly sum up my experiences with genetic algorithms. Oh, I also used GAs a while ago to come in 5th place in a Games Magazine contest. I've got a Games T-Shirt as a result.

So, yeah, despite GAs shortcomings, I decided to try to recreate the logo with a simple GA.

Maybe not so simple. Looking at that logo, it's easy to recognize there are some circles and some polygons. It's not too hard to pull out the colors, so the GA doesn't have to work to find them. So, I hardcoded a 40-dimensional representation - three numbers for each circle (x,y,r), six numbers for the one triangle, and eight for the two quads. 40 floats, which I could seed with some vaguely neighborhoodish values.

I wrote a python function that would take an array of 40 floats, and use them to draw a series of circles and polygons. My seed numbers drew this:

Which get the GA started. Recognizably using the pieces of the logo, now just fine tune the values. Go.

So, the evaluation function would take the rendered output, subtract it from an image I captured by scanning one of my business cards, histogram the difference, and count the number of pixels that had a difference.

That was a reasonably quick evaluation function, and I got some output looking like this:

Closer to the target than the seeds, in some ways, but not really all that good.

My GA is still running, around 5 days in now. Still nothing accurate. I kinda like the jaunty, rakish version there, but it's not what I was going for. I'm keeping it, in case I decide I want to revamp the logo later, though.


Stab #2 - Hough Transforms

A couple years ago, I listened to a talk about computer vision, particularly as it applied to recovering text from Google street view photographs. The details of that talk aren't important here, except that the speaker mentioned Hough Transforms. The basic idea is that you create a big chunk of memory that captures all the possible parameters for the thing you're looking for. If you're looking for a line in your picture, you have a 2d space with some sort of line parameters. Could be the m and b in your algebra class standby y = mx + b, or maybe you're more clever, and want to avoid infinite slopes for vertical lines, and you use a radius / angle representation, or whatever. 2 floats capture a line pretty well. You set up an accumulator array for those two values, and for every pixel in the source image that seem to be part of an edge, you have it "vote" on possible parameter pairs for lines that would pass through that pixel. Or, flipping it around, for each parameter pair, generate a line, then for that line, for each pixel in the source image, collect votes on how much that line has edge pixel candidates.

It's clever, it's kind of compute-intensive, it's the kind of thing that GPUs can compute pretty easily.

There's a Python implementation, which makes me happy.

Circles can also be detected, and ellipses, as well, if that's your thing. Could be anything, really - as long as you can parameterize it, and don't mind the high dimensional space for wobbly peanut shaped whatevers you're looking for. Circles and lines were plenty for what I was trying to do.

I downloaded scikit-image - which was an annoying process of using the easy_install command, which didn't work, trying to trace back through the dependencies, and installing those, and eventually just using apt-get to install scikit-image, which seemed to work, except that much of the documentation and sample code was out of sync with the version that I installed, so I wasn't able to use the Canny edge detector, only the Sobel one. Which was OK.

Pretty much OK.

I did a quick edge detection path (good grief, my edges are so wide, in part due to the gross job I did scanning the business card), and asked scikit to find straight lines in my image, and it found a couple. I think I was overloading it with edge pixels.

So, I decided to simplify things. I wrote a script to force pixels into one of the six colors that should be in the image:

That cleans things up some, but I'm getting unfortunate gray edges that I don't want. Maybe it's not such a big deal.

I also wrote a version of that script that broke each color out into a single file:

I proceeded to open these bitmaps (well, black and white PNGs, but close enough) in GIMP, and manually cut things further apart into individual primitives.

I passed these hand-cut PNGs back into the Hough Transform scikit script, and asked for some lines and circles, and started getting fairly good values. In some cases, I got a couple different candidates for lines or circles, but at least for lines, I got a "strength" value, so I just took the strongest candidate.

Ok, so now that I had these, it was time to see what the output was. I started drawing some circles, ok, that looks pretty good, gray, green, white... hmm... Oops, the output from the scikit was coming out as y,x and my drawing code was expecting x,y. Thank you, science.

Flipping things around, the circles all looked like they were coming out about right.

The polygons, though... that would be some more work.

I started with the triangle for the hat. The scikit line parameters were theta, radius - an angle from the origin to the closest point on the line, along with the distance from the origin to that point. I futzed around with some drawing code, and eventually got three very long lines tracing the outlines of the hat, and then continuing well beyond the corners.

Ok, so I need to intersect some lines.

For each line, I parameterized the lines starting at that closest point to the origin, and proceeding in a direction perpendicular to that radius. So, I had x0,y0,dx,dy descriptions of lines, which you could think of as x(t) = x0+dx*t, y(t) = y0+dy*t. That's convenient.

For each pair of lines, I'd have two equations in two unknowns, and as long as I don't have any infinities around, it should be a matter of algebra to figure out the point of intersection.

My algebra teacher from 7th grade insisted I show my work. So there you go.

So, I now had three intersection points, which looked pretty sweet.

Only two more primitives to go - a blue quad for the wizard's robe, and a brown one for his staff.

I had broken the robe into two different pieces when doing the edge detection, so I ended up with something like eight different candidate edges. With trial and error, I figured out four that I wanted to keep, and the right order to draw them.

The staff was trickier - my edge detection efforts only got two edges, so I started there, and inserted random other edges from the cloak to begin with. Fortunately, the right side of the staff gets buried underneath the red fireball circle, so I could do a lot of things there and have no visible effect.

On the tail end of the staff, I tweaked the offset until it looked about right. So much for computer recovery of subpixel parameters. -300? Sure, looks good.

I had something that looked pretty good at this point. My eyes were getting a little bleary from all the pixel pushing, so I went back to the original scan, and was pleased to see that things looked pretty close to the original. The mage's left hand seemed to be gripping the staff a little high - the bottom of the circle was just about tangent to the staff polygon. So, I manually offset it down 10 pixels. Again, not doing a great job of adhering to the machine recovery process.

I'm pretty happy with the result, though:

Look at those sharp edges, those clean colors. You may not be able to tell, but it's got an alpha channel. It's still not a SVG, which I could probably have got without too much difficulty by just tracing some edges in Inkscape, but I've got values that approximate the original design that I can begin to play around with for fancy animated logo screens if I want to do that. The primitives could fall into frame from above, revealing the mage in the space of a few seconds. Or I could animate scale - stretch and squash into place. Or combinations of these. Or rasterize the logo, one primitive at a time, one scanline at a time, like one might have done on an Apple ][ back in the day.

So many options.

I could even make a new sweatshirt.

Smooth Animation, but lots of jaggy edges

You'd think a game loop wouldn't be a hard thing.

while(true) {

  process_input();

  update_game_logic();

  render();

}

That can be adequate for a lot of simple games, but the cool thing to do is to decouple the update calls from the render calls, update on a fixed (sim) clock, and render as often as you can, using a very lightweight interpolation inside the render loop to smooth the trajectories between update calls.

In particular, I'm using a version from Robert Nystrom's "Game Programming Patterns", which looks like this in my language:

 loop {

    float currentTime = get_current_time();

    float elapsedTime = currentTime - previousTime;

    previousTime = currentTime;

    lag = lag + elapsedTime;

    

    sdl_tick_input();

    if (sdl_quit_signalled() == 1) {

      break;

    }

    while (lag >= SECONDS_PER_UPDATE) {

      update();

      lag = lag - SECONDS_PER_UPDATE;

      updates = updates + 1;

    }

    float alpha = lag / SECONDS_PER_UPDATE;

    draw(alpha);

    renders = renders + 1;

  }

The nice thing about this is that the updates are always at a fixed rate, so the simulations don't go unstable, and you still get to render as often as your machine is capable of. I could stick an artificial delay in there to keep the frame rate from going too high (rarely a problem, but if I wanted to conserve battery power on portable devices (phones, tablets, laptops) it might be worth considering.

Several bits that I ran into along the way that I need to clean up:

• I'm being sloppy about pointers within my compiler. I just throw an extra load() to dereference the pointer, and things seem to work out, but it feels super sloppy.
• I'm getting a segmentation fault about 13 seconds into the run. Don't know why that is, but it's reproducible. Which is a nice thing for a crash bug.
• I've got user-defined data types (let's call them "structs"). But if I create them at global scope, they don't get linked properly. Gotta figure that out.

I was hoping to get the ship to fly around with simulated intention by this point. That's soon, but not yet, I guess.

White Triangle

From a compiler/language perspective, this isn't an interesting post. All I've done is incorporate OpenGL into my existing SDL2 support from the Pong game, earlier.

It was a bit of a hassle merging the SDL2 OpenGL tutorials (which are, I guess, pretty new, and pretty spartan) with the NeHe "drawing a shape on the screen" tutorial (which has a SDL1 implementation). But, hey, there you go. A triangle, rendered in perspective, in my language.

If you're familiar with the NeHe tutorials, you might expect there to be a square on the screen, too. And the square does get drawn, just not at the point that you see here - I have a few different "game modes", and in the first state, I draw a triangle. After several seconds, I switch states, and then I draw the square. So that's even fancier than the NeHe tutorials. Take that!

For the next foreseeable bit, I'll be hooking up OpenGL to my language, so that's not pretty, but it's what needs to happen. I suppose I can write a Python script to grab GL.h and provide some amount of interface for free.


A few things that I should add to my TODO list:

• GLES support - I'm using the old OpenGL glBegin(GL_TRIANGLES) style. That won't fly on all the platforms I intend to hit, so I'll rewrite the triangle using a vertex array, which hopefully my language will be able to support natively.
• Strings - pretty soon, I'm going to want to accept user input (for a high score list?) and show text onscreen (on an about screen?) without the gross approach I used in Pong, which included a draw_char call that put a character at a position on the screen - no word wrapping, no language support for strings. Maybe that won't be too hard.

I have nothing to say, but it's OK, because now I can say it.

Apologies to The Beatles.

A bit ago, I copied the sourcecode for my Pong game into a new directory, as a way to start work on my next game in my language. I proceeded to comment out a large chunk of code.

Tangent: languages often don't have good facilities for commenting out chunks of code that might already include commented out code. In C++, say, you've got your single line comments

// like this

And there are multiple-line comments

/*
 * that can go on for many
 * lines, like this
 */

And if you want to disable a chunk of code that has a single-line comment, it's fine:

  for (int i=0; i<10; i++) {
    if (i < 3) {
/*
      // show small numbers
      printf("small number %d", i);
*/
      process_data(i);
  }

But it gets tricky if I wanted to disable that entire loop because */ terminates a comment, even if the comment was itself in a comment.

C and C++ have one more tool, the preprocessor, which helps some, so I could just do this:

#if 0
  for (int i=0; i<10; i++) {
    if (i < 3) {
/*
      // show small numbers
      printf("small number %d", i);
*/
      process_data(i);
  }
#endif //0

but that's still not terrific. Maybe disabling code isn't what a compiler is for. Still.


But that's not what I came here to talk about today. As I was saying at the top, I commented out a bunch of code from my Pong game, and stuff wouldn't compile. Ok, I thought, perhaps I was sloppy and commented out half of a function, and the remaining bits are causing problems. That may well have been part of it, but I cleaned up the obvious errors like that, and still I was running into issues.

One thing that doesn't get a lot of coverage in compilers tutorials is how to deal with errors - lexing errors, parse errors - there's perhaps a paragraph talking about inserting a special error token into your language and that's what gets called when things go wrong, which is a start, but then what do you do when that production gets called? How do you present enough information to the user of your compiler to fix the problem?

Right now, I print a warning with a line number and a little more information, which isn't currently sufficient. For one thing, the line number doesn't line up with the actual line number of the file being compiled. I think part of that comes from my compiler starting at line number 0 versus emacs, which starts at 1. Also, if I #include files, those throw off the numbering. Whoops. So, that's stuff to fix.

It'd also be nice to know what column the error was on, if I know that.

I've looked a little bit at pycparser, which seems to do a better job than I am for this sort of thing. TODO: roll in more of pycparser's approach to error handling.


And even that isn't what I meant to be talking about.

So, I waded through the output of my compiler, complaining about unexpected closing braces, and I ultimately determined that code like this was causing trouble:

void display_char(char c) {
# sdl_show_char(c);
}

Seems innocuous - a call to an external function that I commented out, since I'm rewriting my graphics library. Except, whoops, aha. The body of display_char is empty. And, whaddayaknow, my compiler doesn't like empty bodies for functions. Or, as it turns out for if/elif/else bodies, either:

if (phase == PLAY_GAME) {
#  draw_game();
} elif (phase == SHOW_TITLE) {
# draw_title();
} elif (phase == SHOW_CREDITS) {
# ...
}

As it turned out, that was super easy to fix - I just extended my grammar to allow statementlists to be 0 or more statements, instead of 1 or more, which is how they were before.

So, now I can have functions that do nothing, and blocks of code that are empty. Progress!    

Local arrays, arrays of objects

What you see here is an array of user-defined objects (Ship) like so:

class Ship {
  Vec2f pos;
  Vec2f vel;
}

in a locally-defined array. And you can see position and velocity being set, and then the position being updated using the ship's velocity. And the values are being read out correctly.

All working as you expect.

After the flailing to get the arrays working to begin with, this feels anticlimactic.

Next up: graphics, including using the above position and velocity data, vertex arrays, all on the way to an Asteroids-like game.

Reading/Writing ints/floats to global arrays

It doesn't look like a big thing, but the relevant bit of my code is this:


int intvals[3];
float floatvals[10];

int main() {
  intvals[0] = 17;
  intvals[1] = 19;
  floatvals[0] = 3.14;
  floatvals[1] = 1.5;

Here, I'm allocating two arrays in global space, assigning to them (and then reading from them, not pictured in the code snippet here).

A couple things I discovered along the way, which isn't well documented in the stuff I was looking at, was that array allocations need to have their "linkage" specified, which I haven't been doing for other global variables. Also, I wasn't able to get things working until I provided initializers for my arrays. That's a good thing, and I was considering providing default initialization anyway. I found it surprising that the LLVM assembler didn't want to accept my generated bytecode until I provided initialization values for my arrays.

Next up:

- arrays declared locally (top of function, inside loops)

- arrays of structs (e.g. Vec2f, Ship)

- *GL linkage, passing arrays through to OpenGL and WebGL

Loading into, reading from, structs

I've found that in order to make progress on my language, it helps to have very specific lines of code that I want to make sure my compiler compiles, and focus on those.

The couple lines of code that I've been struggling with off and on lately have been:

  newpos.x = pos.x + vel.x;
  newpos.y = pos.y + vel.y;

Really simple stuff; retrieve member data from an aggregate type, do some arithmetic, store the results into member fields of an aggregate type. It so happens that this is simple physics / animation code, but the compiler doesn't care about that.

I had done some reading of the LLVMlite documentation and was sure that I needed to do some sort of insert_value and extract_value code. And then there's getelementptr, which is tricky, to the point that it's got its own FAQ page: http://llvm.org/releases/3.5.1/docs/GetElementPtr.html

In my previous post, I talked about using Clang as a reference - I might not have to use all of LLVM if Clang's got a way to accomplish what I'm doing, I can do the same thing that it does. And all it does is simple getelementptr instructions. 

So, I started stripping out stuff that I had built to handle stuff on the left hand side of assignments differently from stuff on the right hand side. I put some getelementptr calls into my code. I started seeing errors about "gep not implemented on identified struct type", which I thought I maybe had to work around, but it turns out that somebody else had run into that bug and had submitted a fix for it. So, git pull and reinstall the LLVMlite module, and all of a sudden, things were working a lot better.

There's still some gross bits that are left over from my efforts to set up a complex solution to what was ultimately a simple problem - that's got to get cleaned up before I push this stuff up to my repository. I think I've also found some pointer stuff that now looks ripe for refactoring.

Next short term feature: (static?) array support - being able to create an array of objects, either simple or aggregate objects, and then reading and writing those objects.

Longer term ambition: some sort of Asteroids-ish clone. That'll put the above physics / animation code into context, and having a collection of asteroids floating around the screen will motivate the array support.

Getting away from language features, an Asteroids clone will provide pressure for more OpenGL support, which will be a good thing.