<style type="text/css">
<!--
@page
{margin:2cm}
pre.cjk
{font-family:"DejaVu Sans Condensed",monospace}
p
{margin-bottom:0.21cm}
-->
</style>
迷宫生成算法和迷宫寻路算法
大学二年级的时候,作为对栈这个数据结构的复习,我制作了一个迷宫生成算法的小程序,当时反响十分好,过了几天我又用自己已经学的DirectX技术制作了DirectX版的程序。这几天回过头看自己的文章,感觉温故而知不足。温故是因为唤醒了我对迷宫算法的回忆,知不足是因为我那个程序一点儿也没有按照面向对象的思路去做。还是那一套C的思想。
我打算重新制作迷宫程序。这次和以前不同,我学习了C++、STL、Lua、OpenGL,还有很多很多对游戏开发很实用的知识。因此我打算将自己的迷宫重新写一遍,使用面向对象的思想。
大家先看看演示程序吧。演示程序的下载地址在这里。
放几张截图出来,给大家一点视觉冲击!
怎么样?眼花缭乱了吧。其实这些都归功于我写的Maze类。
这个Maze类负责所有与迷宫有关的操作,包括自动产生迷宫和迷宫自动寻路算法都是它的方法。一般来说,迷宫的属性有多少行和多少列,以及各个小格子的属性等等。下面是Maze类的声明:
class Maze
{
public:
Maze( void );
~Maze( void );
Maze( unsigned short column, unsigned short row );
void Init( unsigned short column = 12, unsigned short row = 12 );
void SetCallback( IMazeCallback* pCallback );
void Draw( void );
void DrawPath( void );
void RandomCreate( void );
void SetStartPoint( unsigned short row,
unsigned short col );
void SetEndPoint( unsigned short row,
unsigned short col );
void AutoFindPath( void );
void ClearPoints( void );
private:
IMazeCallback* m_pCallback;
unsigned long* m_pMap;
unsigned short m_MaxColumn;
unsigned short m_MaxRow;
};
这里最重要的算法算是自动迷宫生成算法和迷宫自动寻路算法了。上面的声明是RandomCreate()和AutoFindPath(),为了实现该算法,我使用了一个辅助的类MazeStep,它用来标记迷宫中的每一步。也就是说这一“步”既可以开辟天地形成迷宫,也可以聪明地从迷宫的一端到达另外一端。
不要担心一个点到达不了另外一个点,因为我们前前后后只使用了一条栈。如果你使用两条栈生成迷宫或者你在一个迷宫中生成了两次,那么可能真的存在不可达路径了。
下面是RandomCreate()和AutoFindPath()的关键代码。
void Maze::RandomCreate( void )
{
……
MazeStep newStep( 1, 1 );
MazeStep dummyStep( 0, 0 );// 无效的,用来压栈底
// 新式迷宫生成方法
stepStack.push( dummyStep );// 压入一个无效的步
while ( !stepStack.empty( ) )
{
newStep.RandomState( );// 自动产生状态
bool statement1 = dummyStep == stepStack.top( );// 栈中元素个数是否为1
bool statement2 = newStep.CheckBoundary( );// 检测边界
if ( statement1 && statement2 ||
statement2 && newStep.CheckPrevious( stepStack.top( ) ) &&// 检测是否走回头路
newStep.CheckTraveled( ) )// 检测该路是否走过了
{
newStep.SetCell( );
newStep.SetTraveled( );
stepStack.push( newStep );
newStep.Init( );
newStep.SetPrevious( stepStack.top( ) );
continue;
}
newStep.DisableCurrentState( );
if ( newStep.IsDead( ) )// 是死路一条
{
newStep.SetTraveled( );
newStep = stepStack.top( );
stepStack.pop( );
if ( dummyStep == stepStack.top( ) ) stepStack.pop( );// 把无效的步也弹出吧
}
}// 新式迷宫生成方法
……
}
void Maze::AutoFindPath( void )
{
……
MazeStep newStep = s_StartStep;
MazeStep dummyStep( 0, 0 );// 无效的,用来压栈底
pathStack.push( dummyStep );
while ( s_EndStep != pathStack.top( ) )
{
newStep.RandomState( );
bool statement1 = dummyStep == pathStack.top( );// 栈底是否为无效
bool statement2 = newStep.CheckBoundary( );// 检测边界
bool statement3 = newStep.PathCheckAccessible( );// 检测路径是否可达
if ( statement1 && statement2 && statement3 ||
statement2 && statement3 &&
newStep.CheckPrevious( pathStack.top( ) ) &&// 检测是否走回头路
newStep.CheckTraveled( ) )// 检测是否已经走过了
{
newStep.SetPath( );
newStep.SetTraveled( );
pathStack.push( newStep );
newStep.Init( );
newStep.SetPrevious( pathStack.top( ) );
continue;
}
newStep.DisableCurrentState( );
if ( newStep.IsDead( ) )// 是死路一条
{
newStep.SetTraveled( );
if ( s_EndStep == newStep ) break;// 死路也是终点啊
newStep = pathStack.top( );
pathStack.pop( );
newStep.ClearPath( );
if ( dummyStep == pathStack.top( ) )
{
newStep = s_StartStep;
}
else
{
newStep.SetPrevious( pathStack.top( ) );
}
}
}
SetStartEndPoint( );
……
}
在我的演示程序中使用了Lua脚本语言,因此你可以修改Config.lua中的变量,看看不同效果。
如果你想和我一样顺利地编译运行程序或者是想深入地了解我是怎样制作这个演示程序的,那么可以先看看我写的另外一篇博客:用QtCreator开发OpenGL游戏,然后可以下载我的程序源代码。另外还有什么问题的话可以留言给我。
分享到:
相关推荐
C#实现4种经典迷宫生成算法和迷宫寻路算法,4种经典的迷宫生成算法是:(1)使用并查集算法生成,(2)使用深度优先算法生成,(3)使用随机算法生成,(4)使用递归切割算法,而迷宫寻路使用A*算法。
使用A*算法求解迷宫寻路问题,使用python编程,人工智能导论课后实验
本项目实现了一个基于递归分割迷宫和自动寻路的java可视化,相应博客地址为:http://blog.csdn.net/yutianzuijin/article/details/52078340
详情介绍:https://www.yuque.com/sxbn/ks/100010517 基于C++生成树思想的迷宫生成算法,包含迷宫生成算法和寻路算法。
入口坐标和出口坐标分别为(startx,starty)和(endx,eny),每一个坐标点有两种可能:0或1,其中0表示该位置允许通过,1表示该位置不允许通过。以寻路问题为例实现A*算法的求解程序,设计两种不同的估价函数。
作品:《最短迷宫寻路算法的演示》.rar
1.定义迷宫节点 10*10的方格。 2.定义墙 每道墙都会有两个相连的迷宫节点。 3.每个迷宫节点都有4道墙,如果靠近了边界,则设置为-1(画图时只有>0的墙体才会被画出)。 4.从地图所有节点中挑出一个节点作为迷宫的...
该应用程序将五种不同的寻路算法和五种迷宫生成算法可视化。 您可以一次可视化一个算法,也可以同时可视化多个算法。 最多有四个网格可用,在每个网格中,您可以分配一个迷宫生成算法和一个寻路算法。 每个网格都...
A星算法 迷宫寻路,源代码,注释详细,适合刚刚接触java和算法的人学习
A星算法 迷宫寻路,源代码,注释详细,适合刚刚接触java和算法的人学习
大学二年级的时候,作为对栈这个数据结构的复习,我制作了一个迷宫生成算法的小程序,当时反响十分好,过了几天我又用自己已经学的DirectX技术制作了DirectX版的程序。这几天回过头看自己的文章,感觉温故而知不足...
迷宫的生成类Maze.php,采用树的深度遍历算法 自动寻路是大众的寻路A*(AStar)算法
(1)使用并查集算法生成,(2)使用深度优先算法生成,(3)使用随机算法生成,(4)使用递归切割算法 ,几种经典的迷宫算法
最近学到A星寻路算法,觉得颇有意思,于是百度Google,花了2天时间捣鼓出一个基于Swing的可视化迷宫生成和寻路demo。在此做个记录~ 小demo使用的迷宫生成算法是DFS,寻路用的A星。这样以来,生成的迷宫任意2个格子...
C# 控制台迷宫深度寻路算法代码
恋情申道友优先肯prim算法随机生成迷宫,有自动寻路功能,做了界面,需要easyX库的支持
迷宫算法是采用树的深度遍历原理,这样生成的迷宫相当的细,而且死胡同数量相对较少! 任意两点之间都存在唯一的一条通路。 至于A*寻路算法是最大众化的一全自动寻路算法
实现的功能是:随机生成迷宫地图和入口,出口位置,然后利用这两种搜索算法自动走出迷宫。用到的工具是C++的MFC,可以看到运动轨迹。 第一次做C++项目,代码优点乱。可以直接运行My_QQ.sln文件。
寻路和迷宫生成可视化器使用React Framework构建的图形用户界面,以可视化寻路算法和迷宫生成算法。 如果您想尝试或使用此代码作为基础来创建自己的Pathfinding Visualizer,请随意分叉或下载该项目。 样本(具有...
上下左右四方向走迷宫&寻路算法,可改为8方向,C语言编写。