90% 还原南宫梦吃豆人

2020-5-6 ~ 2022-1-10 落幕🌻 (2)

MyPacman 作者 bridgeL

开发软件：VS2019

使用的图形库 easyx，版本 2020-1-9
使用的图片素材 /pacman2/res 来自于网络
项目 github 地址: https://github.com/bridgeL/pacman2

本文对应版本 v1.4.7

特性：迷宫；四只怪物，A*算法，差异化追逐；大力丸，用于反杀怪物；怪物会感受恐惧，四散躲避

游戏运行画面展示

核心框架概述

类图/设计流图

类关系

CMover 派生

CMonster
CPacman

CFlash 容器

CFlashGroup

CPoint 组合

CRect

多线程

游戏一开始时从资源文件载入图片素材，初始化各个对象，并设置两个独立线程：按键输入线程、定时器计数线程

按键输入线程

DWORD WINAPI keyboard_thread(PVOID)
{
	while (1)
	{
		int a = _getch();
		if (a == 224)
		{
			a = _getch();
			switch (a)
			{
			case 72: key = 'w'; break;
			case 80: key = 's'; break;
			case 75: key = 'a'; break;
			case 77: key = 'd'; break;
			}
		}
		else if (a == 13)
		{
			key = ' ';
		}
		else
		{
			key = a;
		}
	}

	return 0L;
}

小键盘的方向键输入为两个 char 字符，且第一个字符值为 224，需要特殊处理

key 为全局变量，用于存放捕获到的键值，在主循环的时候使用 key 时需要注意清空 key，防止一 key 多用

定时器计数线程

void HpSleep(int ms)
{
	static clock_t oldclock = clock();		// 静态变量，记录上一次 tick

	oldclock += ms * CLOCKS_PER_SEC / 1000;	// 更新 tick

	if (clock() > oldclock)					// 如果已经超时，无需延时
		oldclock = clock();
	else
		while (clock() < oldclock)			// 延时
			Sleep(1);						// 释放 CPU 控制权，降低 CPU 占用率
}

DWORD WINAPI time_thread(PVOID param)
{
	int fps = (int)param;
	int ms = 1000 / fps;
	while (1)
	{
		HpSleep(ms);
		update_event = 1;
		cnt1++;
	}

	return 0L;
}

控制帧率，update_event 为全局变量，在主循环使用的时候需要注意清空 update_event ，防止一 update_event 多用

页 Page

游戏被划分为三页，游戏菜单页，游戏进行页，游戏结束页（这里暂时未设计 class 来封装页，因此页仅仅是由三个函数构成的一个概念）。

主循环根据页码（全局变量），执行对应的页的函数，页函数有三类：

初始化函数
按键处理函数
帧更新函数（可缺省）

初始化函数用于初始化该页必需的变量成员，并绘制一些图片，例如游戏底图、UI 界面等不会在帧更新时频繁变动的图像

按键处理函数从按键输入缓存（全局变量）读取按键操作，并根据对应的页码修改页的变量成员，以及执行一些迫不得已的绘制操作（不建议）

帧更新函数主要用于刷新页的一些需要随时间变化的变量成员

页与页的切换通过专门的页切换函数实现，该函数负责修改页码（全局变量），并结束上一页，调用页初始化函数，开启下一页

游戏进行页 Gaming Page

游戏进行页主要负责四件事：

清除元素旧图案
更新元素位置、状态
绘制元素新图案
FlushBatchDraw();（更新帧图像）

使用 FlushBatchDraw() 的好处是显而易见的：隐藏了绘制图片的中间环节的画面，保证游戏观感良好

移动者 CMover

CMover 是游戏最主要的类，实现了迷宫中的受限移动，提供了绘制自身图像的 API（动画序列、非静图，且可以根据方向设置对应的动画序列）

通过 Move()（无检查前进），Go()（有检查前进，判断与墙的距离），Turn()（有检查转弯，并适当修正位置）实现了CMover 在迷宫中的受限移动

