Are two threads better than one?
We all know that multi-threading is a convenient way of making UIs appear faster to the user. They are also great for running background processes and such. But would it be faster to create multiple threads to solve the same problem on a single processor machine? For some problems...Yes!
Solving mazes is one of those problems, at least with the algorithm I've chosen here. This algorithm works by repeatedly looping through the maze, blocking off any dead ends encountered. Each iteration of the loop gets us closer until finally, there are no more dead ends, only the solution to the maze. This solution is like putting together a jigsaw puzzle. The more people you have working on it, the faster it will get done...sort of.
This application demonstrates this in a very visual way. From the File menu, you can select whether to solve the maze with 1-16 threads. Each thread is assigned a unique color so that when the solution is complete, you can see the contribution made by each thread separately.
The picture above shows the maze solved by a single thread of execution in 3.09 seconds. The picture below shows the same maze solved by 16 threads simultaneously. You can see that the improvement in performance is remarkable (2.26 seconds). Imagine how multiple threads might improve the performance of even larger problems.
Let's look at the code
Starting a new thread of execution is easy in C# In our form object, we run this code when the user chooses File->Solve Single Thread :
Thread aThread = new Thread(new ThreadStart(TheMaze.SolveA));
aThread.Start();
In the maze object, we have sixteen different SolveX methods so that we can assign 16 unique colors to the threads. SolveA is the first one. It calls SolveIt to loop through the maze repeatedly, blocking dead ends with WALLA ( a nice blue colored wall ). When complete, it raises the event MazeSolutionComplete.
public void SolveA()
{
SolveIt( Cell.CellState.WALLA );
MazeSolutionComplete( this, EventArgs.Empty );
}
SolveB is similar, but I thought it might be even faster if the second thread worked from the bottom up so I created SolveItBackward. In practice, I don't think this made a substantial improvement in performance, but there you go.
public void SolveB()
{
SolveItBackward( Cell.CellState.WALLB );
MazeSolutionComplete( this, EventArgs.Empty );
}
When the form object receives a MazeSolutionComplete message from each thread, we know we're done and we post the results in the status bar.
Credits
The maze creation code was written by Mike Gold so thanks to him for that. I simply modified it to use jagged arrays for speed and added the multi-threaded maze solution code.