游戏人工智能实验报告三.doc

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