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 checks to see whether the dungeon is "unsolvable" due to some keys and/or lockpicks being inaccessible. (For example, if key number 1 is placed behind locked iron door number 2, and key number 2 is behind locked iron door number 1, and no lockpicks are readily accessible, then there is no way to open either of those doors.)

To prevent this, kts.ConnectivityCheck searches through the dungeon to determine whether a scenario like the above has occurred. If a problem is found, kts.ConnectivityCheck will resolve the situation by spawning one or more lockpicks (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 should 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, and relies on heuristics. It might not be able to detect all situations where keys and/or lockpicks are inaccessible. For this reason, there is a second line of defence: after a few minutes of gameplay, the game will start spawning lockpicks at random locations within the dungeon. 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 didn't place lockpicks where they were needed, for whatever reason.

(This lockpick auto-spawning is enabled by calling kts.SetLockpickSpawn at some point during dungeon setup. The "base" module already takes care of this, so unless it has been overridden by some mod, nothing special needs to be done to set this up.)

Another point to be aware of is that the connectivity check only looks for issues with the placement of keys and lockpicks. It cannot detect things like unsolvable switch puzzles – but these are more of a map design issue, and are not something that a run-time "connectivity check" could fix.

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 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.

The default value for connectivity_check is 0, and this does the right thing in the vast majority of cases. For example, ordinary floor tiles are considered passable by the heuristic (because they have "walking" access of "clear"), and wall tiles are considered impassable (because none of the bullet points apply: they don't have "walking" access of "clear", they are not destructible, and they don't have type="door").

At the moment, the only known case where the default heuristic fails is for "open pit" tiles. These have "walking" access of "clear", so they look (to the heuristic) like normal floor tiles, but they also have an "on_walk_over" Lua function (which the heuristic cannot see) which kills the player when they walk onto the pit. Therefore, the "base" module sets connectivity_check = -1 manually for these tiles, which forces the connectivity check to consider them impassable to knights, which is what we want.

Note: if you are making new tiles, and you don't set connectivity_check correctly, it is not the end of the world. The worst that can happen is that knights will not be able to reach the required keys or lockpicks from the beginning of the game, and will have to wait for the randomly generated lockpicks to spawn after a few minutes (see kts.SetLockpickSpawn). This is an inconvenience for players, but doesn't make the game unwinnable (provided they are patient enough to wait, and they find the randomly spawned lockpicks!). The main thing to remember, probably, is that if you create new open pit tiles (or other similar tiles that a knight can't pass through), then you should set connectivity_check = -1 on them.

Examples

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

See Also

kts.LayoutDungeon

kts.Tile