The Gothic 1 Remake came out recently, and I love it. The first two games in that series have been massive favourites of mine since I was like 10 years old. The original Gothic is the first proper RPG I remember playing, and nothing has really come close to that and Gothic 2 since.
One of the things getting a lot of press currently is the lockpicking mechanic in the Remake. In the original game, it was a minigame based purely on trial and error and memorisation of combinations (or looking them up in walkthroughs). For most people it involved a lot of saving and reloading.
In the new one, it’s a game of skill. People are reacting to it in many ways but largely it seems it’s a big source of frustration. Personally, I mostly like it, I think it’s probably my favourite lockpicking minigame in an RPG so far… but it is a bit too hard I think.
Here’s an example video of the lockpicking:
I’ve heard several people mention writing BFS solvers for it. It’s not something I have a ton of experience in but it sounded like a fun use of time, so I spent a bit of time trying to come up with a program to help me solve these. (Many thanks to Gemini for accelerating much of the visualizations!)
The generic description for the challenge is this:
There’s a series of N number of locks, L1, L2, L3, … LN.
Each Lock’s state can be represented as a number from 1 to 7.
To unlock the chest / door, all of the locks need to equal the number 4.
There’s a set number of ways you can change the values of the locks, and they are usually interconnected in some way, so that you can almost never change a single lock’s value independently of the other locks.
Let’s use a concrete example of a real lock from the game.
It starts off in this state: L1 = 1, L2 = 3, L3 = 5.
You can change the lock in the following ways:
The constraints are to make each lock’s value equal to 4.
If any of the lock’s values go below 1 or above 7, you lose the game.
Here is a toy to illustrate.
Here’s a version that stops you from losing, by disabling moves that would result in a lock’s value from going below 1 or above 7:
Preventing losses makes it possible to win the game simply by button smashing. But even if you successfully beat the game like this, the series of moves it takes to get you to that point is seriously long and is going to involve a lot of repeat states.
To help avoid that, we can add an option to prevent repeat states:
However, simply avoiding repeated states can easily bring you to a dead-end point in the game. A place from which it is impossible to get to [4, 4, 4] without going backwards.
How do we deal with that the best way? In the current version, we have to remember our moves and reset the game if we want to try a different path.
This is what the next version does. Every time you select an option, it creates a new copy of the game from the new position. This way, you can explore every possible path without losing your place.
(The below simulation uses a simple version of the game by default to avoid there being far too many branches, but you can change to the original challenge by clicking the “Classic” / “Simple” toggle)
In the above version, you can explore any paths as you like. It disallows you from repeating states you’ve already visited, so eventually, you will reach the goal. However, it’s not guaranteed this is the optimal path.
To find the fastest path we can explore the options layer-by-layer. We can start at the initial state, and make all the possible moves we can make at that point. Then, we move onto the next layer and make all the possible moves from there. Eventually, we’ll hit [4, 4, 4], and we know that it’s the fastest path.
That method of finding the shortest path in a graph is called BFS (Breadth-First Search), and it’s the same thing that an automatic solver would do to solve the puzzle.