Laying Out Heat Signature’s Ships: Snakey Vs Branchy

Last time I covered how I taught Heat Signature to build ships out of sectors, join those sectors together, lock some of those doors, then place keycards in the right places to ensure they’re all openable. I’d got the algorithm generating layouts like this, which is great:

But as I said at the end of the post, there might be a problem with this layout. Here’s the route you’d have to take to get from the airlock to the front of the ship:

The Snaking Algorithm

That long, snakey, back-and-forth route is common to a lot of ships this code generates, and it comes from the order in which it places the sectors. It starts with one at the airlock, then tries to surround it with new sectors. But! I also wanted each of those sectors to be surrounded too, so as soon as it creates the first one, it tries to surround that. And as soon as it places the first surrounding sector, it tries to surround that one too.

If you keep trying to surround the last sector you placed, what you’re really doing is placing sectors one after the other in a line. And since we connect each sector we place to the last one we put down, we end up making one long route that weaves back and forth across the ship.

There are a few possible problems with this:

• It’s obviously inefficient for the crew of the ship, though that’s not necessarily a major problem.
• A bigger concern is that the player might feel they’re being messed around, that the layout is contrived to take up their time.
• And the biggest one is that this long, linear path doesn’t lead to much branching – a few little twiglets sprout off here and there, but usually only one at a time. That doesn’t give me a lot of places to put keycards: ideally, before every locked door, I want to place two different key-type things that let the player open it, and put different types of hazards or obstacles in front of them. That way, the player has a choice of challenges.

I call this the Snaking Algorithm, because it tends to create one long and winding snakey path. Since my biggest concern was the lack of branching, I tried to come up with a new one that would focus on that.

The Branching Algorithm

The snaking, as I say, comes from trying to surround each sector as soon as it’s created. So I took that part out, and just let the algorithm finish surrounding that first sector.

That gives you lots of branching, but obviously doesn’t fill the whole ship. At some point, it’s got to decide which of the remaining sectors to try to surround next. So I defaulted to what I always default to: random.

It goes through all sectors that haven’t been surrounded yet, picks one at random, and surrounds it. Since we make doorways between sectors at the time we join them on, this gives the early sectors it picks lots of branches. But then as the ship fills up, it has less and less room to place new sectors around the one it’s picked, and so those later sectors have fewer branches. But where those are on the ship is pretty random.

Once every sector has had its turn being surrounded, we’re done.

Nice!

Cool!

Well! You can see pretty clearly here that the sector the player’s ship is docked with, in the bottom right, was surrounded by other sectors – and joined to all of them – before anything else.

And now I’m starting to see the problem.

The Problem

On anything but a tiny ship, branching a lot early on ends up leading to multiple long paths.

This clashes a bit with our policy of “place multiple keys protected by varied hazards before placing a locked door”. What kind of keys and doors do we place along these multiple parallel paths? Either:

1. We have multiple parallel tracks of level 1 key > level 1 door > level 2 key > etc.
2. Or we have only one track like that, and all the others start with higher sec doors – level 6 or so – ones you don’t get the key for until you reach the end of the first path.

Neither option appeals much. The first feels redundant, messy, and an inefficient use of space – we’d need very big ships to ensure one path is long enough to be interesting, and big ships are daunting and expensive performance-wise. The second involves a lot of backtracking, and makes the critical path – Where You Have To Go – almost impossible to read without meticulous examination. I tried to design a set of keys and doors for a big Branching ship by hand, and it was laborious even to draw:

The more ways the Branching Algorithm clashed with my plans for keys and locks, the more I thought “Boy, that Snaking Algorithm really wasn’t far off.”

Tweaking The Snake

So the Snake’s problems were a) an almost dickish determination to take you on the longest possible route to your objective, and b) not enough branching to place multiple keys before a locked door. But maybe these are fixable. Like everything at this early stage, I wrote every step of this code in whatever way was easy, simple and short, so there are loads of biases and cheats in it.

I looked for the easiest one to mess with, and it’s this: when surrounding a sector, it always tries placing them above and below, then switches to looking down both sides. To be more ‘true random’, it should find all the adjacent modules and then pick a random one to start a sector from. But even that seemed too much like hard work to me, so first I wanted to test if this ordering stuff even made much of a difference. There is one super easy way to do that: switch those two bits of code round. Try placing sectors along the sides, then try above and below. I give you The Sidewinder:

It’s snakey, but it’s trying to snake lengthwise.

And right away this answers lots of questions. Firstly: yep, this makes a huge difference. This ship is nuts. And secondly: look! Branching! Enough? Too much? Dunno! But it’s worth taking the next step.

I’m still too lazy to do true random selection of adjacent modules, so I came up with another super easy trick: instead of always doing vertical first, or always doing horizontal first, it flips a coin. And because this one piece of code is run again for every module, the coin flip will mean some snake horizontally and others vertically. I give you: The Drunk Snake Algorithm.

That’s lovely, but small ships almost always are with sector systems, I’m finding.

This huge one is a bit ugly, but just because it picked a lot of 3×1 rooms all next to each other – I may bias it against that. But pathwise, it’s surprisingly good – the critical path is not dickishly circuitous, and there’s a good amount of branching along the way. There’s a huge amount of path after the objective, but I don’t know yet if that’s bad.

My next step involved giving every sector a ‘distance’ value: how many sectors do you have to go through to get to this one? So the airlock sector is 0, any attached to it are 1, and so on. They usually go up to about 8, on a medium ship. Then I boarded one and saw the number 23. I thought it was a bug at first, but then I traced the route, and no, the Drunk Snake is just a dick sometimes:

I actually love that layout. And it gave me an idea: these distance values could also be used to spot good places for a shortcut. So if this sector is at distance 14, but it’s right next to one that has distance 3, maybe we just make a door. Maybe it’s locked. Maybe it has a hazard on it. Dunno! That’s what I’m gonna play with next.

More Procedural Generation