我目前正在使用 SDL 在 C++ 中构建一个基于网格的小型游戏。我制作了一个瓦片类，它代表地图上的每个瓦片。该瓦片类用于二维向量，一维表示 X 轴，另一维表示 Y 轴。
我遇到了算法问题，我什至不知道从哪里开始，假设我有这张地图：
0 0 1 1 0 E
0 0 0 1 0 1
0 C 0 1 0 1
0 1 0 1 0 1
0 1 1 1 1 1
C是我的角色，E是出口，1是地砖。
我想找出最好的方法来确定角色是否有办法到达出口。我知道我可以使用一个函数来手动检查 C 周围的每一块地砖，并且对于 C 周围的每一块地砖，我会再次检查周围的每一块地砖，直到找到通往 E 的一致路径，但这似乎不是最优的。
我可以有一个线索或某种方向来定位自己吗？
有很多算法可以找到两点之间的路径。三种算法易于实现和理解。
深度优先搜索
该算法获取当前节点，找到所有邻居，将它们放入堆栈，弹出一个并遍历到最后或找到路径。
广度优先搜索
该算法获取当前节点，找到所有邻居，将它们放入队列中，逐个出列并遍历直到结束或找到路径。
DFS 和 BFS 的区别在于，DFS 不能保证最优解。考虑这种情况。
S 1 1
1 1 1
1 1 E
假设 S 是 (0,0) 而 E 是 (2, 2)。这个迷宫有很多最优解。因为，DFS 会检查其邻居的路径直到最后，它可能需要S -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (1,2) -> E并且它将返回 6 作为路径的成本。然而，BFS 找到所有邻居，所有邻居的邻居并继续。如果邻居之一是 E，则返回成本。这将保证是最佳的。所以，BFS 可能会这样。S -> (1,0) -> (2,0) -> (2,1) -> E（它找到邻居的邻居，它不会与每个邻居一起走到最后）。
Dijkstra 算法
它类似于 BFS，但它可以有权重。在示例中，我们假设从一个节点移动到另一个节点的成本为 1 个单位。在 Dijkstra 的算法中，它允许我们使用任何正整数作为代价，并且对于每个链接它可以是不同的。
结论
如果您想要最佳结果，请选择 BFS 或 Dijkstra 算法。对于您的情况，BFS 应该可以工作。
#include<bits/stdc++.h>
using namespace std;
#define ROW 9
#define COL 10
// Creating a shortcut for int, int pair type
typedef pair<int, int> Pair;
// Creating a shortcut for pair<int, pair<int, int>> type
typedef pair<double, pair<int, int> > pPair;
// A structure to hold the neccesary parameters
struct cell
{
// Row and Column index of its parent
// Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
int parent_i, parent_j;
// f = g + h
double f, g, h;
};
// A Utility Function to check whether given cell (row, col)
// is a valid cell or not.
bool isValid(int row, int col)
{
// Returns true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// A Utility Function to check whether the given cell is
// blocked or not
bool isUnBlocked(int grid[][COL], int row, int col)
{
// Returns true if the cell is not blocked else false
if (grid[row][col] == 1)
return (true);
else
return (false);
}
// A Utility Function to check whether destination cell has
// been reached or not
bool isDestination(int row, int col, Pair dest)
{
if (row == dest.first && col == dest.second)
return (true);
else
return (false);
}
// A Utility Function to calculate the 'h' heuristics.
double calculateHValue(int row, int col, Pair dest)
{
// Return using the distance formula
return ((double)sqrt ((row-dest.first)*(row-dest.first)
+ (col-dest.second)*(col-dest.second)));
}
// A Utility Function to trace the path from the source
// to destination
void tracePath(cell cellDetails[][COL], Pair dest)
{
printf ("\nThe Path is ");
int row = dest.first;
int col = dest.second;
stack<Pair> Path;
while (!(cellDetails[row][col].parent_i == row
&& cellDetails[row][col].parent_j == col ))
{
Path.push (make_pair (row, col));
int temp_row = cellDetails[row][col].parent_i;
int temp_col = cellDetails[row][col].parent_j;
row = temp_row;
col = temp_col;
}
Path.push (make_pair (row, col));
while (!Path.empty())
{
pair<int,int> p = Path.top();
Path.pop();
printf("-> (%d,%d) ",p.first,p.second);
}
return;
}
// A Function to find the shortest path between
// a given source cell to a destination cell according
// to A* Search Algorithm
void aStarSearch(int grid[][COL], Pair src, Pair dest)
{
// If the source is out of range
if (isValid (src.first, src.second) == false)
{
printf ("Source is invalid\n");
return;
}
// If the destination is out of range
if (isValid (dest.first, dest.second) == false)
{
printf ("Destination is invalid\n");
return;
}
// Either the source or the destination is blocked
if (isUnBlocked(grid, src.first, src.second) == false ||
isUnBlocked(grid, dest.first, dest.second) == false)
{
printf ("Source or the destination is blocked\n");
return;
}
// If the destination cell is the same as source cell
if (isDestination(src.first, src.second, dest) == true)
{
printf ("We are already at the destination\n");
return;
}
// Create a closed list and initialise it to false which means
// that no cell has been included yet
// This closed list is implemented as a boolean 2D array
bool closedList[ROW][COL];
memset(closedList, false, sizeof (closedList));
// Declare a 2D array of structure to hold the details
//of that cell
cell cellDetails[ROW][COL];
int i, j;
for (i=0; i<ROW; i++)
{
for (j=0; j<COL; j++)
{
cellDetails[i][j].f = FLT_MAX;
cellDetails[i][j].g = FLT_MAX;
cellDetails[i][j].h = FLT_MAX;
cellDetails[i][j].parent_i = -1;
cellDetails[i][j].parent_j = -1;
}
}
// Initialising the parameters of the starting node
i = src.first, j = src.second;
cellDetails[i][j].f = 0.0;
cellDetails[i][j].g = 0.0;
cellDetails[i][j].h = 0.0;
cellDetails[i][j].parent_i = i;
cellDetails[i][j].parent_j = j;
/*
Create an open list having information as-
<f, <i, j>>
where f = g + h,
and i, j are the row and column index of that cell
Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
This open list is implenented as a set of pair of pair.*/
set<pPair> openList;
// Put the starting cell on the open list and set its
// 'f' as 0
openList.insert(make_pair (0.0, make_pair (i, j)));
// We set this boolean value as false as initially
// the destination is not reached.
bool foundDest = false;
while (!openList.empty())
{
pPair p = *openList.begin();
// Remove this vertex from the open list
openList.erase(openList.begin());
// Add this vertex to the open list
i = p.second.first;
j = p.second.second;
closedList[i][j] = true;
/*
Generating all the 8 successor of this cell
N.W N N.E
\ | /
\ | /
W----Cell----E
/ | \
/ | \
S.W S S.E
Cell-->Popped Cell (i, j)
N --> North (i-1, j)
S --> South (i+1, j)
E --> East (i, j+1)
W --> West (i, j-1)
N.E--> North-East (i-1, j+1)
N.W--> North-West (i-1, j-1)
S.E--> South-East (i+1, j+1)
S.W--> South-West (i+1, j-1)*/
// To store the 'g', 'h' and 'f' of the 8 successors
double gNew, hNew, fNew;
//----------- 1st Successor (North) ------------
// Only process this cell if this is a valid one
if (isValid(i-1, j) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i-1, j, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j].parent_i = i;
cellDetails[i-1][j].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j] == false &&
isUnBlocked(grid, i-1, j) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue (i-1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j].f == FLT_MAX ||
cellDetails[i-1][j].f > fNew)
{
openList.insert( make_pair(fNew,
make_pair(i-1, j)));
// Update the details of this cell
cellDetails[i-1][j].f = fNew;
cellDetails[i-1][j].g = gNew;
cellDetails[i-1][j].h = hNew;
cellDetails[i-1][j].parent_i = i;
cellDetails[i-1][j].parent_j = j;
}
}
}
//----------- 2nd Successor (South) ------------
// Only process this cell if this is a valid one
if (isValid(i+1, j) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j].parent_i = i;
cellDetails[i+1][j].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j] == false &&
isUnBlocked(grid, i+1, j) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i+1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j].f == FLT_MAX ||
cellDetails[i+1][j].f > fNew)
{
openList.insert( make_pair (fNew, make_pair (i+1, j)));
// Update the details of this cell
cellDetails[i+1][j].f = fNew;
cellDetails[i+1][j].g = gNew;
cellDetails[i+1][j].h = hNew;
cellDetails[i+1][j].parent_i = i;
cellDetails[i+1][j].parent_j = j;
}
}
}
//----------- 3rd Successor (East) ------------
// Only process this cell if this is a valid one
if (isValid (i, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i][j+1].parent_i = i;
cellDetails[i][j+1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j+1] == false &&
isUnBlocked (grid, i, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue (i, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i][j+1].f == FLT_MAX ||
cellDetails[i][j+1].f > fNew)
{
openList.insert( make_pair(fNew,
make_pair (i, j+1)));
// Update the details of this cell
cellDetails[i][j+1].f = fNew;
cellDetails[i][j+1].g = gNew;
cellDetails[i][j+1].h = hNew;
cellDetails[i][j+1].parent_i = i;
cellDetails[i][j+1].parent_j = j;
}
}
}
//----------- 4th Successor (West) ------------
// Only process this cell if this is a valid one
if (isValid(i, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i][j-1].parent_i = i;
cellDetails[i][j-1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j-1] == false &&
isUnBlocked(grid, i, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i][j-1].f == FLT_MAX ||
cellDetails[i][j-1].f > fNew)
{
openList.insert( make_pair (fNew,
make_pair (i, j-1)));
// Update the details of this cell
cellDetails[i][j-1].f = fNew;
cellDetails[i][j-1].g = gNew;
cellDetails[i][j-1].h = hNew;
cellDetails[i][j-1].parent_i = i;
cellDetails[i][j-1].parent_j = j;
}
}
}
//----------- 5th Successor (North-East) ------------
// Only process this cell if this is a valid one
if (isValid(i-1, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i-1, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j+1].parent_i = i;
cellDetails[i-1][j+1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j+1] == false &&
isUnBlocked(grid, i-1, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i-1, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j+1].f == FLT_MAX ||
cellDetails[i-1][j+1].f > fNew)
{
openList.insert( make_pair (fNew,
make_pair(i-1, j+1)));
// Update the details of this cell
cellDetails[i-1][j+1].f = fNew;
cellDetails[i-1][j+1].g = gNew;
cellDetails[i-1][j+1].h = hNew;
cellDetails[i-1][j+1].parent_i = i;
cellDetails[i-1][j+1].parent_j = j;
}
}
}
//----------- 6th Successor (North-West) ------------
// Only process this cell if this is a valid one
if (isValid (i-1, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination (i-1, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j-1].parent_i = i;
cellDetails[i-1][j-1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j-1] == false &&
isUnBlocked(grid, i-1, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i-1, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j-1].f == FLT_MAX ||
cellDetails[i-1][j-1].f > fNew)
{
openList.insert( make_pair (fNew, make_pair (i-1, j-1)));
// Update the details of this cell
cellDetails[i-1][j-1].f = fNew;
cellDetails[i-1][j-1].g = gNew;
cellDetails[i-1][j-1].h = hNew;
cellDetails[i-1][j-1].parent_i = i;
cellDetails[i-1][j-1].parent_j = j;
}
}
}
//----------- 7th Successor (South-East) ------------
// Only process this cell if this is a valid one
if (isValid(i+1, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j+1].parent_i = i;
cellDetails[i+1][j+1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j+1] == false &&
isUnBlocked(grid, i+1, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i+1, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j+1].f == FLT_MAX ||
cellDetails[i+1][j+1].f > fNew)
{
openList.insert(make_pair(fNew,
make_pair (i+1, j+1)));
// Update the details of this cell
cellDetails[i+1][j+1].f = fNew;
cellDetails[i+1][j+1].g = gNew;
cellDetails[i+1][j+1].h = hNew;
cellDetails[i+1][j+1].parent_i = i;
cellDetails[i+1][j+1].parent_j = j;
}
}
}
//----------- 8th Successor (South-West) ------------
// Only process this cell if this is a valid one
if (isValid (i+1, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j-1].parent_i = i;
cellDetails[i+1][j-1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j-1] == false &&
isUnBlocked(grid, i+1, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i+1, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j-1].f == FLT_MAX ||
cellDetails[i+1][j-1].f > fNew)
{
openList.insert(make_pair(fNew,
make_pair(i+1, j-1)));
// Update the details of this cell
cellDetails[i+1][j-1].f = fNew;
cellDetails[i+1][j-1].g = gNew;
cellDetails[i+1][j-1].h = hNew;
cellDetails[i+1][j-1].parent_i = i;
cellDetails[i+1][j-1].parent_j = j;
}
}
}
}
// When the destination cell is not found and the open
// list is empty, then we conclude that we failed to
// reach the destiantion cell. This may happen when the
// there is no way to destination cell (due to blockages)
if (foundDest == false)
printf("Failed to find the Destination Cell\n");
return;
}
// Driver program to test above function
int main()
{
/* Description of the Grid-
1--> The cell is not blocked
0--> The cell is blocked */
int grid[ROW][COL] =
{
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 }
};
// Source is the left-most bottom-most corner
Pair src = make_pair(8, 0);
// Destination is the left-most top-most corner
Pair dest = make_pair(0, 0);
aStarSearch(grid, src, dest);
return(0);
}
您可以尝试为 9 行和 10 列制作的 A* 算法，根据您的要求对其进行更新
让我们假设地面为：
1 1 1 1 1 E 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 C 1 1 1 1 1
但是总是试着让程序知道形状的属性，例如正方形在所有边上都是相等的，这就是为什么完美的对角线方式是最短的，所以如果有墙，你可以让你的程序选择对角线的最近部分作为
1 1 1 1 1 E 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 C 1 1 1 1 1
C (1) 旁边的部分，然后再继续对角线将有所帮助。为任何语法或拼写错误道歉。