用C#開發智能手機軟件：推箱子(四)（1）

在上篇文章“使用 C# 開發智能手機軟件：推箱子(三)”中，我對推箱子程序作了總體介紹。在這篇文章中，介紹 Common/FindPath.cs 源程序文件。

以下是引用片段：

using System;
using System.Drawing;
using System.Collections.Generic;
namespace Skyiv.Ben.PushBox.Common
{
///
/// 尋找最短路線
///
static class FindPath
{
static Size[] offsets = { new Size(0, 1), new Size(1, 0), new Size(0, -1), new Size(-1, 0) };
static Direction[] directions = { Direction.South, Direction.East, Direction.North, Direction.West };
///
/// 尋找最短路線
///
/// 地圖
/// 出發點
/// 目的地
/// 最短路線
public static Queue Seek(ushort[,] map, Point from, Point to)
{
Queue moveQueue = new Queue(); // 路線
int value; // 離目的地距離
if (Seek(map, to, out value)) // 找到了一條路線
{
Point here = from; // 出發點(即工人的位置)
Point nbr = new Point(); // 四周的鄰居
for (value--; value > 0; value--) // 逐步走向目的地
{
for (int i = 0; i < offsets.Length; i++)
{
nbr = Fcl.Add(here, offsets[i]); // 開始尋找四周的鄰居
if (Block.Value(map[nbr.Y, nbr.X]) == value) // 就往這個方向走
{
moveQueue.Enqueue(directions[i]); // 路線向目的地延伸一步
break;
}
}
here = nbr; // 繼續前進
}
}
Block.CleanAllMark(map); // 清除所有標志,恢復現場
return moveQueue; // 所尋找的路線,如果無法到達目的地則為該路線的長度為零
}
///
/// 尋找最短路線,使用廣度優先搜索
///
/// 地圖
/// 目的地
/// 輸出:路線的長度(加1)
/// 是否成功
static bool Seek(ushort[,] map, Point to, out int value)
{
Queue q = new Queue();
Block.Mark(ref map[to.Y, to.X], 1); // 從目的地開始往回尋找出發點,目的地標記為1
Point nbr = Point.Empty; // 四周的鄰居
for (; ; )
{
value = Block.Value(map[to.Y, to.X]) + 1; // 離開目的地的距離(加1),用作標記
for (int i = 0; i < offsets.Length; i++)
{
nbr = Fcl.Add(to, offsets[i]); // 開始尋找四周的鄰居
if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達出發點(即工人的位置)
if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可以走的路
{
Block.Mark(ref map[nbr.Y, nbr.X], value); // 標記,防止以後再走這條路
q.Enqueue(nbr); // 加入隊列,等待以後繼續尋找
}
}
if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達出發點
if (q.Count == 0) return false; // 無法到達出發點

to = q.Dequeue(); // 出隊,繼續尋找,這是廣度優先搜索,因為前面已經把四周能夠走的路全部加入隊列中了.

}
return true; // 找到一條路線
}
}
}