人工智能课件第四次课

基本路径搜索和航点应用Basic Pathfinding and WaypointsAt its most basic level,pathfinding is simply the process of moving the position of a game character from its initial location to a desired destination.基本路径搜索是从初始位置移动到目标位置的过程。基本路径搜索和航点应用Basic Pathfinding 1基本路径搜索Basic pathfinding algorithmif(positionXdestinationX)positionX-;else if(positionXdestinationY)positionY-；else if(positionYdestinationY)positionY+;基本路径搜索Basic pathfinding algor2限制条件Some limitationsSimple path movementLine-of-sight path movement限制条件Some limitationsSimple pa3障碍问题Problems with obstacles障碍问题Problems with obstacles4（1）随机运动避开障碍Random Movement Obstacle AvoidanceRandom movement can be a simple and effective method of obstacle avoidance.随机运动能够简单而有效地解决避开障碍。（1）随机运动避开障碍Random Movement Ob5Random movement obstacle avoidance algorithmif player in line of sight following straight path to playerelse move in random directionRandom movement obstacle avoid6（2）围绕障碍物的追踪Tracing Around ObstaclesThis method can be effective when attempting to find a path around large obstacles,such as a mountain range in a strategy or role-playing game.解决围绕大障碍物寻找路径的问题。（2）围绕障碍物的追踪Tracing Around Obs7基本追踪Basic tracingComputer-controlled characterIts goal基本追踪Basic tracingComputer-con8存在的问题Problem with tracingDeciding when to stop tracing?什么时候停止追踪？We need a way to determine when we should switch from the tracing state back to a simple pathfinding state.如何从追踪状态转换为路径搜索状态？One way of accomplishing this is to calculate a line from the point the tracing starts to the desired destination.解决方法-计算从追踪开始点到目标点的直线距离。存在的问题Problem with tracingDeci9改进的追踪Improved tracing改进的追踪Improved tracing10改进的追踪Improved tracingTracing the outskirts of the obstacle until the line connecting the starting point and desired destination is crossed ensures that the path doesnt loop back to the staring point.沿着障碍物外围追踪时，穿过障碍物连接开始点和目标点，防止追踪路径又回到起点。改进的追踪Improved tracingTracing 11视线追踪Tracing with line of sight视线追踪Tracing with line of sigh12视线追踪Tracing with line of sightWe follow the outskirts of the obstacle,but at each step we check to see if the destination is in the computer-controlled characters line of sight.每一步检测是否处在视线之内。If so,we switch from a tracing state to a line-of-sight pathfinding state.处在视线之内，路径搜索从追踪状态转换为视线搜索状态。视线追踪Tracing with line of sigh13（3）标记路径搜索Breadcrumb PathfindingBreadcrumb pathfinding can make computer-controlled characters seem very intelligent because the player is unknowingly creating the path for the computer-controlled character.带标记的路径搜索是玩家无意地留下轨迹。Each time the player takes a step,he unknowingly leaves an invisible marker,or breadcrumb,on the game world.每次玩家走一步，它就留下一个不可见的标记。（3）标记路径搜索Breadcrumb Pathfindi14Breadcrumb trailA troll randomly moves about the tile-based environment until it detects a breadcrumb on an adjacent location.Breadcrumb trailA troll random15ai_Entity class#define kMaxTrailLength 15class ai_Entity public:int row;int col;int type;int state;int trailRowkMaxTrailLength;int trailColkMaxTrailLength;ai_Entity();ai_Entity();ai_Entity class#define kMaxTra16变量说明#define statement sets the maximum number of player steps to track.设置kMaxTrailLength为玩家标记轨迹的最大步骤数。trailRow,trailCol arrays store the row and column coordinates of the previous 15 steps taken by the player.trailRow,trailCol保存由玩家标记的15步的横、纵坐标。变量说明#define statement sets the17标记数组的初始化Trail array initializationint i;for(i=0;ikMaxTrailLength;i+)trailRowi=-1;trailColi=-1;标记数组的初始化Trail array initializ18记录玩家的位置Recording the player positionsvoid ai_World:KeyDown(int key)int i;if(key=kUpKey)for(i=0;i0)entityListi.row-;DropBreadCrumb();if(key=kDownKey)for(i=0;ikMaxEntities;i+)if(entityListi.state=kPlayer)if(entityListi.row=kMaxRows-1)entityListi.row+;DropBreadCrumb();记录玩家的位置Recording the player p19if(key=kLeftKey)for(i=0;i0)entityListi.col-;DropBreadCrumb();if(key=kRightKey)for(i=0;ikMaxEntities;i+)if(entityListi.state=kPlayer)if(entityListi.colkMaxCols-1)entityListi.col+;DropBreadCrumb();if(key=kLeftKey)20设置标记Dropping a breadCrumbvoid ai_World:DropBreadCrumb(void)int i;for(i=kMaxTrailLength-1;i-)entityList0.trailRowi=entityList0.trailRowi-1;entityList0.trailColi=entityList0.trailColi-1;entityList0.trailRow0=entityList0.row;entityList0.trailCol0=entityList0.Col;设置标记Dropping a breadCrumbvoid21追踪标记Following the breadcrumbsThe goal is to determine if any of the eight positions adjacent to the computer-controlled troll contain a breadcrumb.是否在八个相邻方向之一中有标记。追踪标记Following the breadcrumbs22Following the breadcrumbsfor(i=0;ikMaxEntities;i+)r=entityListi.row;c=entityListi.col;foundCrumb=-1;for(j=0;j=0)entityListi.row=entityList0.trailRowfoundCrumb;entityListi.col=entityList0.trailColfoundCrumb;else entityListi.row=entityList0.row+Rnd(0,2)-1;entityListi.col=entityList0.col+Rnd(0,2)-1;if(entityListi.row0)entityListi.row=0;if(entityListi.col=kMaxRows)entityListi.row=kMaxRows-1;if(entityListi.col=kMaxCols)entityListi.col=kMaxCols-1;if(foundCrumb=0)26Following the shortest path12,11,10,9,8,7,6,2Following the shortest path1227（4）Path FollowingIt is necessary to move computer-controlled characters in a game environment in a realistic way even though they might not have an ultimate destination.没有目的地的移动Car-racing game 赛车 navigate a roadway want the cars to stay on the road（4）Path FollowingIt is necessa28Path Following2-road 1-out of boundsPath Following2-road 1-out o29地域分析Terrain analysisW e need to analyze the surrounding terrain and decide on the best move.分析周围的地域并决定选取最佳移动。We examine all eight directions and then eliminate those that are not part of the road.对八个方向检测，消除不在路上的部分。The problem becomes one of deciding which of the remaining directions to take.决定选取哪一个方向移动？地域分析Terrain analysisW e need 30地域分析Terrain analysisint r;int c;int terrainAnalysis9;r=entityListi.row;c=entityListi.col;terrainAnalysis1=terrainr-1c-1;terrainAnalysis2=terrainr-1c;terrainAnalysis3=terrainr-1c+1;terrainAnalysis4=terrainrc+1;terrainAnalysis5=terrainr+1c+1;terrainAnalysis6=terrainr+1c;terrainAnalysis7=terrainr+1c-1;terrainAnalysis8=terrainrc-1;地域分析Terrain analysisint r;31for(j=1;j=8;j+)if(terrainAnalysisj=1)terrainAnalysisj=0;else terrainAnalysisj=10;for(j=1;j=8;j+)32Possible directionsPossible directions33Direction analysisif(entityListi.direction=1)terrainAnalysis1=terrainAnalysis1+2;terrainAnalysis2+;terrainAnalysis5-;terrainAnalysis8+;if(entityListi.direction=2)terrainAnalysis1+;terrainAnalysis2=terrainAnalysis2+2;terrainAnalysis3+;terrainAnalysis6-;Direction analysisif(entityLis34if(entityListi.direction=3)terrainAnalysis2+;terrainAnalysis3=terrainAnalysis3+2;terrainAnalysis4+;terrainAnalysis7-;if(entityListi.direction=4)terrainAnalysis3+;terrainAnalysis4=terrainAnalysis4+2;terrainAnalysis5+;terrainAnalysis7-;if(entityListi.direction=5)terrainAnalysis4+;terrainAnalysis5=terrainAnalysis5+2;terrainAnalysis6+;terrainAnalysis8-;if(entityListi.direction=3)35if(entityListi.direction=6)terrainAnalysis2-;terrainAnalysis5+;terrainAnalysis6=terrainAnalysis6+2;terrainAnalysis7+;if(entityListi.direction=7)terrainAnalysis3-;terrainAnalysis6+;terrainAnalysis7=terrainAnalysis7+2;terrainAnalysis8+;if(entityListi.direction=8)terrainAnalysis1+;terrainAnalysis4-;terrainAnalysis7+;terrainAnalysis8=terrainAnalysis8+2;if(entityListi.direction=6)36Weighting directionsThis enables us to give added weight to the previous direction whenever it is time to update the trolls position.当角色更新到新的位置时，对前一次的方向加一权值。Weighting directionsThis enabl37Choosing a direction maxTerrain=0;maxIndex=0;for(j=1;jmaxTerrain)maxTerrain=terrainAnalysisj;maxIndex=j;寻找最大值作为可能的方向。Choosing a direction maxTerrai38更新位置Update positionif(maxIndex=1)entityList.direction=1;entityListi.row-;entityListi.col-;if(maxIndex=2)entityList.direction=2;entityListi.row-;更新位置Update positionif(maxInde39if(maxIndex=3)entityList.direction=3;entityListi.row-;entityListi.col+;if(maxIndex=4)entityList.direction=2;entityListi.col+;if(maxIndex=5)entityList.direction=5;entityListi.row+;entityListi.col+;if(maxIndex=3)40if(maxIndex=6)entityList.direction=6;entityListi.row+;if(maxIndex=7)entityList.direction=6;entityListi.row+;entityListi.col-;if(maxIndex=8)entityList.direction=8;entityListi.col-;if(maxIndex=6)41Road PathRoad Path42（5）Wall TracingWall tracing is more of an exploration technique.Its most useful in game environments made of many small rooms,although you can use it in maze-like game environments as well.通常运用在一些小房子或迷宫游戏中。（5）Wall TracingWall tracing is43Wall TracingWall Tracing44左手方法Lefthanded approachA better approach would be to make the troll systematically explore the entire environment.最好是能够系统地遍历整个环境。If the troll always moves to its left,it will do a thorough job of exploring its environment.设定巡视者总是向左移动。左手方法Lefthanded approachA bett45面向玩家的右侧Facing players right面向玩家的右侧Facing players right46左手移动方法lefthanded movement approachThe troll always will try to move to its left first.总是沿着左侧移动。If it cant move to its left,it will try to move straight ahead.不能转向左侧时，直行。If that is blocked,it will try to move to its right next.如果是障碍，移向右侧。If that is blocked,it will reverse direction.如果是障碍，移向相反方向。左手移动方法lefthanded movement app47Left-handed movementr=entityListi.row;c=entityListi.col;if(entityListi.direction=4)if(terrainr-1c=1)entityListi.row-;entityListi.direction=2;else if(terrainrc+1=1)entityListi.col+;entityListi.direction=4;else if(terrainr+1c=1)entityListi.row+;entityListi.direction=6;else if(terrainrc-1=1)entityListi.col-;entityListi.direction=8;Left-handed movementr=entityLi48else if(entityListi.direction=6)if(terrainrc+1=1)entityListi.col+;entityListi.direction=4;else if(terrainr+1c=1)entityListi.row+;entityListi.direction=6;else if(terrainrc-1=1)entityListi.col-;entityListi.direction=8;else if(terrainr-1c=1)entityListi.row-;entityListi.direction=2;else if(entityListi.directio49else if(entityListi.direction=8)if(terrainr+1c=1)entityListi.row+;entityListi.direction=6;else if(terrainrc-1=1)entityListi.col-;entityListi.direction=8;else if(terrainr-1c=1)entityListi.row-;entityListi.direction=2;else if(terrainrc+1=1)entityListi.col+;entityListi.direction=4;else if(entityListi.directio50else if(entityListi.direction=2)if(terrainrc-1=1)entityListi.col-;entityListi.direction=8;else if(terrainr-1c=1)entityListi.row-;entityListi.direction=2;else if(terrainrc+1=1)entityListi.col+;entityListi.direction=4;else if(terrainr+1c=1)entityListi.row+;entityListi.direction=6;else if(entityListi.directio51Relative directions This requires because the tile to the trolls left is dependent on the direction its facing.巡视者的左边依赖于它的朝向。Relative directions This req52Wall-tracing pathWall-tracing path53（6）Waypoint Navigation航点导航Placing nodes Every point on the map is in the line of sight of at least one node.（6）Waypoint Navigation航点导航Pla54Labeling nodesLabeling nodes55Building a pathBuilding a path56Empty node tableEmpty node table57Filling in the node tableFilling in the node table58Completed node tableCompleted node table59Finding the pathFinding the path60小结Random Movement Obstacle Avoidance 随机移动避开障碍物Tracing Around Obstacles 绕行障碍物Breadcrumb Pathfinding 以面包屑寻找路径Path Following 遵循路径走Wall Tracing 沿着墙走Waypoint Navigation 航点导航小结Random Movement Obstacle Avo61思考题在基本路径搜索中障碍物较少情况下采用了什么方式解决避开障碍物问题？为什么必须在较少障碍物情况使用这种方式？视线追踪与穿过障碍算得的直线追踪方式有何不同？哪一个更好一些？为什么？在Road Path中利用权值方式有什么好处？不使用会采用何种方式处理不同可能方向？思考题在基本路径搜索中障碍物较少情况下采用了什么方式解决避开62本次实验设计一、二个障碍，并实现如何避开障碍寻找目标点；最好实现Tracing with line of sight,可以结合Bresenham Algorithm算法。可以尝试一下Breadcrumb Pathfinding的思想。可利用二维数组形式实现Waypoint方法。本次实验设计一、二个障碍，并实现如何避开障碍寻找目标点；63