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 algorithmif(positionXdestinationX) positionX-;else if(po
2、sitionXdestinationY) positionY-；else if(positionYdestinationY) positionY+;限制条件Some limitationsSimple path movementLine-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 algorithmif 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 strategy
4、 or role-playing game. 解决围绕大障碍物寻找路径的问题。基本追踪Basic tracingComputer-controlled characterIts 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 way of acc
5、omplishing 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 ensures that th
6、e 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 sight. 每一步检测是
7、否处在视线之内。 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 computer-con
8、trolled character. 带标记的路径搜索是玩家无意地留下轨迹。 Each time the player takes a step, he unknowingly leaves an invisible marker, or breadcrumb, on the game world. 每次玩家走一步，它就留下一个不可见的标记。Breadcrumb trailA troll randomly moves about the tile-based environment until it detects a breadcrumb on an adjacent location.ai
9、_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为玩家标记轨迹的最大步骤数。 trailRow,
10、trailCol arrays store the row and column coordinates of the previous 15 steps taken by the player. trailRow, trailCol保存由玩家标记的15步的横、纵坐标。标记数组的初始化Trail array initializationint i;for(i=0; ikMaxTrailLength; i+) trailRowi=-1; trailColi=-1;记录玩家的位置Recording the player positionsvoid ai_World:KeyDown(int key)
11、 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(); if(key=kRightKey) for
12、(i=0; ikMaxEntities;i+) if(entityListi.state=kPlayer) if(entityListi.colkMaxCols-1) entityListi.col+; DropBreadCrumb(); 设置标记Dropping a breadCrumbvoid ai_World:DropBreadCrumb(void) int i; for(i=kMaxTrailLength-1;i-) entityList0.trailRowi=entityList0.trailRowi-1; entityList0.trailColi=entityList0.trai
13、lColi-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 breadcrumbsfor(i=0; ikMaxEntities;i
14、+) 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(
15、entityListi.col=kMaxRows) entityListi.row=kMaxRows-1;if(entityListi.col=kMaxCols) entityListi.col=kMaxCols-1;Following the shortest path12,11,10,9,8,7,6,2（4）Path Following It is necessary to move computer-controlled characters in a game environment in a realistic way even though they might not have
16、an ultimate destination.没有目的地的移动 Car-racing game 赛车 navigate a roadway want the cars to stay on the roadPath Following2-road 1-out of bounds地域分析Terrain analysis W e need to analyze the surrounding terrain and decide on the best move. 分析周围的地域并决定选取最佳移动。 We examine all eight directions and then elimina
17、te those that are not part of the road. 对八个方向检测，消除不在路上的部分。 The problem becomes one of deciding which of the remaining directions to take. 决定选取哪一个方向移动？ 地域分析Terrain analysisint r;int c;int terrainAnalysis9;r=entityListi.row;c=entityListi.col;terrainAnalysis1=terrainr-1c-1;terrainAnalysis2=terrainr-1c;
18、terrainAnalysis3=terrainr-1c+1;terrainAnalysis4=terrainrc+1;terrainAnalysis5=terrainr+1c+1;terrainAnalysis6=terrainr+1c;terrainAnalysis7=terrainr+1c-1;terrainAnalysis8=terrainrc-1;for(j=1;j=8;j+) if(terrainAnalysisj=1) terrainAnalysisj=0; else terrainAnalysisj=10; Possible directionsDirection analys
19、isif(entityListi.direction=1) terrainAnalysis1=terrainAnalysis1+2; terrainAnalysis2+; terrainAnalysis5-; terrainAnalysis8+;if(entityListi.direction=2) terrainAnalysis1+; terrainAnalysis2= terrainAnalysis2+2; terrainAnalysis3+; terrainAnalysis6-;if(entityListi.direction=3) terrainAnalysis2+; terrainA
20、nalysis3= terrainAnalysis3+2; terrainAnalysis4+; terrainAnalysis7-;if(entityListi.direction=4) terrainAnalysis3+; terrainAnalysis4= terrainAnalysis4+2; terrainAnalysis5+; terrainAnalysis7-;if(entityListi.direction=5) terrainAnalysis4+; terrainAnalysis5= terrainAnalysis5+2; terrainAnalysis6+; terrain
21、Analysis8-;if(entityListi.direction=6) terrainAnalysis2-; terrainAnalysis5+; terrainAnalysis6= terrainAnalysis6+2; terrainAnalysis7+;if(entityListi.direction=7) terrainAnalysis3-; terrainAnalysis6+; terrainAnalysis7= terrainAnalysis7+2; terrainAnalysis8+;if(entityListi.direction=8) terrainAnalysis1+
22、; terrainAnalysis4-; terrainAnalysis7+; terrainAnalysis8=terrainAnalysis8+2;Weighting directionsThis enables us to give added weight to the previous direction whenever it is time to update the trolls position.当角色更新到新的位置时，对前一次的方向加一权值。Choosing a direction maxTerrain=0;maxIndex=0;for(j=1;jmaxTerrain) m
23、axTerrain=terrainAnalysisj; maxIndex=j; 寻找最大值作为可能的方向。更新位置Update positionif(maxIndex=1) entityList.direction=1; entityListi.row-; entityListi.col-;if(maxIndex=2) entityList.direction=2; entityListi.row-;if(maxIndex=3) entityList.direction=3; entityListi.row-; entityListi.col+;if(maxIndex=4) entityLis
24、t.direction=2; entityListi.col+;if(maxIndex=5) entityList.direction=5; entityListi.row+; entityListi.col+;if(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-;Road Pat
25、h（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 environments as well. 通常运用在一些小房子或迷宫游戏中。Wall Tracing左手方法Lefthanded approach A better approach would be to make the troll systemat
26、ically explore the entire environment. 最好是能够系统地遍历整个环境。 If the troll always moves to its left, it will do a thorough job of exploring its environment. 设定巡视者总是向左移动。面向玩家的右侧Facing players right左手移动方法lefthanded movement approach The troll always will try to move to its left first.总是沿着左侧移动。 If it cant mov
27、e 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. 如果是障碍，移向相反方向。Left-handed movementr=entityListi.row;c=entityListi.col;if(entityListi.direction=4) if(terrainr-1c=1) entit
28、yListi.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; else if(entityListi.direction=6) if(terrainrc+1=1) entityListi.c
29、ol+; 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.direction=8) if(terrainr+1c=1) entityListi.row+; ent
30、ityListi.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.direction=2) if(terrainrc-1=1) entityListi.col-; entityListi
31、.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; Relative directions This requires because the tile to the trolls left is dependent on th
32、e 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 node.Labeling nodesBuilding a pathEmpty node tableFilling in the node tableCompleted node tableFinding the path小结 Random Movement Obstacle Av
33、oidance 随机移动避开障碍物 Tracing Around Obstacles 绕行障碍物 Breadcrumb Pathfinding 以面包屑寻找路径 Path Following 遵循路径走 Wall Tracing 沿着墙走 Waypoint Navigation 航点导航思考题 在基本路径搜索中障碍物较少情况下采用了什么方式解决避开障碍物问题？为什么必须在较少障碍物情况使用这种方式？ 视线追踪与穿过障碍算得的直线追踪方式有何不同？哪一个更好一些？为什么？ 在Road Path中利用权值方式有什么好处？不使用会采用何种方式处理不同可能方向？本次实验 设计一、二个障碍，并实现如何避开障碍寻找目标点； 最好实现Tracing with line of sight,可以结合Bresenham Algorithm算法。 可以尝试一下Breadcrumb Pathfinding的思想。 可利用二维数组形式实现Waypoint方法。
