While working on the Make It Random library for Unity, I took up an engineering challenge: generation of random floating point numbers between zero and one quickly and with perfect uniform distribution. The most common method, dividing a random integer by the full range of possible integers, has a few substantial flaws that I hoped to avoid:
First, it involves a division operation, which could naturally slow things down a bit.
Secondly, although the distribution on a high level is uniform, it’s more clumpy for higher numbers closer to one, and more diffusely spread for lower numbers closer to zero, so the uniformity is imperfect.
Third, the quantity of possible integers generated rarely maps cleanly to the possible number of floating point values available, and so different floating point values are likely to have at least slightly different probabilities of occurring, further weakening the uniformity.
And fourth, even when the mapping from integers to floating point values is carefully managed, if the range of values needed is not a power of two, this adds further problems to any attempt to get perfect uniformity without sacrificing performance, due to how typical random engines generate data as chunks of bits.
With the help of various sources around the internet plus some clever use of probability mathematics, I was able to conquer all of these difficulties, providing perfectly uniform and fast generation of floating point numbers in the unit range. This includes all four variants of whether the lower and upper bounds are inclusive or exclusive. The techniques involved are explained below.
The first two are not at all new, but are included because I have not seen them discussed as often as I think they deserve, and because they help build the context for the third technique. This last technique is something I devised on my own, and although I have no doubt other smart people have already discovered it or something similar, I never ran across it while researching, so I’m eager to share it with others in this post. Plus, I suspect that the general technique can be usefully applied to other random value generation beyond just floating point numbers, so the more people are aware of it, the better. (more…)
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.
As always, a demo is available for download, and the full product can be purchased from the store page. (Once purchased, you’ll continue to have free access to future updates.) If you have already purchased Worldbuilder, the downloads can be found here. (more…)
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…)
A user alerted me of a bug with the tectonic plate visualization layer, in which ugly black stripes were showing up. Upon inspection, it turns out that it was due to some angle values becoming excessively large, but only on some maps and not others. Clamping them to a maximum reasonable value got rid of the black stripes.
The fix has been uploaded and is available in version 0.2.1, available now.
So I had a few errors in my initial v0.2.0 packages. I have corrected these and uploaded the new files. Sorry for any inconvenience!
The first problem was that I embarrassingly left in some debug code that was trying to save image files to a hard-coded path on my local system. Oops.
The second was that I thought I had included all the necessary files for the new Visual Studio 2015 runtime library. Apparently not, and apparently it’s best to just use the redistributable installer from Microsoft. But until I get a proper installer created for Worldbuilder, it’s more convenient for users to not have to go through that process. So I returned to Visual Studio 2013 for this 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.
A demo is available for download, and the full product can be purchased from the store page. (Once purchased, you’ll continue to have free access to future updates.) If you have already purchased Worldbuilder, the downloads can be found here. (more…)
In an attempt to make the OpenGL support more robust, I offer you Worldbuilder Version 0.1.2. In particular, prior versions implicitly required OpenGL 4.1 or higher, and if that version was not available, would mysteriously fail to to run, render, or in the worst case crash. Worldbuilder now only requires OpenGL 3.0, and it ought to fail more gracefully and with improved error reporting when that or other miscellaneous requirements are not met.
Pixel format requirements have also been loosened so that the program should still work even in the absence of certain nice-to-have features such as multisampling, or can work with color/depth/stencil buffer combinations of a few different bit sizes, instead of requiring exactly 32, 24, and 8 bits for each.
As a small bonus, saving a view to an image file will now attempt to use multisampling if available, reducing the need to save to a larger image and then downsample manually in order to get antialiasing.
If you already own Worldbuilder, you can head over to the product page now to download the new version. If not, you may download the demo to get a feel for the program’s current capabilities (and validate that it functions well on your system). Then head over to the store if you would like to pick it up at the early support discount price.
Improved OpenGL initialization to be more robust and flexible.
Enhanced OpenGL-related error detection and reporting.
Required OpenGL version reduced from 4.1 to 3.0, and is now explicitly checked instead of resulting in a crash.
Save to Image will now use multisampling if that option is available.
Lua module suites updated to no longer use UInt32 instances as loop counters, as that turned out to be useless and in rare cases unstable.
So as to not leave you with only the dryest of dry content, I shall also whimsically include a distance field that was produced from a randomly generated tectonic plate. Black indicates regions that are outside of the tectonic plate, and the grays of increasing intensity specify the distance of each pixel to the nearest edge of the tectonic plate. The closer to white a pixel gets, the further it is from the nearest border. There’s a lot I’ll be able to do with this information!
You can see a couple more pictures related to distance fields and planet rendering in my recent tweet.
Reviews of my Ludum Dare 32 game Deserializer are going well! Feedback has been very positive, but has also provided some useful critiques. I’m looking forward to the rankings being finalized and published Monday evening.
But I haven’t been sitting still. Although I’m proud of what I accomplished in three days, I know that the game is far from perfect. I believe that the core mechanic of a Frogger-style play field and movement plus pattern-matching is solid, but the specific type of pattern matching and its associated mechanics are definitely not ideal. So yesterday I spent some time away from the computer doing some paper prototyping. After a few iterations of conjuring up and tweaking new rules, I believe I’ve found a game objective that will work better. Allow me to describe a bit of the process I went through. (more…)
Ludum Dare 32 is over! It’ll be three weeks before ratings are completed and I find out how well I placed, but I already feel like my experience this weekend counts as a smashing success.
My entry is Deserializer, a vaguely Frogger-like game of network packet sniffing. The objective is to steal the system password by deserializing passing packets of data, without getting caught and blocked from the system.
Time to take a break from Worldbuilder development, for it is once again a Ludum Dare weekend! This time I’m going to try out Unity 5.0. I’ve dabbled in Unity 4.x in the past, but never quite felt comfortable enough with it to use it for rapid prototyping. I’m looking to remedy that by subjecting my inexperience to the fires of game jam hell.
But before Ludum Dare 32 officially starts, I did want to make sure I am capable of producing at least something playable in Unity in a short period of time, so I made a tiny little vertical shooter. Took around five lazy hours, so I’d say that’s a good sign that I’ll be able to pump something out over a 72-hour timespan. As long as I don’t get paralyzed by game design brain farts.
The game can be played using the experimental WebGL build or the Unity Web Player, and you can grab a Windows build, in 64-bit or 32-bit form. Controls are basic; AD/arrow keys to move left/right, and spacebar/left mouse button to fire. The points you get for each enemy destroyed are proportional to the number of enemies on the screen.
The first follow-up version of Worldbuilder is released, Version 0.1.1! This is admittedly a minor version, but comes with some very nice usability improvements, a few new features, and better error detection and messaging, as well as some miscellaneous bug fixes. (Click here to purchase. There is also a demo available. If you have already purchased it, you may proceed to the download page.) (more…)
Today I back-ported some of my flat map code from Worldbuilder to the planet generator prototype that I made last year. So for anyone who has been wanting to view a flat map rendition of those really cool planets, but isn’t ready to spend $4 on my Worldbuilder early supporter discount offer, you can give the new version of the old prototype a spin. No procedural generation code was altered, so seeds from the original version will work in this one, generating the same planets as before.
Lua is a dynamically typed language, with only a small selection of primitive types. Any aggregate or otherwise complex types must use tables (i.e., dictionaries/associative arrays) in some form, which will significantly impact the performance of field/method access as well as the efficiency of data storage (and thus cache usage). LuaJIT’s foreign function interface (FFI) let’s us work around those limitations by offering us the ability to use C declarations to define new types with much greater control and efficiency. In this blog post, I’ll share how, for my Worldbuilder project, I used the FFI to implement a fairly performant fixed point number type. Public domain source code can be downloaded here. (more…)
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…)
I mentioned in my previous post that I needed to do some serious performance optimizations on my Lua code, and indicated in an edit that after a day’s worth of effort, I managed to speed things up by roughly a factor of 13. I have some more work to do, but in the hopes that the steps I’ve taken so far are helpful to anyone else going through a similar process, allow me to describe some of them before they slip my mind. (more…)
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…)
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…)
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…)