假设针对某间教室，试设计一算法模拟同学下课后疏散离开教室的过程（如图1，四周为墙壁，灰色长条区域为课桌，黑色实心圆代表同学）。疏散过程中考虑2个因素影响：（1）每个同学首先选择最近的出口进行疏散；（2）当该出口聚集了大量同学形成拥塞，这时可能考虑离次近的出口进行疏散。这两方面的权重分别为0.7和0.3。

疏散规则：
（1）    将教室离散成为大小相等的网格，每个同学在单位时间内只能移动一个网格或者保持不动，并且移动方向只能时上、下、左、右（如图2）；
（2）    如果某个同学选择的移动目标网格被其他同学占用，那么该同学选择等待；
（3）    如果多个同学同时竞争同一网格，随机选择其中一个同学占用该网格，其余同学保持不动；
（4）    同学不能移动到桌子占用的网格，并且只能通过出口处进行疏散；
（5）    当所有同学疏散完成后，算法结束。
（图在附件里）
         
图1                                  图2
我自己想了个算法但想和大神讨论下，如果有想法的话欢迎发到我邮箱

那我就先说哈我自己的算法，这样大家就可以放心交流了吧。我的邮箱好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秒的时间，会产生随机方向的变换，当然最糟糕的情况的时间花费为无限大。

我想定义一个随机变量，由电脑随机分配。来判断人是向左还是向右。先判断是否四周都有阻碍，若有则不动，只有一个方向就走哪个方向，有两个方向就想刚才说的就随机分配个(0,1).0则向左，1向右可以吧？还有就是有3个，4个方向的时候我就判断人距离哪个门的距离近，再判断是怎么走。
你就当行得通吗？