触屏版推箱子游戏中的走迷宫算法

在Android等移动平台上的触屏版推箱子游戏中,游戏主角在触摸操作下的移动路径计算属于走迷宫算法.提出了一种基于右手法则、足迹标记和捷径优化的迷宫路径搜索算法,采用直行、沿墙搜索和路径优化三个步骤实现.经实际项目的应用验证,该算法具有良好的有效性和高效性,能够满足游戏操作的实时性要求.

用Θ(t)的广义连接图求有障碍时的最短路径

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为Q(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用不改向启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到Q(t).