A Simple C# Labyrinth and Maze

• Download Source [C#] - 80.42 KB
• Download Binary [EXE] - 29.73 KB
• Mirror Direct Download 80 KB

Introduction

This is a sample application for training of algorithm, multi-thread, multi-language, GDI+, parsing, file-IO, ...

Background

An algorithm with multi-thread for best path found in the maze.

Using the Code

The "Kernel.Engine" class and the "FindInputAndOutputPoints/FindNextPoint/AsyncStart" methods are the main class/methods for the algorithm processing.

FindInputAndOutputPoints Method

//-----Top search ...
pt.Row = 0;
for (pt.Column = (byte)(matrix.m_Size.Column - 2); pt.Column > 0; --pt.Column)
{
    if (matrix.m_Buffer[pt.Row, pt.Column] == CellType.None)
    {
        switch (++iFindCount)
        {
            case 1:
                inside1 = value1 = pt;
                ++inside1.Row;
                break;
            case 2:
                inside2 = value2 = pt;
                ++inside2.Row;
                break;
            default:
                return false;
        }
    }
}

//-----Right search ...
pt.Column = (byte)(matrix.m_Size.Column - (byte)1);
for (pt.Row = (byte)(matrix.m_Size.Row - 2); pt.Row > 0; --pt.Row)
{
    if (matrix.m_Buffer[pt.Row, pt.Column] == CellType.None)
    {
        switch (++iFindCount)
        {
            case 1:
                inside1 = value1 = pt;
                --inside1.Column;
                break;
            case 2:
                inside2 = value2 = pt;
                --inside2.Column;
                break;
            default:
                return false;
        }
    }
}

//-----Bottom search ...
pt.Row = (byte)(matrix.m_Size.Row - (byte)1);
for (pt.Column = (byte)(matrix.m_Size.Column - 2); pt.Column > 0; --pt.Column)
{
    if (matrix.m_Buffer[pt.Row, pt.Column] == CellType.None)
    {
        switch (++iFindCount)
        {
            case 1:
                inside1 = value1 = pt;
                --inside1.Row;
                break;
            case 2:
                inside2 = value2 = pt;
                --inside2.Row;
                break;
            default:
                return false;
        }
    }
}

//-----Left search ...
pt.Column = 0;
for (pt.Row = (byte)(matrix.m_Size.Row - 2); pt.Row > 0; --pt.Row)
{
    if (matrix.m_Buffer[pt.Row, pt.Column] == CellType.None)
    {
        switch (++iFindCount)
        {
            case 1:
                inside1 = value1 = pt;
                ++inside1.Column;
                break;
            case 2:
                inside2 = value2 = pt;
                ++inside2.Column;
                break;
            default:
                return false;
        }
    }
}

The "FindInputAndOutputPoints" method finds the start and end points in the matrix.

If only two blank points (hole) exists on the border of the matrix, this method works successfully and returns a "true" value.

So, matrices that in their borders have less or more blank points (hole), are invalid and are not processed.

FindNextPoint Method

private static int FindNextPoint
	(Matrix matrix, PointSpeedBuffer buffer, Point end, int index, bool first)
{
    if ((index + 1) >= buffer.m_Capacity) return -1;
    PointSide side = PointSide.None;
    Point point = buffer.m_Buffer[index];
    Point back = buffer.m_Buffer[index - 1];
    Point next;
    //-----
    if (first)
    {
        //For speed.
        next = point; --next.Row; //Top
        if ((next != back) && (buffer.IndexOf(next) >= 0)) return -1;
        if (next == end)
        {
            buffer.m_Buffer[index + 1] = next;
            return +1;
        }
                
        next = point; ++next.Column; //Right
        if ((next != back) && (buffer.IndexOf(next) >= 0)) return -1;
        if (next == end)
        {
            buffer.m_Buffer[index + 1] = next;
            return +1;
        }

        next = point; ++next.Row; //Bottom
        if ((next != back) && (buffer.IndexOf(next) >= 0)) return -1;
        if (next == end)
        {
            buffer.m_Buffer[index + 1] = next;
            return +1;
        }

        next = point; --next.Column; //Left
        if ((next != back) && (buffer.IndexOf(next) >= 0)) return -1;
        if (next == end)
        {
            buffer.m_Buffer[index + 1] = next;
            return +1;
        }
    }
    else
    {
        next = buffer.m_Buffer[index + 1];

        if (point.Column == next.Column)
        {
            if ((point.Row - 1) == next.Row)
                side = PointSide.Top;
            else if ((point.Row + 1) == next.Row)
                side = PointSide.Bottom;
        }
        else if (point.Row == next.Row)
        {
            if ((point.Column - 1) == next.Column)
                side = PointSide.Left;
            else if ((point.Column + 1) == next.Column)
                side = PointSide.Right;
        }
    }
    //-----Goto next point ...
    byte maxRow = (byte)(matrix.m_Size.Row - 2);
    byte maxCol = (byte)(matrix.m_Size.Column - 2);
    while (true)
    {
        ++side;
        next = point.GetSidePoint(side);
        if (next == point) return -1; //side != Top|Right|Bottom|Left

        //-----Range test ...
        if ((next.Row <= 0) || (next.Column <= 0) || 
		(next.Row > maxRow) || (next.Column > maxCol)) continue;

        //-----Is fix ...
        if (matrix.m_Buffer[next.Row, next.Column] == CellType.Fix) continue;

        //-----Exist test ...
        if (next == back) continue;

        //----Next point finded ...
        buffer.m_Buffer[index + 1] = next;
        return +1;
    }
}

The "FindNextPoint" method chooses the next point for the path.

Each point in the matrix, has four sides ...
Top, Right, Bottom, Left (clock work[CW]).

The "side" variant specifies the direction start for scanning and processing the next point.

The "first" argument specifies that the current point (that its next point, should be chosen) ...
Is it a new point?
Or ...
Does it return back algorithm to this point?

1. [first==true]

   If this point is a new point...
   So, method will ensure that this point isn't adjacent to other points in the current path (because, it can't be a member of the shortest path!)

   side = Top = first direction. (clock work[CW])