通过自定义的 CFlashGroup 实现了对动画序列的封装，通过自定义的 CAStar 实现了对 A* 寻路算法的封装

动画序列 CFlash 及其容器 CFlashGroup

CFlash 中存放了一组动画序列的图片，例如吃豆人向左移动的一套图（3张）

CFlashGroup 存放了多个 CFlash，例如存放吃豆人四个方向移动的动画

A*算法 CAStar

CAStar 中存放了一个结点矩阵，通过地图信息初始化这一矩阵，随后进行 A* 算法寻路，为怪物提供追逐的方向

参考资料 https://blog.csdn.net/m0_37290785/article/details/93203624

对 A star 的实现做了一定的优化：

取消 close_list，直接使用哈希表存储节点是否关闭，大大提高了 A star 的计算速度

在初始化节点网络时计算并存储各个节点的距离代价（H值），为后来计算总代价（F值）提供方便

核心代码展示

CMover 的实现

//zh_CN.GBK
#pragma once
// 此文档主要定义了 mover类，以及其派生的 monster类

#include "define.h"
#include "flash.h"
#include "astar.h"

// 引用该库才能使用 TransparentBlt 函数
#pragma comment( lib, "MSIMG32.LIB")

class CMover
{
protected:
	IMAGE* p_background;		// 背景图片的指针
	IMAGE back;					// 为了加快clear的速度，设置back成员储存每次的背景图
	CFlashGroup faces;	// 各方向动画序列的容器

	CRect rect;					// 当前的位置

	CPoint burn;				// 出生地点

	int* map;					// 地图的指针

	double speed;
	double speed_d;

	int new_dir;				// 新的运动方向，加入此属性是为了改善游戏手感
	int dir;					// 运动方向


public:
	CMover() :p_background(NULL), map(NULL), speed(0), speed_d(0), new_dir(DIR_NONE), dir(DIR_NONE) 
	{
		faces = CFlashGroup(EAT_FLASH_TIME);
	}

	// 将初始化分解为一系列函数,请按照顺序执行
	void init_speed(double s)
	{
		// 设置速度
		speed = s;
	}

	void init_map(int* m)
	{
		// 设置地图地址
		map = m;
	}

	void init_rect(CRect r)
	{
		// 设置当前位置
		rect = r;
		burn = rect.site;
	}

	void init_img(IMAGE* p_back, IMAGE* p_face, int r, int c)
	{
		// 设置背景图指针
		p_background = p_back;

		// 根据图片生成四个方向的动画序列
		int h = rect.shape.x;
		int w = rect.shape.y;

		SetWorkingImage(p_face);

		for (int i = 0; i < r; i++)
		{
			CFlash flash;
			for (int j = 0; j < c; j++)
			{
				IMAGE face;
				int x = i * h;
				int y = j * w;
				getimage(&face, y, x, w, h);
				flash.Add(face);
			}
			faces.Add(flash);
		}

		SetWorkingImage(NULL);
	}

	void Reset()
	{
		rect.site = burn;
		dir = DIR_NONE;
		new_dir = DIR_NONE;
	}

	// 设置/读取 当前位置的左上角坐标
	CPoint GetSite() { return rect.site; }

	// 读取 当前位置的中心点坐标
	CPoint GetCenter()
	{
		CPoint center;
		center.x = rect.site.x + rect.shape.x / 2;
		center.y = rect.site.y + rect.shape.y / 2;
		return center;
	};

	void SetFlash(int d)
	{
		switch (d)
		{
		case DIR_DOWN:  faces.SetIdx(3);  break;
		case DIR_UP:	faces.SetIdx(2);  break;
		case DIR_RIGHT: faces.SetIdx(0);  break;
		case DIR_LEFT:	faces.SetIdx(1);  break;
		}
	}

