文档章节

A*算法解决迷宫问题(DIY制作地图类似于小游戏,界面设计非常不错。)

huser_YJ
 huser_YJ
发布于 2014/09/22 16:38
字数 2898
阅读 547
收藏 1

人工智能老师要求实现一个算法,刚开始的时候自己做的是一个深度优先搜索,然后又学了A*,觉得深度优先效率还是不行,就打算用A*算法实现兔子找萝卜的小游戏。

  地图设计采用的是坦克大战中的地图设计图案。

这是用C语言写的,编译器是VC6.0

需要源程序代码参考的可以在我的csdn下载资源中找到。

附上下载地址:http://download.csdn.net/detail/yujin753/7060747




问题的描述

迷宫问题可以表述为:一个二维的网格,0表示点可走,1表示点不可以走,点用(x,y)表示,寻找从某一个给定的起始单元格出发, 经由行相邻或列相邻的单元格(可以通过的),最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中,都只能看到与它邻近的4个单元格(如果位于底边,则只有3个;位于4个角上,则只有2个是否能通过。迷宫问题用传统的广度优先搜索或带回溯的深度优先搜索等算法都能很好地解决。当然采用A*算法更能体现对人工智能这门的理解,比起盲目的搜索,A*算法更具有针对性。

深度优先搜索算法实现

所谓“深度优先”,即:状态树的生长或展开,首先沿状态树的深度方向进行。深度优先搜索算法需要记录下状态树的生长过程。深度优先搜索算法是一种盲目的搜索算法,搜索中可能很多次的搜索到目标点,深度搜索算法通过不断剪枝,寻找出一条从起始点到目标点最近且最省时的路径,即深度优先搜索算法也是一种全局的搜索算法,这样的深度优先搜索算法运用到未知迷宫搜救中是没有意义的。而本次实验中,深度优先搜索算法是以找到目标物为目的,没有剪枝的步骤,只要搜索到目标物,迷宫的搜索过程就成功退出。

深度优先搜索的一些特点:

a) 一般不能保证找到最优解

b) 当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制

c) 最坏情况时,搜索空间等同于穷举

d) 是一个通用的与问题无关的方法

 

 

图一 深度优先搜索

深度优先伪码:

1) Push(S,Open) 将初始节点放入Open表中;

2) Judge(S) 判断S节点是不是目标节点,if(S为目标节点),那么找到目标节点;

3) While(判断Open表是否为空)

如果为空,那么搜索失败 end;

否则把第一个节点N从Open表中移至Close表中;

4) 将N的后继节点放入Open表中;

判断后继节点中是否有目标节点;

If(存在目标节点)

成功;

Else

返回3);

 

 A*算法实现

A*算法是人工智能中的一种搜索算法,是一种启发式搜索算法,它不需遍历所有节点,只是利用包含问题启发式信息的评价函数对节点进行排序(Node Ordering),使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价节点处于最短路线上的可能性的度量。

 

I.启发函数的确定

A*算法中引入了评估函数,评估函数如下:

f(n)=g(n)+h(n)

其中:n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。即评估函数f ( n) 是从初始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和[10]。

这里我们定义n点到目标点的最小实际距离为h(n)*,A*算法要满足的条件为:

h(n)<=h(n)*

由前面的迷宫问题的描述我们可以知道,迷宫走的时候只能往上下左右走,每走一步,代价为1,这里我们采用的估价函数为当前节点到目标节点的曼哈顿距离,即:

h(n)=|end.x – n.x|+ |end.y – n.y|[11]

这里end表示迷宫的目标点,n表示当前点,很明显这里h(n)<=h(n)*。

g(n)容易表示,即每走一步的代价是1,所以利用f(n)=g(n)+h(n)这种策略,我们可以不断地逼近目标点,从而找到问题的解。

 

II A*的主要实现步骤的伪码表示

1) OPEN:=(s), f(s):=g(s)+h(s);

2)LOOP: IF OPEN=( ) THEN EXIT(FAIL);

3) n:=FIRST(OPEN);

4)IF GOAL(n) THEN EXIT(SUCCESS);

5)REMOVE(n, OPEN), ADD(n, CLOSED);

6)EXPAND(n) →{mi}, 

计算f(n, mi):=g(n, mi)+h(mi);

ADD(mj, OPEN), 标记mj到n的指针;

IF f(n, mk)<f(mk) THEN f(mk):=f(n, mk), 

标记mk到n的指针;

IF f(n, ml)<f(ml,) THEN f(ml):=f(n, ml),

标记ml到n的指针, 

ADD(ml, OPEN);

7, OPEN中的节点按f值从小到大排序;

8, GO LOOP;

这里OPEN表和CLOSED表分别用来存储要搜索的状态结点和存储已经访问过的状态。


编程实现

