Building mazes and synchronizing threads

A maze builder is a program that every newbie should try to code, right after learning about arrays, branches and loops. And if you want to visualize the maze, it is also a great project to practice how to draw and paint.

As I was learning VB.NET, this is one of the first projects I decided to attempt and it was a really fun experience.

The most basic and fundamental algorithm to build a maze is as follows:

Define a grid of n by m points
Choose a random point in the surface
Draw the point
Store the point position (in a stack)
Using a random function, select a direction (either left, right, forward or backwards)
Check if we can move in that direction (that is, check if there’s already a point drawn):
- If we can, move to that position and go to step #3
- If we cannot move in that direction go to step #5
- If we cannot move in any direction, go back in history:
  - If we are at the end of the history then terminate
  - Otherwise, go to step #5

Here’s the algorithm’s code in VB.NET:

If CanMove(p) Then
	Do
		direction = CType(rnd.Next(0, 4), DirectionConstants)
	Loop Until CanMove(p, direction)

	Select Case direction
		Case DirectionConstants.Top : p.Y -= moveStep
		Case DirectionConstants.Right : p.X += moveStep
		Case DirectionConstants.Bottom : p.Y += moveStep
		Case DirectionConstants.Left : p.X -= moveStep
	End Select
	history(i) = p.Clone()
Else
	For i = i - 1 To 0 Step -1
		If CanMove(history(i)) Then
			p = history(i).Clone()
			Exit For
		End If
	Next
End If

This algorithm is known as “Recursive Backtracker” and it’s the most basic maze building algorithm I know.

Fast forward several years…
I was presented with a project that, among other things, would require an unknown and constantly variable number of threads performing “simultaneous” modifications to a bitmap.

If you have ever received the “InvalidOperationException: Object is currently in use elsewhere” exception then you already know that implementing such functionality is not that easy, as you need to carefully synchronize all the threads so that only one can have exclusive access to the bitmap at a given time.

Each new version of .NET provides a new set of more robust and (even) easier to use solutions to this problem. So, to evaluate which one would be the easiest to implement (and, specially maintain) I decided to use my maze building program as a testing ground.

NOTE: I will not go into any detail regarding .NET’s threading synchronization options and methodologies, as this alone deserves a separate (and HUGE) post.

The initial version of the maze builder program did all the drawing on a single bitmap and in a single step. Then, when the maze was completed, it was presented (drawn) onto the main form.
So, the first thing I did was to allow the program to show the progress as the bitmap was being drawn.

This required the use of two bitmaps, one as the main drawing surface (also used to evaluate if a move to a given position was possible) and a second one, used to actually display the maze in the form’s surface through a simple DrawImage call.

This change alone required the implementation of a thread that would do the “drawing” (the main loop) onto the main surface and then have the main program’s thread handle the drawing.
Both threads were kept synchronized by a simple set of “SyncLock” instructions, which prevented one thread from performing changes to one of the bitmaps while some other thread was using it.

Something I haven’t mentioned is that the drawing and querying routines access the bitmap directly; otherwise, the code would be too slow.
Both the SetPixel and GetPixel methods of the Bitmap class are horrendously slow, so the program accesses the bitmap directly by locking it and then implementing custom SetPixel and GetPixel methods.

To really push things to the limit and make sure the synchronization was working correctly, I implemented a way to start multiple “maze building” threads that would work over the same bitmap surface.
This way, I could have multiple threads performing drawing and querying operations, as well as the main program thread drawing a secondary bitmap into the main form’s surface.
An ideal scenario to test the synchronization code.

The thing ended working wonderfully and the use of two bitmaps, along with the SyncLock implementation, made it to the program I was asked to develop.
Although the program worked perfectly, it never got released due to the poor performance of .NET’s GDI+, but the implementation did prove that the approach worked quite reliably.

In the end, it was a great learning experience.

Here are the links to download the Maze Builder application.
When running it, press the ‘H’ key to display some information and instructions on how to modify the algorithm parameters.

Maze Builder binary (requires .NET 4.0):
Maze Builder (1060 downloads )

Maze Builder source code (Visual Studio format):
Maze Builder Source Code (1018 downloads )

Please, let me know, through the comments section below, if you think this synchronization code could be improved to provide a more robust and/or better (performance-wise) implementation.

Oct201219

xfx

0