kts.ConnectivityCheck

Name

kts.ConnectivityCheck – check dungeon connectivity

Synopsis

kts.ConnectivityCheck(num_keys, lockpick_item_type)

Description

This function is called at the final stage of dungeon generation. It scans the dungeon to check whether a situation has been created in which the dungeon cannot be fully explored, because some of the keys and/or lockpicks required have been placed behind locked iron doors, in such a way that it is impossible to reach them. (For example, this might happen if key number 1 was placed behind locked door number 2, and key number 2 and the lockpicks were both behind locked door number 1. If you are outside of both locked doors, and the doors cannot be bashed down, then there is no way to get in.) If this scenario was allowed to occur, then the quest might be impossible to complete.

To prevent this, kts.ConnectivityCheck searches through the dungeon to try to determine whether a scenario like the above has occurred. If it detects that it has, then it will resolve the situation by spawning one or more lockpick items (i.e. items of the given lockpick_item_type) at accessible locations within the dungeon. This will make sure that all knights can find at least one lockpick, and therefore all knights will be able to unlock and open any doors that they encounter.

Return Value

None.

Errors

In rare cases the kts.ConnectivityCheck function might not be able to place lockpicks in the required way. In these cases an error "dungeon generator failure" will be raised.

Notes

The connectivity check is only approximate – there are (or could be) situations where it does not place the required lockpicks correctly. However, this should be rare. Nevertheless, it is recommended to call kts.SetLockpickSpawn somewhere during dungeon setup (and this is indeed done by the standard Knights data files). Doing so means that the game will start spawning lockpicks at random locations within the dungeon after a few minutes of gameplay; this acts as a "fail-safe" and means that all knights should be able to find a set of lockpicks eventually, even if kts.ConnectivityCheck did not behave as expected and did not place lockpicks properly.

How the connectivity check works internally

Most readers will not need to worry about this too much, but for those wanting more details of how the connectivity check algorithm works, read on.

The connectivity check is implemented as a "flood fill" algorithm. The fill starts from a player's entry point location and expands out through all "passable" squares. A square is considered "passable" if all of the Tiles on that square meet the following conditions:

The tile has connectivity_check set to 1 (see kts.Tile documentation); or
The tile has connectivity_check set to 0, and any of the following are true:
- The tile has "walking" access of "clear".
- The tile is destructible. (Knights can always smash their way through destructible tiles if needed.)
- The door is locked, and requires a key to open, but that key was found in one of the squares previously visited by the flood fill. (If a knight finds a key, they then become able to open any doors locked using that key.)
- The door is locked, but it doesn't have a key at all (e.g. switch-operated doors). (It is assumed that the dungeon maps have been designed in such a way that knights can always reach any necessary switches!)

The flood fill ends (in success) as soon as either (a) all keys have been found, or (b) the lock picks have been found (in either of these cases, knights will now have the means to open any door in the dungeon, so there is no issue). If the flood fill runs out of squares to search before either of those conditions are met, then it ends in failure. (In the failure case, lockpicks are placed on a random square, chosen from among all squares encountered during the flood fill – this ensures that the knight will indeed be able to find the lockpicks during the game.)

Note that a separate flood fill is done from each player's starting point (in case some knights are cut off from the key(s) but others are not).

When does connectivity_check need to be set on a Tile?

As noted above, the flood fill algorithm is influenced by the value of connectivity_check that has been set on each Tile. Most Tiles have connectivity_check equal to zero, but it is possible to override this when creating the Tile. Examples of when it might be desirable to set connectivity_check to -1 instead of 0 are as follows:

In the default Knights data files, there are "pit" tiles which have access = clear, but walking into a pit will kill the knight. If connectivity_check was 0, then the above rules would mark a pit as being "passable" (on the grounds that access is clear) but this would not be accurate. Therefore, pits set connectivity_check = -1 to make sure that the dungeon generator treats open pits the same as walls, for the purposes of connectivity checks.
Another case where an override is needed is in the "closed gate" tiles. Under the final bullet point above, these would be treated as passable, on the assumption that there is a switch somewhere that opens them; however, this is not always the case – some gates are not openable at all. Therefore, gates also have connectivity_check = -1 in the data files.
A final example might be if there is a switch-controlled door somewhere in the dungeon, but the switch that opens that door is itself behind a locked iron door. In that case, the game would assume that the switch-controlled door is always openable without needing a key (according to the above rules), but this would not necessarily be the case here – a key might be needed to access the switch itself! The solution, in this case, would be to set connectivity_check = -1 for the "locked iron door" that guards the switch, in that scenario. Luckily, I don't believe this scenario actually occurs for any of the standard Knights rooms (the rooms are all designed to put the switches "out in the open" as opposed to behind locked iron doors), so this particular case hasn't arisen yet, but it is something to bear in mind if new rooms are being designed.

Note that, once again, it is not strictly speaking required to make these connectivity_check tweaks; after all, we are mostly talking about edge cases here, and on the rare occasions where one of these edge cases is triggered, the kts.SetLockpickSpawn fail-safe should kick in and rescue the situation. However, if you do think of a situation where setting connectivity_check = -1 on a Tile might be required, then it is a good idea to go ahead and set it up, because relying on the fail-safe is not exactly ideal (e.g. it does take a few minutes before the lockpicks start spawning); therefore, if we can create the dungeon correctly in the first place, then it is better to do so, whenever possible.

Examples

You can see this function being used in the standard Knights data files here.