IA Logo


IA Information
Communication

Dave Mark's books

IA on AI


Random Map Generation for Warzone 2100

I ended up on this page via a tweet as I was ingesting my morning caffeine (meaning it was a sort of idle, random click). What I found, however, was strangely compelling. The game, Warzone 2100, seems to be a small indie project of some sort having to do with finding oil wells as resources in a post-apocalyptic world. The page I was linked straight into, however, was specifically about their random map generation tool. Specifically, I read the “about” page on a piece called “Diorama” and how it works. Interesting stuff.

The page starts out with this blurb:

This article is part technical documentation, part feature list and also part FAQ. It intends to explain why Diorama was written the way it was, why `it takes so long’ and what it can do that would be extremely hard for other random map generators to achieve.

I had to wonder if that was meant to be pretentious or not. After all, random map generation has been around for quite some time – and with excellent results in some cases (e.g. I was never disappointed with a random map in Empire Earth).

Anyway, it steps through the procedures that they use for generating the random terrain, complete with cliffs, etc., adding roads, textures, and interesting features.
The most important thing that they emphasize (IMHO) is how they transition from the blocky “first pass” into a more natural looking layout. Both for cliffs and roads they used the word “jitter” somewhat often to explain how they fuzzied things up. The before and after shots of this effect shows how much of an effect it has.
I think one of the more compelling mentions on this page, however, was that they are attempting to use answer set programming (ASP) to address the initial set-up the starting locations for players and the oil wells. From their description:
ASP is a declarative approach to solving search problems, so you write a description of the problem (in a logic like language) and then give this description to a solver (kind of like a theorem prover) which will come up with valid model (solution) of the problem. But not just any solution, we will arrive at the optimal solution, and we can prove that the solution is optimal. The down side is that generating this can take exponential time (this is why requesting very large maps can take a while) but it allows both local (“a base must have a given number of entrances”) and global (“every base must be able to reach every other base”) conditions on the map to be expressed simply, cleanly and efficiently. Critically we don’t have to change any of the algorithms when the conditions on the map change, we just change the description that gets input into the solver.

I don’t know if that is necessarily the best approach for this. Does it work? Probably. Is it overkill? Maybe. They provide other descriptions of methods that could be used (they even mention genetic algorithms) prior to offering ASP as a solution. I think, however, that there were some serious gaps in that list. I don’t want to get too deep into how I would tackle the problem… after all, I still don’t have enough caffeine in me. That’s not the point of this anyway… I just want to give kudos to they for looking into novel solutions.

Anyway, check it out. It’s an interesting read.

Tags: , ,



One Response to “Random Map Generation for Warzone 2100”

  1. Ticamai says:

    Just an FYI, Warzone 2100 was actually a commercial game- but the company who made it, Pumpkin Studios, died off, and the publisher- Eidos Interactive- released the source, and since then, people have improved the game.

Leave a Reply

Add to Google Reader or Homepage

Latest blog posts:

IA News

IA on AI

Post-Play'em




Content ©2002-2010 by Intrinsic Algorithm L.L.C.

OGDA