This is a Depth-First Search (DFS) implementation to solve the chest and door locks in the video game Gothic 1 Remake implemented in C.
A few weeks ago I purchased the Gothic 1 Remake game on Steam. I started playing and must say that I rather enjoy the experience and the game mechanics. I have not played any of the Gothic games before as I was too young to play them when they came out but until now it does not get boring, repetetive, too easy, or other anoying resons for me to leave it for dead in my Steam library like many other games as I (unfortunately) have to admit.
Gothic’s world feels immersive and I think thats the biggest factor why I still play. I am not sure what exactly makes it so immersive but one factor is probably that every NPC has its own daily routine with its own bed somewhere and places they visit during the day. I played Skyrim before which is the most comparable game to Gothic that I played for a longer time (at least more comparable than Rainbow Six Siege, Overwatch, PUBG, …). Yes, I am aware that Skyrim is now closing in on being 15 years old but since Todd Howard thinks that teasing Elder Scrolls 6 ONCE 8 year ago (feeling old yet?) is enough Skyrim is the most recent game that is comparable for me. I digress… In Skyrim the most OP build is the Stealth Archer which can basically do everything which is illegal in Skyrim without anyone noticing or caring (especially with having done the Thieves Guild and Brotherhood questlines). In Gothic that is very different. NPCs are quickly hostile towards you if they don’t like what you are doing (for example stealing from their chests, which they apperently don’t like…?).
The point I originally wanted to make is there are chests in the game (Yes, it could have been that simple). Chests can be already unlocked in which case you can just open them but they can also be locked in which case you need a lockpick and try to solve the lock puzzle. As I have played Skyrim before I was pretty happy with the amount of lockpicks you get in the game but I quickly realized that this is also needed as Gothic’s lockpicks break rather quickly.
I have a Bachelor’s degree in Cyber Security which I don’t mention to brag but because I thought to myself that it has to be possible to write a program which can solve the lock for you perfectly without breaking a single lockpick. I am aware that there are solutions like this but come on, where is the fun in that?
Let’s dive in!
The locks in the game have a set of disks which can be shifted to the left or the right on top of the inserted lockpick. Each disk has 7 holes in it and the goal is to align all of them so that the middle hole is over the lockpick.
As an example we will use a simple lock with three disks.
Solved lock:
v
disk 0: oooxooo
disk 1: oooxooo
disk 2: oooxooo
^Each of these disks may shift left or right. In the code a shift is always a right shift but can be inverted to become a left shift. The locks have some predefined initial state.
Example initial lock state:
v
disk 0: oooxooo
disk 1: oooxooo
disk 2: oooxooo
^This lock can be solved by:
Seems rather simple but here comes the catch: shifting a disk might implicitly shift other disks in either direction. Now it is not so simple anymore.
For example let’s define the following dependencies:
These defined dependencies result in the following dependency matrix
where a 1 denotes a shift in the same direction, a
0 denotes no dependency, and a -1 denotes an
inverse dependency:
| Disk 0 | Disk 1 | Disk 2 | |||
|---|---|---|---|---|---|
| Disk 0 | 1 | 0 | 0 | ||
| Disk 1 | 1 | 1 | 0 | ||
| Disk 2 | 0 | -1 | 1 |
As you might see the dependencies are not symmetric in the sense that
when disk a moves disk b, disk b
does not necessarily have to move disk a. In this example
shifting disk 2 will shift disk 1 inversely but shifting disk 1 does not
have any effect on disk 2.
Solving this by hand is already not so easy any more. Feel free to give it a try though. You can compare your solution to that of the program later.
The general idea to solve this is very simple:
In pseude code this would look something like this:
main()
while lock_unsolved
find_best_next_shift
shiftSounds simple but the tricky part of course is finding the best next shift. Take a little time and think about how you as a human would evaluate a given lock state as good or bad or better or worse as some other state.
I used a DFS approch which is also commonly used to solve puzzles like the Rubik’s Cube and let’s computers evaluate chess positions. The idea is to take the current state of the lock and explore all possible shifts. The number of possible shifts is equal to 2 times the number of disks in the lock as every disk can be shifted left or right. Now we evaluate every of our new states. I will talk later about how my evaluation of a good state looks like but for now let’s just leave it as abstract as that. After evaluating every state we take the one that was evaluated as the best and apply the shift that led to this state to the lock. We now do this iteratively until the lock is in the solved state.
Back to our pseudo code:
find_best_next_shift(lock_state)
for shift in possible_shifts
new_state = lock_state + shift
return evaluate(new_state)
main()
while (lock_unsolved)
find_best_next_shift
shiftSometimes you have to do a shift evaluated as bad to get a better solution at the end. To fix this we have to take a look into the future to see how the different states play out in the long run. So instead of looking at all possible shifts at the current state and evaluating the new state we dive deeper. From every new state we again make every possible shift to get a state which differs from the original one by two shift operations. With this state we do the same thing again and so on. We recursively look at every state that is reachable until a certain depth. I chose 8 as my depth limit as this is the highest number which will still run relatively quickly on my machine for larger lock configurations. What we essentially do is try every state that is reachable in 8 shifts, evaluate all resulting states and find the best one. Perform only the first shift that was done to reach that best state. Now do that whole thing iteratively until the lock is solved.
Applying this to our pseudo code:
find_best_next_shift(lock_state)
if depth == 8 OR is_solved(lock_state)
return evaluate(lock_state)
for shift in possible_shifts
new_state = lock_state + shift
return find_best_next_shift(new_state)
main()
while lock_unsolved
find_best_next_shift
shiftIf you are not familiar with those topics its a little hard to understand so here I tried to visualize it. This is a way simplified form with only one disk and a depth of two.
depth 0 depth 1 depth 2
+- shift disk 0 -----------> state
|
+- shift disk 0 -----------> state -+
| |
| +- shift disk 0 inversely -> state
|
original state -+
|
| +- shift disk 0 -----------> state
| |
+- shift disk 0 inversely -> state -+
|
+- shift disk 0 inversely -> state
This tree evaluates 4 states which is the number of disks times 2
(for the possible shifts per depth) to the power of the depth:
(2 * disks)^depth. So in our example lock with 3 disks and
a search depth of 8 we get a total of
(2 * 3)^8 = 6^8 = 1 679 616 states evaluated per iteration
until the lock is solved. Adding just 1 more disk would result in
(2 * 4)^8 = 8^8 = 16 777 216 states which is roughly ten
times more states.
But we can optimize a little. For example in our visual tree representation half of the resulting states can be ignored. Why? Because a shift followed by its inverse shift does nothing:
depth 0 depth 1 depth 2
+- shift disk 0 -----------> state
|
+- shift disk 0 -----------> state -+
| |
| +- shift disk 0 inversely -> state = original state
|
original state -+
|
| +- shift disk 0 -----------> state
| |
+- shift disk 0 inversely -> state -+
|
+- shift disk 0 inversely -> state = original state
So these two cases can be skipped in the evaluation. In fact for
every state I can ignore exactly one shift operation because it would
just reverse the last shift. This optimization will already reduce our
exapmle lock from 1 679 616 states to be evaluated to
(2 * 3 - 1)^8 = 5^8 = 390 625 states. The formular now is
(2 * disks - 1)^depth.
We can do one more optimization though. In our example lock disk 0
has no dependencies on other disks and can therefore be moved freely.
These free shifts of independent disks are skipped during the DFS
because they have virtually no effect. An unsolved independent disk can
be solved by just shifting it in the correct position. After every shift
a correction has to be done to fix all as a dependency shifted
independent disks. This will reduce the number of disks we have to look
at by one resulting in only
(2 * (3 - 1) - 1)^8 = 3^8 = 6 561 states. The formular now
is (2 * (disks - independent_disks) - 1)^depth.
With these two rather simple optimizations we could reduce the states
which have to be evaluated from 1 678 616 to only
6 561.
The psudo code with the optimizations:
find_best_next_shift(lock_state)
if depth == 8 OR is_solved(lock_state)
return evaluate(lock_state)
for disks in lock
if is_independent(disk)
continue
for direction in left/right
if shift(disk, direction) == -last_shift
continue
new_state = lock_state + shift(disk, direction)
return find_best_next_shift(new_state)
main()
while lock_unsolved
find_best_next_shift(lock_state)
shiftWith our optimizations in place let’s look at the evaluation. Evaluating a state is difficult but the approch that I chose is one where I reward things I deem good and punish things I deem bad. This is applied to a score which is initially 0. The question what is good and what is bad in this context is hard to answer, but I came up with the following rules:
The first rule is pretty self explanatory. If we found the solved state then we punish for the searched depth. In the case where multiple ways to a solved state are found we want to take the one which used the least amount of shifts or in other words the fastets, most direct way.
The second rule rewards solved disks as the end goal is to have all disks solved.
The third rule rewards solved disks which have more dependencies. These disks have a high influence on the lock state and I want to solve them as quick as possible.
The fourth rule rewards a close distance of an unsolved disk to its solved state. A disk which is shifted all the way to the right or left takes more shifts to solve than a disk which is only 1 position off from being solved.
The fifth rule is applied always but only yields a benefit in the case of rule 1.
Taking our initial example lock state we can now evaluate how good it is:
v
disk 0: oooxooo
disk 1: oooxooo
disk 2: oooxooo
^The lock is unsolved so rule 1 does not apply. No disk is solved so rule 2 and 3 do not apply. Disk 0 gets a reward of 10 from rule 4 as the disk alone could be solved in three shifts. Disk 1 gets a reward of 30 and Disk 2 a reward of 20. We ignore the depth for now as we are currently not doing a search but evaluate a singular state. This will result in a score of 60.
As an example let’s choose to shift disk 2 inversely two times which is a valid state in a depth of 2. The state would be:
v
disk 0: oooxooo
disk 1: oooxooo
disk 2: oooxooo
^Note how disk 1 shifted in the opposite direction of the shifted disk 2. Lets evaluate this state: The lock is unsolved, so rule 1 does not apply. Disk 2 is solved and rule 2 applies rewarding with 1000. Additionally rule 3 applies and rewards with 100 because of the dependency to disk 1. Rule 4 rewards 10 for Disk 0 and 10 for Disk 1. The depth is 2 and we penalize that with -2. The resulting score is 1118. We compare this to the scores of all other states and pick the one with the highest result executing the first shift which led to that result on the lock.
Adding the evaluation to out pseudo code:
evaluate(lock_state, depth)
if is_solved(lock_state)
return SCORE_MAX - depth
for disk in lock
if is_solved(disk)
score += 1000
for dependency in disk
score += 100
else
score += 40 - shifts_needed_to_solve_disk
return score - depth
find_best_next_shift(lock_state, depth)
if depth == 8 OR is_solved(lock_state)
return evaluate(lock_state, depth)
for disks in lock
if is_independent(disk)
continue
for direction in left/right
if shift(disk, direction) == -last_shift
continue
new_state = lock_state + shift(disk, direction)
return find_best_next_shift(new_state, depth++)
main()
while lock_unsolved
find_best_next_shift(lock_state, 0)
shiftAt the end of this blog you can see how the program solved the example lock.
An alternative approch I came up with is to simplify or reduce the lock. The easiest step of this I already used by cutting out independent disks from the evaluation and search. But in theory I think it should be possible to solve for every disk, so that you have a sequence per disk which will eventually result in shifting that exact disk by one and all other disks are untouched. This is often used with Rubik’s Cube solving as you want to solve a smaller part of the cube by keeping the rest untouched.
If you are not familiar with the Complexity notation
O(n) called Big O
notation you can read about it in the linked article (although it is
quite an abstract topic so feel free to skip this section).
I define the following variables for our complexity analysis:
d: number of disks in the locki: the number of independent disks in the lock where
0 <= i <= dD: the depth to which to search toThe resulting complexity in Big O notation is:
O( 2 * (d - i) )^D ) = O( (d - i)^D ).
So all in all I am pretty happy with my solution. During development I sometimes thought of just using some fancy AI to write the code but eventually I did everything myself. As it is written as a CLI in C the interface is a little retro but I don’t mind it. This solver is not perfect. There are still some locks which it cannot solve which is probably a result of the depth being to low but increasing depth scales very badly with performance. I believe there are some cases in which the lock has to be in a very bad state before being able to be solved in the next DFS iteration but the lock will never enter this state because the evaluation rewards good states. One mitigation idea I have is taking the locks solved position and applying the worst move possible. When I do this once on startup after 8 iterations I have a state which is as bad as it gets after 8 shifts. During DFS I can now compare each state against these 8 states from the backwards search and if they match I handle it exactly like the solved case because after reaching this bad state the next iteration should find the solution.
Anyways for now this is good and since I have now delayed playing the actual game for a long enough periode of time I will go back to it.
This is the output of the solver for the example lock. Shifts are
denoted as disk, direction where disk is the disk number to
shift and direction is a for left and d for
right shift as these are the keyboard keys used to shift the disk in the
game. The dependencies are entered using y for symmetric,
n for none, i for inverse (asymmetric), and
N for no further dependencies which saves a few questions.
Before running the actual algorithm the program will solve all
independent disks. You can see this in the first two lock prints. The
first is the actual inital lock position and the second is the lock with
all independent disks (here only disk 0) already solved.
====== Welcome to the Gothic 1 Remake Lock Solver ======
How many disks does your lock have? (1-8) 3
What is the position of disk 0? (0-6) 6
Does disk 0 have a dependency on disk 1? (y/n/i/N) N
What is the position of disk 1? (0-6) 2
Does disk 1 have a dependency on disk 0? (y/n/i/N) y
Does disk 1 have a dependency on disk 2? (y/n/i/N) N
What is the position of disk 2? (0-6) 1
Does disk 2 have a dependency on disk 0? (y/n/i/N) n
Does disk 2 have a dependency on disk 1? (y/n/i/N) i
0: 1 0 0
1: 1 1 0
2: 0 -1 1
v
oooxooo
oooxooo
oooxooo
v
oooxooo
oooxooo
oooxooo
2, a
v
oooxooo
oooxooo
oooxooo
1, a
v
oooxooo
oooxooo
oooxooo
1, a
v
oooxooo
oooxooo
oooxooo
2, a
v
oooxooo
oooxooo
oooxooo
2, a
v
oooxooo
oooxooo
oooxooo
1, a
v
oooxooo
oooxooo
oooxooo
2, d
v
oooxooo
oooxooo
oooxooo
Solved!
2, a
1, a
1, a
2, a
2, a
1, a
2, dFinn Callies, 08.07.2026