I'm currently new to game design and development. I'm working on a game that needs the use of pathfinding and have decided to use the Breadth First Search algorithm for it.
bool isPath(int map[row][col])
{
// Directions
int dir[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
std::queue<std::pair<int, int>> frontier;
// Insert the starting position.
frontier.push(std::make_pair(0, 0));
while (frontier.size() > 0)
{
std::pair<int, int> reached = frontier.front();
frontier.pop();
// Mark as visited
map[reached.first][reached.second] = 1;
// Destination is reached
if (reached == std::make_pair(4, 0))
{
// Add in traceback code..
return true;
}
// Check all four directions
for (int i = 0; i < 4; i++)
{
// Using the direction array
int a = reached.first + dir[i][0];
int b = reached.second + dir[i][1];
// Not blocked and valid
if (map[a][b] != 1 && a >= 0 && b >= 0 && a < row && b < col)
{
frontier.push(std::make_pair(a, b));
}
}
}
return false;
}
void main()
{
// Map
int map[row][col] = { { 0, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 1 },
{ 0, 0, 1, 0, 0 } };
// Path from map[0][0] to map[4][4]
if (isPath(map))
std::cout << "Found";
else
std::cout << "Not Found";
}
The current code I have is able to search from the starting position to the destination and return if the destination is found. The issue I'm facing right now is that I'm unsure and confused about how to trace back from the destination to the starting position. From what I know, I need to implement the trace back once the destination is reached.
These are the references I have looked into:
