A*算法在三维空间实现C++(1)——图的相关定义

A*算法在三维空间实现C++(1)——图的相关定义,第1张

之前做过二维平面,基于网格的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:

};

(未完待续...)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/785924.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-04
下一篇 2022-05-04

发表评论

登录后才能评论

评论列表(0条)

保存