Blobs in Games

Updating the Polygon Map Generator demo #

Saturday, November 16, 2013

When I published the Polygon Map Generation article in 2010, I wasn't expecting it to get as much attention as it did. It's now one of the more popular pages on my site. I also got lots of feedback and feature requests. I decided to implement a few of the easier features.

Labels: maps , voronoi

– Amit – Saturday, November 16, 2013 – 3 comments

Notes on noise functions and map generation #

Sunday, September 01, 2013

Over the summer I decided to study signal processing, with audio and music as potential applications. I should've realized that my brain would get back to maps somehow. I had been writing newbie-level notes for myself using emacs org-mode. Someone asked me about map generation, so I turned the signal processing notes into notes about map generation. Org-mode was really nice for writing notes. It let me mix notes and source code, and then I exported it all to HTML:

Notes on Noise Functions and Map Generation

Labels: maps , math , noise

– Amit – Sunday, September 01, 2013 – 0 comments

Summer break #

Wednesday, August 07, 2013

After finishing the hex guide and then playing with emscripten I decided to collect all the techniques I used for html5 visualizations. I wanted to see what there was in common among the articles I had written so that I could turn it into a library that I could use for future articles. Unfortunately there wasn’t much. That left me a bit disappointed. I also tried to solve some performance woes with my hex guide when viewed on an iPad. I got some improvement but not as much as I had hoped. That also left me disappointed.

I’m also finding myself spending more of my time helping people privately, over email, and am trying to decide how much time to spend there. I’d rather be helping thousands of people with an article than helping one person with an email, but maybe I can turn some of the emails into short articles, less polished than the ones I’ve been writing.

When I was a kid I spent most of my time on schoolwork. I seemed to learn slower than my friends did, so I was the one reading and re-reading the book while they were out playing. I learned to value 16 weeks of summer break and 3 weeks of winter break as the times when I could learn new things in unstructured time, with no expectation of doing something useful.

So I thought back on those times as a kid when I just learned something without a specific goal in mind, and decided to take a break from writing articles for the rest of the summer. I pulled out my list of things I’ve always been curious about, and decided to study sound & music. That’s a pretty big area, so I explored a little bit and ended up looking at digital audio signal processing.

I’m reading David Cottle’s tutorial to learn about procedurally generated music. I’m also reading Andy Farnell’s Designing Sound to learn about procedurally generated sound effects. I’m also reading Steven W. Smith’s The Scientist and Engineer’s Guide to Digital Signal Processing to understand the math and algorithms.

SuperCollider is an app that lets you program sound and music. Cottle’s tutorial uses it. Here’s an example of using one sine wave to set the frequency of another sine wave, and then removing the high frequency sounds using a filter:

{ LPF.ar(
    in: SinOsc.ar(
       freq: SinOsc.kr(freq: 70, mul: 100, add: 440)
    ),
    freq: 300
  ) }.play

Pure Data is a more visual way to program sound and music. Farnell’s book uses Pure Data for its examples. Here’s a Pure Data example of the same thing as above:

It’s not as compact (especially every add and multiply having to be a box with connections) but you can click on numbers and change them easily. That makes it easier to explore the space of values; the space of structures is still inconvenient to explore. My programmer background makes me lean towards SuperCollider, which is why I’m trying to spend more time in Pure Data to learn a different way of approaching problems.

Will I do anything with this? I don’t know. It doesn’t matter. I’m just learning it because it’s interesting!

Labels: project

– Amit – Wednesday, August 07, 2013 – 6 comments

Porting SimBlob to the web #

Thursday, June 13, 2013

I first saw Emscripten a few years ago. It compiled C++ to Javascript. My mind boggled! How cool! This year at Game Developers Conference there was a talk showing that Emscripten plus asm.js could run C++ games in the browser with good performance. I was amazed.

After publishing my article on hex grids, I decided I should do something different for a little while. I remembered Emscripten looked intriguing, and I should try it out. Could I make BlobCity, an OS/2-only game from 15 years ago, run in the browser?

TL;DR: Yes, try it out here!

Here's what I started with, a game that only runs in OS/2:

