65.9K
CodeProject 正在变化。 阅读更多。
Home

一个简单的 C# 迷宫和花园

_H2_
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.38/5 (7投票s)

2010 年 7 月 20 日

CPOL

2分钟阅读

viewsIcon

67948

downloadIcon

4376

迷宫的最佳路径应用程序和算法

Screen.png

引言

这是一个算法训练、多线程、多语言、GDI+、解析、文件 IO 等的示例应用程序。

背景

一个使用多线程在迷宫中寻找最佳路径的算法。

Using the Code

"Kernel.Engine" 类和 "FindInputAndOutputPoints/FindNextPoint/AsyncStart" 方法是算法处理的主要类/方法。

FindInputAndOutputPoints 方法

//-----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;
        }
    }
}

"FindInputAndOutputPoints" 方法在矩阵中寻找起点和终点。

如果矩阵边界上只有两个空白点（洞），则此方法成功工作并返回一个 "true" 值。

因此，在其边界上具有较少或较多空白点（洞）的矩阵是无效的并且不被处理。

FindNextPoint 方法

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;
    }
}

"FindNextPoint" 方法选择路径的下一个点。

矩阵中的每个点都有四个边...
上、右、下、左 (顺时针 [CW])。

"side" 变量指定扫描和处理下一个点的方向起始。

"first" 参数指定当前点（其下一个点应该被选择）...
它是一个新点吗？
或者...
算法是否返回到此点？

  1. [first==true]

    如果这个点是一个新点...
    那么，该方法将确保此点不与当前路径中的其他点相邻（因为它不可能是最短路径的成员！）

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

    如果这个点不是一个新点...
    那么，"side" 变量会考虑并设置最后一个前进点（对于当前点）。

最后，考虑到 "side" 和顺时针 (上、右、下、左) 的 "while" 循环选择新的下一个点。

如果 "left" 方向已经过测试并且无效...
那么，测试在四个方向上进行处理，并且没有得到有利的响应，该算法应该返回到之前的某个点。

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;
    }
}

"AsyncStart" 方法对算法进行一般处理。

此方法将处理所有路径。

每次它找到一条更短的路径时，它会被复制到 "pathMin" 变量中，并引发 "Result" 事件以进行 UI 更新。

最后，当所有情况都处理完毕
并且，算法返回到连续的
并且，当算法到达起点时，处理完成
并且，所有情况都已处理
并且，最短路径已在 "pathMin" 变量中找到。

使用演示

要使用演示程序示例，请注意矩阵在其边界上应该只有且只有两个空白点（洞）。
（有关更多信息，请查看 "FindInputAndOutputPoints" 方法的描述。）

关注点

  • 在 *.txt 或 *.map 文件中保存/加载迷宫和路径
  • 调试和跟踪模式
  • 多线程处理
  • 多语言

历史

  • 2010 年 7 月 18 日：初始发布
  • 2010 年 7 月 20 日
    • 添加了解释
    • 添加了“调试和跟踪模式”
    • 添加了 RemoveClosePoints_Pass1 以提高速度和性能
    • 添加了 IMatrixSerializer
  • 2010 年 7 月 21 日
    • 解决了在“调试和跟踪模式”中停止的错误

谢谢！

© . All rights reserved.