算法-寻路算法：被围住的区域

Question

寻路使用的是A*算法，基于方格八方向寻路。但是在寻到死路的时候，比如被障碍物围起来的区域，这个时候会花费很长时间。所以想预先判断下那些区域是被围起来的，一定没有路，然后找到最近的障碍物，让寻路者走到这个障碍物边上停下。
这个思路有没有问题？有没有更好的解决办法？如果这个思路可行的话，有什么好的算法，可以判断这个点是被障碍物围住的，并且可以找到围住的最近的障碍物？

Answer 1

一般八方寻路通常都使用了8叉数运算..这个网上可以搜索到很多..我写的A*是区域运算..把地图分成若干区域找出大区域之间可通行的位置后..区域是我生成地图的时候就生成好的..然后每帧2次运算..如果区域不通则把最后的区域保存下来..
第一帧算 A->B B->A..发现B点~目标点不可到达A则停止搜索..A->B继续运行..直到上面我保存的最后的区域附近为止就停下来...
这个语言表达貌似有问题-.-希望没有误导你...

Answer 2

完全可以抽象为象棋的马的行动轨迹，模型。利用递归进行计算。该方法一定可行，但不是最优方案。可以参考王辉的去掉孤岛区域进行优化。