人工智能课件第五次课.ppt

1、A*路径搜索A* Pathfinding We are going to discuss the fundamentals of the A* pathfinding algorithm. 基本A*路径搜索算法 The A* Algorithm provides an effective solution to the problem of pathfinding.定义搜索区域Defining the search area The first step in pathfinding is to define the search area. 首先定义搜索区域。 The game world

2、needs to be represented by points that both the game characters and objects can occupy. We need to reduce the nodes to a manageable number, which is what we mean when we say we need to simplify the search area. 减少搜索区域的节点数量，简化搜索区域。 定义搜索区域Defining the search area基于方块的搜索区域Tiled search areaStarting the

3、search We will use the A* algorithm to find the shortest path between any two nodes while avoiding the obstacles. 避开障碍在任意两点之间用A*算法获得最短路径。 OpenList-We need a way to keep track of which tiles need to be searched. 可以作为后备检测的点的集合； ClosedList-the tiles that already were checked. 已经检测完成的点的集合。A*伪代码A* pseudo

4、 codeAdd the starting node to the open listWhile the open list is not empty current node=node from open list with the lowest cost if current node=goal node then path complete else move current node to the closed list examine each node adjacent to the current node for each adjacent node if it isnt on

5、 the open list and isnt on the closed list and it isnt an obstacle then move it to open list and calculate cost A*伪代码A* pseudo code将开始点加到Open List表中；重复一下过程，直到Open List表空为止： 当前点=OpenList表中代价值最小的点； 如果当前点为目标点， 则 搜索完成； 否则 将当前点移到ClosedList表中； 对与当前点相连的每一点，重复执行： 如果该点不在OpenList、ClosedList，并且不是障碍点 则 将该点移到Ope

6、nList表中，计算该点的代价值；Create a tiled search areaSpider-starting pointHuman character-destinationSolid black squares-wall obstaclesAdjacent tiles to considerWe proceed to check each of the eight adjacent tiles and then add each valid tile to the open list.对与蜘蛛相邻的八个点检查，不在任何表中和不是障碍的点加入OpenList表中。将开始点移到Close

7、d List表中Moving the starting tile to the closed listStart point开始点Linking to the parentsLink to parents赋予数值Scoring We will use path scoring to determine the best path from the starting tile to the destination tile. (1) We look at the cost to move from the starting tile to any given tile. (2)We look a

8、t the cost to move from the given tile to the destination tile. (3)We take the sum of the cost of each tile that leads back to the initial location.Calculating the path score Score=Cost from start+Heuristic We will check the tiles with the lowest cost. A lower cost will equate to a shorter path.Star

9、t pointgiven pointdestinationCost from startheuristicInitial tile path scores初始化每一点的数值Initial tile path scores The s value is the cost of getting there from the starting tile. s=从开始点到当前点的累计代价值 The h value is the heuristic which is an estimate of the number of steps from the given tile to the destina

10、tion tile. h=从当前点到目标点的步数值 The c value is the sum of s and h. c=s+hExamining tile (5,6)Examining tile (5,5)Examining tile (5,4)Examining all the tiles with a cost of 5Examining all tiles with a cost of 6Examining tile (3,4)Examining tiles (2,5) and (3,5)Examining tiles (1,6)(2,6)(3,6)最终路径The complete

11、d pathS=6543210Finding a dead endexercise区域代价值Terrain Cost The shortest path isnt always the fastest path. 最短路径不一定是最快路径。 Along walk along a road might be faster than a shorter walk through a swamp. 如有沼泽地的情况。对区域代价赋予数值Scoring with terrain cost Total cost from start=cost from start+terrain cost Score=t

12、otal cost from start+heuristic 每一点总代价值=从开始点到当前点的累计代价值+区域代价值+启发式数值。区域的种类Types of terrainOpen terrain平坦区域Cost=1Grassland草地Cost=3Swampland沼泽地Cost=5Adding different terrain elementsOriginal path over terrain elementsCalculating the lowest-cost pathThe lowest-cost pathInfluence Mapping Other elements can

13、 influence path cost when calculating a path with A*. 其他因素也能影响路径代价。 Nodes that pass through the line of sight of any enemy might present a higher cost. 如在敌人的视线范围内，区域代价比较高。Influence Mapping Influence Mapping is a way to vary the cost of the A* nodes depending on what is happening in the game. 依赖游戏的不同

14、，给节点不同的代价值。敌人炮火影响的区域代价Influenced by the enemy firing zone记录事件计算代价Recording game incidents We can record individual game incidents in an influence map. We are using what the character does. If the player repeatedly ambushes and kills computer-controlled characters at a given doorway, that the doorway

15、 might increase in cost. 如果玩家在门口重复地伏击并杀死角色，则门口的代价增加。Influenced by the number of kills小结 A*算法的基本思想； 对区域代价的搜索实现的算法分析； 在运行过程中代价的改变。思考题 （1）A*算法的核心思想是什么？ （2） A*算法与其他（如基本路径搜索）算法有何不同？ （3）在路径搜索算法中为什么A*算法是最有效的算法？ （4）A*算法有何不足？遇到什么样情况不是最快的搜索算法？本次实验内容 用A*算法实现路径搜索。 如有时间，可以考虑区域代价情况的搜索。 在实现过程中，对代价可采用数组方式记录代价值。 感兴趣可以将根据运行状况改变代价值的思想，运用到实际的游戏或优化系统中。