该测试程序在VC6.0环境下编译实现,编程语言用的是c语言。

代码中数据结构设计

struct mark //定义迷宫内点的坐标类型 

int x; 

int y; 

}; 

struct mark start,end; //start,end入口和出口的坐标 

 

struct Element //栈元素, 

{  int f;//估价函数

int g;//代价

int h;//启发函数

int x,y; //x行,y列 

}; 

Element elem,e; 

 

typedef struct LStack //链栈 

{   Element elem; 

struct LStack *next; 

}*PLStack;

PLStack Open,Close;//OPEN表和CLOSE表用来储存链节点

 函数框架实现

InitStack(Open); //用于初始化open 表

InitStack(Close); //用于初始化close表

Push(Open,elem); //表示初始节点elem进入open表

 

while(!StackEmpty(Open)&&Flag==0) //栈不为空 有路径可走 

Pop(Open,elem); //将open表中的当前元素提出来

Push(Close,elem);//将从open表取出来的元素放入close表

if(判断elem节点的子节点是否可以走)判断上下左右{

if(elem_child不为目标节点){

Push(Open,elem_child) 子节点进Open表,这里的push()函数进入栈中,为有序进入,也就是说进栈是按顺序插入的。

}//if

  else(该节点为目标节点){

Push(Close,elem_child)//目标节点进close表

Flag=1//将标志置为一表示已经找到了目标节点

End//找到了目标节点结束

 

}//else

}//if

}//while

 

If(StackEmpty(Open)||Flag==0)

Printf(”迷宫没有解\n”)

返回迷宫没有解//表示走到这里还没有找到解则迷宫走不出去

核心函数代码

int InitStack(PLStack &S) //初始化链栈,Open表和Close表初始化

{

S=NULL;

return 1;

}

 

int StackEmpty(PLStack S)//判断栈是否为空 

if(S==NULL) 

return 1; 

else 

return 0; 

}

int Push1(PLStack &S, Element e)//压入新数据元素 

PLStack p; 

PLStack q,t;

p=(PLStack)malloc(sizeof(LStack));

p->elem.g=deep;//表示深度

//估价函数即使用曼哈顿距离表示

p->elem.h=abs(end.x-e.x)+abs(end.y-e.y);

p->elem.f=p->elem.h+p->elem.g;

p->elem.x=e.x;

p->elem.y=e.y;

p->next=NULL;

 

if(NULL==S||p->elem.f<=S->elem.f)

{

p->next=S;

S=p;

//return 1;

}

else

{

q=S;

t=q->next;

while(t!=NULL)

{

if(p->elem.f>t->elem.f)

{

q=t;

t=t->next;

}

else

break;

}

p->next=t;

q->next=p;

}

return 1;

int Pop(PLStack &S,Element &e) //栈顶元素出栈 

PLStack p; 

if(!StackEmpty(S)) 

e=S->elem; 

p=S; 

S=S->next; 

free(p); 

return 1; 

else 

return 0; 

}

界面设计

   界面设计非常友好、清晰、表达明确、功能集中、操作简单。

迷宫大小设定为18*25的,入口和出口的位置分别设为(1.0)、(16,24),

迷宫状态用一个二维表存储,0表示可以走,即界面中的可行域表示,1表示不能走,即界面中的黄金墙和铂金墙。可选的地图有三个,每次只能选择一个,选择完地图之后就可以画迷宫了,之后就可以搜索了。

我采用的WindowsAPI程序设计,整个的界面是利用windows程序设计的窗口设计实现的,地图的样子是通过一个地图编辑器来实现的,总体给人的感觉是比较清楚、清晰,也比较新颖。然后把地图当作图片画出来,即每一小格代表的数字,决定了地图将会画出什么颜色的图片来,当二维表中的数据为1时,我们就可以画出墙的图片,当其中数据为0是我们就可以画出可行域的图片。通过这样的方法,我们可以比较简单的实现地图样式的变换,能够达到非常不错的效果,旁边的选择地图按钮能够帮助我们选择我们想要的地图,选择好了之后,运行完程序,然后通过地图重置可以实现地图的删除,然后可以再进行地图的选择,非常方便的实现了地图的更换。

调用函数:

HWND hmap;

    HDC hm;

      hmap = GetDlgItem(hwnd,IDC_MAP);

hm = GetDC(hmap);

将整个窗口的句柄控制,使用函数:

BitBlt(hm,x,y,p_Lsize,p_Hsize,h,0,0,SRCCOPY);

其中hm为窗口句柄,x,y为对应位置的坐标,p_Lsize,p_Hsize为图片的大小,h为图片画的位置,这样就可以画出界面了。

 

图二 迷宫界面

 运行结果分析

