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