Labels: emscripten , programming , project

– Amit – Thursday, June 13, 2013 – 8 comments

Origin Story #

Wednesday, June 12, 2013

SimBlob. This is the project that got me interested in tile games, hex maps, pathfinding, road drawing, economic simulation, AI, and procedural map generation. Those of you who have been following me for a long time know that these are topics I'm especially fond of. This project was a huge influence on me and my game programming site. It ended 15 summers ago.

SimBlob was the simulation game engine / project that I was going to use for a building game called BlobCity, but I also wanted to use it for other games. As typical for people who work on a game engine first, I didn't finish. But that's ok. I was writing the game in order to learn and experiment, not learning and experimenting in order to write a game.

More screenshots from 1995-1998

Labels: project

– Amit – Wednesday, June 12, 2013 – 3 comments

Notes on implementing interactive articles #

Friday, May 10, 2013

While writing my guide to hexagonal grids I ran into some html+css+js issues that I need to spend more time learning about. Here are a few things that are on my mind.

Labels: making-of

– Amit – Friday, May 10, 2013 – 0 comments

Guide to hexagonal grids #

Wednesday, May 08, 2013

A few weeks before Game Developers Conference, I thought to myself, what article can I write that’ll just take 2 weeks? I decided hexagonal grids, as a subset of my bigger article on all grids, would be a reasonable choice. I already have all the material; I've collected it for nearly 20 years on my site.

I was wrong.

Labels: grids , hexagons , math

– Amit – Wednesday, May 08, 2013 – 2 comments

Curved Roads and Tracks #

Thursday, February 21, 2013

I love city building and transportation games, and ever since I worked on one, I’ve had a side interest in how to represent and draw roads and railroad tracks. After playing lots of Cities XL, I started to wonder how I’d represent curved roads.

Labels: math

– Amit – Thursday, February 21, 2013 – 5 comments

Playing with the dot operator #

Sunday, July 22, 2012

Normally the “[]” operator is used for extracting an element out of a sequence. Sequence[Index] turns into *(Sequence+Index) in C. And since + is commutative, it’s also Index[Sequence]. Yes, you can write 3[a] and it’s the same as a[3]. Is that useful? Probably not. But it’s interesting.

I want to talk about the “.” operator. It’s taken for granted, like “[]”, but I think it’s interesting to question how it works.

Normally the “.” operator is used for extracting an element out of a record. In Python it’s two hash table lookups. Given a.x you first look up a in the current namespace (stack frame) to find a record, then look up x in the record. In many languages one or both of these steps are optimized, but I’m going to explore the straightforward unoptimized implementation.

Field lookup

Let’s consider field lookups a.x, a.y, b.n, and b.y. (Note: for simplicity I’m conflating variable names and record ids in the diagrams and sample code but they’re really separate things.) Here’s the conventional view:

In code, we can think of it like this (Python syntax):

values = {}
values["a"] = {}
values["b"] = {}
values["a"]["x"] = 3.14
values["a"]["y"] = 2.71
values["b"]["n"] = "no"
values["b"]["y"] = "yes"

We think of the record as primary and the field as secondary. But does it have to be this way? One of the reasons this layout is preferred is optimization. In a language where record types are known, mapping from field name to offset in the record can be resolved at compile time (like this). This means we can use a simple dereference instead of a hash table lookup. For this blog post however I’m going to ignore optimizability and instead look at the alternatives.

Combined lookup

What if we put both the record id and the field name into a tuple, and made them siblings in the lookup process?

In code, we can think of it like this:

values = {}
values[("a", "x")] = 3.14
values[("a", "y")] = 2.71
values[("b", "n")] = "no"
values[("b", "y")] = "yes"

Are there any downsides to this, other than optimizability? It’s a little more work to enumerate the fields of a record but you can mostly do the same sorts of things with this implementation as you can with the conventional implementation — lookup, assignment, field insertion, field deletion. This approach may be useful in some situations but I didn’t pursue it.

Record lookup

What if we made the field name primary and the record id secondary? Back in the 1990s when I was into programming languages (I’ve since recovered), I played around with this idea.

