基于自动机理论的自动循迹搜索目标算法

Algorithm of automatic target tracking search based on automata theory

自动机是一种抽象的计算模型,它可以根据输入的字符串来实现状态与状态之间的跳转。基于这个特点,可以把自动机理论运用搜索目标问题当中。以贪吃蛇自动寻找食物为例,利用确定型有空自动机理论,把贪吃蛇搜索到网格进行标记并设置成相应的状态。以实现贪吃蛇绕开障碍物并且不触碰其蛇身,在游戏景中自动规划出一条最短路径到达目标食物的位置。

Automatic machine is an abstract computational model, which can help the input string to jump from one state to another. Because of this feature, automata theory can be applied to the search target problems. With the help of deterministic finite automata theory, this article takes the snake searching food in the game for exqmple, setting the grids the snake has searched as corresponding states to make sure that the snake dodges the obstacles and does not touch its body and automatically searches a shorest path to the target food in the game map.