寻路
就是对图的遍历，目前主要处理对可转换为二维矩阵的方格图遍历
DFS 与 BFS
两种最基础的遍历方式，DFS采用回溯思想，将从起点开始沿着一个方向搜索，直到超出界限(回溯)或者到达目的地(返回结果)
//只考虑上下左右四个方向
vector<vector<pair{int,int}>> res;
vector<pair{int,int}> path;
int dir[4][2] = {-1,0,1,0,0,1,0,-1};
void dfs(vector<vector<int>>& grid,int x,int y)
{
if(x == targetx && y == targety)
{
res.push_back(path);
}
for(int i = 0;i<4;i++)
{
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())
{
continue;
}
path.push_back({nextx,nexty});
dfs(grid,nextx,nexty);
path.pop_back();
}
}
而BFS则是一圈一圈的搜索，从起点向终点逐渐扩展，直到下一个圈包含了终点
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que;
que.push({x, y});
visited[x][y] = true;
while(!que.empty()) {
pair<int ,int> cur = que.front();
que.pop();
int curx = cur.first;
int cury = cur.second;
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
if (!visited[nextx][nexty]) {
que.push({nextx, nexty});
visited[nextx][nexty] = true;
}
}
}
}
最短路寻找
在游戏中自动寻找路径一般为对最短路的寻找，当点与点之间存在距离权重时，可以考虑Dijkstra算法
Dijkstra算法
利用优先队列实现排序，降低时间复杂度。
//定义一条边，从u点到v点的权值为w
struct edge {
int v, w;
};
//定义一个节点存储距离和当前节点
struct node {
int dis, u;
bool operator>(const node& a) const { return dis > a.dis; }
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
//优先队列存储起点到当前点的dis
priority_queue<node, vector<node>, greater<node> > q;
void dijkstra(int n, int s) {
memset(dis, 63, sizeof(dis));
//起点为s点
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
//获取当前队列的头部
int u = q.top().u;
q.pop();
//如果之前被访问过，跳过，因为现在肯定距离不是最小的
if (vis[u]) continue;
//置为1，说明访问过了
vis[u] = 1;
//对于所有与u点连通的点
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
//当记录的路径大于新的路径，那么更新
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
}
A*算法
(参考链接)[https://blog.csdn.net/Zhouzi_heng/article/details/115035298]
A*算法应该算作最常用的算法了。其想法是对当前点的路径排序，排序基准就是路径消耗(F) = 起点到该点的消耗(G) + 终点到该点的消耗(H)
首先需要维护两个数组，
数组1：一个为根据路径排序的数组，其存储的是从起点到终点可能走过的点，而这些点通常是下面那个数组的每个元素的可以到达的点组成的
数组2：第二个数组为最短路径数组，即结果数组，每次可以将第一个数组中的第一个元素取出放入即可。
其次就是路径排序了。可以对当前点计算路径消耗，然后利用插入排序寻找该点在数组1中的合理位置。
对于每个节点我们需要维护的是以下几个元素
- 当前节点位置
- 其父节点位置（即能到达他的最小消耗的节点）
- F
- G
- H
当我们找到了终点时，可以通过终点沿着存储的元素2，一直退回到起点得到路径
路径计算
起点到该点的路径消耗，由于退化为了二维数组，所以距离消耗计算就变为了横纵坐标插值（如果考虑对角线的话，还有对角线长度）
当前点到起点的消耗，就可以变为前一个点到起点的消耗 + 前一个点到当前点的消耗
对于终点到该点的消耗，一般采用估算法，首先是不考虑路径上的障碍，并且忽略通过对角线移动的情况，只考虑横纵坐标方向移动之和，然后乘以某个因子，即得到终点到起点的消耗。
最终两个消耗相加，可以得到该点的路径消耗
不断更新数组1，数组2，直到到达
当对起点周围的点计算完路径消耗后，加入到数组1中，再从数组1中取出第一个元素加入数组2中。该元素将作为下一轮路径计算的起点。
通过新元素计算G，如果该元素能到达的点已经出现在了数组1中，那么就需要进行比较，如果新G值为小值，就需要对数组1进行更新。并且改变这个已记录值的父亲。
对数组1更新主要是重新进行排序。
UE中实现
蓝图
首先需要创建一个结构体代表一个节点信息
对应了当前节点,G(第二个和第三个之和),H,父节点
同样创建两个数组1DiscoveredTileIndex以及数组2AnalysedTileIndex，分别表示搜索数组以及压入的下一个地点数组。
同时创建了一个用于排序的数组3DiscoveredTileSortingCosts
还有一个数组4结果数组
- 首先压入起点，并从起点开始寻找邻接点
在上图中，实现的功能是寻找某点的邻接点，并且计算该邻接点的消耗(由于从上一个点到该点的消耗都为1所以忽略了)，而用来估算终点到该点的消耗采用下方这个方式
当数组3长度为0时，或者消耗值大于数组3的最后一个元素时，直接向数组1以及数组3队尾压入即可
如果小于数组3的最后一个元素值，那么就需要搜索合适的位置，然后向数组1以及数组3插入。 - 对获得的数组1进行循环
如果数组1的长度大于0，说明该点有可以到达的点，那么就可以计算最短路径
首先将数组1中的第一个元素压入到数组2中，表示该点为前一个点向终点移动的最小消耗点
然后将该最小消耗点记录，计算其的邻接点数组，对这个邻接点数组进行遍历，求解消耗，压入数组1和数组3中 - 求解邻接点消耗
首先判断该邻接点是否已经存在数组2中，如果已经存在就可以返回
然后根据结构体中的当前点记录的起点消耗，以及邻接点的前一个点消耗计算出邻接点的起点消耗
如果邻接点不存在于数组1中，那么直接构造结构体，压入即可
如果存在，那么就要从之前遍历过的路径数组4中找到旧消耗来进行比较
然后构造结构体压入
- 生成路径
倒序寻找到的路径数组，通过结构体存储的前一个节点数据值，获得路径。