	void Move(double ss)
	{
		int s = (int)ss;
		speed_d += (ss - s);
		if (speed_d >= 1)
		{
			s++;
			speed_d--;
		}

		switch (dir)
		{
		case DIR_DOWN:  rect.site.x += s; break;	// 下
		case DIR_RIGHT: rect.site.y += s; break;	// 右
		case DIR_UP:	rect.site.x -= s; break;	// 上
		case DIR_LEFT:	rect.site.y -= s; break;	// 左
		}
	}

	void SetNewDir(int d)
	{
		new_dir = d;
	}

	void GetNearCross(int& dx, int& dy, int& i, int& j)
	{
		CPoint c = GetCenter();

		// 距离最靠近的格点的距离
		dx = (c.x + BLOCK_SIZE / 2) % BLOCK_SIZE - BLOCK_SIZE / 2;
		dy = (c.y + BLOCK_SIZE / 2) % BLOCK_SIZE - BLOCK_SIZE / 2;

		int x = c.x - dx;
		int y = c.y - dy;

		i = x / BLOCK_SIZE;
		j = y / BLOCK_SIZE;
	}

	bool Turn()
	{
		// 转向判定
		// 我们要求吃豆人像火车一样，总是位于固定的轨道上，不能自由移动到随意的坐标，
		// 因此在转向的时候，需要进行严格的审查


		// 是否有转向，
			// 是否在转弯容限内，
				// 转弯后是否撞墙
					// 均通过则正确转弯，按新方向前进，并更新动画序列
				// 撞墙了，不许转弯，按旧方向前进
			// 不在转弯容县内，不许转弯，按旧方向前进
		// 没有转向，按旧方向前进

		if (new_dir == DIR_NONE)
		{
			dir = DIR_NONE;
			return 1;
		}
		else if (abs(new_dir) != abs(dir) )	// 是否有转向
		{
			// 转弯限制
			const int t = MOVE_TOLERENCE;	// 宽容门限

			int dx, dy, i, j;
			GetNearCross(dx, dy, i, j);

			bool turn_flag = 0;

			if ((abs(new_dir) == 2 && abs(dx) < t) || (abs(new_dir) == 1 && abs(dy) < t))
				turn_flag = 1;

			if (turn_flag)		// 是否在转弯容限内
			{
				// 下一个格点
				switch (new_dir)
				{
				case DIR_DOWN:  i++;  break;
				case DIR_UP:	i--;  break;
				case DIR_RIGHT: j++;  break;
				case DIR_LEFT:	j--;  break;
				}

				bool edge_flag = 0;
				if (j < 0 || j >= MAP_COLUMN)
					edge_flag = 1;

				if (!edge_flag)	// 是否在边界
				{
					bool wall_flag = 0;

					if (map[i * MAP_COLUMN + j] == 3)
						wall_flag = 1;

					if (!wall_flag)	// 转弯后是否撞墙
					{
						// 方向赋值，并修改动画

						dir = new_dir;	

						// 坐标修正
						rect.site.x -= dx;
						rect.site.y -= dy;

						return 1;
					}
					else
					{
						return 0;
					}

				}
				else	// 如果超过边界，不许转弯
				{
					return 0;
				}

			}
			else	// 转弯后撞墙，不许转弯
			{
				return 0;
			}

		}
		else	// 可能是掉头或者从DIR_NONE起步
		{
			dir = new_dir;
			return 1;
		}
	}

