Xiaoxia[PG] Yesterday is history, tomorrow is mistery, today is a gift!

用C++和libSDL开发游戏系列(3) – 简单A*算法寻径

游戏中经常会用到寻径算法，最简单的寻径算法就是走直线或者总是往最接近目的地的方向走，遇到障碍物就不可以继续前进。这样虽然得到的路线一定是最短的，但是一旦碰到障碍物就被卡住了，显然不够灵活。BFS、A*是最常见的路径寻找算法。BFS算法从起始点一直向周围辐射扩张盲目地寻找目的地，虽然找到的路径一定是最短路，但是效率不高。A*算法加入了对每个发现了的位置的评估，选择与目的地接近的方向搜索，比较灵活，效率也很高。

A*算法是改进的BFS（宽度优先搜索）算法，区别在于A*算法在搜索下一个点的时候，会在等待搜索的点中寻找一个最优的。这里最优的意味着，最容易到达目的地。最简单的一个评估方法是，看当前位置到目的地还有多远。

设f(x, y)为对位置(x, y)的评估函数，g(x, y)为从起始点到当前点所经过的路程，h(x, y)为从当前点到目的地还需要的大概路程。则f的表达式可以为f(x, y) = g(x, y) + h(x, y)

以下面这个地图为例，比较BFS和A*的差异。

19 33
 ###############################
 #                       #     #
 #                       #     #
 #                       #  @  #
 #                       #     #
 #                       #     #
 #     #     #######     ### ###
 #     #     #           #     #
 #     #     #           #     #
 #     #     #        x  #     #
 #     #     #           #     #
 #     #     #           #     #
 #     #     #######     #     #
 #                             #
 #                             #
 #                             #
 #                             #
 #                             #
 ###############################

地图中，#表示障碍物，x表示起始位置，@表示终点，.表示搜索过的位置，*表示最终找到的路径。
假设地图上的怪物只可以上下左右四个方向移动。

用C++和libSDL开发游戏系列(2) – 使用SDL_mixer播放音乐和音效

SDL_mixer的用法很简单，它可以帮助你在你使用了SDL的项目中播放音频文件，包括
项目网址是：http://www.libsdl.org/projects/SDL_mixer/

这里有SDL_mixer的API说明，很详细，而且用法很简单，看了代码你就知道了！
http://www.libsdl.org/projects/SDL_mixer/docs/SDL_mixer_frame.html

编译选项：
g++ -lmingw32 -lSDLmain SDL_mixer.dll -lSDL main.cpp

随手写的一坨代码：

#include <stdio.h>
#include <SDL/SDL.h>
#include <SDL/SDL_mixer.h>

int main(int argc, char **argv)
{
	/* 初始化SDL */
	SDL_Init(SDL_INIT_AUDIO);
	/* 在使用SDL_mixer前进行初始化 */
	int ret = Mix_Init(MIX_INIT_MP3);
	if(ret & MIX_INIT_MP3 != MIX_INIT_MP3){
		perror("failed to initialize mp3 module.");
		exit(1);
	}

	/* 设置音频格式，使用44100的cd格式即可 */
	if(Mix_OpenAudio(44100, MIX_DEFAULT_FORMAT, 2, 1024)==-1) {
		fprintf(stderr, "Mix_OpenAudio: %s\n", Mix_GetError());
		exit(2);
	}

	/* 加载一个wav音频文件 */
	Mix_Chunk* wav = Mix_LoadWAV("./heal.wav");
	if(wav == NULL){
		fprintf(stderr, "Mix_LoadWAV: %s\n", Mix_GetError());
		exit(1);
	}
	/* 播放音频文件，第三个参数是循环次数这里设置为0表示播放一次，1表示播放两次，-1表示无穷次
	 * 第一个参数是音频轨道，轨道数目可以通过Mix_AllocateChannels函数来改变，-1表示随机选择一个空闲的轨道 */
	Mix_PlayChannel(-1, wav, 0);

	/* 加载一首MP3吧！ */
	Mix_Music* mp3 = Mix_LoadMUS("./music.mp3");
	if(mp3 == NULL){
		fprintf(stderr, "Mix_LoadMUS: %s\n", Mix_GetError());
		exit(1);
	}
	/* 播放一次 */
	Mix_PlayMusic(mp3, 1);
	/* 等待播放结束 */
	while(Mix_PlayingMusic())
		_sleep(1000);

	/* 资源回收处理 */
	Mix_CloseAudio();
	Mix_Quit();
	return 0;
}

Tomb Raider – Room 151

我的数据结构大作业完成了，一个叫做Tomb Raider - Room 151的游戏，中文译名可以为盗墓者-151室。
当前发布的仅为游戏的demo版本，欢迎帮忙测试找bug，程序附带源代码！

110305修改：
1、互联网多人游戏。
2、联网聊天功能，系统消息。
3、迷宫地图自动生成器，生成了20关地图。
4、优化联网速度，使用脏列表，网络中传输每帧需要重绘的对象。
5、更成熟的复活功能。
6、Ghost、Pharaoh变得更精明。

110301修正bug：
1、单人游戏的时候隐藏的witch不会动。
2、挂掉了仍然可以装雷。
3、去掉Explosion对象，爆炸时候不会增加额外Object数目。
4、优化A*算法，去除不必要的检查。

Room 151 Network 110305 (Win32 Binary & Source Code)

运行平台： Windows XP、Vista、7
开发环境：Codelite、libSDL

玩法很简单。
Ctrl：佩剑
Alt：手枪
Space：安装定时炸弹
方向键：行走

可以联网合作游戏，进入游戏默认为单人模式，F3切换到服务器模式，F2切换到客户端模式。
命令行下执行可以加入一些参数：xxtomb [-m GameMode] [-p PlayerName] [-h HostToConnect]
GameMode可取0：单人游戏，1：服务器模式，2：客户端模式。

附带几张游戏相关的图：

用C++和libSDL开发游戏系列(1)——环境与框架

做这个游戏是为了交作业，另外需要制作一份作业报告，故顺便以日志的形式连载一下！！！
非专业写游戏高手，水平有限，望多多指教。

开发工具：codelite v2.9
图形库：libSDL
开发平台：Windows
游戏类型：即时战略游戏