Procedural Methods

Introduction

Recently, I've been doing research and prototyping for an economic simulation game. Yep, another one of those. However, for reasons I can't disclose, it's not exactly just another one of those. I could, however, discuss some of the stuff I came up with for this project.

One of the things we really want our system to have is the ability to have randomly-generated towns. Our simulation will have a concept of levels, but we don't want base data for a level be fixed and unchanging. Fixed maps tend to have optimal strategies for winning, and players WILL find them, and SHARE them among each other – making the game easier to later players. Random includes not only the map and the town layout, but also the demographics. In this blog, I'll discuss how I came up with the random systems we require.

Random Demographics

For random demographics, I found this website invaluable in jump-starting my knowledge of economics – at least those that I will need to make a realistic enough simulation. I started on the classic consumer theory essay to get the nails down. That essay had a link to the alternative approach using agents, which looks a lot more like something we can use. Of course, prior to reading these stuff, I've already studied a couple of economics text book for a solid grounding overall.

First, I built a couple of quick prototypes using the classical methods: indifference curves, aggregate demand and supply. It worked fine, but feels like all I'm writing are, basically, code to solve equations involving some knowns and unknowns. This isn't so hard, it turned out. It was easy enough that I have enough time to include elasticities of supply and demand relative to price, and have demographics breakdown three-ways: income scale, gender, and age. Having created these prototypes, I felt we could do better.

In the next iteration, I tried the agent-based consumer simulation. That, too, wasn't too hard. As a bonus, I got the behavior trumpeted by the article (see link above), AND the classical behavior regarding demand elasticity relative to price. There was only one hitch: it's sloooow! We're creating a web-based game and this just won't cut it. I had to be a bit creative if I want to use this approach. But first, find out why it's slow.

When doing the agent-based simulation, the code essentially generates the per-agent information once, and persists them in a database. However, during my testing/prototyping, this turns out to be the speed bottleneck. To help around this problem, I modified the simulation such that agents represent one household instead of one individual, but it didn't help much. More testing finally revealed that generating the per-agent information is faster than streaming it in and out of the database! Not that it was surprising, I just didn't think it would be such a significant problem. Finally, I modified it again to just store the rng (random-number generator) seed and use that to recreate the agents' information every time they are needed.

Random Terrain

I must confess, this part of my research is perilously close to an embellishment – until a bit later. Because a bit later, I found a pretty good way to generate random towns, and that one requires a height-map terrain – which is the output of this terrain generator. I also figured that, hey, we might someday want a way to generate random, height-map terrain procedurally. When that time comes (I hope it does of course, so I can work on this thing more. :)), we already have one ready for the task.

I started by using random numbers all over the grid. It didn't work out well of course, but I want to start somewhere! Several research ticks later I found the diamond-squares midpoint-displacement terrain generation method (a mouthful, that), and coded an implementation. My first few attempts were awful, but eventually figured it out. I also used neighbor-smoothing and band-smoothing to remove the worst of the blockiness. Much later, I simply used an erosion filter (not very good yet, but works), and neighbor-smoothing. As for the latter, turns out I had an overlooked bug during my first implementation, so I fixed it.

All in all, the terrain generation portion worked out very well.

Random Towns

This one is a lot harder that it first appears – mostly because the literature on procedural towns are either 3d-oriented, or are much too vague to easily translate to code. The one I settled on was the latter. But hey, if it's too easy, it's probably not worth doing at all. :)

Anyway, this article discussed the method I wound up using. It's basically an agent-based city generator that requires a height-map terrain as input. Its output are very reasonably realistic, and the generation can be stopped at anytime (for instance, when the desired densities are reached). The only drawback is that there are no reference implementation available. The only thing I have to go on is the article and nothing more. So that's what I used. I simply read and re-read it until I distilled the stuff I can use.

My implementation, however, does not make use of road-related agents. I 'cheated' and simply pre-generated rectilinear road grids ready to be populated with zones. This worked because the method, as discussed in the article, also 'knows' how to populate cities with pre-generated road networks.

During my coding of this random-town generator, I first used if-else clauses when laying down zones. This turned out to be a bad idea as races eventually bogged down the town-generation. That is, one cycle a zone is residential, next cycle it becomes a commercial, and the the cycle after that it goes back to being residential, and so on and on. So I recoded that zoning portion into a pseudo-agent model. I followed the article's approach of generation a normalized score for the prospect tile, and decide off that. Things went well after that and I even had time to add park zoning.

Downloads

Demo program that generates terrain, town, and zonings. This is not bug-free, and the usual disclaimer applies: I'm not responsible for any shenanigans that can happen while running this program. It ran alright on my system, but YMMV. I will appreciate any comments though, especially constructive ones.

Also, the demo program requires the dll files from the FreeSL project. I didn't really use any sound, but the framework I used used those.

Other Notes

I haven't had time to create documentation, but here are some for those who will download the files and run them.

* Zones are color-coded thus: yellow - residential, cyan - commercial, red - industrial, pink - parks.
* Regenerating roads also resets the zone development
* Regenerating the terrain, applying the filter or the smoothing, resets everything!
* Terrain generation sometimes takes a bit more time since terrain with more than 30% water are discarded. A new one will be recreated until one that has 30% or less water is found.
* The blue road is the main road and can span anything, including bodies of water. All the other roads can only span land.
* All roads MUST be accessible from the main roads (the blue ones).