Teaching Heat Signature’s Ship Generator To Think In Sectors

I haven’t talked about the way I randomly generate spaceships in Heat Signature since this post – before it even had actual art. That’s partly because I’ve barely touched it since then. I showed the game to developer friends and the press in LA and SF a few weeks ago, and got lots of great input and ideas, but the main thing I came away thinking was: the on-board game needs to be more interesting. And I think better ship interiors are the foundation of that.

So that’s why I was replaying the Deus Ex games recently. My conclusions from that combined with two other ideas I’d been having about how to improve ship generation, namely:

1. Getting from the airlock to your objective should involve a series of Gates and Keys. For each locked Gate you encounter, there’s a corresponding Key somewhere in the area you can access, and fighting/hacking/sneaking your way to that is how you progress.

2. Whenever I sketch out what a cool ship interior might look like, I draw it as a series of little bubbles of space, about 3-6 modules each. One might be a long room, another might be a row of rooms, another might just be corridors that connect the rest. I call them Sectors. It feels like these lead to natural/pleasing/readable ship layouts – can I teach the game to build them this way?

And the relevant conclusions from my Deus Ex replay are:

3. The player needs multiple routes to their objective.

4. Those routes must be blocked by different obstacles, which require different methods to get past.

There’s some other stuff, but that’s what’s relevant to ship layout.

The first two are more instinct than rigorous logic: I feel like 1 will make the ships feel more like ‘levels’, and I think that’s more positive than it sounds: right now they feel like random, empty mazes – to use an even less liked term, they don’t feel like ‘content’. And they need to – if each ship isn’t a fun little challenge, the game has nothing at its core.

And 2 is my best guess at how to combat the corresponding visual ‘blah’ factor: they look like random mazes, and I want them to look more designed.

Teaching the computer to think in Sectors

Checking all these boxes is a massively complicated challenge both technically and creatively, so I tried to start as simple as possible. Let’s just have one type of Sector for now: a 3×1 room. Can you build a ship out of these?

The two neat features of my current ship generation algorithm are:

a) The interior layout always fills the whole ship
b) You can always get from every module to every other module

a) would be tricky with only 3×1 sectors, but should be doable with sectors in general – we just let one of the Sector types be a 1×1 module and then any gaps are fillable.

b) sounds tricky, but actually I’m already fulfilling it in the sketches I draw, and the way I draw them is the key to teaching the computer to do it. I start by drawing one Sector, then draw another adjacent to it, then new ones adjacent to those, and so on. If I created a doorway from the existing sector to the new one I’m drawing each time, every sector would have a route back to the start, and therefore every sector has a route to every other.

So after tinkering for a bit, I got the algorithm to do this:

And then this:

Great! They’re not connected yet, and they all tend to point in the same direction, but this is promising. The little 1×1 rooms are spaces where it couldn’t fit a 3×1 sector, in the order that they were laid. It’s definitely possible to do a better job of it than that, but that’s irrelevant – those little pockets look nice, I want them. If they were all clustered in one corner it’d look bad, but randomly dotted around like that is great.

So next, remove that direction bias. It’s happening because the code tries to place the sector lengthwise, and then if it doesn’t fit, goes through each possible rotation in turn. Since it always tries them in the same order, you end up with a lot of lengthwise ones. I tweaked it to try the rotations in a random order, producing this:

Lovely!

Now we need to connect them. As I say, it seems like you could just do this each time you place one: connect it to the old one. It’s a little trickier than it sounds to find the co-ords of the two modules in question (we need to know which modules to link, not just which sectors), but I got something logical working:

I actually don’t know why this works so well. My connect-as-you-go concept assumes that every module is part of some sector, but at this stage those 1×1 bits aren’t part of any sector – they’re just leftovers. I don’t quite have a good enough handle on my own code to tell you how it knows to link those up too, but it does.

So now I need to do some messy replumbing: right now we’re working with a single fixed sector size, but obviously I want a variety of sectors. After some deliberating, I decided to make each Sector type an object – a sort of invisible template the ship can refer to when creating itself. The template for each sector could store what its dimensions are, and what kinds of modules it contains.

Making those is easy, but having the algorithm read them in, rotate them to try 8 different orientations, then actually place them is all rather fiddly. For now I’ve settled on a slightly rigid system, where a Sector can either be a ‘Big Room’ or ‘Corridors’ or ‘Small Rooms’, but it can’t specify an arrangement of multiple elements – like one small room surrounded by corridors, for example. Supporting that would add a lot of complexity, so I decided to leave it until I’m really sure I need it.

So, with the new Sector templates in – just 3×1 and 1×1 for now – how does it look?

Oh, it’s broken. Parts of this layout are OK, but it fails both our conditions: doesn’t fill the ship, and the bits it does fill aren’t all connected to each other. Doesn’t make sense as a ship.

This, and a similar glitch, took me about a day to solve. I kept thinking there was some flaw in the way I’d implemented ‘connect as you go’ that could lead to a Sector being created but not connected to the previous one. As it turned out, the reason I couldn’t find a flaw in this code is that it was exactly right. I just had two very stupid, unrelated mistakes that both caused very similar symptoms, and kept looking like one thing.

a) I’d created a 3×1 ‘Corridor’ sector, but forgot to tell each module of it to link to the next – it wasn’t internally connected. The connections to other sectors were fine.

b) I’d set the dimension values of the 1×1 Sector to 1×3. This is incorrect. Maths tells us that 1 = 1 and not 3, so that 3 should be 1, so that it reads ‘1×1’, because one is not three, in fact it is less. Stop me if I’m going too fast.

Fixed these, and blam:

Blam is the sound of a ship being generated with a connected and spanning interior graph:

This is looking great to me, especially on smaller ships. So, on to Gates and Keys!

On, indeed, to Gates and Keys

Again I wanted to start as simple as possible. Some ships will play host to a particular mission with a specific objective, but for any that don’t, we should default to treating the ship’s cockpit as the ‘objective’ – it’s the thing they’d most want to protect.

Because we generate as we go, we don’t actually know how far along your path to the objective we are when we place a Sector. But we can fudge it: if the next sector is physically closer to the objective’s location, then we increase the security level of the door we’re placing between them. And to ensure you can open it, we put a keycard of the same level somewhere in the previous sector. Again, for now, I went ultra-basic: it dumps it right in front of the door.

This works! You can’t see them well, but those black square outlines in some modules are where keycards are placed, and some are placed less gracefully in corridors and stuff. The level it generates is always completable, though obviously not challenging yet.

So we need to move those keycards to more secluded locations, so that we can put obstacles between the player and them: enemies, security, etc. But before I put a lot of work into ensuring that can happen, I wanted to look into a possible worry with the kind of layout this is generating. And since this has taken a while to write up already, I’ll save that for the next post!

More Procedural Generation