	bool Go()
	{
		// 计算离自己最近的节点，并知道自己与此节点的相对位置
		// 根据 移动方向 和 与节点的相对位置, 下一个节点的坐标
		// 计算自己与下一个节点的距离
		// 判断三种状态
			// 不会撞到/不是墙
			// 会撞到，但仍然有一定距离
			// 已经撞到了，没有距离

		int dx, dy, i, j;
		GetNearCross(dx, dy, i, j);

		switch (dir)
		{
		case DIR_DOWN:  if (dx >= 0) i++; break;	// 下
		case DIR_RIGHT: if (dy >= 0) j++; break;	// 右
		case DIR_UP:	if (dx <= 0) i--; break;	// 上
		case DIR_LEFT:	if (dy <= 0) j--; break;	// 左
		}

		// 如果超过边界，就不进行撞墙检查
		if (j < 0 || j >= MAP_COLUMN)
		{
			// 移动
			Move(speed);

			if (rect.site.y < 0)
				rect.site.y += GAME_WIDTH;
			else if (rect.site.y >= GAME_WIDTH)
				rect.site.y -= GAME_WIDTH;

			return 1;
		}


		int s = (int)speed;	// 移动距离

		if (map[i * MAP_COLUMN + j] == 3)	// 墙
		{
			const int t = BLOCK_SIZE - PERSON_SIZE / 2;	// 墙壁的厚度

			// 计算与墙的距离
			int instance = (int)speed;

			switch (dir)
			{
			case DIR_DOWN:  instance = (i * BLOCK_SIZE - t) - (rect.site.x + rect.shape.x);	break;
			case DIR_RIGHT: instance = (j * BLOCK_SIZE - t) - (rect.site.y + rect.shape.y); break;
			case DIR_UP:	instance = (rect.site.x) - (i * BLOCK_SIZE + t);				break;
			case DIR_LEFT:	instance = (rect.site.y) - (j * BLOCK_SIZE + t);				break;
			}

			
			if (instance == 0)
			{
				return 0;
			}

			s = instance;
		}

		// 移动
		Move(s);

		return 1;
	}

	void Update()
	{
		faces.Update();

		// 转向
		if (Turn())
			SetFlash(dir);

		// 前进
		Go();
	}

private:
	// 透明贴图函数
	// 参数：
	//		dstimg: 目标 IMAGE 对象指针。NULL 表示默认窗体
	//		x, y:	目标贴图位置
	//		srcimg: 源 IMAGE 对象指针。NULL 表示默认窗体
	//		transparentcolor: 透明色。srcimg 的该颜色并不会复制到 dstimg 上，从而实现透明贴图
	void transparentimage(IMAGE* dstimg, int x, int y, IMAGE* srcimg, UINT transparentcolor)
	{
		HDC dstDC = GetImageHDC(dstimg);
		HDC srcDC = GetImageHDC(srcimg);
		int w = srcimg->getwidth();
		int h = srcimg->getheight();

		// 使用 Windows GDI 函数实现透明位图
		TransparentBlt(dstDC, x, y, w, h, srcDC, 0, 0, w, h, transparentcolor);
	}

public:
	void Draw()
	{
		// 为了美观，
		// 绘图坐标draw 和 实际坐标site 之间存在固定偏差 bias = BLOCK_SIZE / 2
		// center = site + shape / 2
		// draw = center + bias - shape / 2 
		//      = site + bias
		transparentimage(NULL, rect.site.y + BLOCK_SIZE / 2, rect.site.x + BLOCK_SIZE / 2, &faces.GetImage(), BLACK);
		//putimage(rect.site.y + BLOCK_SIZE / 2, rect.site.x + BLOCK_SIZE / 2, &faces.GetImage());
	}

	void Clear()
	{
		SetWorkingImage(p_background);
		getimage(&back, rect.site.y + BLOCK_SIZE / 2, rect.site.x + BLOCK_SIZE / 2, rect.shape.y, rect.shape.x);

		SetWorkingImage(NULL);
		putimage(rect.site.y + BLOCK_SIZE / 2, rect.site.x + BLOCK_SIZE / 2, &back);
	}

	int GetDir() { return dir; }

};

CAStar 的实现

//zh_CN.GBK
#pragma once
#include "define.h"

class CAStarNode
{
public:
	int father;
	int G;
	int H;
	bool close;
	bool open;

	CAStarNode() : father(0), G(0), H(0), close(0), open(0) {}
};


class CAStar
{
private:
	CAStarNode ns[MAP_CNT];	// 点集

	vector<int> open_list;		// 开放列表
	//list<int> close_list;		// 关闭列表 // 二维地图关闭列表的大小成n^2增长，遍历耗时极高，因此使用分布式存储，直接访问结果
								// 而开放列表的数量级较小，可以使用list形式，耗时不是很多

