BREADTH-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 "BFSAllVisitedNodes"
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. The first major adjustment needed is that we now
need to stablish bidirectional Edges between connected Nodes and consider for putting forward to use only those Nodes
that form a direct path from the Source Node to the Destination Node. 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 "BFSPathFinding"
.png)
.png)
.png)
.png)
.png)
.png)
.png)