实验三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;

}