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

实验三 A*算法
实验报告

一、实验目的
掌握游戏中寻路算法尤其是目前产用的A*算法原理

二、实验仪器
Windows7系统
Microsoft Visual Studio2015

三、实验原理及过程
//描述A*的算法原理
//描述程序实现时的思路包括对每个调用的API进行详细说明
A*的算法原理：
（1）定义搜寻区域：就是让游戏角色和物体能找出任意两点的最佳路径并避开障碍物，这就是路径寻找算法的工作。
（2）开始搜寻：一旦我们简化了搜寻区域，使其由适当数量节点构成时，就能准备开始搜寻了。我们会以A* 算法找出任何两节点间的最短路径。

以下就是A*算法伪代码：
把起始节点加进open list
while (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*节点成本的方法，根据游戏里发生的情节而定。

四、 实验结果

五、实验心得(需包括有何不足如何改进)
//你认为目前的A*算法有什么不足之处,如何改进
A*算法的不足之处
相比于平常的算法它需要的计算量比较大，而且也很繁琐。
如何改进：（来自一位大神的说法）
此改进的模糊C-此函数实现遗传算法，用于模糊C-均值聚类。

六、 主要代码

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;i<2;i++) {
for (int j=-1;j<2;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);
}
}
}
void CAStar::LinkChild(_asNode *node, _asNode *temp)
{
int x = temp->x;
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->children[node->numchildren++] = check;
// A better route found, so update
// the node and variables accordingly.
if (g < check->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->children[node->numchildren++] = check;
if (g < check->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->children[node->numchildren++] = newnode;
udFunc(udNotifyChild, node, newnode, 5, m_pNCData);
}
}
_asNode *CAStar::CheckList(_asNode *node, int num)
{
while (node) {
if (node->number == num) return node;
node = node->next;
}
return NULL;
}

THANKS !!!

致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求

欢迎您的下载，资料仅供参考

-可编辑修改-