之前做过二维平面,基于网格的A*算法,地图采用硬编码的方式,用一个二维数组存下来整个地图的情况。
现在因为项目原因,需要升维到三维空间的寻路算法,如果还使用硬编码的方式将三维空间的场景保存下来,确实太不友好了....!!!所以现在考虑使用图的有关知识来实现A*算法。
1、三维空间寻路,有哪些可能的方向呢?在二维平面,一个点可能向周围8个点移动,但是在三维空间,变成了26个点。可以想象以下三阶魔方,就是那个样子。所以需要现将26个方向进行一个记录。
typedef typename std::tuple Point;
// 想象魔方
std::set directions =
{
// 平面的8个点
Point(0, 1, 0), //North 正上
Point(1, 1, 0), //NorthEast
Point(1, 0, 0), //East 正右
Point(1, -1, 0), //SouthEast
Point(0, -1, 0), //South 正下
Point(-1, -1, 0), //SouthWest
Point(-1, 0, 0), //West 正左
Point(-1, 1, 0), //NorthWest
// 按左手坐标系
// 后面的9个点
Point(0, 0, 1), //UpMiddle 正后
Point(0, 1, 1), //UpNorth
Point(1, 1, 1), //UpNorthEast
Point(1, 0, 1), //UpEast
Point(1, -1, 1), //UpSouthEast
Point(0, -1, 1), //UpSouth
Point(-1, -1, 1), //UpSouthWest
Point(-1, 0, 1), //UpWest
Point(-1, 1, 1), //UpNorthWest
//前面的9个点
Point(0, 0, -1), //DownMiddle
Point(0, 1, -1), //DownNorth
Point(1, 1, -1), //DownNorthEast
Point(1, 0, -1), //DownEast
Point(1, -1, -1), //DownSouthEast
Point(0, -1, -1), //DownSouth
Point(-1, -1, -1), //DownSouthWest
Point(-1, 0, -1), //DownWest
Point(-1, 1, -1), //DownNorthWest
};
2、如何描述图呢?
图的数据结构就不复习了,要有顶点,和边。
对于顶点的定义,需要描述该点的id、位置、以及g h f值。(GVertex是为了和DirectX中的Vertex区分开)
//定义图中的节点
struct GVertex
{
GVertex() {};
GVertex(int id) :id{ id }
{
this->cost_g = 1;
this->cost_h = 0;
this->cost_f = cost_g + cost_h;
this->coord = Point(0, 0, 0);
}
…… //其他构造函数
int id;
double cost_g = 0;
double cost_h = 0;
double cost_f = 0;
Point coord;
void calc_f(double g, double h) { this->cost_f = g + h; }
};
对于边的描述,记录其id和权重即可。
//定义图中的边
struct Edge
{
Edge() {};
…… //其他构造函数
int id;
double edge_weight;
};
最后,就可以定义Graph类。
class Graph
{
public:
Graph() {};
//图中的节点
std::unordered_map> vertex_map;
//图中的边
std::unordered_map> edge_map;
// 邻接表 <节点的id,vector<边的id,邻接点id> >
std::unordered_map> > adjacency_map;
std::vector sources; //起点
std::vector destinations; //终点
//获取一些参数
……
// 获取坐标分量
……
// 获取和设置f,g,h值
……
// 插入节点,插入边,插入邻接关系
……
private:
};
(未完待续...)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)