我正在使用SDL和C++构建一个基于网格的小游戏。我已经创建了一个"tile"类，它代表地图上的每个单独的方块。这个"tile"类被用在一个二维向量中，其中一个维度代表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
S 1 1
1 1 1
1 1 E
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）旁边的部分，然后再沿着对角线继续会有帮助。
对于任何语法或拼写错误，我们深表歉意。
“找出角色是否有方法到达出口的最有效方式”
嗯……根据您地图的大小，我会考虑模糊处理。
在小或密集的地图/迷宫中进行位模糊处理
想象一下将您的地图‘平铺’成一个长比特串，其中1表示可通过，0表示不可通过。您的地图宽度可以被用作‘步幅’...也就是说，对于任何比特位置，-W位代表向上，+W位代表向下。+1和-1表示左右移动。因此，2D地图以1D形式表示。
我们称这种扁平的位表示为‘M’
现在准备一个完全相同的uint64字符串，并将它们设置为零。这将是您的地图工作空间。
我们将这个空白位图称为‘S’，即搜索。
现在，要进行模糊处理，只需在‘S’中设置一个表示玩家位置的1位。
然后，将OR运算符'S'与S>>W、S<<W、S>>1和S<<1相结合。这会形成一个+形状。接下来，将其与M位图进行AND运算...这将删除任何与障碍物相交的+部分。
重复此操作，直到S中匹配您的出口的位被设置（或S未从其先前的值更改，表示搜索已完成）
在具有许多路径的图形中，这是快速的。使用uint64，您可以一次评估地图的64个方格。如果打开编译器优化，您可以使用SIMD，每个周期评估256个地图方格。
高级位操作
有一种更快的方法，涉及一些位技巧，以一次设置整个水平运行，并将设置位向下级联，直到它们撞到障碍物为止。
不幸的是，第二种方法可能有点复杂，在这里解释起来有些困难。两种方法都适用于内联ASM以及您选择的HLL...并且两种方法都可以利用SIMD。
当然，这些方法只告诉您出口是否可达。
字段的字节加法
可以使用类似字节的方案，这样可以模糊1并将其添加回来，生成一个可以反向跟随的距离场。因此，您可以在出口处设置1，一旦完成，您的玩家可以沿着升序值向出口走255步。
更好的方法：预计算
预计算是您的朋友。如果您有多个设置级别，则可以将这些预计算的路径和距离烘焙到级别地图本身中...允许在游戏时间内高效导航。每个正方形都可以具有（尽可能小的2位）值，其中编码U、D、L和R，表示某个特征的方向。可以以这种方式有效地编码多个特征。
毕竟，没有比预先计算的查找更快的了;)
预构建的、大大简化的图形
最后，有预定义的图形。许多迷宫都有长而可能曲折的通道，可以有效地被视为单个正方形或节点。通过将这样一个高度简化的节点结构与您的级别保存在一起，您可以在飞行中进行非常快速的路径查找。
希望这些内容能够帮助某些人以不同的方式思考问题。如果不行，还有A*、Dijkstra、BFS等...