Click here to Skip to main content
Click here to Skip to main content

A Simple C# Labyrinth and Maze

, 20 Jul 2010
Rate this:
Please Sign up or sign in to vote.
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

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

License

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

Share

About the Author

_H2_
AMP
Iran (Islamic Republic Of) Iran (Islamic Republic Of)
H.Hajisharifi

Comments and Discussions

 
Generalsome ideas [modified] PinmemberJohn Adams20-Jul-10 15:29 
AnswerWPF UI. Pinmember_H2_20-Jul-10 20:37 
GeneralHello Pinmember_H2_18-Jul-10 23:47 
GeneralCode dump PinmemberThe Man from U.N.C.L.E.18-Jul-10 23:03 
GeneralYou need to spellcheck your article title Pinmemberleppie18-Jul-10 19:57 
Generali don't understand PinmemberChrist Kennedy18-Jul-10 17:31 
GeneralI was looking forward to reading this... PinmvpDave Kreskowiak17-Jul-10 18:22 
GeneralNeeds More explanation PinmemberKenJohnson17-Jul-10 15:19 

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

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140814.1 | Last Updated 20 Jul 2010
Article Copyright 2010 by _H2_
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid