那我就先说哈我自己的算法,这样大家就可以放心交流了吧
。我的邮箱好582797956@
目录
1最初设计
If-else版设计 (X)
扫雷版设计 (X)
2设计改进
队列与遍历版设计
3最短路径算法
广度优先搜索算法
4实现方案
一
最初设计(if-else)
(1)思考顺序
1先判断离前后门三条轴线的距离,因无法斜向行走,故只要到达三条轴线即可。[1]
2可以几乎排除向左走的可能,见最短路径判断法。
3前后和拥挤的权重比为0.7比0.3,故在判断时优先考虑距离。
4图中前后门宽度不一样,故前门的权重大于后面。
5把教室划分为前后,但因第4条所述,前后划分不等。
[1]关于三条轴线
(2)基本AI设定
1.方案设计图(if-else判断)
总共执行3次循环,与1次函数的迭代算法,编程较为困难,这只是单纯的走迷宫法(顺着右边走的方法),并无法算出最短路径,也无从得到最优算法,此方案否决。
最初设计(扫雷版)
(1)
将教室离散成相等的小方格,并采用扫雷的计数方法,判断周围障碍与人的数量,数字和越大,就说明密度越高,因该回避该区域
(2)
初始可采用数组的方式,对数进行记载,可以方便的编程,且快速计算出密度。
一个目标可使总数加4,当全图的数字和相等于初始障碍物的和时,算法结束。
但因无法判断人与障碍物,就算使用特定标识,几乎无法建立最短路径算法,至少我办不到,且每当一个运动时会改变5个数字,并且还要知道路径周围的障碍,故否决。
队列与遍历设计
设计思路
(1)
将教室离散成相等的小方格,设置一位数组,并建立Point方法,确认坐标。
(2)
共有三种物品状态,人,桌,地面,设计Block类(基本单元格)
Static class Block
{
public
const
byte Land = 0;
// 地面
public
const
byte Desk= 2;
// 桌
public
const
byte Man= 6;
// 人
}
(3)
建立方法,获取数据状态,完成准备工作
const
string
mask = "-+#%xX()";
public
static
char GetChar( ushort block)
{
return mask[block & 0x07];
}
public
static
byte GetByte( char block)
{
return ( byte)mask.IndexOf(block);
}
public
static
void CleanAllMark(ushort[,] bb)
{
for
( int
i = 0; i < bb.GetLength(0); i++)
for
( int
j = 0; j < bb.GetLength(1); j++)
bb[i, j] &= 0x07;
}
public
static
void Mark(ref ushort block,
int
value)
{
block |= ( ushort)(value << 3);
}
public
static
int
Value( ushort block)
{
return block >> 3;
}
最短路径算法
广度优先搜索算法
(1)
共两种方式,一是从人找出口,二则从出口找人,遍历全组,且搜索所有的节点(不重复),在每个分支处做下标记排入队列,在之后又从这出发,再次搜索,一直到找到人或出口时停止算法。如果未找到,返回错误的布尔值。
(2)
此方法不使用递归,而是循环,全部搜索,而不具有判断经验。
(3)
详细视图
但是这样时间复杂度为(N*N-1)/2+N-1,同时这也是最短路径的情况,但如果图再大一些,时间复杂度会急剧上升,所以因改进算法。
算法改进
(1)
将所标记的数,进行压缩,按倍数压缩,如(1,2,3,4,5,6,7,8,9)化为(1,2,3,1,2,3,1,2,3)只保留3个数来记录路径,因为来时的一个方向除开,剩下只有3个方向足够了。可减少内存占用量。
(2)
算法表达式 C#
static
bool Seek(byte[,] map, Point to, out
int
value)
{
Queue<Point> q =
new Queue<Point>();
Block.Mark( ref map[to.Y, to.X], 1);
Point nbr = Point.Empty; 60
for
(; ; )
{
value = Block.Value(map[to.Y, to.X]) % 3 + 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;
}
}
}
如果找到返回最短路径长度,没有返回长度为0,具体如下
1=>2=>3=>1=>2=>3
=>3=>1=>2=>3=>1=>2=>3
=>1=>2=>3
=>2=>3=>1=>2=>3
按红绿蓝的顺序,黑为障碍,呈中心扩散开,不断增大,直到查遍全部的路径
实现方案
(1)
如之前所述,计算出到门的最短路径长度,再利用之前的权重比,将较拥挤的长度乘以0.7,再与另一个门的最短路径相比,再作判断。
(2)
拥挤情况,如果按一个接一个的状况,对单体的时间会有影响,但总时间不会产生变化(全部单体最短路径情况下),无需再考虑占位的问题。
(3)
基于数组与VSM的绑定结合,可开发可视演算程序。
(4)
可以不考虑最糟糕的情况,撤离时一定会发生慌乱,有3~4秒的时间,会产生随机方向的变换,当然最糟糕的情况的时间花费为无限大。