基本路径搜索和航点应用 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(positionXdestinationY) 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. 随机运动能够简单而有效地解决避开障碍。,Random movement obstacle avoidance algorithm,if player in line of sight following straight path to player else 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 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 way 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 ensures 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 sight. 每一步检测是否处在视线之内。 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-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 adjacent location.,ai_Entity class,#define kMaxTrailLength 15 class 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, 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_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(); ,if(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(); ,设置标记 Dropping a breadCrumb,void 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; ,追踪标记 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,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.trailColfoundCrumb; 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 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 ana