之前做过二维平面，基于网格的A*算法，地图采用硬编码的方式，用一个二维数组存下来整个地图的情况。
现在因为项目原因，需要升维到三维空间的寻路算法，如果还使用硬编码的方式将三维空间的场景保存下来，确实太不友好了....！！！所以现在考虑使用图的有关知识来实现A*算法。
1、三维空间寻路，有哪些可能的方向呢？
在二维平面，一个点可能向周围8个点移动，但是在三维空间，变成了26个点。可以想象以下三阶魔方，就是那个样子。所以需要现将26个方向进行一个记录。
typedef typename std::tuple<double, double, double> Point;
// 想象魔方
std::set<Point> 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() {};
//图中的节点<id,GVertex>
std::unordered_map<int, std::shared_ptr<GVertex>> vertex_map;
//图中的边<id,Edge>
std::unordered_map<int, std::shared_ptr<Edge>> edge_map;
// 邻接表 <节点的id，vector<边的id，邻接点id> >
std::unordered_map<int, std::vector<std::pair<int, int>> > adjacency_map;
std::vector<int> sources; //起点
std::vector<int> destinations; //终点
//获取一些参数
……
// 获取坐标分量
……
// 获取和设置f,g,h值
……
// 插入节点，插入边，插入邻接关系
……
private:
};
（未完待续...）
