DEPTH-FIRST SEARCH ALGORITHM
Considering an arrangement of a Computer Games platform, the design below can be taken as the detail of a level in
the game, which includes a number of narrow corridors separated by walls (green tiles) and is enclosed by a
continuous outer wall (dark-grey tiles):
From the “Actual Game Arrangement” we next create the so called “Network Diagram”, which is nothing more than a
collection of “Nodes” and “Edges” representing in a diagrammatic form the articulation of the platform area we
are interested in being able to search through the Algorithm:
At the next step, from the “Network Diagram” the “Tree Diagram” is constructed, which defines the arrangement of
Nodes that will be directly transferred into the code:
We have now reached the point where the only thing remaining is to implement the arrangement of Nodes and Edges into
code. To achieve this we need to define a 2D Array to accommodate the interrelations between the Nodes as dictated by
the distribution of the Edges in the Tree. The total number or Rows and the total number to Columns in the 2D Array
reflect the total number of Nodes in the Tree. The interrelations between the Nodes are marked as grey-filled and
blue-filled squares, with number one (1) to signify the presence of an Edge in the Tree and number zero (0) to signify
the absence of an Edge in the Tree:
As an example, suppose that we want to move along the Tree from the Root Node (Node 1) to Node 11. In a step-by-step
diagrammatic form the operation of the Algorithm is expected to be as shown below:
The actual output of the Algorithm, for the same parameters, is as shown below:
Download "DFSAllVisitedNodes"
From an observation of the actual output becomes apparent that the Algorithm needs some adjustments to be made in
order to be used effectively for Path-finding purposes in a Computer Game. After these adjustments to the Algorithm
its actual output is now as shown below. The output sequence of Nodes can now be directly used to guide sprites in a
Computer Game from the Source Node (Node 1) to the Target Node (Node 11):
Download "DFSPathFinding"
.png)
.png)
.png)
.png)
.png)
.png)
.png)