游戏人工智能实验报告三

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