资源描述：
《游戏人工智能实验报告三.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验三A*算法实验报告一、实验目的掌握游戏中寻路算法尤其是目前产用的A*算法原理二、实验仪器Windows7系统MicrosoftVisualStudio2015三、实验原理及过程//描述A*的算法原理//描述程序实现时的思路包括对每个调用的API进行详细说明A*的算法原理：（1）定义搜寻区域：就是让游戏角色和物体能找出任意两点的最佳路径并避开障碍物，这就是路径寻找算法的工作。（2）开始搜寻：一旦我们简化了搜寻区域，使其由适当数量节点构成时，就能准备开始搜寻了。我们会以A*算法找出任何两节点间的最短路径。以下就是A*算法伪代码：把起始节点加进openli
2、stwhile(openlist不空){当前节点=openlist中成本最低的节点if(当前节点==目标节点){路径完成从目标节点开始寻找其母节点，直到母节点是起始节点位置，得到路径}else{把当前节点移入到closelist检视当前节点的每个相邻节点for(每个相邻节点)if(该节点不在openlist中&&该节点不在closedlist中&&该节点不是障碍物){把该节点移进openlist计算其成本记录该节点的母节点为当前节点}}}if(还没有找到路径){无法从起始点到达目的地}具体过程：从起始节点开始搜寻，然后依次去搜寻周围结点【1】openli
3、st是A*算法中的记录方式，开始时，他只有一个节点，也就是起始节点，接着会陆续把其它节点放进去。【2】建好openlist后，接着予以检查，搜寻清单内每个砖块相邻的砖块。即检查每个相邻砖块是否为路径上的有效砖块。八个相邻砖块，有效则加入openlist，无效则忽略。【3】建立closedlist（存放已访问过的成本最低的节点），当某砖块的相邻八个砖块都已经检查过，则将该砖块放进去。以上，一次循环完成。在openlist中相邻砖块如何连接，做法是记录openlist中每个砖块的母砖块，即该角色走到当前位置前的那个砖块。（3）记分：用路径得分，找出起始砖块和
4、目的砖块间的最佳路径。【1】计算从起始砖块移到任何指定砖块上的移动成本。【2】计算从指定砖块移动到目的地砖块所需的移动成本。（4）搜寻死路：最简单的方法就是监控openlist。如果检查到最后的节点，openlist中再也没有任何成员，就是遇上死路了。（5）地形成本：有时候还需要考虑其他因素，最短的路径不一定是最快的，比如不同地形的移动成本是不同的，只有在计算总的移动成本时，考虑到地形因素就可以了。当然对于金钱，燃料或其他类型的资源时，问题就会变得更加复杂一些。（6）影响力对应：例如：通过任何敌人的视线的节点，有较高的成本。这种成本无法在设计游戏软件阶段
5、时建立，因为游戏角色的位置是会改变的。影响力对应(influencemapping)是一种改变A*节点成本的方法，根据游戏里发生的情节而定。四、实验结果五、实验心得(需包括有何不足如何改进)//你认为目前的A*算法有什么不足之处,如何改进A*算法的不足之处相比于平常的算法它需要的计算量比较大，而且也很繁琐。如何改进：（来自一位大神的说法）此改进的模糊C-此函数实现遗传算法，用于模糊C-均值聚类。六、主要代码voidCAStar::StepInitialize(intsx,intsy,intdx,intdy){ClearNodes();m_iSX=sx;m
6、_iSY=sy;m_iDX=dx;m_iDY=dy;m_iDNum=Coord2Num(dx,dy);_asNode*temp=new_asNode(sx,sy);temp->g=0;temp->h=abs(dx-sx)+abs(dy-sy);temp->f=temp->g+temp->h;temp->number=Coord2Num(sx,sy);m_pOpen=temp;udFunc(udNotifyList,NULL,m_pOpen,ASNL_STARTOPEN,m_pNCData);udFunc(udNotifyChild,NULL,temp,0
7、,m_pNCData);}intCAStar::Step(){if(!(m_pBest=GetBest()))return-1;if(m_pBest->number==m_iDNum)return1;CreateChildren(m_pBest);return0;}_asNode*CAStar::GetBest(){if(!m_pOpen)returnNULL;_asNode*temp=m_pOpen,*temp2=m_pClosed;m_pOpen=temp->next;udFunc(udNotifyList,NULL,temp,ASNL_DELETE
8、OPEN,m_pNCData);m_pClosed=temp;m_pClosed
