如今游戏中最最常用的两种寻路算法为Dijkstra算法和A*算法，虽然现代引擎中的Al寻路算法看似很复杂,其实大部分是Dijkstra算法或者A*算法的变种。
无论是2D游戏的导航网格或者3D游戏导航网格, 本质上就是一个图，里面包含了各种点数据和边数据。
图(Graph)由点(Node)和边(Edge)构成，这里以二维为示例
class FVector2D
{
public:
float x;
float y;
}//2D位置
class FVector2D
{
public:
float x;
float y;
}
//点
class FGraphNode
{
private:
int index;
FVector2D pos;
}
//边
class FGraphEdge
{
private:
int fromIndex;
int toIndex;
float distance;
}
//图
class FGraph
{
public:
vector<FGraphNode> nodes;
vector<list<FGraphEdge>> edges;
}所谓 “寻路” 就是从图的一个点A出发，经过一系列边，到达一个点B，一般而言都是要求经过最短的路径。
深度优先搜索(DFS)就是在优先在树节点的深度搜索，直到到达最深度在回朔上一个较浅的节点，大致行为如下:
深度优先搜索(DFS)本质上是一种暴力搜索。如果采用深度优先搜索(DFS)在图中寻找从一个点寻找到另外一个点，寻找的路径并不是最短路径，如下所示：
广度优先搜索(BFS)就是在优先搜索同一个层级的节点,然后在考虑下一个层级的节点。
广度优先搜索(BFS)本质上也是一种暴力搜索，寻找的路径也和深度优先搜索(DFS)一样不是最短路径.
Dijkstra本质上是一种贪心算法,从起始点出发,总是优先选择沿着起点到目前点为最短的那个路径往下走.
这里引入一个概念:最短路径树(Short Path Tree, SRT),就是代表了从SPT这颗树上的任意一点达到起点都是最短路径。
这里引入一个搜索边的概念(Search Frontier)代表了图中的某条边是否被搜索过.
下面展示下,搜索点5到点3的最短路径的过程:
从上面图中可以看出Dijkstra算法总是非常贪心的, 如果起点到目前搜索点是最短的路径, 继续往下寻找，如果不是最短路径，回到最短路径的那个点继续往下找。这个过程模拟就是Queue队列，只不过这个队列的元素是点，而决定点优先级的是起点到对应点的距离,原点到哪个点的路径越短，就是在优先级最高的，所以我们采用数据结构优先队列(priority_queue)或者索引优先队列(index_priority_queue)。
实现代码：
struct CostNode
{
public:
int nodeIndex;
float cost;
public:
CostNode(int newNodeIndex = -1, float newCost = 0.0f):
nodeIndex(newNodeIndex),
cost(newCost)
{
}
};
struct OperaterCostNode
{
bool operator() (CostNode a, CostNode b)
{
return a.cost > b.cost;
}
};
void GetPathInDijkstra(int souceIndex, int destIndex, vector<FGraphNode>& pathPoints)
{
pathPoints.empty();
//SRT最短路径树(edge toindex = index)
vector<const FGraphEdge*> shortestPathTree(nodes.size(), nullptr);
//目前到N点最小花费
vector<float> costToNodes(nodes.size(), 0.0);
//目前到达N点最小花费的边(edge toindex = index)
vector<const FGraphEdge*> searchFrontier(nodes.size(), nullptr);
priority_queue<CostNode, vector<CostNode>, OperaterCostNode> pq;
pq.push(CostNode(souceIndex));
while (!pq.empty())
{
int nextNodeIndex = pq.top().nodeIndex;
pq.pop();
shortestPathTree[nextNodeIndex] = searchFrontier[nextNodeIndex];
if(destIndex == nextNodeIndex)
break;
const list<FGraphEdge>& EdgeList = edges[nextNodeIndex];
for (auto& edge : EdgeList)
{
float newCost = costToNodes[nextNodeIndex] + edge.GetDistance();
int toNodeIndex = edge.GetToIndex();
if (nullptr == searchFrontier[toNodeIndex])
{
costToNodes[toNodeIndex] = newCost;
searchFrontier[toNodeIndex] = &edge;
pq.push(CostNode(toNodeIndex, newCost));
}
else if(nullptr == shortestPathTree[toNodeIndex] &&
newCost < costToNodes[toNodeIndex])
{
costToNodes[toNodeIndex] = newCost;
searchFrontier[toNodeIndex] = &edge;
pq.push(CostNode(toNodeIndex, newCost));
}
}
}
int findNodeIndex = destIndex;
pathPoints.push_back(nodes[destIndex]);
while (findNodeIndex != souceIndex)
{
findNodeIndex = shortestPathTree[findNodeIndex]->GetFromIndex();
pathPoints.push_back(nodes[findNodeIndex]);
}
std::reverse(pathPoints.begin(), pathPoints.end());
}demo测试:: 构建 5 * 5 的网格数据，从(0, 0)寻找到(3, 4)，如下所示：
int main()
{
FGraph graph;
BuildTestGraph1(graph);
vector<FGraphNode> nodes;
int sourceIndex = graph.GetNodeIndex(FVector2D(0.0, 0.0));
int destIndex = graph.GetNodeIndex(FVector2D(3.0, 4.0));
if (sourceIndex == INDEX_INVALID || destIndex == INDEX_INVALID)
{
printf("error index\n");
return 0;
}
//graph.GetPathInAStar(sourceIndex, destIndex, nodes);
graph.GetPathInDijkstra(sourceIndex, destIndex, nodes);
for (auto& node : nodes)
{
node.Print();
printf("\n");
}
system("pause");
return 0;
}
Dijkstra算法虽然能找出最短路径，由于盲目的贪心，只以起点到目前点最短路径为最优先级来进行搜索，导致寻找了很多无用点，如下所示
上面说到Dijkstra算法因为 “以起点到目前点最短路径为最优先级来进行搜索”导致了搜索了很多无用点，所以人们改进了Dijkstra算法的“贪心策略”，由 “起点到目前点最短路径为最优先级” 转为 “（起点到目前点的最短距离 + 目前点到目标点的距离）最短距离为最优先级”，即
Dijkstra算法贪心策略 = Min(起点到目前点路径)
A*算法贪心策略 = Min(Min(起点到目前点路径) + 目前点到目标点的距离), 这里得注意：目前点到目标点的距离 不一定是欧式距离，可能是绝对距离，你得根据自己的算法需求来定等等，我们称其为估值函数(estimate function)
这样A*算法就不用寻找很多无用点，快速的得到最短路径
代码实现:(下面的距离计算用一个自定义的函数来实现，根据需求选用欧式距离,绝对距离还是其它)
#define AStarEstimateFunc std::function<float(const FGraphNode&, const FGraphNode&)>
void GetPathInAStar(int souceIndex, int destIndex, vector<FGraphNode>& pathPoints, AStarEstimateFunc estimateFunc)
{
pathPoints.empty();
//SRT最短路径树(edge toindex = index)
vector<const FGraphEdge*> shortestPathTree(nodes.size(), nullptr);
//目前到N点最小花费
vector<float> costToNodes(nodes.size(), 0.0);
//预估花费 = 到N点最小花费 + N点到终点最小距离
vector<float> costEstimateNodes(nodes.size(), 0.0);
//目前到达N点最小花费的边(edge toindex = index)
vector<const FGraphEdge*> searchFrontier(nodes.size(), nullptr);
priority_queue<CostNode, vector<CostNode>, OperaterCostNode> pq;
pq.push(CostNode(souceIndex));
while (!pq.empty())
{
int nextNodeIndex = pq.top().nodeIndex;
pq.pop();
shortestPathTree[nextNodeIndex] = searchFrontier[nextNodeIndex];
if (destIndex == nextNodeIndex)
break;
const list<FGraphEdge>& EdgeList = edges[nextNodeIndex];
for (auto& edge : EdgeList)
{
int toNodeIndex = edge.GetToIndex();
float hCost = estimateFunc(nodes[destIndex], nodes[toNodeIndex]);
float newCost = costToNodes[nextNodeIndex] + edge.GetDistance();
float costEstimate = hCost + newCost;
if (nullptr == searchFrontier[toNodeIndex])
{
costToNodes[toNodeIndex] = newCost;
costEstimateNodes[toNodeIndex] = costEstimate;
searchFrontier[toNodeIndex] = &edge;
pq.push(CostNode(toNodeIndex, costEstimate));
}
else if (nullptr == shortestPathTree[toNodeIndex] &&
newCost < costToNodes[toNodeIndex])
{
costToNodes[toNodeIndex] = newCost;
costEstimateNodes[toNodeIndex] = costEstimate;
searchFrontier[toNodeIndex] = &edge;
pq.push(CostNode(toNodeIndex, costEstimate));
}
}
}
int findNodeIndex = destIndex;
pathPoints.push_back(nodes[destIndex]);
while (findNodeIndex != souceIndex)
{
findNodeIndex = shortestPathTree[findNodeIndex]->GetFromIndex();
pathPoints.push_back(nodes[findNodeIndex]);
}
std::reverse(pathPoints.begin(), pathPoints.end());
}
auto astarEstimateFunc = [](const FGraphNode& nodeA, const FGraphNode& nodeB)
{
return nodeA.GetDistance(nodeB);
};
graph.GetPathInAStar(sourceIndex, destIndex, nodes, astarEstimateFunc);
从上面可以知道在图数据中 寻找一个点到另外一个目标点的最短路径， A*算法和Dijkstra算法都能计算出最短路径，但是A*算法比Dijkstra算法快(快多少取决于图中点和线的分布).
但这是否意味着A*算法无敌了呢？答案是否定的,因为A*算法在寻找指定的一个点到另外一个指定点路径是很快，但是碰上模糊条件搜索(存在n多个搜索目标)的情况，A*算法就有点懵逼了，比如：
一个人在城市市中心，这个城市有几十万甚至更多出口(由一条包围线包围着，可以分解为几十万甚至几百万个点）,这时候用A*一个个遍历几百万个点真的比Dijkstra算法快? 这种情况下Dijkstra算法真有可能比A*算法快。当然这两种算法并非是生死仇敌，某些情况搭配混用，效果更佳。
所以：
(1)明确一个点到另外一个点的最短路径：A*算法
(2)模糊条件搜索(存在N个对象)优先考虑Dijkstra算法
DijkstraAndAstar.rar-其他文档类资源-CSDN下载
(1)《游戏人工智能编程案例精粹》第五章 图的秘密生命