I found these two videos by Marchel Vos: (1) (2) that show how you can make hedge mazes that are very hard for the simple roller coaster tycoon 2 park guest AI to solve. Long story short, he eventually makes mazes that cover the entire map and leaves the guest to wander for what we’ll just call eternity.

Because the mechanics are actually very simple, I decided to try to learn threading by making a multithreaded program that simulate various “mazes” and how much time they take on average (and maybe make a nice scatter plot).

## The maze AI and simulation of it

The maze AI that is simulated here is the OpenRCT2 one, which works like this.

```
If there is a dead end:
Turn around
Otherwise:
Make a list of all directions (Except the one that you entered from)
Randomly pick one from the list and take that one
```

What Marchel simply did was make a maze entirely of blocks like this

```
^ out
## #
# #
## #
^ in
```

The AI enters the junction and will have a 50-50 chance of turning into the indent or continuing forward. After turning around in the indent, there is then a further 50-50 chance of continuing forward and turning around. So for each indent there is

- A 50% (2/4ths) chance of going forward
- A 25% (1/4th) chance of wasting time and going forward
- A 25% (1/4th) chance of wasting time and turning around

This is what `simulate`

does repeatedly until it reaches its goal indent. “wasting time” is simply counted as a extra step taken to solve the maze.

## Some intresting results

*This section is not needed to understand the code, i just thought it would be fun to share stuff that would just go to waste otherwise.*

The simulation is very coarse and has alot of room for improvement. The error when compared to the actual solve times in the video starts to grow linearly (and pretty quickly at that) after 40 indents. Despite this, the results are pretty intresting anyway.

The complexity of the AI was predicted to exponential in the video, with complexity $mathcal{O}(1.052^n)$ for n indents. The simulation instead has the much better $mathcal{O}(n^2)$, or $mathcal{O}(n^3)$ if we (foolishly?) assume that the error factor stays linear. The simulation-predicted time for the full maze (which now is a pretty useless lower bound) is 2½ years.

The distribution of times to solve a maze with a certain indent count seems to follow a binomial distribution, which makes sense. I cannot even pretend to understand statistics well enough to approximate parameters, but there it is.

## Questions

Hopefully there aren’t to general.

- Is the threading done safetly here? Is there any big no-nos here?
- Is the RNG handled properly? I know that java uses a “uniquifier” for each instance of its RNG, but it didn’t seem to be needed here.
- Is the code style general good?

## The code

The main thread syncronizes the simulation threads that each simulate a park guest navigating the maze, counting the number of needed steps. These threads increment a counter that keeps track of the number of trials performed, with the treads waiting on others to finish if enough trials are done. When all threads are waiting the the main tread makes the “maze” bigger and gets the other threads running again. The total step count is used to compute a average for that maze size which is written to a file as CSV.

```
#include <iostream>
#include <random>
#include <chrono>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <iostream>
#include <fstream>
long long simulate(int goal, std::default_random_engine &rng) {
int pos = 0;
long long stepCount = 0;
// Direction to move. abs(facing) == 1
int facing = +1;
auto zeroto3 = std::uniform_int_distribution<>(0, 3);
while (pos < goal) {
stepCount++;
// Boundary condition: Always turn around if pos 0
if (pos == 0) {
facing = +1;
pos = 1;
continue;
}
// There is a 50% chance of entering a indent and 50% chance
// to go forward. When exiting a indent there is a 50% chance of
// going forward and 50% chance of going backward.
// Thus
// 2/4 -> forward
// 1/4 -> wait, then forward
// 1/4 -> wait, then backward
int val = zeroto3(rng);
if (val <= 1) {
//forward
pos += facing;
}
else if (val == 2) {
// wait, then forward
stepCount++;
pos += facing;
}
else {
// wait, then turn around
stepCount++;
facing = -facing;
pos += facing;
}
}
return stepCount;
}
const int INITIAL_GOAL = 3;
const int FINAL_GOAL = 10000;
const int THREAD_COUNT = 8;
const int SAMPLE_COUNT = 10000;
std::mutex testNo_check_mutex;
std::mutex output_mutex;
std::mutex next_sim_mutex;
std::mutex all_waiting_mutex;
std::condition_variable next_sim;
std::condition_variable all_waiting;
void simulate_task(std::atomic<int>* testNo, std::atomic<int>* goal, std::atomic<int>* threadsWaiting, std::atomic<long long>* sum) {
int seed = std::chrono::system_clock::now().time_since_epoch().count();
std::default_random_engine rng(seed);
while (true) {
testNo_check_mutex.lock();
if (testNo->load() >= SAMPLE_COUNT) {
testNo_check_mutex.unlock();
std::unique_lock<std::mutex> cond_lock(next_sim_mutex);
threadsWaiting->fetch_add(1);
all_waiting.notify_all();
next_sim.wait(cond_lock);
if (goal->load() > FINAL_GOAL) {
return;
}
} else {
testNo->fetch_add(1);
testNo_check_mutex.unlock();
}
long long result = simulate(goal->load(),rng);
//output_mutex.lock();
// Keep these mutexes in case more statistics are needed
sum->fetch_add(result);
//output_mutex.unlock();
}
}
int main()
{
std::atomic<int> testNo = 0;
std::atomic<int> goal = INITIAL_GOAL;
std::atomic<int> threadsWaiting = 0;
std::atomic<long long> sum = 0;
std::ofstream resultFile;
resultFile.open("--- Removed for privacy ---");
if (!resultFile.is_open()) {
std::cout << "Failed to open file." << std::endl;
return -1;
}
std::thread Threadpool(THREAD_COUNT);
for (int i = 0; i < THREAD_COUNT; i++) {
Threadpool(i) = std::thread(simulate_task, &testNo, &goal, &threadsWaiting, &sum);
}
while (goal.load() <= FINAL_GOAL) {
std::unique_lock<std::mutex> cond_lock(next_sim_mutex);
// ThreadsWaiting is not global, so it can't be
// in the wait condition lambda.
while (threadsWaiting.load() < THREAD_COUNT) {
all_waiting.wait(cond_lock);
}
resultFile << goal.load() << ";" << sum.load() / SAMPLE_COUNT << "n";
double percentage = ((double)goal.load()*100)/FINAL_GOAL;
std::cout << "rProgress: " << goal.load() << " of " << FINAL_GOAL << " (" << percentage << "%) ";
// Update relevant variables, calculate stats
testNo.store(0);
goal.fetch_add(1);
sum.store(0);
threadsWaiting = 0;
next_sim.notify_all();
}
std::cout << "done!" << std::endl;
for (int i = 0; i < THREAD_COUNT; i++) {
Threadpool(i).join();
}
resultFile.close();
std::cout << "And this was hopefully not a massive waste of time!n";
return 0;
}
```