	int s;	// 开始结点（怪物）
	int e;	// 结束结点（玩家）

	int w_inst;	// 距离权重，此值越大，monster越注重距离控制
	int w_path;	// 路径权重，此值越大，monster越注重短路径

	COLORREF color;
	bool path_show;
	int cnt;

public:
	CAStar() :s(0), e(0), w_inst(1), w_path(1), path_show(0), color(RED), cnt(0) {}

	void SwitchPathShow(COLORREF c)
	{
		if (path_show)
			path_show = 0;
		else
			path_show = 1;

		color = c;
	}

	void SetStyle(int instance, int path)
	{
		w_inst = instance;
		w_path = path;
	}

	// 初始化
	void init(int* map, CPoint sp, CPoint ep)
	{
		open_list.clear();
		//close_list.clear();
		
		e = ep.x * MAP_COLUMN + ep.y;
		s = sp.x * MAP_COLUMN + sp.y;

		for (int i = 0; i < MAP_CNT; i++)
		{
			//if (map[i] == 3)
				//close_list.push_back(i);
			ns[i].close = (map[i] == 3) ? 1 : 0;
			ns[i].open = 0;
			ns[i].G = 0;
			
			int dk = abs(i - e);
			ns[i].H = (dk / MAP_COLUMN + dk % MAP_COLUMN) * w_inst;

			ns[i].father = 0;
		}
	}

	int FindMinF()
	{
		int i_min = 0;
		int k_min = 0;
		int F_min = 1000000;

		int n = open_list.size();
		for (int i = 0; i < n; i++)
		{
			int k = open_list[i];
			int F = ns[k].G + ns[k].H;
			if (F < F_min)
			{
				F_min = F;
				k_min = k;
				i_min = i;
			}
		}

		if (k_min != 0)
		{
			open_list[i_min] = open_list[n - 1];
			open_list.pop_back();
		}

		return k_min;
	}

	void BuildAWay()
	{
		open_list.push_back(s); // 添加第一个结点
		ns[s].open = 1;

		int k_current = s;	// 设置起点

		while (1)
		{
			if (k_current == e)
				break;

			if (open_list.size() == 0)
				break;

			// 查询下一个结点
			k_current = FindMinF();
			ns[k_current].close = 1;


			// 搜寻周围结点
			for (int i = 0; i < 4; i++)
			{
				int ni = k_current / MAP_COLUMN;
				int nj = k_current % MAP_COLUMN;

				switch (i)
				{
				case 0: ni--; break;
				case 1: ni++; break;
				case 2: nj--; break;
				case 3: nj++; break;
				}

				if (ni < 0 || ni >= MAP_ROW || nj < 0 || nj >= MAP_COLUMN)
					continue;

				int k_next = ni * MAP_COLUMN + nj;

				if (!ns[k_next].close)			// 没加入close （ 墙，或者探查完毕的结点 ）
				{
					int G_old = ns[k_next].G;
					int G_new = ns[k_current].G + w_path;

					if (ns[k_next].open)		// 已经加入了open
					{
						// 优化路径
						if (G_old > G_new )	
						{
							ns[k_next].G = G_new;
							ns[k_next].father = k_current;
						}
					}
					else
					{
						ns[k_next].G = G_new;
						ns[k_next].father = k_current;

						open_list.push_back(k_next);			// 添加进open_list
						ns[k_next].open = 1;
					}
				}

			}
		}
	}