In code, we can think of it like this:

values = {}
values["x"] = {}
values["y"] = {}
values["n"] = {}
values["x"]["a"] = 3.14
values["y"]["a"] = 2.71
values["n"]["b"] = "no"
values["y"]["b"] = "yes"

One interesting idea that came out of this experimental language was the idea that the field name could be local to a module or function. (See also: symbols in Lisp packages.) With this feature, you can attach fields to records without needing subclassing. (Ruby’s mixins are some like this except they only allow methods, not data.) Records become only IDs; all the actual data is attached from the outside. (See also: database normalization.)

Imagine being able to attach per-module fields to objects. Imagine being able to treat a “field” just as you might treat an “object” in a regular language: take fields as function parameters, return them from factory functions, import/export them with modules, store them inside objects, etc.!

Use in games

Is this useful in games? I think so. I think it might be related to what entity/component systems are trying to build without having direct language support. The entities are the records and the components are the modules and local data. Consider this data:

Object-oriented systems organize this by column. There’ll be a soldier module that defines a class with x, y, and health, and a beacon module that defines a class with x, y, and color. There will probably be a game object superclass that contains x, y.

When you treat fields as first class constructs in the language, you organize this differently — by row. You’d put the x and y fields into one module, health into another, and color into a third. Code that works with soldiers would import the position and health modules. Code that works with beacons would import the position and color modules. And code that works on either would only import the position module. You can mix and match features — for example, an object with both health and color takes no additional classes or code in this system, because health and color are in separate modules. You keep traditional syntax like soldier2.health; it’s just that health might be a local field instead of a global one, visible only in modules that have imported the health field. You can attach local fields to records at run time and detach them when no longer needed.

It’s quite possible this system wouldn’t work out in practice. I never finished my programming language so I can’t point to a concrete test of the principles described here. The ideas from the experiment have definitely influenced how I write code; that’s the outcome I hope for when exploring an idea. It’s fun to take something mundane like “.” and ponder how else it could work.

Labels: ideas , programming

– Amit – Sunday, July 22, 2012 – 3 comments

2d Visibility #

Thursday, July 05, 2012

For one of my projects I wanted to calculate the areas that are visible from the player. In a 2d top-down game or an isometric game you can calculate visibility and lighting in 2 dimensions and store it in a bitmap. As usual I got distracted by writing about the algorithm. I've spent too much time on writing it up so I'm going to publish it even though I'm not quite happy with the explanation. I can revise it later.

Here's the algorithm for 2d visibility along with a demo and source code.

Notes about the process

Part of what took a long time was going back and forth between the demo and the tutorial. The demo showed some concepts, then the tutorial tried to explain them. Then I realized that I'm missing some concepts and need to update the demo to show them. This took quite a bit of iteration.

A nice side effect of trying to explain the algorithm is that it helped me improve the algorithm. In an earlier version, sorting lines of different sizes didn't work well. It wasn't a problem in my project because all the lines were the same size, but in the demo it was an issue. While trying to explain this I found a better way to sort the lines so that it worked on all lengths. Another corner case that doesn't work well is when the lines intersect. This also doesn't happen in my project but it can happen in the demo. I decided the solution would complicate the demo code too much (I want it to be reasonably readable) so I instead detected those corner cases and marked them in the demo.

The other thing that took so long was that I kept rewriting the UI portion. The original version was for an isometric game, and used shaders to project the light map onto the 3d world. Next I wrote a Haxe + Canvas implementation to run as part of the article, but decided that I should write the UI in Javascript directly because I was more familiar with it. I kept the core algorithm in Haxe (shared with my Flash projects) and wrote the UI in Javascript + d3.js + SVG. It was easier to work with but it ran too slowly on the iPad, and as much as I love d3, this isn't a great fit. So I then wrote a JqueryUI + Canvas implementation. That too was slow but after learning more about Canvas I was able to speed it up to run reasonably on the iPad. I learned a lot by trying different languages and libraries; I hope not to spend several months on the next tutorial.

Blobs in Games
From Red Blob Games's Blog