从程序运行的结果我们可以知道,深度优先搜索和A*搜索两种搜索策略都实现了。我们也已经知道,深度优先搜索是一种盲目的搜索,也就是说搜索过程中并没有带启发式信息,而A*搜索带了启发式信息,在程序运行过程中,我们可以明显的感知,这两种算法的区别。

我通过实验验证了深度优先搜索和A*搜索在本规模迷宫环境下的情况,可以利用遍历Open表和Close表中的节点,得出所扩展的节点和所走的步数。这里我们可以计算出三个地图走出迷宫需要走的步数。

下面的数据为两种搜索算法从初始节点走到目标节点所走的步数:

表一 深度优先搜索和A*搜索所走步数比较

地图

所走步数

深度优先搜索

A*搜索

地图一

178

90

地图二

207

87

地图三

218

82

从上表我们可以明显看出来采用启发式的A*搜索比盲目的深度优先搜索所走的步数更少,也就是说,在迷宫问题中采用A*搜索算法较传统的深度优先搜索能更快的找到迷宫的目标节点,并且效率提高的非常快。从表中可以看出,效率提高了两倍多,这样在更大规模的迷宫问题中,能够节约更多的时间找到问题的解。


© 著作权归作者所有

huser_YJ
粉丝 2
博文 21
码字总数 28816
作品 0
武汉
私信 提问
游戏制作中的大宝剑---常用的数据结构与算法

前言 时间流逝,物是人非,就好像涌动的河流,永无终焉,幼稚的心智将变得高尚,青年的爱慕将变得深刻,清澈之水折射着成长。 ----------《塞尔塔传说》 PS:为了方便大家阅读,个人认为比较...

loving_forever_
2016/09/02
0
0
[Beautifulzzzz的博客目录] 快速索引点这儿O(∩_∩)O~~,红色标记的是不错的(⊙o⊙)哦~

3D相关开发 [direct-X] 1、direct-X最小框架 [OpenGL] 1、环境搭建及最小系统 [OpenGL] 2、企业版VC6.0自带的Win32-OpenGL工程浅析 51单片机 [51单片机] 1602液晶显示控制代码 [51单片机] 1...

史迪奇2号
2017/08/01
0
0
从0开始:开发自己的游戏[0]

我是Lem0,自学倡导者,执迷于“不务正业”,被批评“旁门左道”。我注册并使用简书,希望能够记录一些我记不住的事情,或者与大家一起共享知识,共同学习。 在「从0开始:开发自己的游戏」中...

Lem0
2017/03/08
0
0
Cocos2d-x游戏开发之图片元素

[Cocos2d-x相关教程来源于红孩儿的游戏编程之路 CSDN博客地址:http://blog.csdn.net/honghaier] 红孩儿Cocos2d-X学习园地QQ群:249941957 加群写:Cocos2d-x 本章为我的Cocos2d-x教程一书初...

长平狐
2012/11/19
1K
0
TensorFlow应用实战-17-Qlearning实现迷宫小游戏

什么是Q-learning Q是Quality的首字母,表示"质量/优劣",表示给它打一个分。 在某些状态下做某个动作,会给他一个Q的价值。 learning就是学习的意思。基于质量,评判做出选择。 Q learning...

天涯明月笙
2018/06/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

日志相关---日志配置和过滤器

一、log4j日志简介 1.1、 Loggers 级别和介绍 Loggers组件在此系统中被分为八个级别:ALL、TRANCE、DEBUG、INFO、WARN、ERROR和FATAL、OFF。这八个级别是有顺序的, ##off表示关闭ALL < T...

spinachgit
33分钟前
1
0
六个面试题层层剖析——LongAddr原子类

并发编程面试题 (1)LongAddr的结构是怎样的? (2)当前线程应该访问Cell数组里面的哪一个Cell元素? (3)如何初始化Cell数组? (4)Cell数组如何扩容? (5)线程访问分配的Cell元素有冲...

须臾之余
34分钟前
8
0
MySQL-入门(二)

本部分主要是MySQL的常用函数和高级用法。 一、MySQL排序 排序关键字:order by 排序字段。后面写上要排序字段,排序字段可以有多个,多个采用逗号间隔,order by默认采用升序(asc)排序,可...

潜行-L
45分钟前
3
0
BAM转VCF的方法对比

1 使用GATK HaplotypeCaller #java -jar gatk.jar HaplotypeCaller --native-pair-hmm-threads 4 -R xx.fa -I xx.bam -O xx.vcf --native-pair-hmm-threads用来设置多线程,默认为4线程 2 sa......

悲催的古灵武士
53分钟前
2
0
软件架构设计原则之“KISS”的总结使用

今天聊一聊软件架构设计中的 KISS 原则。 对! 就是亲嘴的那个 “KISS”! 一定要多练习。 ... ... ... ... 作为一个程序员我是推荐理解为“亲嘴”的,可以很好的解决单身问题,但作为一个架...

Owen_Jia
56分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部