分享
 
 
 

用C#开发智能手机软件:推箱子(四)

王朝c#·作者佚名  2008-05-31
窄屏简体版  字體: |||超大  

在这篇文章中,介绍 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; // 找到一条路线

}

}

}

静态类 FindPath 是用来寻找工人移动到鼠标点击的目的地的最短路线的。她采用一种广度优先搜索算法,使用循环,没有使用递归,而且地图上已经搜索过的路线决不再走第二遍。该算法分两个阶段进行:首先是寻找并标记最短路线,由该类的第二个 Seek 方法实现,这个私有的方法返回一个布尔值表明是否成功。然后,如果在第一阶段中找到了一条路线,则根据第一阶段所做的标记生成最短路线并将该路线返回给调用者。我们来看几个实例:

在该算法中,是从要到达的目的地开始往回寻找出发点。首先,将目的地标记为1,然后查看周围的四个邻居(按南、东、北、西的顺序)是否是“空白”(即“地”和“槽”,使用 Block.IsBlank 方法来判断),如是,则表明这是可以走的路,将其作上标记(使用 Block.Mark 方法,标记的数值等于离开目的地的距离加一),然后加入队列。这有两个作用,首先,标记过的单元格将不再被认为是可以走的路,防止重复搜索。其次,在第二阶段中要根据标记的值来生成最短路线。如果发现周围的邻居中有一个是工人(用 Block.IsMan 方法来判断),说明到达出发点,则立即结束搜索,退出循环,返回成功。否则,就检查队列是否为空,如果为空,则说明无法到达出发点,返回失败。如果不为空,则出队,从这一点继续开始搜索。如此一直循环。

这个算法是广度优先的,如上面的两个图所示,该算法是按标记的值从小到大进行遍历的,而该标记的值表示的是离开目的地的距离加一。

第二个阶段,如果在第一阶段返回失败,则返回一条空的路线(长度为零)给调用者。否则,从出发点(即工人的位置)开始,查看周围的四个邻居(按南、东、北、西的顺序),如果其标记的值(使用 Block.Value 方法来获得)为到目的地的距离加一(至少可以找到一个,可能有多个,可以任取一个,程序中使用第一个),就往这个方向走。如此一直循环,直到到达目的地。然后返回这条路线给调用者。

从这里可以看出,为什么地图(即 ushort[,] map)要使用 ushort 而不使用 byte。因为在该算法需要在地图中作标记,而且标记的值还必须是到目的地的距离加一(如果只须判断目的地是否可达,而不要求给出到达目的地的具体路线,则在算法中标记的值可全部都为1,这样用 byte 就足够了)。地图中总共有八种类型的单元格,需要用三个二进位表示。而 byte 只有八个二进位,那么,只剩下五个二进位,25=32,也就是说,目的地在工人32步以外该算法就无能为力了。而 ushort 有十六个二进位,减去三个,还有十三个二进位,213=8192,这应该足够了。让我们看看下图吧:

这是一个 9x9 的地图,共有81个单元格,其中49个是空地,假设目的在地图的右上角(标记为1的地方),则工人需要48步才能到达目的地。根据计算,如果是 NxN (这里N是奇数)的地图,工人在最坏的情况下需要 (N2 - 1)/2 + N -1 步(走最短路线)才能到达目的地。这就是说,在 127x127 的地图上,工人最多只需要 8190 步就可以到达目的地,这刚好在我们算法的范围之内。如果地图再大,我们的算法就可能(只是可能,因为在大地图上一般情况下并不会出现超过 8192 步的最短路线)无能为力了。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有