It took me three weeks of design, redesign, more redesign, lots of implementing scattered within, and three intense days of debugging a giant mass of previously untested code, but I finally have a basic modular system in place for running all procedural generation from Lua. This will enable me (and eventually anyone else) to quickly experiment with various algorithms for every stage of planet creation and presentation.

Unfortunately, I have a lot of optimizing investigations to do, because it seems to be running about 100 times slower than the prior C++ code. But at least it generates the exact same planet (give or take a few subtle discrepancies due to slightly different math here and there). Based on some of my earlier experiments at the beginning of the month, I’m pretty sure I can bring that up to within at least 10% of the speed of my C++ implementation, and quite possibly within 50% of its speed. Just need to profile and figure out the bottlenecks. (Edit: A day’s worth of investigation has gotten me up to around 13%, or 7.5 times slower than the C++ implementation. That should be acceptable for the moment.)

A cool thing about the architecture I ended up with is that not only will it naturally support a rich modularity of hooking up algorithms at different stages to each other, but that the way this modularity is exposed will also automatically enable a significant degree of concurrent execution on multiple cores with little to no effort on the part of the script writer. Right now I have only implemented a single threaded execution model, but I should be able to change these details under the hood when I get to that stage in the project, and the Lua scripts won’t know the difference. If you’re curious, allow me to provide an overview of how I’ve designed this modularity and concurrency. (more…)

A few weeks ago I introduced you to what I felt was an impressive little data structure that can provide constant time complexity for the standard operations, stores data contiguously, and provides stable handles that remain valid across all operations other than removing the referenced items themselves.  Today I want to extend the basic data structure with some additional functionality which will be focused on iterating over the contiguous items in order.  While iterating, we may wish to modify the collection as we go (such as conditionally removing some items).  We may also wish to rearrange the items so that a simple linear traversal will also happen to hit the items in a particular order (such as sorting 3D objects from front to back to take advantage of a depth buffer and reduce fill-rate). (more…)

I recently ran across a couple of blog articles describing a data structure that provides a set of properties that I often am seeking:

  1. Contiguous data storage, good for linear iteration and maximizing cache utilization
  2. Constant-time insertion, deletion, and relocation of elements
  3. Stable external references to elements regardless of internal relocation
  4. Constant-time look-up from external references without hashing

(The two articles were from the makers of the Molecule Engine and the BitSquid engine, respectively.)

Fascinated by data structures and algorithms in general, and lured by the appeal of these properties, I set out to study the concept and implement my own version.  It’s quite simple to implement in a basic form to achieve the above four properties, and can easily be extended to acquire some additional behaviors at the cost of additional memory or extra operations.  In this first article, I’ll walk through the basic concept, as well as a simple implementation in JavaScript.  Later articles will explore some of the possible extensions. (more…)

Understand the data, and understand how it is used.

Over the past few weeks, I’ve been struggling to get past a point of excessive complexity in the simulation code for my city builder prototype.  I went through a few different refactoring attempts trying and generally failing to manage the complexity.  But the most recent attempt finally appears to have succeeded, and I think it has also has gotten me one step closer to properly grokking data oriented design. (more…)

The game concept that has generated the greatest amount excitement for me thus far is a modern large-scale city builder, naturally inspired most strongly by the SimCity series.  I have waffled on whether I should even try to make any progress on this project right now, as it is a large one, perhaps monumental, and it is arguably unwise to get bogged down on such a big project right out of the gate.  But I gave myself a Christmas gift and allowed myself to take a pause from my other prototype projects and to begin digging into this one.  No reason to fight one’s inspiration, and nothing wrong with having multiple projects ongoing. (more…)