2. [first==false]

   If this point isn't a new point...
   So, "side" variant, calculate and set with consideration in the last forward point (for the current point)

Finally, "while" loop with consideration to "side" and clock work (top, right, bottom, left) chooses the new next point.

If the "left" direction has been tested and is not effective...
So, testing was processed in four directions and does not have a favorable response, the algorithm should go back to a point.

AsyncStart

//-----Find start and end point ...
Point ptStart, ptEnd;
Point ptStartInside, ptEndInside; //For speed.
if (!FindInputAndOutputPoints
    (this.m_Matrix, out ptStart, out ptStartInside, out ptEnd, out ptEndInside)) return;

//-----Initialize ....
pathMin = new PointSpeedBuffer((this.m_Matrix.m_Size.Column - 2) * 
	(this.m_Matrix.m_Size.Row - 2));

if ((ptStart == ptEndInside) || (ptStartInside == ptEnd))
{
    pathMin.m_Buffer[pathMin.m_Count++] = ptStart;
    pathMin.m_Buffer[pathMin.m_Count++] = ptEnd;
    return;
}

var matrix = new Matrix(this.m_Matrix);
matrix.ClearWay();

//-----Remove close points. Only for speed and performance.
RemoveClosePoints_Pass1(matrix);
RemoveClosePoints_Pass2(matrix);

if (
    (matrix.m_Buffer[ptStartInside.Row, ptStartInside.Column] == CellType.Fix) ||
    (matrix.m_Buffer[ptEndInside.Row, ptEndInside.Column] == CellType.Fix)
    )
{
    pathMin = null;
    return;
}
//-----
var pathCur = new PointSpeedBuffer((this.m_Matrix.m_Size.Column - 2) * 
		(this.m_Matrix.m_Size.Row - 2));
                
pathMin.m_Count = int.MaxValue;
pathCur.m_Buffer[pathCur.m_Count++] = ptStart;
pathCur.m_Buffer[pathCur.m_Count++] = ptStartInside;
                
//-----Start ....
--pathCur.m_Count;
int iFront = 1;
while (true)
{
    if (this.m_Version != version) return;

    if (this.m_DebugMode)
    {
        this.OnResult(new ResultEventArgs(pathCur, false));
        System.Threading.Thread.Sleep(SLEEPINDEBUGMODE);
    }

    if (iFront > 0)
    {
        ++pathCur.m_Count;
    }
    else
    {
        pathCur.m_Count += iFront;
        if (pathCur.m_Count <= 1) break;
    }


    iFront = FindNextPoint
		(matrix, pathCur, ptEndInside, pathCur.m_Count - 1, iFront > 0);
    if (iFront > 0)
    {
        if (pathCur.m_Buffer[pathCur.m_Count] == ptEndInside) //Found a true path?
        {
            if (pathCur.m_Count < (pathCur.m_Capacity - 2))
            {
                ++pathCur.m_Count;
                pathCur.m_Buffer[pathCur.m_Count++] = ptEnd;

                if (pathCur.m_Count < pathMin.m_Count)
                {
                    pathMin.Fill(pathCur);
                    this.OnResult(new ResultEventArgs(pathMin, false));
                }

                if (pathCur.m_Count <= 5) break;
                iFront = -3;
            }
            else
            {
                iFront = -1;
            }
        }
        else
        {
            iFront = +1;
        }

    }
    else if (pathCur.m_Count <= 2)
    {
        break;
    }
}

The "AsyncStart" method does general processing for the algorithm.

This method will process all paths.

Every time it finds a smaller way, it is copied in the "pathMin" variant and, raises the "Result" event for the UI update.

Finally, when all cases were processed
and, the algorithm go back to successive
and, when algorithm comes to start-point, the processing is finished
and, all cases are processed
and, shortest path has been found in "pathMin" variant.

Using the Demo

To use the demo program example, note that the matrix should have only and only two blank points (hole) on its border.
(For more information, please review descriptions for the "FindInputAndOutputPoints" method.)

Points of Interest

• Save/Load the maze and path in *.txt or *.map file
• Debug and Trace Mode
• Multi-thread processing
• Multi-language

History

• 18 July, 2010: Initial post
• 20 July, 2010:
  • Added explanation
  • Added 'Debug and Trace Mode'
  • Added RemoveClosePoints_Pass1 for speed and performance
  • Added IMatrixSerializer
• 21 July, 2010:
  • Solved a bug in stopping in 'Debug and Trace Mode'

Thanks!