Click here to Skip to main content
15,867,686 members
Articles / Desktop Programming / Windows Forms

A Simple C# Labyrinth and Maze

Rate me:
Please Sign up or sign in to vote.
4.38/5 (7 votes)
20 Jul 2010CPOL2 min read 65.4K   4.3K   23   12
An application and algorithms for best path in maze
Screen.png

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

C#
//-----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

C#
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!)

    C#
    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

C#
//-----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!

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer AMP
Iran (Islamic Republic of) Iran (Islamic Republic of)
H.Hajisharifi

Comments and Discussions

 
QuestionAlgorithm Pin
Muhammad Khan4-Nov-16 3:41
Muhammad Khan4-Nov-16 3:41 
AnswerRe: Algorithm Pin
_H2_12-Jan-17 4:14
_H2_12-Jan-17 4:14 
QuestionThanks Pin
Mansurjon Kurtov7-Oct-14 23:20
Mansurjon Kurtov7-Oct-14 23:20 
Generalsome ideas [modified] Pin
John Adams20-Jul-10 15:29
John Adams20-Jul-10 15:29 
AnswerWPF UI. Pin
_H2_20-Jul-10 20:37
_H2_20-Jul-10 20:37 
GeneralHello Pin
_H2_18-Jul-10 23:47
_H2_18-Jul-10 23:47 
GeneralCode dump Pin
The Man from U.N.C.L.E.18-Jul-10 23:03
The Man from U.N.C.L.E.18-Jul-10 23:03 
GeneralYou need to spellcheck your article title Pin
leppie18-Jul-10 19:57
leppie18-Jul-10 19:57 
Labyrinth is spelt wrong
xacc.ide
IronScheme - 1.0 RC 1 - out now!
((λ (x) `(,x ',x)) '(λ (x) `(,x ',x)))
The Scheme Programming Language – Fourth Edition

Generali don't understand Pin
Christ Kennedy18-Jul-10 17:31
mvaChrist Kennedy18-Jul-10 17:31 
GeneralI was looking forward to reading this... Pin
Dave Kreskowiak17-Jul-10 18:22
mveDave Kreskowiak17-Jul-10 18:22 
GeneralNeeds More explanation Pin
KenJohnson17-Jul-10 15:19
KenJohnson17-Jul-10 15:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.