《人工智能幻灯片第五次课》由会员分享，可在线阅读，更多相关《人工智能幻灯片第五次课（41页珍藏版）》请在金锄头文库上搜索。
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 wor
2、ld 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 area,Starti
3、ng the 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*伪代码
4、A* pseudo code,Add the starting node to the open list While 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
5、 it isnt on 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，并且不
6、是障碍点 则 将该点移到OpenList表中，计算该点的代价值； ,Create a tiled search area,Spider-starting point Human character-destination Solid black squares-wall obstacles,Adjacent tiles to consider,We proceed to check each of the eight adjacent tiles and then add each valid tile to the open list. 对与蜘蛛相邻的八个点检查，不在任何表中和不是障碍的点加
7、入OpenList表中。,将开始点移到Closed List表中 Moving the starting tile to the closed list,Start point 开始点,Linking to the parents,Link 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
8、to any given tile. (2)We look at 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 wi
9、ll equate to a shorter path.,Start point,given point,destination,Cost from start,heuristic,Initial 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
10、steps from the given tile to the destination tile. h=从当前点到目标点的步数值 The c value is the sum of s and h. c=s+h,Examining tile (5,6),Examining tile (5,5),Examining tile (5,4),Examining all the tiles with a cost of 5,Examining all tiles with a cost of 6,Examining tile (3,4),Examining tiles (2,5) and (3,5)
11、,Examining tiles (1,6)(2,6)(3,6),最终路径 The completed path,S= 6 5 4 3 2 1 0,Finding a dead end,exercise,区域代价值 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
12、 cost,Total cost from start=cost from start+terrain cost Score=total cost from start+heuristic 每一点总代价值=从开始点到当前点的累计代价值+区域代价值+启发式数值。,区域的种类 Types of terrain,Adding different terrain elements,Original path over terrain elements,Calculating the lowest-cost path,The lowest-cost path,Influence Mapping,Othe
13、r elements can 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 th
14、e game. 依赖游戏的不同，给节点不同的代价值。,敌人炮火影响的区域代价 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 doorwa
15、y, that the doorway might increase in cost. 如果玩家在门口重复地伏击并杀死角色，则门口的代价增加。,Influenced by the number of kills,小结,A*算法的基本思想； 对区域代价的搜索实现的算法分析； 在运行过程中代价的改变。,思考题,（1）A*算法的核心思想是什么？ （2） A*算法与其他（如基本路径搜索）算法有何不同？ （3）在路径搜索算法中为什么A*算法是最有效的算法？ （4）A*算法有何不足？遇到什么样情况不是最快的搜索算法？,本次实验内容,用A*算法实现路径搜索。 如有时间，可以考虑区域代价情况的搜索。 在实现过程中，对代价可采用数组方式记录代价值。 感兴趣可以将根据运行状况改变代价值的思想，运用到实际的游戏或优化系统中。,
