I’ve been wondering for a little while how one could generate new Dust-style maps.
Map generation itself isn’t new - generators that produce acceptable results have existed as far back as Doom (see ObHack, which is based off even earlier work) - so this isn’t a novel idea by any stretch. Witnessing the progress made with AI-driven techniques to create ‘new’ artwork, it feels like applying similar techniques to creating new maps should be possible.
Considering the constraints of the Dust style - axis-aligned roads, pathways, and lots of identical buildings between them (in CS 1.6 anyway!) - it feels that would be a good starting point. A decent facsimile of CS 1.6-era de_dust could be reasonably created from a 16x16 grid, where one cell in that grid could represent a stretch of road, a corner, a doorway, a bomb spot, a spawn area, or more. It’s then theoretically trivial to extend to a size of 32x32, 64x64 etc. until the desired fidelity is achieved.
There are plenty of challenges. At a minimum, you have to ensure the playable area is traversable and fully-connected, that there are sufficient spawn points (at a reasonable distance from each other), and appropriate bomb spots (or hostage locations) placed at sensible locations. That’s before even considering aspects of balance, fairness, visibility, complexity and exploitability.
There are lots of approaches, but a couple that have tickled my mind are below:
(Disclaimer: none of this my area of expertise; to an actual expert the words below may be indistinguishable from the output of a deranged GPT-2 network.)
Wave Function Collapse
This dramatic-sounding approach is nicely described in this article by Robert Heaton, which sparked this entire endeavour. My gut feel is this would be sufficient to produce the most basic of Dust-style layouts.
I also suspect this would be applied as the second step of a two step pipeline - where the first step involves generating a 2D grid defining spawn/bomb locations and connectivity between them (using simple heuristics). The second step would decorate that grid with Dust-style infrastructure using WCF.
Subsequent steps could theoretically then refine the output into something less rigid and more ‘creative’ (much like the ‘upsampling’ stages of GAN-based image generators.)
Probably my favourite approach, but a lot of weight sits on the shoulders of that first stage (generating the high-level 2D grid layout) which would be responsible for make-or-break decisions for the core viability and (re-)playability of the end result.
Generative Adversarial Network (GAN)
This approach has led us to the plethora of image generators across the web, and are now capable of generating output that is seemingly indistinguishable from that of actual artists (living, dead, and imaginary.)
My suspicion is that, with sufficient training on a corpus of map overview images from a variety of games (but let’s say Counter-Strike) - perhaps augmented with markers for spawn points, bomb locations, trails representing players moving through those environments - such a network could reasonably start producing novel designs.
My concern is that, there isn’t anywhere near enough data to produce a corpus capable of training such a network to an appropriate degree. Secondly, one would still need to convert that output (assumed to be a map overview-style image) into a physical map - a process that would have to be done by hand.
However there is one set of data we could generate plenty of, and that’s playthroughs of maps. Thousands of CS matches are played every day across hundreds of different maps - what if the movements of those players flowing through those environments could be collected and used to generate a corpus of player motion?
Augmented again with information about the map, and the outcome of the match, perhaps these data could be used to synthesise new maps with similar patterns of player motion through them. These floating streams of invented player movements could then be manually decorated with matching floors and walls into a physical, playable map.
This approach could then be extended to include sightlines, to better direct where walls and obstacles should and should not be placed.
Yet despite the vaguely-related prior art and large amount of data one could harvest to feed such a machine, it doesn’t get us quite as close as I would like to fulfilling the original goal.
Flesh-guided
Perhaps training computers to create entire new maps for us is the wrong aim. The reality is that (in the short term at least) human guidance will always be required to produce an acceptable result. So how about we only use computers to do the ‘hard’ bit until we can get them do do the entire thing?
Trouble is, what is the ‘hard’ bit? I could sketch out a decent-looking Dust-style map layout in 10 minutes, but its viability as a good map would not be immediately obvious - indeed, it would only tend towards such a state through iteration (which, in my case at least, typically occurred while physically building the thing.) Perhaps a computer can detect and ‘correct’ such a design with sufficient training or computational budget to trial-and-error it.
Perhaps the ‘hard’ bit is taking a rough layout and converting it into a high-fidelity, playable map? It’s certainly not trivial, but definitely feasible for some definition of ‘high-fidelity’ (let’s assume the now-ancient standards of CS 1.6.) CS:GO might be a stretch, though.
So would we want computers to generate the layout (which a human iterates into a playable map), or should humans generate the layout (which a computer turns into a playable map)?
Likelihood is there’s something in-between. I’m not sure what level of assistance exists in modern level-editing tools, but I would have killed for a “check playability” or “generate room” button back in the day as a means to save time.
Regardless, Clippy popping up with a “It looks like you’re trying to make a Counter-Strike map. Let me tell you why your design won’t work…” is probably still a little way off.
Next de_dust when?
Clearly, I can’t yet delegate the job of creating new de_dust maps to computers, but I wouldn’t be surprised if such a capability is reached soon, achieved by some intrepid individual.
But when that day comes I can only hope someone hooks it up to a server with an endless cycle of freshly-generated, never-before-seen maps to stop those “next de_dust when?” emails once and for all.