《人工智能ppt课件第四次课.ppt》由会员分享，可在线阅读，更多相关《人工智能ppt课件第四次课.ppt（63页珍藏版）》请在三一办公上搜索。
1、基本路径搜索和航点应用Basic Pathfinding and Waypoints,At 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 algorithm,if(positionXdestinationX) positionX-;else if(p
2、ositionXdestinationY) positionY-；else if(positionYdestinationY) positionY+;,限制条件Some limitations,Simple path movement,Line-of-sight path movement,障碍问题Problems with obstacles,（1）随机运动避开障碍Random Movement Obstacle Avoidance,Random movement can be a simple and effective method of obstacle avoidance.随机运动能
3、够简单而有效地解决避开障碍。,Random movement obstacle avoidance algorithm,if player in line of sight following straight path to playerelse move in random direction,（2）围绕障碍物的追踪Tracing Around Obstacles,This method can be effective when attempting to find a path around large obstacles, such as a mountain range in a
4、strategy or role-playing game.解决围绕大障碍物寻找路径的问题。,基本追踪Basic tracing,Computer-controlled character,Its goal,存在的问题Problem with tracing,Deciding 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 w
5、ay of accomplishing this is to calculate a line from the point the tracing starts to the desired destination. 解决方法-计算从追踪开始点到目标点的直线距离。,改进的追踪Improved tracing,改进的追踪Improved tracing,Tracing the outskirts of the obstacle until the line connecting the starting point and desired destination is crossed ensu
6、res that the path doesnt loop back to the staring point.沿着障碍物外围追踪时，穿过障碍物连接开始点和目标点，防止追踪路径又回到起点。,视线追踪Tracing with line of sight,视线追踪Tracing with line of sight,We 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 s
7、ight. 每一步检测是否处在视线之内。If so, we switch from a tracing state to a line-of-sight pathfinding state. 处在视线之内，路径搜索从追踪状态转换为视线搜索状态。,（3）标记路径搜索Breadcrumb Pathfinding,Breadcrumb pathfinding can make computer-controlled characters seem very intelligent because the player is unknowingly creating the path for the
8、computer-controlled character. 带标记的路径搜索是玩家无意地留下轨迹。Each time the player takes a step, he unknowingly leaves an invisible marker, or breadcrumb, on the game world. 每次玩家走一步，它就留下一个不可见的标记。,Breadcrumb trail,A troll randomly moves about the tile-based environment until it detects a breadcrumb on an adjacen
9、t location.,ai_Entity class,#define kMaxTrailLength 15class ai_Entity public: int row; int col; int type; int state; int trailRowkMaxTrailLength; int trailColkMaxTrailLength; ai_Entity(); ai_Entity();,变量说明,#define statement sets the maximum number of player steps to track. 设置kMaxTrailLength为玩家标记轨迹的最
10、大步骤数。trailRow, trailCol arrays store the row and column coordinates of the previous 15 steps taken by the player. trailRow, trailCol保存由玩家标记的15步的横、纵坐标。,标记数组的初始化Trail array initialization,int i;for(i=0; ikMaxTrailLength; i+) trailRowi=-1; trailColi=-1;,记录玩家的位置Recording the player positions,void ai_Wor
11、ld: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(); ,if(key=kLeftKey) for(i=0; i0) entityListi.col-; DropBreadCrumb();
12、if(key=kRightKey) for(i=0; ikMaxEntities;i+) if(entityListi.state=kPlayer) if(entityListi.colkMaxCols-1) entityListi.col+; DropBreadCrumb(); ,设置标记Dropping a breadCrumb,void ai_World:DropBreadCrumb(void) int i; for(i=kMaxTrailLength-1;i-) entityList0.trailRowi=entityList0.trailRowi-1; entityList0.tra
13、ilColi=entityList0.trailColi-1; entityList0.trailRow0=entityList0.row; entityList0.trailCol0=entityList0.Col;,追踪标记Following the breadcrumbs,The goal is to determine if any of the eight positions adjacent to the computer-controlled troll contain a breadcrumb.是否在八个相邻方向之一中有标记。,Following the breadcrumbs
14、,for(i=0; ikMaxEntities;i+) r=entityListi.row; c=entityListi.col; foundCrumb=-1; for(j=0;jkMaxTrailLength;j+) if(r=entityList0.trailRowj) ,if(r-1=entityList0.trailRowj) ,if(r=entityList0.trailRowj) ,if(foundCrumb=0) entityListi.row=entityList0.trailRowfoundCrumb; entityListi.col=entityList0.trailCol
15、foundCrumb; else entityListi.row=entityList0.row+Rnd(0,2)-1; entityListi.col=entityList0.col+Rnd(0,2)-1; if(entityListi.row=kMaxRows) entityListi.row=kMaxRows-1;if(entityListi.col=kMaxCols) entityListi.col=kMaxCols-1;,Following the shortest path,12,11,10,9,8,7,6,2,?,（4）Path Following,It is necessary
16、 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,Path Following,2-road 1-out of bounds,地域分析Terrain analysis,W e need to analyze the
17、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 analysis,int r;int c;int
18、 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;,for(j
19、=1;j=8;j+) if(terrainAnalysisj=1) terrainAnalysisj=0; else terrainAnalysisj=10;,Possible directions,Direction analysis,if(entityListi.direction=1) terrainAnalysis1=terrainAnalysis1+2; terrainAnalysis2+; terrainAnalysis5-; terrainAnalysis8+;if(entityListi.direction=2) terrainAnalysis1+; terrainAnalys
20、is2= terrainAnalysis2+2; terrainAnalysis3+; terrainAnalysis6-;,if(entityListi.direction=3) terrainAnalysis2+; terrainAnalysis3= terrainAnalysis3+2; terrainAnalysis4+; terrainAnalysis7-;if(entityListi.direction=4) terrainAnalysis3+; terrainAnalysis4= terrainAnalysis4+2; terrainAnalysis5+; terrainAnal
21、ysis7-;if(entityListi.direction=5) terrainAnalysis4+; terrainAnalysis5= terrainAnalysis5+2; terrainAnalysis6+; terrainAnalysis8-;,if(entityListi.direction=6) terrainAnalysis2-; terrainAnalysis5+; terrainAnalysis6= terrainAnalysis6+2; terrainAnalysis7+;if(entityListi.direction=7) terrainAnalysis3-; t
22、errainAnalysis6+; terrainAnalysis7= terrainAnalysis7+2; terrainAnalysis8+;if(entityListi.direction=8) terrainAnalysis1+; terrainAnalysis4-; terrainAnalysis7+; terrainAnalysis8=terrainAnalysis8+2;,Weighting directions,This enables us to give added weight to the previous direction whenever it is time
23、to update the trolls position.当角色更新到新的位置时，对前一次的方向加一权值。,Choosing a direction,maxTerrain=0;maxIndex=0;for(j=1;jmaxTerrain) maxTerrain=terrainAnalysisj; maxIndex=j; ,寻找最大值作为可能的方向。,更新位置Update position,if(maxIndex=1) entityList.direction=1; entityListi.row-; entityListi.col-;if(maxIndex=2) entityList.dir
24、ection=2; entityListi.row-;,if(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=6) entityList.direction=6; entityListi.row+;if(maxIndex
25、=7) entityList.direction=6; entityListi.row+; entityListi.col-;if(maxIndex=8) entityList.direction=8; entityListi.col-;,Road Path,（5）Wall Tracing,Wall 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
26、environments as well. 通常运用在一些小房子或迷宫游戏中。,Wall Tracing,左手方法Lefthanded approach,A 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. 设定巡视者总是向左移动。,面向玩家的右侧F
27、acing players right,左手移动方法lefthanded movement approach,The 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 dir
28、ection. 如果是障碍，移向相反方向。,Left-handed movement,r=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;
29、 else if(terrainrc-1=1) entityListi.col-; entityListi.direction=8; ,else 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
30、if(terrainr-1c=1) entityListi.row-; entityListi.direction=2; ,else 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(ter
31、rainrc+1=1) entityListi.col+; entityListi.direction=4; ,else 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+
32、1c=1) entityListi.row+; entityListi.direction=6; ,Relative directions,This requires because the tile to the trolls left is dependent on the direction its facing. 巡视者的左边依赖于它的朝向。,Wall-tracing path,（6）Waypoint Navigation航点导航,Placing nodes Every point on the map is in the line of sight of at least one n
33、ode.,Labeling nodes,Building a path,Empty node table,Filling in the node table,Completed node table,Finding the path,小结,Random Movement Obstacle Avoidance 随机移动避开障碍物Tracing Around Obstacles 绕行障碍物Breadcrumb Pathfinding 以面包屑寻找路径Path Following 遵循路径走Wall Tracing 沿着墙走Waypoint Navigation 航点导航,思考题,在基本路径搜索中障碍物较少情况下采用了什么方式解决避开障碍物问题？为什么必须在较少障碍物情况使用这种方式？视线追踪与穿过障碍算得的直线追踪方式有何不同？哪一个更好一些？为什么？在Road Path中利用权值方式有什么好处？不使用会采用何种方式处理不同可能方向？,本次实验,设计一、二个障碍，并实现如何避开障碍寻找目标点；最好实现Tracing with line of sight,可以结合Bresenham Algorithm算法。可以尝试一下Breadcrumb Pathfinding的思想。可利用二维数组形式实现Waypoint方法。,
