Worldbuilder 0.2.2 Release

The next incremental version of Worldbuilder is now out. No huge changes to planet generation itself, but the user interface has received some significant improvements in terms of usability. Some of this stuff is really standard, and sort of feel bad that it wasn’t already in early versions, so I apologize that it took this long to become available. But the program continues to get polished up, a little here, a little there, so I hope your experience will keep getting better.

Generating Spherical Distance Fields from Polygons

While working on Worldbuilder v0.2, I spent a fair amount of time implementing an algorithm for generating distance fields on the surface of a sphere. It was admittedly a struggle, with many false starts, but I finally stumbled upon a solution that works well, producing a distance field with a high degree of accuracy, and executing very quickly with the help of the GPU.

Most of the literature I could find on the topic was focused either on generating distance fields for flat 2D images, or for full 3D space. In both cases, space was always Euclidean, whereas distance on the surface of a sphere behaves quite differently. Additionally, most algorithms I ran across were focused on calculating distances from a collection of points, but for reasons I’ll discuss below, I needed to calculate accurate distances from polygon outlines. Some of the 3D algorithms were tantalizingly close to what I wanted, since they often started with a triangle mesh as their input, but the 3D aspect greatly increased the complexity of the algorithms relative to my needs, while still not addressing my non-Euclidean needs.

In the end, the algorithm that I finally implemented is honestly nothing very impressive, and I kind of figured it out by accident. But it works, and it works well, despite being something of an ugly hack. As it might help others needing to do something similar, allow me to share the details of this algorithm, along with the journey getting there. Though admittedly, the journey does get a bit verbose at times, so feel free to jump straight to the final algorithm. I tried to keep that section relatively self-contained. Just know that you’re skipping over loads of pretty pictures. (more…)

Worldbuilder 0.2.0 Release

Today brings a new version of Worldbuilder! The primary focus has been on the presentation of the planets. Much work has gone into getting away from being limited by a low-resolution triangle mesh during rendering, and instead doing far more on a per-pixel level. It has also made it significantly easier to add lighting and to handle a wider variety of map projections.

Worldbuilder: Initial Release!

I apologize for being quiet for so long. I’ve been working hard on my Worldbuilder random planet generator, as well as preparing my website for Worldbuilder’s eventual release. Today that release has finally arrived, and Worldbuilder is now available for purchase from the Experilous Store!

It’s a long ways off from what I envision it could become, but it’s already got a lot of potential value. If you are an author of speculative fiction, a map enthusiast, or a programmer interested in procedural generation, read on to find out what Worldbuilder is already capable of, and where I hope to go with it in the future. Or grab the free demo here and try it out yourself. (more…)

Modular Procedural Generation with Lua

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…)

Planet Generation Tool for Worldbuilding

As I mentioned earlier this month, I’ve been encouraged by the interest in my planet generator experiment. In particular, I was surprised and excited by the wide diversity of interest outside of strict gaming and game development circles. This interest led a friend to suggest the possibility of developing a fully functional professional tool based on the experiment that had been predominantly intended for use in a strategy game.

After recovering from this month’s Ludum Dare game jam, followed by research, planning, and some early development, it appears that I’m definitely proceeding with this project. In terms of determining core features and priorities, I’m taking fantasy/sci-fi authors as my primary target audience, to aid them in their worldbuilding efforts. But the intention is that the software will be quite engaging for worldbuilders and map aficionados in general, as well as for those interested in procedural generation. (more…)

C++, PRNGs, and Function Parameter Order of Evaluation

Tl;dr:
If numerical determinism is important for your application, never use a PRNG to generate more than one function parameter at a time.

I just got bit by C++’s unfortunate underspecificity regarding the order of evaluation of function parameters. I was working on adapting a procedural generation algorithm (based loosely on my planet generator code) from floating point numbers to fixed point numbers. The goal was to ensure that regardless of compiler, OS, or CPU architecture, the same code would generate the same planet, if starting from the same pseudo-random number seed and using the same generation parameters. Despite IEEE 754 being an extensively designed and very mature standard, in practice there are more than enough other variables at play to make floating point unreliable from machine to machine if exact replication is required. Just search for “floating point determinism” for plenty of examples.

Quite obnoxiously, but not unexpectedly, the results with the new fixed point code were substantially different from the floating point results. Not completely different; I could tell that some steps were behaving nearly identically, which proved that most of my fixed point code was functioning correctly. Tracking down the source of the discrepancy was harder. Was my implementation of a cross product backwards, leading to blatantly wrong vectors? Or was it something more subtle, such as a chaotic variable tipping just enough across its threshold to lead to radically different behavior? (more…)

Ludum Dare 31

U+2603: The theme for LD31?

Only three hours remaining until the theme for Ludum Dare 31 is announced. I’m gonna have a go at it again, preferably with far more success than Ludum Dare 30. I’ve been in a rather good mental state this past week, and am well rested, so I’m optimistic. And the possibility that the Unicode Snowman will be the chosen theme doesn’t scare me. Not that I have any idea for what I’d make for that theme or any other. I’m fully in the just-wing-it mode of thinking for this one. We’ll see how that goes.

I’m assisted this time by Jeremy Breau of Antithesis Design. The media assets he’ll be creating will no doubt be far better than any weak vector art I would throw together, and having a partner with whom to share the design efforts is always rad.

Meanwhile, the very encouraging interest from Hacker News and reddit this past week, along with a very insightful business suggestion from a friend, has me reconsidering my plans regarding my planet generator. (more…)

Procedural Planet Generation

For the past two and a half weeks, I’ve been working on a procedural planet generator.  This weekend I finally polished it up enough to talk myself into putting it online.  You can check it out here.  (It’s heavy on the JavaScript, so I recommend Chrome.  Firefox and IE are slower, but manage.  I haven’t tried any other browser yet.  Also, I’ve never yet delved into supporting touch controls, so it’s pretty much keyboard only.  Sorry mobile users.) (The above link is for version 2, uploaded April 7th, 2015; version 1 is still accessible here.)

Update, October 2015: Worldbuilder Version 0.2.2 has been released, inspired by this prototype. Includes flat map projections and per pixel detail!

A lot of different steps go into generating the planet, utilizing a variety of algorithms and techniques.  They’re not perfect, and some of them are in fact quite finicky, requiring a lot of cautious tweaking of parameters and behaviors.  Some of them are bad enough to make me cringe.  But they work.  At least well enough to make some pretty pictures, and some planets with enough variety that they might be a half decent foundation for some strategy mechanics.  So in case anyone might be able to glean some useful ideas from my work, allow me to delve into some of the details (and include tons of colorful pictures along the way). (more…)