Multi-threaded Maze Solver
How can you solve a 10,000 by 10,000 cell maze quickly using multiple threads? This C++ multi-threading project required me to use concurrency in a creative and efficient way. My solution uses standard C++ synchronization tools and atomic variables to solve the maze approximately 2 times faster than a single threaded depth first search.
The data in the maze is stored as atomic integers, and my solution uses atomic variables to communicate between threads. Atomic data allows for indivisible, thread-safe operations.
This is good for a large data structure with simple data like the 10,000 by 10,000 maze. There is no need to protect the data with slower tools like a mutex.
This is a visualization of how my maze solver works. There are 2 threads: the forward solver and the reverse solver. Both threads use depth first search. The threads mark their path as they go, and check for an overlap with the opposite thread's path. Once they collide, the solution is retraced.
The threads are launched as futures that return a vector of "directions". The directions are just the correct steps to take at each cell along the path. The threads return their partial solution, up to the connection point, then they are combined.
Each thread has a unique bit-mask. They share the connection point data and a few flags for signaling.
forward
reverse
On each step of the depth first search, the threads mark the data and check for a connection with the other thread.
The threads must synchronize access to the shared connection point. They use the compare exchange operation on an atomic Boolean to provide exclusive access.
