A dummy array (equivalent to that of maze) is used to hold the current status of the respective nodes in the maze. To apply the above algorithm, the class uses two integer array Queue and Origin. The class, however, doesn't use separate methods for these transformations, they are done directly. Void GetMatrixIndexes( int matrix, int iNodeNo, out ithIndex, out jthIndex) Return ( ithIndex*matrix.GetLength( 1)+ jthIndex ) Int GetNodeNo( int matrix, int ithIndex, int jthIndex) Methods below can be used to transform between node number and indexes of a matrix Node numbersįirst, we assign node numbers to every element of the array starting from 0 to ' RowsXCols-1' in the manner below. The only thing is mathematics the class uses certain mathematical formulae to access the adjacent nodes of an element (node) in the matrix (maze). there is no class/struct used for graphs, no adjacency lists, no weights assigned to edges, etc. Yes, the class uses breadth-first search technique without actual implementation of graphs. how we reach a particular element in the maze) by using an array Origin together with the array Queue. Add to the rear of Queue all the neighbors of N that are in the ready state (Status=Ready), and change their status to the waiting state (Status=Waiting)Ī minimum path between two nodes can be found using breadth-first search if we keep track of the origin of each edge (i.e.Process N and change the status of N to the processed state (Status=Processed) Remove the front node, say N, of Queue.Repeat steps a and b until Queue is empty:.Put the starting node, say A, in Queue and change its status to the waiting state (Status=Waiting).Initialize all nodes to the ready state (Status=Ready).The outline of the algorithm is as follows: This is accomplished by linking a field "status" with all the nodes. Naturally, we need to keep a track of all the nodes to assure that no node is processed more than once. Then we examine all the neighbors of A, then we examine all the neighbors of all the neighbors of A, and so on., until we reach the desired ending node or until we have no nodes to examine (in this case no path will exist). The general idea behind a breadth-first search algorithm is that we examine a starting node, say A. I assume that reader is familiar with graphs and its terminologies (edges, nodes, etc). Throughout this article, we will use "node" to refer elements of the matrix (2D integer array representing a maze). The class can also trace diagonal paths if it is allowed to do so. If a path is to be found, a new 2D integer array is created with the path traced by PathCharacter whose default value is '100'. The MazeSolver class stores the Maze as a 2D integer array with value '0' for open (available) nodes and non-zero for closed nodes (walls). It uses a technique similar to breadth-first search. Similar applications use graphs in such situations but this article shows how this can be done without the headache of graphs. The article presents a simple technique to find the shortest path between two points in a 2D Maze. Download source of Maze Solver class - 24 Kb.Download demo project in Visual C# (requires Visual Studio.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |