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

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;
}
}
}
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;
}
}
}
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;
}
}
}
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)
{
next = point; --next.Row; if ((next != back) && (buffer.IndexOf(next) >= 0)) return -1;
if (next == end)
{
buffer.m_Buffer[index + 1] = next;
return +1;
}
next = point; ++next.Column; if ((next != back) && (buffer.IndexOf(next) >= 0)) return -1;
if (next == end)
{
buffer.m_Buffer[index + 1] = next;
return +1;
}
next = point; ++next.Row; if ((next != back) && (buffer.IndexOf(next) >= 0)) return -1;
if (next == end)
{
buffer.m_Buffer[index + 1] = next;
return +1;
}
next = point; --next.Column; 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;
}
}
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;
if ((next.Row <= 0) || (next.Column <= 0) ||
(next.Row > maxRow) || (next.Column > maxCol)) continue;
if (matrix.m_Buffer[next.Row, next.Column] == CellType.Fix) continue;
if (next == back) continue;
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?

`[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])

`[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

Point ptStart, ptEnd;
Point ptStartInside, ptEndInside; if (!FindInputAndOutputPoints
(this.m_Matrix, out ptStart, out ptStartInside, out ptEnd, out ptEndInside)) return;
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();
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;
--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) {
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!