A Maze Routing Algorithm Based on Two Dimensional Cellular Automata

摘要

This paper propose a maze routing algorithm based on cellular automata. The aim of this algorithm is find the shortest path between the source cell and the target cell , so that the path does not pass from the obstacles. Algorithm has two phases, exploration and retrace. In exploration phase a wave is expanded from source cell and it puts token on cells which it passes via them while expanding. In the retracing phase , we start from target cell, follow the wave and arrive to source cell; the path created in this phase is desirable. Propose algorithm is simple and it's transactions are local and follow the cellular automata properties. This algorithm find the desirable path in m × m two dimensional CA in O(m~2) time step.