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:

Two keys and a door

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

No keys, no branches

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.

10 Replies to “Generating Locks And Keys In Heat Signature’s Ships”

  1. Love reading about your progress. :) Do you plan to have alternate means to go through a door/camera? For example breaching the door? Some sort of upgrade that would allow this kind of functionality would add a real sense of progress to the game. However, it will have to be carefully balanced, I guess.

  2. I’d already mused in this direction, but this is a much better place for it – how do the ships look if you change the room lighting or colours between different security zones?

  3. “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.”
    Tom, what you wrote is totally a pathfinding algorithm :) It was less complicated than you thought.

  4. I’m imagining how amazing it would be if you added a Crosslink to this game. Or some similar way to repurpose security systems…

  5. Based on your development blogs, I’d like to pull up a thoughtful point.

    As much as the coding is really interesting, the ships look utterly horrible right now (for me. this is my opinion. it could be you’ve just shown pictures of these big canvas sized ships)

    The problem i have is that, while in early screenshots, all the ships had this wonderful crazy symetry about them, now… they look just like rectangles, with a single dent maybe. Biggest example of why i think this comes from this post:

    It looks rather dull, and the lack of interestingly just becomes a bit of a turn off. Not least because now they seem to just be elongated slug-shaped ships

    again, it’s my own opinion, but I thought i’d mention it Tom.

    Good luck and hope development stays strong

  6. Hi Tom! I was just curious: What happens if you ram a ship into another ship? How do you know which blocks get blown up and which ones stay? Just a question!

  7. Ah, Hadn’t seen that image (not sure how)

    I just thought I’d mention it here, because i know better than some at how you can get focused on a feature and loose sight of how you originally intended it

  8. @wwarnick I like the ideas of sectors in that long ship design. Each section of the long ship being a puzzle to overcome, maybe even be the size of one of these ships to be REALLY long and take a while to beat.
    Have different time length ships, like “This is a 2 minute ship” and “This is a 7 minute ship”. It will probably be difficult to generate ships that take a long time to generate… But hey, I too, regret this already.

  9. Will you implement multiple branches for sectors? Eg. having sector 1-3 on one branch and acquiring the sector 4’s key, and returning back to the entrance to open sectors 4-6. What about a door to return to the entrance from the highest security area?

    You might have to make a trade off between imitating hand made level design and making it realistic-ish in functionality. No one likes raiding a ship with one large area with no security other than the entrance, but that’s what makes sense; but on the other hand no one likes a future with box-like ship/maze hybrids.

Comments are closed.