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:

Runner 2015-11-13 18-50-07-72 with security doors, snakey

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:

Snakey Route

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.

Branching Ship Sectors 3


Branching Ship Sectors 2


Branching Ship Sectors 1

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.

Branching Ship Sectors 4

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.

Branching Routes

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:

Heat Signature door sec level mockup colour coded

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:

Sidewinder layout

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

Sidewinder path

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.

Small Drunk Snake

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

Large Drunk Snake

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.

Large Drunk Snake Paths

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:

Dickish Drunk Snake

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.

10 Replies to “Laying Out Heat Signature’s Ships: Snakey Vs Branchy”

  1. No loops? I see the gameplay value of a branchy-snakey layout, but it undermines the game’s fiction a little to give every ship an inefficient layout, with only one winding path between the airlock and the objective. Would it break the game’s fun if exiting a ship were easier than entering? As a reward for finding keycards, perhaps they could open up shortcuts, not just let you reach places that were previously inaccessible. You get a more believable interconnected layout and maybe the player feels powerful for having ‘mastered’ the ship. Does this make sense?

  2. Yep, that’s what I mean by shortcuts: any extra connection I make here will create a loop, but I only want to do that if the ‘distance’ difference between the sectors it connects is significant (we want to avoid tiny loops, because they add nothing and look silly). So the shortcut door would be locked at the level of the deeper sector, making it a quick exit once you have the keycard, or a neat shortcut if you have a way to bypass/modify the door.

  3. As was already pointed out by Magnificentophat in the last article, all these ships are structurally very similar on their extreme left, as in all of them have these indents poking out at the extreme left(except one that has the indents at the bottom instead of left). Is this just a coincidence, or a bug in the code?

  4. It’s by design. You can’t really tell which way the ships are facing because these dummy ones have no vision cones or cockpit, but those notches are in the sides, towards the aft of the ship. That’s (a basic version of) this faction’s style: they’re the practical, no-nonsense engineering faction that built the space stations here. Other possible ship gen concepts here:

  5. Wouldn’t it make these questions easier if, in some cases, you added “exits” ? Think, initially closed airlocks, not too far from the objective (to limit boring backtracking), that you have to activate/open remotely (via some button or whatever) somewhere along your path ? Then you just control your pod remotely to come and grab you.

    It also opens the possibility of ships divided in two or more isolated parts, where you initially have access only to one airlock and must work in each part to open airlock access to additionnal parts. Not sure if I make sense !

  6. Yep, you make sense! I do plan for locked airlocks with a certain security level. They could help for a speedy exit once you’re at you’re objective. They’re not that useful for the kind of backtracking that the Branching algorithm produced – where you haven’t got to the objective yet, you’re somewhere in the middle of the ship, and you need to get back to an earlier trunk of the tree. Getting out of the ship and back in would probably be as slow as walking, since we can’t guarantee you’re near the edge of the ship any more than we can guarantee you’re near the point you need to get back to.

    Divided ships are a fun idea, but I think it’d make my code more complicated rather than less – and it certainly raises the “Why did they build it this way?” question more than just a snakey route does.

    Thanks for the ideas though!

  7. As a player I’d expect it to have a dickish determination to take you on the longest possible route.

    Maybe that’s just because in games with hand-built levels it’d be a waste of the designer’s time to build things the player had no motivation to look at.

  8. Now that you have rooms and corridors, there are several different thicknesses of bulkhead between sectors. Maybe there could be tools available that slowly cut a new doorway through the thinner walls, while creating very visible showers of sparks. The snakier layouts would offer safer corners to risk such a device.

  9. Related thought, you could add visual interest and readability to the larger ships by allowing the algorithm to change room colours occasionally, making some of the branching and disconnections visible at a glance.

Comments are closed.