Information Technology Reference
In-Depth Information
Fig. 5.27 Determination of the shortest path in a simple treelike maze
The propagation of waves through the maze from the starting point of the maze
to its end point is shown in Fig.
5.27
. Since this process takes about 3-5 s, it is easy
to record successive stages of the propagation of the wave by a video camera and to
store them in computer memory. Some of these consecutive images are shown in
Fig.
5.27
.
Digital processing of the images recorded in the memory was used for finding
the shortest path from the entry point into the maze to the destination point.
Various algorithms are known for determining the shortest path from the
entrance to the labyrinth to its exit. In this study a different procedure was used
which is apparently more effective for the technique based on wave propagation in
a maze.
In the process of wave propagation through branch points the maze is split into
two (or more) fragments (Fig.
5.28
). One of them is connected with an exit from the
maze while the other one is not. It is easy to identify a fragment that is connected
with the end point of the maze by initiating a backward wave from the exit of the
maze. As a result fragments connected with the exit change their color (from black
to the background color), while the color of the fragments not connected with the
exit remains unchanged.
If the maze is not very complicated, it is possible to replace this auxiliary
reaction-diffusion process by a standard image processing procedure, i.e., to use
the “fill” of black fragments by the background color (Paint Bucket operation of the
Photoshop software package), initiated at the maze exit point. Subtraction of the
