How to find Paths and Mazes in Artificial Intelligence Algorithm

Find Paths and Mazes:

Fig:A directed graph representation is shown on the left and a twodimensional grid (or maze) representation is shown on the right. In both representations, the letter R is used to represent the current position (or reference point) and the arrowheads indicate legal moves generated by a search operator.

          The example program used in this section is MazeSearch.java in the directory src/search/maze and I assume that the reader has downloaded the entire example ZIP file for this book and placed the source files for the examples in a convenient place.

           Figure shows the UML class diagram for the maze search classes: depth first and breadth first search. The abstract base class AbstractSearchEngine contains common code and data that is required by both the classes DepthF irstSearch and BreadthF irstSearch. The class M aze is used to record the data for a twodimensional maze, including which grid locations contain walls or obstacles. The class M aze defines three static short integer values used to indicate obstacles, the starting location, and the ending location. The Java class M aze defines the search space. 

          This class allocates a two-dimensional array of short integers to represent the state of any grid location in the maze. Whenever we need to store a pair of integers, we will use an instance of the standard Java class java.awt.Dimension, which has two integer data components: width and height. Whenever we need to store an x-y grid location, we create a new Dimension object (if required), and store the x coordinate in Dimension.width and the y coordinate in Dimension.height. As in the right-hand side of Figure 2.1, the operator for moving through the search space from given x-y coordinates allows a transition to any adjacent grid location that is empty. The Maze class also contains the x-y location for the starting location (startLoc) and goal location (goalLoc). Note that for these examples, the class Maze sets the starting location to grid coordinates 0-0 (upper left corner of the maze in the figures to follow) and the goal node in (width - 1)-(height - 1) (lower right corner in the following figures).