C++A星寻路的实现

前言

本文主要讲的A星寻路的代码实现，对A星寻路有一定的了解后再来阅读本文是个不错的选择。
本文还用到了图形库，编译器为vs2019。图形库没有的可以去官方网站下载，步骤很简单下载直接安装即可。

A星寻路的流程
1.准备存储的路径和终点标志位。
2.将起点放入closeList
3.将起点周围的格子放入openlist
4.寻找最小和值F和终点
5.找到后将它存入closelist同时将它从openlist中剔除
6.从终点标志位开始往父亲节点遍历，存入路径中。
7.输出路径。
剩下的解释全在代码注释中。

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include<vector>
#include<easyx.h>
#include<list>
#include"AStart.h"
#include"Level.h"
#include"Draw.h"
using namespace std;
class LevelMap:public Level
{
public:
	vector<vector<int>> level;
	// 通过 Level 继承
	virtual bool isValid(Pos v) override
	{
		return !((v.x<0||v.y<0)||
			v.x> level[v.x].size()||v.y> level.size()||
			level[v.y][v.x]==1);
	}
};
void test()
{
	vector < vector<int>> vec = {//15*15
		{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//▶x 
		{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
		{1,0,0,0,0,0,1,1,1,0,0,0,0,0,1},
		{1,0,1,1,1,1,0,1,0,1,0,0,0,0,1},
		{1,0,1,0,1,0,1,0,1,0,0,0,0,0,1},
		{1,0,1,1,1,0,1,1,1,0,0,0,0,0,1},
		{1,0,0,0,0,0,1,0,1,0,0,0,0,0,1},
		{1,0,0,0,0,0,1,1,1,0,0,0,0,0,1},
		{1,0,0,1,1,1,1,1,0,0,0,0,0,0,1},
		{1,0,0,0,1,1,0,1,0,0,0,0,0,0,1},
		{1,0,0,1,0,1,1,0,0,0,0,0,0,0,1},
		{1,0,0,0,0,1,0,0,0,0,0,0,0,0,1},
		{1,0,0,1,0,1,0,1,0,0,0,0,0,0,1},
		{1,0,1,0,1,1,0,1,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
		//▼y
	};
	LevelMap lm;
	lm.level = vec;
	AStart a(lm);
	Draw draw(600, vec);
	draw.update();
	list<Pos> path;
	Pos start{ -1,-1 };
	Pos end{ -1,-1 };
	int x;//从鼠标的位置转换到
	int y;//贴图需要更改的位置
	bool flag=false;//起点和终点的标志位
	while (true)
	{
		draw.level = lm.level;
		draw.update();
		while (true)
		{
			MOUSEMSG msg = GetMouseMsg();
			x = msg.x / draw.getSize();
			y = msg.y / draw.getSize();
			if (msg.uMsg == WM_RBUTTONDOWN)//右键按下，路变墙，墙变路。
			{
				lm.level[y][x] = draw.level[y][x] =
					draw.level[y][x] == Draw::road ? Draw::wall : Draw::road;
				draw.update();
			}
			if (msg.uMsg == WM_LBUTTONDOWN)//左键按下设置起点终点准备寻路。
			{//这里不能将lm.level改变，需要还原用。
				if (!flag && draw.level[y][x] == Draw::road)
				{
					start.x = x;
					start.y = y;
					draw.level[y][x] = Draw::visit;
					flag = true;
					draw.update();
				}
				else if (draw.level[y][x] == Draw::road)
				{
					end.x = x;
					end.y = y;
					draw.level[y][x] = Draw::end;
					path = a.find(start, end);
					flag = false;
					draw.update();
					break;
				}
			}

		}
		for (const auto& e : path)
		{
			draw.level[e.y][e.x] = Draw::visit;
			draw.update();
		}
	}
}
int main()
{
	test();
	return 0;
}

Level.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#pragma once
struct Pos
{
	int x;
	int y;
	Pos(int x = 0, int y = 0):x(x),y(y){}
};
class Level
{
public:
	//外部规则
	virtual bool isValid(Pos v) = 0;
};

Draw.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#pragma once
#include <vector>

//取别名
using Vec2r = std::vector<std::vector<int>>;

//绘制地图的类
class Draw
{
public:
  /*使用图形库的接口实现地图绘制
   *length  屏幕长度
    level   地图关卡
   */
  Draw(int length, Vec2r& level);
  ~Draw();
  /*
  0 路
  1 墙
  2 走过的路径
  3 终点
  */
  enum {
	road=0,
	wall,
	visit,
	end,
  }; 
  Vec2r level;   //绘制的地图上

  //地图更新函数
  void update();

  //获取瓦片大小
  int getSize();

protected:

  int length;			    //宽度和高度
  int size;				    //每个瓦片的大小
  void draw();              //绘制地图
  void text();              //绘制文本
  void rect(int x,int y);   //绘制瓦片

};

Draw.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "Draw.h"
#include <easyx.h>		//图形库文件
#include <string>
#include <iostream>
using namespace std;

Draw::Draw(int length, Vec2r& level)
  :length(length)
{
  initgraph(length, length, EW_SHOWCONSOLE);		//初始化图形库,EW_SHOWCONSOLE表示显示控制台
  size = length / level.size();					//动态计算小方块的宽度
  this->level=level;							//从外部传入地图
}

Draw::~Draw()
{
  closegraph();
}

void Draw::update()
{
  draw();
  text();
}

int Draw::getSize()
{
  return size;
}

void Draw::draw()
{
  BeginBatchDraw();//开始批量画图
  cleardevice();
  for (size_t i = 0; i < level.size(); i++)//level.size()等于7，
  {
	for (size_t j = 0; j < level[i].size(); j++)//level[i].size()等于7,这里不懂是因为二维vector没理解透。
	{
	  if (level[i][j] == road)//路
	  {
		setfillcolor(RGB(0xdd, 0xdd, 0xdd)); //设置路的颜色
	  }
	  else  if (level[i][j] == wall){  //墙
		setfillcolor(RGB(0x33, 0x33, 0xcc));
	  }
	  else  if (level[i][j] == visit) {	  //走过的路
		setfillcolor(RGB(0x33, 0xcc, 0x33));
	  }
	  else  if (level[i][j] == end) {	  //终点
		setfillcolor(RGB(0xff, 0x33, 0x33));
	  }
	  rect(j, i);	//绘制瓦片，j代表x  i代表y.
	}
  }
  EndBatchDraw();//结束批量画图
}
//绘制瓦片
void Draw::rect(int x, int y) 
{
	fillrectangle(x * size, y * size, (x + 1) * size, (y + 1) * size);
	/*void fillrectangle(
	int left,
	int top,
	int right,
	int bottom
);*/
}

void Draw::text()
{
  string m;
  for (size_t i = 0; i < level.size(); i++)
  {
	for (size_t j = 0; j < level[i].size(); j++)
	{
	  if (level[i][j] == road)//路
	  {
		m += "  "; //设置路的颜色
	  } 
	  else  if (level[i][j] == wall) 
	  {  //墙
		m += "+ ";
	  } 
	  else  if (level[i][j] == visit) 
	  {	  //走过的路
		m += ". ";
	  } 
	  else  if (level[i][j] == end) 
	  {	  //终点
		m += "= ";
	  }
	}
	m += "\n";
  }
  system("cls");	  //调用命令清屏
  cout << m << endl;
}

Astart.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#pragma once
#include "Level.h"
#include<list>
class Node
{
public:
	Pos v;//节点坐标
	int G;//从起点到当前位置的代价；
	int H;//从当前位置到终点的预估代价；
	Node* pre;//树的父亲节点
	int getF() { return G + H; }//代价和值
	Node(Pos v, int G, int H, Node* pre = nullptr) :v(v), G(G), H(H), pre(pre) {}
};
class AStart 
{
public:
	AStart(Level& level) :level(level) {}//多态不能用基类实例化对象这里的引用不能掉
	std::list<Pos> find(Pos start, Pos end);
private:
	Level& level;//多态
	Pos end;//保存终点坐标
	std::list<Node*> openLsit;//准备要走的路但是没有走；
	std::list<Node*> closeList;//走过的路，正在走的路；
	void addRound(Node* now);//将节点周围的节点加入openlist
	int getH(Pos now);//获取节点位置与终点的预估距离
	bool check(Pos v);//检查该坐标能不能加入openlist
	bool findList(Pos v);//检查该坐标是否在openlist或者closelist中
	void destory();//释放内存。
};

Astart.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include "AStart.h"
#include<algorithm>
std::list<Pos> AStart::find(Pos start, Pos end)
{
    this->end = end;
    std::list<Pos> path;
    closeList.push_back(new Node(start, 0, getH(start)));
    Node* endNode = nullptr;//终点到达标志位,同时为遍历父亲节点做准备
    
    size_t length = 0;//做循环的判断条件用的
    while (length < closeList.size()&&!endNode)
    {
        length = closeList.size();
        addRound(closeList.back());
        
        //找到openList里面和值最小的node
        auto it = openLsit.begin();//默认最小的是openList的第一个元素，如果找到了就将其替换。
        for (auto i = openLsit.begin(); i != openLsit.end(); i++)
        {
            //判断是否到达终点
            if ((*i)->v.x == end.x && (*i)->v.y == end.y)
            {
                endNode=*i;
                break;
            }
            //找到最小的和值F
            if ((*it)->getF() > (*i)->getF())
            {
                it = i;
            }
        }
        //将找到的最小和值F的节点放入closeList中,同时需要将此节点从openlist中剔除；
        if (it != openLsit.end())
        {
            closeList.push_back((*it));
            openLsit.erase(it);
        }
        //break后将路径从终点往父亲节点遍历，逐个插入到path的头部，实现正序输出。
    }
    if (endNode)
    {
        while (endNode)
        {
            path.push_front(endNode->v);
            endNode = endNode->pre;
        }
    }
    //最后内存的清理
    destory();
    return path;
}

int AStart::getH(Pos now)
{
    return std::abs(now.x-end.x)+std::abs(now.y-end.y);
}

bool AStart::check(Pos v)
{
    if (level.isValid(v) && !findList(v))
        return true;
    return false;
}

bool AStart::findList(Pos v)
{
    for (const auto& e : openLsit)
    {
        if (e->v.x == v.x && e->v.y == v.y)
        {
            return true;
        }
    }
    for (const auto& e : closeList)
    {
        if (e->v.x == v.x && e->v.y == v.y)
        {
            return true;
        }
    }
    return false;
}

void AStart::destory()
{
    for (auto e : openLsit)
        delete e;
    for (auto e : closeList)
        delete e;
    openLsit.clear();
    closeList.clear();
}


void AStart::addRound(Node* now)
{
    static Pos dir[]//使用花括号直接初始化不能有强转否则会报错
    {
        {0,1},//下
        {1,0},//右
        {0,-1},//上
        {-1,0}//左
    };
    for (auto e : dir)
    {
        e = { now->v.x + e.x,now->v.y + e.y };
        if (check(e))
        {
            openLsit.push_back(new Node(e, now->G + 1, getH(e), now));
        }
    }
}

测试结果

在这里插入图片描述

最近有小伙伴需要这整个工程，来满足一下大家。

A星寻路工程，vs2019，0积分下载

C++
C++A星寻路的实现
https://howl144.github.io/2021/02/07/00002. C++A星寻路的实现/
Author
Deng Ye
Posted on
February 7, 2021
Licensed under