4
\$\begingroup\$

I found these two videos by Marcel 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 Marcel 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;
}
\$\endgroup\$
1
  • \$\begingroup\$ (When putting a spelling checker to (beneficial) use: mine doesn't flag lower case is even where used as a pronoun.) \$\endgroup\$ – greybeard Dec 31 '20 at 21:37
2
\$\begingroup\$

Answers to your questions

Is the threading done safetly here? Is there any big no-nos here?

Avoid manually calling .lock() and .unlock(), and use the version of std::condition_variable::wait() that takes a predicate to wait for. Furthermore, you want to avoid needing locks. Instead of having threads update shared variables, consider having them store their results in per-thread variables, and only merge them when all threads are done.

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.

Your "uniquifier" is seed. However, instead of taking the time, you should use a proper random number as the seed. You can use std::random_device for that, like so:

std::random_device rd;
std::default_random_engine rng(rd());

Is the code style general good?

The style looks fine to me. The most important thing is that style is applied consistently, which you do.

Simplify your thread pool

You have four mutexes and two condition variables just to maintain your thread pool. This makes the code quite complex; you've spent roughly as many lines on the thread pool as one the actual simulation. You don't need any mutexes and condition variables, if you don't mind not having a progress counter, and only have the result written out at the end. Here is how it might look:

void simulate_task(std::atomic<int> &goal_counter, std::vector<long long> &results) {
    std::random_device rd;
    std::default_random_engine rng(rd());

    while (true) {
        const int goal = goal_counter++;
        if (goal >= SAMPLE_COUNT)
            break;

        long long sum = 0;
        for(int i = 0; i < SAMPLE_COUNT; ++i)
            sum += simulate(goal, rng);

        results[goal] = sum / SAMPLE_COUNT;
    }
}

int main()
{  
    std::atomic<int> goal_counter = INITIAL_GOAL;
    std::vector<long long> results(FINAL_GOAL);

    std::ofstream resultFile("--- Removed for privacy ---");
    if (!resultFile.is_open()) {
        std::cout << "Failed to open file.\n";
        return 1;
    }

    std::thread Threadpool[THREAD_COUNT];

    for (int i = 0; i < THREAD_COUNT; i++)
        Threadpool[i] = std::thread(simulate_task, std::ref(goal_counter), std::ref(results));
    
    for (int i = 0; i < THREAD_COUNT; i++)
        Threadpool[i].join();

    for (int i = INITIAL_GOAL; i < FINAL_GOAL; ++i)
            resultFile << i << ";" << results[i] << "\n";

    if (resultFile.close(); resultFile.fail()) {
        std::cerr << "Failed to write file.\n";
        return 1;
    }
}

Return EXIT_FAILURE on error

The proper exit code for a program that encountered an error is EXIT_FAILURE (defined in <cstdlib>, and on most systems it will have the value 1), not -1.

Write error messages to std::cerr

Write errors to std::cerr instead of std::cout, so they don't get mixed with regular output. This is especially important if you are redirecting standard output from the program to a file, for example.

Check whether all data was written succesfully

You checked only if the output file could be opened succesfully, but you didn't check whether all data was written at the end. To do this, you have to call .close() first to ensure all the output buffers are flushed, and then check with .fail() whether any error has happened since you opened the file.

\$\endgroup\$
3
  • \$\begingroup\$ Ah, dammit! I really should have thought of having a vector like that. (Might get alot of speedup out of it, too) Some exchanges get mad if you accept too early, but i assume that it's fine at code review, right? \$\endgroup\$ – Anamne Jan 1 at 10:54
  • \$\begingroup\$ You can always change the accepted answer later, so there's no problem accepting something early :) \$\endgroup\$ – G. Sliepen Jan 1 at 11:11
  • 1
    \$\begingroup\$ The exit code for a program that encountered an error is EXIT_FAILURE (defined in <cstdlib>). \$\endgroup\$ – Toby Speight Jan 1 at 16:17
1
\$\begingroup\$

Each branch in simulate's if/else if/else block does pos += facing;. The DRY principle mandates lifting it out. After that the if branch becomes empty:

    int val = zeroto3(rng);
    if (val <= 1) {
    }
    else if (val == 2) {
        stepCount++;
    }
    else {
        stepCount++;
        facing = -facing;
    }
    pos += facing;

This is a strong indication that something is not right. The problem is with a zeroto3 function, which violates an SRP (and also has a very suspicious name, BTW). Consider two decision making calls instead:

    if (enter_indent()) {
        stepCount++;
        if (change_direction()) {
            facing = -facing;
        }
    }
    pos += facing;
\$\endgroup\$
1
  • \$\begingroup\$ The first thing i did with this project was to flatten that decision tree. I am not very smart. (Also, sorry for the brace style, visual studio keeps murdering my formatting for some reason) \$\endgroup\$ – Anamne Jan 3 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.