	// 获得方向
	int GetDir()
	{
		if (path_show)
		{
			cnt++;
			if (cnt > 5)
				cnt = 0;

			if (cnt == 0)
				setlinecolor(BLACK);
			else
				setlinecolor(color);
		}
		

		int k[2] = { 0 };
		
		k[0] = e;

		while (1)
		{
			k[1] = ns[k[0]].father;

			if (k[1] == 0 || k[1] == s)
				break;


			if (path_show)
			{
				int xi = k[0] / MAP_COLUMN * BLOCK_SIZE + BLOCK_SIZE / 2;
				int xj = k[0] % MAP_COLUMN * BLOCK_SIZE + BLOCK_SIZE / 2;
				int yi = k[1] / MAP_COLUMN * BLOCK_SIZE + BLOCK_SIZE / 2;
				int yj = k[1] % MAP_COLUMN * BLOCK_SIZE + BLOCK_SIZE / 2;
				line(xj, xi, yj, yi);
			}


			k[0] = k[1];
	
		}

		if (k[0] - k[1] == MAP_COLUMN)	return DIR_DOWN;
		if (k[0] - k[1] == -MAP_COLUMN)	return DIR_UP;
		if (k[0] - k[1] == -1)			return DIR_LEFT;
		if (k[0] - k[1] == 1)			return DIR_RIGHT;

		return DIR_NONE;
	}



};

/**/

CMonster 的智能躲避

// 可供预先选择的避难点 42个
const static int safe_row[7] = { 1,5,8,18,20,23,25 };
const static int safe_column[6] = { 1,5,9,11,15,19 };

// 吃豆人所在的位置需要避免被选定为避难点
int danger_row_idx = 0;
for (int i = 0; i < 6; i++)
	if (safe_row[i] < pi && pi < safe_row[i + 1])
	{
		danger_row_idx = i;
		break;
	}

int danger_column_idx = 0;
for (int i = 0; i < 5; i++)
	if (safe_column[i] < pj && pj < safe_column[i + 1])
	{
		danger_column_idx = i;
		break;
	}


// 当已经到达避难点，或第一次确定避难点，或吃豆人来到避难点附近时，计算新避难点的坐标
if ((escape_rc.x == mi && escape_rc.y == mj ) || (escape_rc.x == 0 && escape_rc.y == 0) 
	||(abs(escape_rc.x - pi) <= 10 && abs(escape_rc.y- pj) <= 5))
{
	
	// 避开危险的吃豆人选择避难点
	while (1)
	{
		int r = rand() % 7;
		if (abs(r - danger_row_idx) > 1)
		{
			escape_rc.x = safe_row[r];
			break;
		}
	}

	while (1)
	{
		int c = rand() % 6;
		if (abs(c - danger_column_idx) > 1)
		{
			escape_rc.y = safe_column[c];
			break;
		}
	}
	//cout << "escape_rc = (" << escape_rc.x << "," << escape_rc.y << ")\n";
}


// A* 算法，计算移动方向
brain.init(map, CPoint(mi, mj), CPoint(escape_rc.x, escape_rc.y));

// 将吃豆人附近的地段关闭，实现绕路的特性
if (abs(mi - pi) <= 4 && abs(mj - pj) <= 3)
{
	// 离吃豆人较近时关闭较小的地段，防止把自己也关进去
	for (int i = -1; i < 2; i++)
	{
		for (int j = -1; j < 2; j++)
		{
			brain.SetNodeWall(pi + i, pj + j);
		}
	}
}
else
{
	for (int i = -3; i < 4; i++)
	{
		for (int j = -2; j < 3; j++)
		{
			brain.SetNodeWall(pi + i, pj + j);
		}
	}
}

// 构建一条逃避的路径
brain.BuildAWay();

// 获取当前逃避的方向
int dir = brain.GetDir();
SetNewDir(dir);

// 转向
if (Turn())
	SetFlash(dir);

// 前进
Go();

全部代码下载

项目github地址: https://github.com/bridgeL/pacman2

文档内容

mover.h

CMover
CMonster
CPacman

flash.h

CFlash
CFlashGroup

define.h

各类宏定义
CPoint
CRect

astar.h

实现 a* 寻路算法

game.h/game.cpp

存放各个游戏页的初始化、处理、更新函数
键盘输入捕获线程
定时器线程（控制帧率）

app.cpp

游戏主循环

bridgeL