一、广度优先遍历和深度优先遍历
在学习寻路算法之前,我们先来了解一下广度优先遍历和深度优先遍历.
什么是广度优先遍历?
广度优先遍历(breadth first search)是一个万能的算法.
广度优先是从初始状态一层一层向下找，直到找到目标为止。
广度优先遍历，指的是从一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。
例如:
这里遍历的顺序就是 从1到10
广度优先遍历相当于一个队列
先遍历1节点, 相邻节点234加入队列
然后按照顺序开始遍历2节点, 相邻节点5加入队列
再遍历3节点,67节点加入队列
以此类推一直到遍历结束.
什么是深度优先遍历?
DFS顾名思义就是一条路走到黑，再寻其他未走过的路。
深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。
上面的遍历顺序就是
1,2,5,9,3,6,10,7,4,8
其实我们用递归算法遍历二叉树的时候,就是这种遍历方法,也叫先序遍历.
广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。
最简单的寻路
我们来看下，下面最简单的寻路方式是广度优先遍历还是深度优先遍历?
假设:
我们的人物在一个小地图中,每次只能朝上下左右四个方向行走一步.这样的方式走到目的地.
我们每次向4个方向探索,得到边界,下次再继续探索边界
直到探索到目的地为止。
探索的过程中顺势记录下方块的来向,这样在探索到目的地的时候,知道怎么走过来的.也就获得了寻路路径.
这个算法非常的简单。
保存个队列循环遍历就可以了.
很明显这是广度优先遍历,也是可以达到寻路的目的的,
但是这相当于穷举, 没有方向性, 所以效率非常慢!
尤其地图很大的时候,成几何倍数的影响效率.
如果你不在乎效率或则地图非常小，那么你看到这里就够了。
但是，如果我们需要一个更效率更智能的算法,
那就需要了解A星算法（A*算法）
A星不会像广度优先遍历那样探索所有的步骤,而是选择每一步中最优的方块。
这样就可以大大提高效率了。
那么怎么来选择每一步中最优的方块呢？
这里面就涉及到了一个代价值的概念。
字面意思从A点到B点，我们需要付出的代价嘛
如果A点到B点是1公里，A点到C点是2公里，完全没有其他因素干扰的情况下
我们付出的代价肯定是 AC的代价= AB的代价*2.
比如我们要走到红色方框
首先遍历出来和我们相邻的所有节点也就是格子。
然后我们要从遍历出来的4个格子中选择一个代价值最低的格子作为最优格子。
我们这里就暂时只用移动的距离当代价值。
实际情况中，我们可能还需要根据地形，是否和障碍物相邻等等情况判断不同的代价。
每个格子的代价值（F） = 起点到他的代价值 （G）+ 预估从当前格子到终点的代价（H）
为什么要预估呢？因为我们不知道啊，如果能准确知道的话不就知道寻路路线了吗？还计算什么。
所以我们现在只能在忽略地形忽略障碍物的情况下，估算一个代价值。
可以计算直线距离，或则直接横向和纵向距离和（曼哈顿距离）。
后者不需要开平方操作（sqrt）这样会提高一些效率。
以上四个格子，我们叫做上下左右
他们的G 都是 1，这毫无疑问
他们的H 值分别是 4，4，4，2
很明显 右边格子 由于接近终点，所以是代价值最低的。所以我们会选择他为最优节点继续遍历。
当然选择的最优节点不一定是全局的最优节点例如下图：
很明显，向右走是不对的。
但是这就是探索，只有探索到障碍物,发现行不通,才会回头找更优的节点.
我们后面会根据继续的探索来修正线路。不过此时右就是最优节点。
大家可以到以下地址
Introduction to the A* Algorithm
对比一下广度优先遍历和A*遍历的区别和速度。
了解了基本的遍历思想
我们来详细的学习一下
二、A*算法
算法的过程解析
我们还是拿一个小例子来一步步的学习整个算法的过程。
不要嫌繁琐,我们能跟着思路完全的走一遍,完全理解算法的流程,才能把他应用到更多的场景,才能根据自己的需求随意的修改,而不是只会抄袭算法.
1.初始状态，这是一个7*7的小地图，起始点坐标 （3，1 ）终点坐标 （3，4）
我们进行寻路,中间做一堵墙.
首先，在正式开始前，我们先做一定的准备工作。
①，我们要有地图的信息,用一个二维数组来表示,0表示可以走的格子，1表示障碍物。
-
vector<vector<
int>> maptemp =
-
{
-
{
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0}
-
};
②创建两个表
一个表叫做openlist 来存放所有正在探索的节点，每次从整个表中找到最优节点.
一个表叫做closelist 来存放所有已经探索过的最优节点。探索过的就不需要再探索了.
③节点的属性
节点应该有坐标x,y 代价值F,G,H 同时还要有父节点，这样在我们探索到终点的时候，就可以根据父节点回溯出整条寻路路径。什么是父节点? 这个节点从哪个节点走过来的,哪个节点就是他的父节点,起点没有父节点.
我们先简写成伪代码这样: {x,y,F,G,H,father}
好的那么开始：
起点的属性={3，1，3，0，3，0} 起点坐标3,1 G = 0 H = 3 F = G+H = 3 父节点是空指针。
初始状态，我们只有起点，那么将起点加入 openlist.
openlist = {(3，1，3，0，3，0)};
closelist = {}
2.
openlist中选择最优节点，很明显只有起点一个节点。
那么把最优节点（3，1）从openlist中删除 因为已经探索过了，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，并且加入openlist
openlist = {(3，0，5，1，4，（3，1）)
(2，1，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
};
closelist = {(3，1，3，0，3，0)}
此时3个格子的F值都是5 = 1(出发点达到这里的值) + 预算值4
3.
openlist中选择最优节点，3个节点F值一样。
所以会根据存入openlist的先后顺序,选择一个作为下一个最优节点，这里选择的（2，1）
图中是先存放的上,我们自己存放不一定哦.
那么把最优节点（2，1）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外,已经在列表中的节点排除，并且加入openlist
openlist = {(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
}
此时新加入的2个格子的F值都是7 明显比最开始的2个格子的F值大，所以这里下一步不会沿着当前线路继续遍历，而是会回头去判断之前的线路有没有更优解。
4.
openlist中选择最优节点，这里选择的（3，0）
那么把最优节点（3，0）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外,已经在列表中的节点排除,并且加入openlist
(((但是这里值得注意的是:
如果周围相邻的节点,
已经在closelist列表中,说明再走向他就是回头路了,所以不用考虑.
已经在openlist列表中的节点,还在探索中,那么之前的F值是通过之前的其他最优节点计算出来的.
如果通过我们现在的最优节点计算出来的F值比之前的小,那么应该替换!
比如这里 2,0 就是 之前的 F 值 = 2 + 5
现在的F 值 = 2 + 5 相等所以不用替换.)))
openlist = {
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
(4，0，7，2，5，（3，0）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
}
5.
openlist中选择最优节点，那么毫无疑问,这次应该选择 最后一个代价值5的节点了
那么把最优节点（4，1）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，已经在列表中的节点排除,并且加入openlist
openlist = {
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
(4，0，7，2，5，（3，0）)
(5，1，7，2，5，（4，1）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
}
目前openlist中就是4个代价值为7的节点了.
目前从起始开始到这里.由于地形的限制，此时我们的A*遍历和正常的广度优先遍历得到的结果和效率没什么区别，那么一会找到一个更优的节点就出现很大的差别了。
这里我们也能看出来了, 边缘的节点就是openlist中的节点, 而内部已经探索过的节点就是closelist节点
6.
继续探索
openlist中选择最优节点 2,0
那么把最优节点（2，0）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，已经在列表中的节点排除,并且加入openlist
openlist = {
(1，1，7，2，5，（2，1）)
(4，0，7，2，5，（3，0）)
(5，1，7，2，5，（4，1）)
(1，0，9，3，6，（2，0）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
}
7.
继续探索
openlist中选择最优节点 1,1
那么把最优节点（1，1）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，已经在列表中的节点排除,并且加入openlist
openlist = {
(4，0，7，2，5，（3，0）)
(5，1，7，2，5，（4，1）)
(1，0，9，3，6，（2，0）)
(0，1，9，3，6，（1，1）)
(1，2，7，3，4，（1，1）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
}
这个时候其实我们发现已经找到了 好的转折点
8.
继续探索
openlist中选择最优节点 1,2
那么把最优节点（1，2）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，已经在列表中的节点排除,并且加入openlist
openlist = {
(4，0，7，2，5，（3，0）)
(5，1，7，2，5，（4，1）)
(1，0，9，3，6，（2，0）)
(0，1，9，3，6，（1，1）)
(1，3，7，4，3，（1，2）)
(0，2，9，4，5，（1，2）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
(1，2，7，3，4，（1，1）)
}
9.
继续探索
openlist中选择最优节点 1,3
那么把最优节点（1，3）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，已经在列表中的节点排除,并且加入openlist
openlist = {
(4，0，7，2，5，（3，0）)
(5，1，7，2，5，（4，1）)
(1，0，9，3，6，（2，0）)
(0，1，9，3，6，（1，1）)
(0，2，9，4，5，（1，2）)
(0，3，9，5，4，（1，3）)
(1，4，7，5，2，（1，3）)
(2，3，7，5，2，（1，3）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
(1，2，7，3，4，（1，1）)
(1，3，7，4，3，（1，2）)
}
10.
继续探索
openlist中选择最优节点 2,3
那么把最优节点（2，3）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，已经在列表中的节点排除,并且加入openlist
openlist = {
(4，0，7，2，5，（3，0）)
(5，1，7，2，5，（4，1）)
(1，0，9，3，6，（2，0）)
(0，1，9，3，6，（1，1）)
(0，2，9，4，5，（1，2）)
(0，3，9，5，4，（1，3）)
(1，4，7，5，2，（1，3）)
(3，3，7，6，1，（2，3）)
(2，4，7，6，1，（2，3）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
(1，2，7，3，4，（1，1）)
(1，3，7，4，3，（1，2）)
(2，3，7，5，2，（1，3）)
}
11.
继续探索
openlist中选择最优节点 2,3
那么把最优节点（2，3）从openlist中删除，同时加入到closelist中
找到最优节点周围可以走的方格,障碍物排除在外，已经在列表中的节点排除,并且加入openlist
openlist = {
(4，0，7，2，5，（3，0）)
(5，1，7，2，5，（4，1）)
(1，0，9，3，6，（2，0）)
(0，1，9，3，6，（1，1）)
(0，2，9，4，5，（1，2）)
(0，3，9，5，4，（1，3）)
(1，4，7，5，2，（1，3）)
(3，3，7，6，1，（2，3）)
(1，4，9，7，2，（2，4）)
(2，5，9，7，2，（2，4）)
(3，4，7，7，0，（2，4）)
};
closelist = {(3，1，3，0，3，0)
(2，1，5，1，4，（3，1）)
(3，0，5，1，4，（3，1）)
(4，1，5，1，4，（3，1）)
(2，0，7，2，5，（2，1）)
(1，1，7，2，5，（2，1）)
(1，2，7，3，4，（1，1）)
(1，3，7，4，3，（1，2）)
(2，3，7，5，2，（1，3）)
(2，4，7，6，1，（2，3）)
}
此时我们发现,openlist中出现了目的地节点 遍历结束
12.回溯完整路径
找到了目的地,我们通过父节点找出整个路径就可以了,其实就是一个简单的链表.
(3，4，7，7，0，（2，4）)父节点是2,4 到closelist中找2,4节点即可
(2，4，7，6，1，（2，3）)父节点是2,3 到closelist中找2,3节点即可
以此类推
(2，3，7，5，2，（1，3）)
(1，3，7，4，3，（1，2）)
(1，2，7，3，4，（1，1）)
(1，1，7，2，5，（2，1）)
(2，1，5，1，4，（3，1）)
(3，1，3，0，3，0)
反序排列即是我们的最优路径
(3，1)---->(2，1)---->(1，1)---->(1，2)---->(1，3)---->(2，3)---->(2，4)---->(3，4)
整理全过程
⑴将起点加入一个openlist列表
⑵在openlist列表中找到一个最优节点(代价值最低)做为当前节点(第一次是起点).
把当前节点从openlist列表中删除并且存到closelist列表中.
把当前节点相邻的所有节点处理过后加入到openlist列表中.
处理过程:
障碍物点或则已经在closelist列表中的相邻节点不处理
如果相邻节点已经在openlist列表中,
意味着已经探索过,而且已经有父节点.
如果从当前节点到那个节点的代价值比原代价值更低
就重置那个节点的代价值和父节点.
⑶在openlist列表中选择一个最优节点.重复2的操作
直到找到目的地.
⑷根据目的地的父节点,一直回溯整个路径.
四朝向可以改八朝向
当然这里面是4朝向 ,我们可以修改成8朝向 路径会更短一些
至少箭头的一步可以由2步省略成一步,
根据距离计算,我们大约少走了半个格子.
算法流程没有任何区别,只是我们在遍历周围节点的时候 ,判断8个位置即可.
例如3,1相邻的8个节点分别是
2,0 2,1 2,2 3,0 3,2 4,0 4,1 4,2
同时要注意:
我们走斜格子的时候,如果穿越障碍物会有碰撞体
很多游戏里这样是行走不了的, 要根据我们的具体情况进行设置.
避免帖墙走导致卡顿
A*算法由于计算最优解,所以计算出来的结果必然是帖子障碍物走的,
这是必然的,只要远离一下障碍物就会绕远对吗?
那么如果我们想不让他贴障碍物移动
需要进行2个修改
①不允许有障碍物的情况斜着移动
②增加贴着障碍物行走的代价值,当然不能完全不让贴着障碍物,某些情况例如 只有1-2排贴着障碍物通过的线路
我们不能绕很远的路哦,所以要给一个合理的代价值增量.
例如这样就完全没必要了,为了躲避一个贴着障碍的点,绕了一大圈
③寻路中不要把其他移动的单位计算为障碍物,因为他们是一直移动的,当你走过去可能已经变了.
我们可以判断自己是否卡点,一旦卡点来重新计算A*寻路
④不同地形 ,我们也应该给予不同的代价值,这是合理的.
也可以给改变了方向的方格增加代价值,使得行走更平滑
我们来完成A*代码
根据我们上面的流程,修改成C++代码
核心代码就100来条, 已经备注的很清晰
头文件
-
#pragma once
-
#include <vector>
-
#include <list>
-
using
namespace std;
-
-
const
int consume1 =
10;
//直移消耗
-
const
int consume2 =
14;
//斜移消耗
-
const
int consume3 =
7;
// 挨着障碍物额外消耗 我认为的最佳值是7
-
const
int consume4 =
5;
//变换方向增加消耗
-
-
struct
Point
-
{
-
int x, y;
-
int F, G, H;
-
Point* father;
//父节点的坐标
-
Point(
int _x,
int _y) :
x(_x),
y(_y),
F(
0),
G(
0),
H(
0),
father(
NULL) {};
-
};
-
-
class
Astar
-
{
-
public:
-
vector<vector<
int>> map;
//地图
-
list<Point*> openList;
//开启列表
-
list<Point*> closeList;
//关闭列表
-
void setMapAstar(vector<vector<int>>& _map);
//初始化地图
-
int getG(Point* temp_start, Point* point);
-
int getH(Point* point, Point* end);
-
int getF(Point* point);
-
int isByOb(const Point* point);
-
Point* getLeastFpoint();
-
Point* isInList(const list<Point*>& list, const Point* point);
//判断开启/关闭列表中是否包含该点
-
bool isCanReach(const Point* point, const Point* temp_end, bool n = false);
//判断某点是否和当前节点相通
-
vector<Point*> get8Points(const Point* point, bool n = false);
//取当前节点周围点
-
list<Point*> GetPath(Point& startPoint, Point& endPoint, bool n = false);
-
Point* findPath(Point& startPoint, Point& endPoint, bool n = false);
-
};
cpp
-
#include <iostream>
-
#include <math.h>
-
#include
"astar.h"
-
using namespace std;
-
-
void Astar::
setMapAstar(vector<vector<int>>& _map)
-
{
-
map = _map;
-
}
-
-
int Astar::
getG(Point* temp_start, Point* point)
-
{
-
int fToMeG = (
abs(point
->x - temp_start
->x) +
abs(point
->y - temp_start
->y)) ==
1 ? consume1 : consume2;
//父节点到这个节点的代价值
-
int fatherG = point
->father == NULL ?
0 : point
->father
->G;
//父节点的代价值
-
int byObG =
isByOb(point) * consume3;
//是否挨着障碍物而增加代价值
-
return fToMeG + fatherG + byObG;
-
}
-
-
int Astar::
getH(Point* point, Point* end)
-
{
-
return (
abs(end
->x - point
->x) +
abs(end
->y - point
->y)) * consume1;
//当然也可以开平方求直线距离,这里为了提高效率直接用x,y距离和
-
}
-
-
int Astar::
getF(Point* point)
-
{
-
return point
->G + point
->H ;
-
}
-
-
int Astar::
isByOb(
const Point* point)
-
{
-
for (int x = point
->x -
1; x <= point
->x +
1; x++)
-
{
-
for (int y = point
->y -
1; y <= point
->y +
1; y++)
-
{
-
if (x < (int)map.
size() -
1 && y < (int)map[
0].
size() -
1 && x >=
0 && y >=
0)
-
if (map[x][y] ==
1)
-
return
1;
-
}
-
}
-
return
0;
-
}
-
-
Point* Astar::
getLeastFpoint()
-
{
-
if (!openList.
empty())
-
{
-
Point* retPoint = openList.
front();
-
for (Point* point : openList)
-
{
-
if (point
->F < retPoint
->F)
-
retPoint = point;
-
}
-
return retPoint;
-
}
-
return NULL;
-
}
-
-
Point* Astar::
isInList(
const list<Point*>& list,
const Point* point)
-
{
-
for (Point* p : list)
-
if (p
->x == point
->x && p
->y == point
->y)
-
return p;
-
return NULL;
-
}
-
-
bool Astar::
isCanReach(
const Point* point,
const Point* temp_end,
bool n)
-
{
-
if (temp_end
->x<
0 || temp_end
->x>(int)map.
size() -
1|| temp_end
->y<
0 || temp_end
->y>(int)map[
0].
size() -
1
//要走的点超出地图,不可达
-
|| map[temp_end
->x][temp_end
->y] ==
1
//要走的点是障碍物,不可达
-
|| temp_end
->x == point
->x && temp_end
->y == point
->y
//要走的点和当前点重合,是自己
-
||
isInList(closeList, temp_end))
//要走的点在关闭列表中，证明已经走过了
-
return
false;
-
else
-
{
-
if (
abs(point
->x - temp_end
->x) +
abs(point
->y - temp_end
->y) ==
1)
//非斜角直接可以
-
return
true;
-
else
-
{
-
//斜对角要判断是否有障碍物
-
if (map[point
->x][temp_end
->y] ==
0 && map[temp_end
->x][point
->y] ==
0)
//没有障碍物
-
return
true;
-
else
//有障碍物根据参数决定是否走
-
return n;
-
}
-
}
-
}
-
-
vector<Point*> Astar::
get8Points(
const Point* point,
bool n)
-
{
-
vector<Point*> retPoints;
//STL库中的容器也是存放在堆中 是可以返回局部变量的
-
-
for (int x = point
->x -
1; x <= point
->x +
1; x++)
-
for (int y = point
->y -
1; y <= point
->y +
1; y++)
-
if (
isCanReach(point, new
Point(x, y), n))
-
retPoints.
push_back(new
Point(x, y));
-
return retPoints;
//注意整个容器的释放 否则会内存泄漏
-
}
-
-
list<Point*> Astar::
GetPath(Point& startPoint, Point& endPoint,
bool n)
-
{
-
Point* result =
findPath(startPoint, endPoint, n);
-
list<Point*> path;
-
while (result)
-
{
-
path.
push_front(result);
-
result = result
->father;
-
}
-
openList.
clear();
-
closeList.
clear();
-
return path;
-
}
-
-
Point* Astar::
findPath(Point& startPoint, Point& endPoint,
bool n)
-
{
-
int x =
1;
-
openList.
push_back(new
Point(startPoint.x, startPoint.y));
-
while (!openList.
empty())
-
{
-
Point* bestPoint =
getLeastFpoint();
-
-
openList.
remove(bestPoint);
//从开启列表中删除
-
closeList.
push_back(bestPoint);
//放到关闭列表
-
-
auto surroundPoints =
get8Points(bestPoint, n);
-
-
for (auto& target : surroundPoints)
-
{
-
if (!
isInList(openList, target))
-
{
-
target
->father = bestPoint;
-
target
->G =
getG(bestPoint, target);
-
target
->H =
getH(target, &endPoint);
-
target
->F =
getF(target);
-
openList.
push_back(target);
-
}
-
else
// 某节点已经在openList中并且通过当前节点计算的G值比之前小,就更新该节点信息
-
{
-
target =
isInList(openList, target);
-
int tempG = bestPoint
->G;
-
tempG += (
abs(target
->x - bestPoint
->x) +
abs(target
->y - bestPoint
->y)) ==
1 ? (consume1 +
isByOb(target) * consume3) : (consume2 +
isByOb(target) * consume3);
-
if (tempG < target
->G)
-
{
-
target
->father = bestPoint;
-
target
->G = tempG;
-
target
->F =
getF(target);
-
}
-
}
-
Point* resPoint =
isInList(openList, &endPoint);
-
if (resPoint)
-
{
-
vector<Point*>().
swap(surroundPoints);
-
return resPoint;
-
}
-
}
-
vector<Point*>().
swap(surroundPoints);
-
}
-
return NULL;
-
}
调用
-
#include <iostream>
-
#include "windows.h"
-
#include <string>
-
#include <vector>
-
#include <array>
-
#include "astar.h"
-
using
namespace std;
-
-
-
-
int main()
-
{
-
//初始化地图，用二维数组代表地图，1表示障碍物，0表示可通
-
vector<vector<
int>> maptemp =
-
{
-
{
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
1,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0}
-
};
-
//模拟一个更大的地图
-
vector<vector<
int>> maptemp2 =
-
{
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
1,
1,
1,
1,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0},
-
{
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0}
-
};
-
Astar astar;
-
astar.
setMapAstar(maptemp);
-
//设置出发点和目的地
-
int x0, y0, x1, y1;
-
cout <<
"请输入起点：" << endl;
-
cin >> x0 >> y0;
-
cout <<
"请输入终点：" << endl;
-
cin >> x1 >> y1;
-
Point start(x0, y0);
-
Point end(x1, y1);
-
-
clock_t starttime =
clock();
-
list<Point*> path = astar.
GetPath(start, end,
false);
-
//vector和list区别
-
//①vector是一块连续的内存,list是双向链表,内存中不是连续的,所以list开销更小
-
//②list是双向链表,所以访问元素的效率特别低,需要频繁随机取元素的时候,vector更好.
-
//③vector删除插入数据时需要复制移动后面所有的元素,所以需要频繁插入删除操作时,list更合适
-
//所以我们这里的代码都选择使用list
-
clock_t endtime =
clock();
-
//map.size()是一维数组的大小 也就是说多少行
-
//map[0].size()是一行有多少个元素
-
cout <<
"\n" <<
"地图大小:" << maptemp.
size() <<
" * " << maptemp[
0].
size() <<
"\n";
-
cout <<
"行走路径:";
-
for (Point* p : path)
-
{
-
cout <<
"(" << p->x <<
"," << p->y <<
") ";
-
}
-
cout <<
"\n";
-
string s[
2] = {
"□",
"■" };
-
-
int findinpath =
0;
-
for (
int w =
0; w < (
int)maptemp.
size(); w++)
-
{
-
for (
int h =
0; h < (
int)maptemp[
0].
size(); h++)
-
{
-
for (
const Point* p : path)
-
{
-
if (w == p->x && h == p->y)
-
{
-
cout <<
"☆";
-
findinpath =
1;
-
break;
-
}
-
}
-
if(findinpath==
0)
-
{
-
cout << s[maptemp[w][h]];
-
}
-
findinpath =
0;
-
}
-
cout <<
"\n";
-
}
-
cout <<
"用时:"<< endtime - starttime <<
"ms" << endl;
-
return
0;
-
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
三、获取地图信息的方法
1.通过内存数据读取二值化地图
其实方法很多,
例如M三国我们通过探索地图迷雾,
某个点黑色的时候搜索1或则0, 被我们探索开搜索1或则0,
这样就可以找到0,1的地图数据了,当然他这里是两层,一层是迷雾,一层是真实,任鸟飞逆向老的课程里面有.
又例如,神途,可以通过地图大小搜索得到地图数据
又例如,大部分游戏可以通过是否在障碍物周围进行扫描
又例如,我们可以通过走路call是否可达,进行代码分析.
方法很多,也都不难,我们需要慢慢锻炼.
2.采集点
地图数据过大或则很难获取完整地图数据的时候,例如某W
我们可以自己录制点,把已经走过的路径视为可通行点.
未探索过的地方设置为不可通行点.这样就可以了.
也可以随时增加更新.扩充区域.
录制点并没有很麻烦,正常玩耍即可.
但是注意,尽量远离障碍物 ,一是防止不小心碰到障碍物降低容错
二是,这样可以给后期,增大方块范围提供更多可能.
3.地图过大导致寻路效率低
我们可以把节点简化成更少,例如9个格子合并成一个
这样一个300*300的大地图 就变成 100*100,合并以后的格子,9个小格子其中一个是障碍物就整理变成障碍物.
四、A星的优化
当地图很大需要寻路的路径很长的时候，或者使用A星算法的寻路频率很高的时候，A星的效率会很低.
1.记录一些常用的路径 和一些路标节点
常用的路径
我们已经保存了A到B的路径,当我们寻路时,出发点在A附近,目的地在B附近
我们可以先寻路到A,然后A到B 走保存好的路径,然后再B到目的地.
以这种方式来规避一些计算量特别大，或者计算频率特别高的寻路算法调用，在大型世界的RPG游戏里特别常用。
路标节点
也可以叫做导航点。就是去目的地的必经的点位。
比如我们从地图的一个区域到另外一个区域, 其中有2个小路是必经的出口.
这2个出口点就可以作为导航点，我们在寻路时可以先寻找到最近的一个出口的导航点，
达到导航点再寻往目的地.
然后很多情况,导航点去任何地方都应该有常用路径,到时候通往下一个路径的终点,再由终点达到的目的地.
2.排序算法优化
其实我们对openlist的排序,查找等操作特别多.
随着队列长度的增大而增大，这上面消耗很多的效率.
可以用二分法查找或则不排序来提高效率.
-
int a[
20] = {
1,
3,
4,
7,
11,
16,
22,
23,
25,
27,
29,
33,
38,
45,
46,
49,
67,
77,
98,
100 };
-
int x;
-
cout <<
"查找一个数值:";
-
cin >> x;
-
int low =
0;
-
int h =
19;
-
int mid;
-
while (low <= h)
-
{
-
mid = (low + h) /
2;
-
if (x == a[mid])
-
break;
-
else
if (x < a[mid])
-
h = mid -
1;
-
else
-
low = mid +
1;
-
}
-
if(low<=h)
-
cout <<
"第"<<mid+
1<<
"个元素";
-
else
-
cout <<
"没有这个数值"<<endl;
具体排序二分法查找,还是不排序好, 这个需要大家在不同大小的地图环境测试.
3.
我们之前的代码会频繁的判断节点是否在CLOSELIST
要在Close列表中找节点，就相当于遍历一遍所有已经找过的节点，Close里的节点越多，越浪费CPU，而且是不只一次浪费，每个循环都会浪费一次，性能消耗巨大。
所以我们可以初始化地图二维int型数组为一个其他结构数组
其中包含一个属性,就是该点是否加入到CLOSELIST
这样我们在加入的同时,把这个属性也写成1,代表加入了CLOSELIST
这样判断一个点是否在CLOSELIST的时候,直接判断这个属性就可以了
避免了大量的遍历.
但是每次在A星寻路开始前，需要将这个属性初始化为0，就需要遍历整个数据来初始化。
这个可不可以避免呢?
也是用一个变量就可以了
第一次我们表示加入CLOSELIST用1, 第二次用2 以此类推就可以了
小于当前值 都算不在列表中即可
这样省去了巨量的初始化操作。
同时待检测列表, 用二叉堆等数据结构也可以提高效率,我们数据结构章节再具体研究.
五、B星算法
1.B星算法的基本思路就是贪心思想+攀爬障碍
1.寻路过程中向前探索的节点称为探索节点，起始探索节点就是起点。
2.探索节点朝着目标前进，如果前方不是障碍物，探索节点可以继续向前进入下一个节点.
这种探索节点我们称为自由探索节点.
3.探索节点朝着目标前进，如果前方是障碍物，探索节点将试图绕过阻挡，绕行中的探索节点我们成为绕爬的探索节点
2.算法过程
1.起始，探索节点为自由节点，从起点出发，向目标前进
自由节点前进过程中判断前面是否为障碍.
如果不是障碍，向目标前进一步，仍为自由节点.
如果是障碍，以前方障碍为界，分出左右两个分支，分别试图绕过障碍，这两个分支节点即成为两个绕爬的探索节点
2.绕爬的探索节点绕过障碍后，又成为自由节点.
3.探索节点前进后，判断当前地图格子是否为目标格子，如果是则寻路成功，根据寻路过程构造完整路径.
4.寻路过程中，如果探索节点没有了，则寻路结束，表明没有目标格子不可达.
例如:
又例如
很明显,B星计算不出来最短路径,只是在绝大部分环境下提高了效率
所以A星和B星怎么用,用谁完全取决于什么应用环境
3.正常b星算法相关数据结构
正常b星算法：一步一步前进，遇到障碍则多条路径同时前进，利用判断语句判断是否撞过墙和方向判断方法来确定下一步的位置。
存储地图和障碍，以及遍历历史。
我们可以采用传统的二维int类型数组或者二维bool类型数组。
-
public
bool[,] mymap;
-
public
bool[,] visit;
存储遇到障碍物产生的分支路径点
利用队列的先进先出原则，使得路径依次进队，当所有路径应该前进时，则依次出队，进行下一步的探索，死路则不再进队，直至队空则是无路可走，或是直至行至终点。
public Queue<bpoint> bpointqueue =new Queue<bpoint>();方向的数据结构
利用枚举类型判断方向
-
public
static
short[] directioncolumn = {
1,
0,
-1,
0 };
-
public
static
short[] directionrow = {
0,
1,
0,
-1 };
-
// 0右 1下 2左 3上
路径点的数据结构
我们在每一个路径点里需要存储：这个点的父路径点；这个点的坐标；以及标记是否撞过墙或是撞过的墙的位置；还有分支方向。
-
public
class
bpoint
-
{
-
public
int pointcolumn, pointrow, step;
-
public
short walldirection, direction;
-
public bpoint daddy;
-
}
路径点的初始化和操作
由于要不断构造新的路径点并且进行操作，为了解决命名和变量使用，可以将所有的路径点合为一个字典，利于路径点的操作，同时也能统计数量。
-
public Dictionary<
int,bpoint> allpoint=
new Dictionary<
int,bpoint>();
-
public
int i =
0;
//字典初始化
-
//使用范例
-
bpointqueue.Enqueue(allpoint[i]);
-
allpoint[i].walldirection =
0;
-
i++;
4、思路拓宽和个人拙见
算法是基于贪心思想的，所以当前的数据结构仍未解决出现凹形的包围状障碍物会出现无法找到通路的情况
但是可以通过修改障碍物的数据结构，就可以完成这一目标。
方案：
将障碍物的数据结构改为闭合的矢量图形，即在初始化地图的时候障碍物周围的节点会被激活节点类中的链式变量，也就是为这些节点增加了顺时针节点和逆时针节点，这两个节点类的变量会指导路径的探索，成为两条分支队列分别继续探索，从而使得路径队列顺利的攀爬过这个凹形的包围状障碍物。
方案缺点：
使得障碍物的初始化过程更加复杂，应该会占用更多空间，而且构造障碍物时间会更长，但是寻路时间却可能减少，这是因为有了顺时针逆时针矢量的存在，使得下一步有可能已经被提前规划好，综合来看，也就是花了更多的空间解决了这个问题。
B* 算法强大之处在于速度（抛开刚刚解决的障碍物问题），这也使得这个算法同最佳优先搜索一样，有可能找到的路径不是最短的路径。
要解决这个问题也可以，加入一个走回路的标记，当路径开始回头走时，标记激活，当不再回头或者已经超过了回头的路程时标记记录下这个点，再使用A* 算法优化起点和这个点之间的路径，使得路径是最短，但是这样其实很费时，就丢失了这个算法的强大之处。
另一个个人想法是利用多线程操作来进行策略选择，分配给不同的cpu分别进行A* 算法和B* 算法，同样也进行回头标记，但是不做更多操作，B* 算法会先完成，若没有回过头，则直接结束两个线程，返回B* 路线，如果有回过头，则等待A* 算法得到路线。
今后若有学余时间，会着手尝试实现提到的方案。
B*算法原理： 一般寻路的方向 上、下、左、右
- 根据开始和结束2个点确定移动的方向
- 每走一步都需要确定一下方向
- 如果中途遇到有障碍物，根据当前位置和终点的位置，确定移动方向，变成2条线路
- 这2 条线交替向终点方向移动
- 如果中途又碰见障碍物了，继续分2个线，此时四条线交替移动
- 最先到终点的就是最终的路线；
六、实战获取地图信息
应用A*算法的前提是要获取当前地图中所有节点的信息.
判断每一个节点是否是一个障碍物，即触碰体。
比如下图中的树，仙人掌，石头等就是障碍物.
为了获取到所有的节点信息，就需要对整个平面地图的内存数据进行分析，而这些障碍物往往就是我们的关键突破口。
障碍点分析
平面地图的障碍点分析，我们可以从走路函数入手，在目标点可达和不可达两种情况下，走路函数经过的代码是不同的，通常会以一个标志位来表示两个点是否可达。
那么首先我们就需要找到这个游戏的明文发包函数，分析的过程就不过多讲解了 ，有兴趣的可以到公众号任鸟飞逆向中学习线程发包的相关课程。
直接跳到明文发包头部
在这里下断，我们可以断到走路函数，此时我们向障碍物寻路是不会断下的，也就是说人物不动的情况下，这个函数是不会经过的。
逐层向外层返回，并观察什么时候点击障碍物会断下，最终找到了一个走路和撞墙都会断下的位置
这里的代码是经过VM的，分析起来会比较困难.
我们看看有没有其他更巧妙的办法.
当然以上办法是比较通用的.
比如通过地图的大小获取到地图所有节点的遍历。
首先我们在一个较小的地图中观察他的X和Y的最大值
这个地图的X坐标最大为38，为了保险起见，我们搜索一个35-100的范围
然后来到房间外面，再看一下大地图的大小是多少
这个地图的X为924左右，那么我们搜索920-1000，经过反复的过滤，最终得到一个结果
在xdbg中观察这个地址，发现X和Y的最大值是挨着的
我们对这个地址进行访问后， 并没有得到遍历相关的代码，也就是说这个位置也许是单纯的写入了地图的大小。
于是我们在CE中继续扫描9E 03 00 00 20 03 00 00这个字节集，看一下是否还有其他的位置存放这两个数值，并得到了9个结果
分别对这9个结果下访问断点，看下哪些会有访问代码，最后剩下了3个地址
第一个地址在下断后需要点击地面才会断下，而后面两个是直接断下的
对第一个地址进行观察，可以得到一个0x39E*0x320的结构体数组，这与地图节点遍历的数据是很接近的。但是对里面的数据下访问断点没有反应，所以我们先看后面两个结果。
第二个结果和第三个结果是挨着的，第二个结果断下后需要点一次F9才能获取到遍历的代码
这也是一个数组套数组的结构，但是我们对其中的任意一个数组结构下访问断点同样没有断下，所以我们看下第三个结果。
对第三个结果下访问断点后直接断下
[[esi+DC]+n*4]+m*4是一个n*m的数组，我们对esi+DC里面的第一个数组下访问断点，并在地图中访问第一行，游戏断下单步执行完这个函数后，观察下面的代码，发现这里是有两个分支的
在返回值经过一次右移3，并进行两次判断后，觉得函数返回1还是0
而我们经过多次的测试发现，当光标所在点是红色的坐标，也就是无法到达的位置时，返回值位1，如果是可达的则显示0。通过这个判断条件，我们就可以获取到整个地图的节点信息。
将地图节点数组的基地址分析出来以后，对公式进行整理如下
[[0x03E4685C]+1C]+40 X坐标最大值
[[0x03E4685C]+1C]+44 Y坐标最大值
[[[[0x03E4685C]+1C]+DC]+n*4]+m*4 地图节点数值
其中m最大值位X坐标最大值
n最大值位Y坐标最大值
((地图节点数值>>3) & 1)==0 或者（(byte)地图节点数值 and 1)==0 节点可达
其他情况不可达
当然，这里我们也可以返回外层后，通过传入坐标调CALL的方式去获得地图节点是否可达的标志
ecx来源于上面的两层CALL，其中一层是基地址，另一侧是1C偏移，内联汇编代码如下
我们任意找一个小一些的地图将可达的标志全部输出出来后，效果如下
地图原型
地图遍历
[[0x03E4685C]+1C]+40 X坐标最大值
[[0x03E4685C]+1C]+44 Y坐标最大值
[[[[0x03E4685C]+1C]+DC]+n*4]+m*4 地图节点数值
获取的数据赋值给我们的A*二维数组即可计算路径了.
然后我们通过对进行CQYH等课题学习锻炼来锻炼A*算法
七、补充
如果地图是立体的
我们可以自上而下,分层的方式存储地图.
比如四叉树,比如unity中的导航三角网.
其他算法:
蚁群算法
关于智能寻路算法的研究，A-Star算法拓展，B星寻路算法 - 大龙软件工作室 - 博客园
贪婪算法和局部搜索
算法速度很快，但是解得质量不能保证
最快速的寻路算法 Jump Point Search
最快速的寻路算法 Jump Point Search - 知乎
CH算法等
之后涌现了很多预处理算法（如CH），在线查询效率是A*算法的数千甚至上万倍。
蚁群算法、模拟退火法、神经网络、禁忌搜索、演化算法、拟人拟物算法、量子算法等很多算法都优于A*算法，
大家有兴趣可以自己搜索下
欢迎大家关注公众：任鸟飞逆向，共同学习研究更多更好的算法
转载：https://blog.csdn.net/qq_43355637/article/details/128212197