Generating Locks And Keys In Heat Signature’s Ships

My summary of where we are after the last ship-generation post would be:

• The Drunk Snake is probably the best algorithm so far, for generating the amount of branching and length of critical path we want while looking fairly pleasing.
• But! There’s a lot of room for improvement.
• But! Improvement is getting harder: we don’t have a huge amount of control with these types of algorithms, so we can’t fine-tune things precisely without a big rewrite.
• And! We don’t know enough about our requirements to get really fussy yet – maybe some things that seem bad now will be good when we have certain security devices or guard patrols in.

In other words, it’s not worth getting tunnel vision and tinkering with layout algorithms until we start fleshing out the systems and elements they’re meant to support.

The most basic one of these is locked doors and keys. The keys and even the doors are partly placeholders: some will literally be keycards and locked doors, but instead of some keycards we might put a terminal that can override things of that security level, and instead of some doors we might put a security camera that needs to be turned off.

I’ve had some version of that system in there since the first post, but it was literally dumping they keys in front of the doors. I wanted them placed in dead ends off the beaten track, so I can put security measures on them.

This turns out to be harder than it sounds. I want an early sector to branch off in three directions – two are dead ends with keycards behind various obstacles, and the third is the locked door either could open. I don’t want exactly that every time, obviously, but that kind of thing.

But because we generate as we go, at the time we place the next sector along, we don’t know whether there’ll be other branches coming from the last one, or if this is the only path. It could be like this sector, whose phallic shape allows for two keycards to be placed in easy reach:

Or this one, which did not branch at all before the door that leads to the rest of the ship.

The Drunk Snake places all the sectors that form the longest path first, and only afterwards does it look for room to make branching paths. The Branching Algorithm is not much better: it’ll let the first sector branch first, but after that it’s effectively random.

Long story short, it gets very tricky if you want to place keys and locks at the same time you place the sectors. It was pretty clear that ‘Security’ needed to be added in a second pass, after the basic geometry of the ship has been generated.

In case I haven’t made it clear yet, keys and doors work on Security Levels: a Security 3 Key can open Security 3 doors as well as Security 2 and 1. And they’re reusable. If you had one Security 9 key, you could open every door on the ship with it.

I’ll spare you my false start at this and skip to the algorithm that worked. What we’re doing kind of involves pathfinding – to ensure there’s a route to Key 2 that doesn’t go through any Lock 2 doors. But it would be complicated to integrate it with Game Maker’s pathfinding systems or to write my own, so I basically do it by making lots of lists.

We place the first sector as normal. But when we join a second sector onto it, we tell that sector to remember that ‘Sector 1’ is one of the ones you have to go through to get here. When we join something onto Sector 2, it copies Sector 2’s list of sectors-you-have-to-go-through, and adds Sector 2 to it. So every sector has a list of every other sector you need to go through to get to it.

Once the whole ship is generated, we go through the sectors and make a list of all the ones that are dead ends.

Then, until we run out of dead ends, we:

• Find the nearest two dead ends – the ones with the fewest ‘sectors you have to go through’.
• Remove them from the list.
• Put a keycard of security level S in each.
• Tell every sector that leads to either of those dead ends: your security level is fixed now.
• For all sectors whose security level is not fixed yet, upgrade them to security level S.
• Increase S.
• Do it all again.

Lastly, we go through every door in the ship and tell it: your security level is equal to the highest of the two sectors you’re between. So if you join a Sec 1 to a Sec 2, you are a Sec 2 door.

This works! Look!

Next I should either try adding hazards – like security cameras or specially placed guards – or I should put all the functional modules back in and check it still works: thrusters, cockpit, etc.

More Procedural Generation