人工智能课件第四次课

基本路径搜索和航点应用

BasicPathfindingandWaypointsAtitsmostbasiclevel,pathfindingissimplytheprocessofmovingthepositionofagamecharacterfromitsinitiallocationtoadesireddestination.基本路径搜索是从初始位置移动到目标位置的过程。基本路径搜索和航点应用

BasicPathfinding1基本路径搜索

Basicpathfindingalgorithmif(positionX>destinationX)positionX--;elseif(positionX<destinationX)positionX++;if(positionY>destinationY)positionY--；elseif(positionY<destinationY)positionY++;基本路径搜索

Basicpathfindingalgor2限制条件

SomelimitationsSimplepathmovementLine-of-sightpathmovement限制条件

SomelimitationsSimplepa3障碍问题

Problemswithobstacles障碍问题

Problemswithobstacles4（1）随机运动避开障碍

RandomMovementObstacleAvoidanceRandommovementcanbeasimpleandeffectivemethodofobstacleavoidance.随机运动能够简单而有效地解决避开障碍。（1）随机运动避开障碍

RandomMovementOb5Randommovementobstacleavoidancealgorithmifplayerinlineofsight{followingstraightpathtoplayer}else{moveinrandomdirection}Randommovementobstacleavoid6（2）围绕障碍物的追踪

TracingAroundObstaclesThismethodcanbeeffectivewhenattemptingtofindapatharoundlargeobstacles,suchasamountainrangeinastrategyorrole-playinggame.解决围绕大障碍物寻找路径的问题。（2）围绕障碍物的追踪

TracingAroundObs7基本追踪

BasictracingComputer-controlledcharacterItsgoal基本追踪

BasictracingComputer-con8存在的问题

ProblemwithtracingDecidingwhentostoptracing?

什么时候停止追踪？Weneedawaytodeterminewhenweshouldswitchfromthetracingstatebacktoasimplepathfindingstate.

如何从追踪状态转换为路径搜索状态？Onewayofaccomplishingthisistocalculatealinefromthepointthetracingstartstothedesireddestination.

解决方法-计算从追踪开始点到目标点的直线距离。存在的问题

ProblemwithtracingDeci9改进的追踪

Improvedtracing改进的追踪

Improvedtracing10改进的追踪

ImprovedtracingTracingtheoutskirtsoftheobstacleuntilthelineconnectingthestartingpointanddesireddestinationiscrossedensuresthatthepathdoesn’tloopbacktothestaringpoint.沿着障碍物外围追踪时，穿过障碍物连接开始点和目标点，防止追踪路径又回到起点。改进的追踪

ImprovedtracingTracing11视线追踪

Tracingwithlineofsight视线追踪

Tracingwithlineofsigh12视线追踪

TracingwithlineofsightWefollowtheoutskirtsoftheobstacle,butateachstepwechecktoseeifthedestinationisinthecomputer-controlledcharacter’slineofsight.

每一步检测是否处在视线之内。Ifso,weswitchfromatracingstatetoaline-of-sightpathfindingstate.

处在视线之内，路径搜索从追踪状态转换为视线搜索状态。视线追踪

Tracingwithlineofsigh13（3）标记路径搜索

BreadcrumbPathfindingBreadcrumbpathfindingcanmakecomputer-controlledcharactersseemveryintelligentbecausetheplayerisunknowinglycreatingthepathforthecomputer-controlledcharacter.

带标记的路径搜索是玩家无意地留下轨迹。Eachtimetheplayertakesastep,heunknowinglyleavesaninvisiblemarker,orbreadcrumb,onthegameworld.

每次玩家走一步，它就留下一个不可见的标记。（3）标记路径搜索

BreadcrumbPathfindi14BreadcrumbtrailAtrollrandomlymovesaboutthetile-basedenvironmentuntilitdetectsabreadcrumbonanadjacentlocation.BreadcrumbtrailAtrollrandom15ai_Entityclass#definekMaxTrailLength15classai_Entity{public:introw;intcol;inttype;intstate;inttrailRow[kMaxTrailLength];inttrailCol[kMaxTrailLength];ai_Entity();~ai_Entity();};ai_Entityclass#definekMaxTra16变量说明#definestatementsetsthemaximumnumberofplayerstepstotrack.

设置kMaxTrailLength为玩家标记轨迹的最大步骤数。trailRow,trailColarraysstoretherowandcolumncoordinatesoftheprevious15stepstakenbytheplayer.trailRow,trailCol保存由玩家标记的15步的横、纵坐标。变量说明#definestatementsetsthe17标记数组的初始化

Trailarrayinitializationinti;for(i=0;i<kMaxTrailLength;i++){trailRow[i]=-1;trailCol[i]=-1;}标记数组的初始化

Trailarrayinitializ18记录玩家的位置

Recordingtheplayerpositionsvoidai_World::KeyDown(intkey){inti;if(key==kUpKey)for(i=0;i<kMaxEntities;i++)if(entityList[i].state==kPlayer)if(entityList[i].row>0){entityList[i].row--;DropBreadCrumb();}

if(key==kDownKey)for(i=0;i<kMaxEntities;i++)if(entityList[i].state==kPlayer)if(entityList[i].row==kMaxRows-1){entityList[i].row++;DropBreadCrumb();}记录玩家的位置

Recordingtheplayerp19if(key==kLeftKey)for(i=0;i<kMaxEntities;i++)if(entityList[i].state==kPlayer)if(entityList[i].col>0){entityList[i].col--;DropBreadCrumb();}if(key==kRightKey)for(i=0;i<kMaxEntities;i++)if(entityList[i].state==kPlayer)if(entityList[i].col<kMaxCols-1){entityList[i].col++;DropBreadCrumb();}}if(key==kLeftKey)20设置标记

DroppingabreadCrumbvoidai_World::DropBreadCrumb(void){inti;for(i=kMaxTrailLength-1;i--){entityList[0].trailRow[i]=entityList[0].trailRow[i-1];entityList[0].trailCol[i]=entityList[0].trailCol[i-1];}entityList[0].trailRow[0]=entityList[0].row;entityList[0].trailCol[0]=entityList[0].Col;}设置标记

DroppingabreadCrumbvoid21追踪标记

FollowingthebreadcrumbsThegoalistodetermineifanyoftheeightpositionsadjacenttothecomputer-controlledtrollcontainabreadcrumb.是否在八个相邻方向之一中有标记。追踪标记

Followingthebreadcrumbs22Followingthebreadcrumbsfor(i=0;i<kMaxEntities;i++){r=entityList[i].row;c=entityList[i].col;foundCrumb=-1;for(j=0;j<kMaxTrailLength;j++){if((r==entityList[0].trailRow[j])&&(c==entityList[0].trailCol[j])){foundCrumb=j;break;}

Followingthebreadcrumbsfor(i23if((r-1==entityList[0].trailRow[j])&&(c-1==entityList[0].trailCol[j])){foundCrumb=j;break;}if((r-1==entityList[0].trailRow[j])&&(c==entityList[0].trailCol[j])){foundCrumb=j;break;}if((r-1==entityList[0].trailRow[j])&&(c+1==entityList[0].trailCol[j])){foundCrumb=j;break;}if((r==entityList[0].trailRow[j])&&(c-1==entityList[0].trailCol[j])){foundCrumb=j;break;}if((r-1==entityList[0].trailRo24if((r==entityList[0].trailRow[j])&&(c+1==entityList[0].trailCol[j])){foundCrumb=j;break;}if((r+1==entityList[0].trailRow[j])&&(c-1==entityList[0].trailCol[j])){foundCrumb=j;break;}if((r+1==entityList[0].trailRow[j])&&(c==entityList[0].trailCol[j])){foundCrumb=j;break;}if((r+1==entityList[0].trailRow[j])&&(c+1==entityList[0].trailCol[j])){foundCrumb=j;break;}}if((r==entityList[0].trailRow[25if(foundCrumb>=0){entityList[i].row=entityList[0].trailRow[foundCrumb];entityList[i].col=entityList[0].trailCol[foundCrumb];}else{entityList[i].row=entityList[0].row+Rnd(0,2)-1;entityList[i].col=entityList[0].col+Rnd(0,2)-1;}if(entityList[i].row<0)entityList[i].row=0;if(entityList[i].col<0)entityList[i].col=0;if(entityList[i].row>=kMaxRows)entityList[i].row=kMaxRows-1;if(entityList[i].col>=kMaxCols)entityList[i].col=kMaxCols-1;}if(foundCrumb>=0)26Followingtheshortestpath{12,11,10,9,8,7,6,2}?Followingtheshortestpath{1227（4）PathFollowingItisnecessarytomovecomputer-controlledcharactersinagameenvironmentinarealisticwayeventhoughtheymightnothaveanultimatedestination.没有目的地的移动Car-racinggame赛车

navigatearoadwaywantthecarstostayontheroad（4）PathFollowingItisnecessa28PathFollowing2-road1-outofboundsPathFollowing2-road1-outo29地域分析

TerrainanalysisWeneedtoanalyzethesurroundingterrainanddecideonthebestmove.

分析周围的地域并决定选取最佳移动。Weexaminealleightdirectionsandtheneliminatethosethatarenotpartoftheroad.

对八个方向检测，消除不在路上的部分。Theproblembecomesoneofdecidingwhichoftheremainingdirectionstotake.

决定选取哪一个方向移动？

地域分析

TerrainanalysisWeneed30地域分析

Terrainanalysisintr;intc;intterrainAnalysis[9];r=entityList[i].row;c=entityList[i].col;terrainAnalysis[1]=terrain[r-1][c-1];terrainAnalysis[2]=terrain[r-1][c];terrainAnalysis[3]=terrain[r-1][c+1];terrainAnalysis[4]=terrain[r][c+1];terrainAnalysis[5]=terrain[r+1][c+1];terrainAnalysis[6]=terrain[r+1][c];terrainAnalysis[7]=terrain[r+1][c-1];terrainAnalysis[8]=terrain[r][c-1];地域分析

Terrainanalysisintr;31for(j=1;j<=8;j++)if(terrainAnalysis[j]==1)terrainAnalysis[j]=0;elseterrainAnalysis[j]=10;

for(j=1;j<=8;j++)32PossibledirectionsPossibledirections33Directionanalysisif(entityList[i].direction==1){terrainAnalysis[1]=terrainAnalysis[1]+2;terrainAnalysis[2]++;terrainAnalysis[5]--;terrainAnalysis[8]++;}if(entityList[i].direction==2){terrainAnalysis[1]++;terrainAnalysis[2]=terrainAnalysis[2]+2;terrainAnalysis[3]++;terrainAnalysis[6]--;}Directionanalysisif(entityLis34if(entityList[i].direction==3){terrainAnalysis[2]++;terrainAnalysis[3]=terrainAnalysis[3]+2;terrainAnalysis[4]++;terrainAnalysis[7]--;}if(entityList[i].direction==4){terrainAnalysis[3]++;terrainAnalysis[4]=terrainAnalysis[4]+2;terrainAnalysis[5]++;terrainAnalysis[7]--;}if(entityList[i].direction==5){terrainAnalysis[4]++;terrainAnalysis[5]=terrainAnalysis[5]+2;terrainAnalysis[6]++;terrainAnalysis[8]--;}if(entityList[i].direction==3)35if(entityList[i].direction==6){terrainAnalysis[2]--;terrainAnalysis[5]++;terrainAnalysis[6]=terrainAnalysis[6]+2;terrainAnalysis[7]++;}if(entityList[i].direction==7){terrainAnalysis[3]--;terrainAnalysis[6]++;terrainAnalysis[7]=terrainAnalysis[7]+2;terrainAnalysis[8]++;}if(entityList[i].direction==8){terrainAnalysis[1]++;terrainAnalysis[4]--;terrainAnalysis[7]++;terrainAnalysis[8]=terrainAnalysis[8]+2;}if(entityList[i].direction==6)36WeightingdirectionsThisenablesustogiveaddedweighttothepreviousdirectionwheneveritistimetoupdatethetroll’sposition.当角色更新到新的位置时，对前一次的方向加一权值。WeightingdirectionsThisenabl37ChoosingadirectionmaxTerrain=0;maxIndex=0;for(j=1;j<=8;j++)if(terrainAnalysis[j]>maxTerrain){maxTerrain=terrainAnalysis[j];maxIndex=j;}寻找最大值作为可能的方向。ChoosingadirectionmaxTerrai38更新位置

Updatepositionif(maxIndex==1){entityList.direction=1;entityList[i].row--;entityList[i].col--;}if(maxIndex==2){entityList.direction=2;entityList[i].row--;}更新位置

Updatepositionif(maxInde39if(maxIndex==3){entityList.direction=3;entityList[i].row--;entityList[i].col++;}if(maxIndex==4){entityList.direction=2;entityList[i].col++;}if(maxIndex==5){entityList.direction=5;entityList[i].row++;entityList[i].col++;}if(maxIndex==3)40if(maxIndex==6){entityList.direction=6;entityList[i].row++;}if(maxIndex==7){entityList.direction=6;entityList[i].row++;entityList[i].col--;}if(maxIndex==8){entityList.direction=8;entityList[i].col--;}if(maxIndex==6)41RoadPathRoadPath42（5）WallTracingWalltracingismoreofanexplorationtechnique.It’smostusefulingameenvironmentsmadeofmanysmallrooms,althoughyoucanuseitinmaze-likegameenvironmentsaswell.

通常运用在一些小房子或迷宫游戏中。（5）WallTracingWalltracingis43WallTracingWallTracing44左手方法

LefthandedapproachAbetterapproachwouldbetomakethetrollsystematicallyexploretheentireenvironment.

最好是能够系统地遍历整个环境。Ifthetrollalwaysmovestoitsleft,itwilldoathoroughjobofexploringitsenvironment.

设定巡视者总是向左移动。左手方法

LefthandedapproachAbett45面向玩家的右侧

Facingplayer’sright面向玩家的右侧

Facingplayer’sright46左手移动方法

lefthandedmovementapproachThetrollalwayswilltrytomovetoitsleftfirst.总是沿着左侧移动。Ifitcan’tmovetoitsleft,itwilltrytomovestraightahead.不能转向左侧时，直行。Ifthatisblocked,itwilltrytomovetoitsrightnext.如果是障碍，移向右侧。Ifthatisblocked,itwillreversedirection.

如果是障碍，移向相反方向。左手移动方法

lefthandedmovementapp47Left-handedmovementr=entityList[i].row;c=entityList[i].col;if(entityList[i].direction==4){if(terrain[r-1][c]==1){entityList[i].row--;entityList[i].direction=2;}elseif(terrain[r][c+1]==1){entityList[i].col++;entityList[i].direction=4;}

elseif(terrain[r+1][c]==1){entityList[i].row++;entityList[i].direction=6;}elseif(terrain[r][c-1]==1){entityList[i].col--;entityList[i].direction=8;}}Left-handedmovementr=entityLi48elseif(entityList[i].direction==6){if(terrain[r][c+1]==1){entityList[i].col++;entityList[i].direction=4;}elseif(terrain[r+1][c]==1){entityList[i].row++;entityList[i].direction=6;}

elseif(terrain[r][c-1]==1){entityList[i].col--;entityList[i].direction=8;}elseif(terrain[r-1][c]==1){entityList[i].row--;entityList[i].direction=2;}}elseif(entityList[i].directio49elseif(entityList[i].direction==8){if(terrain[r+1][c]==1){entityList[i].row++;entityList[i].direction=6;}elseif(terrain[r][c-1]==1){entityList[i].col--;entityList[i].direction=8;}

elseif(terrain[r-1][c]==1){entityList[i].row--;entityList[i].direction=2;}elseif(terrain[r][c+1]==1){entityList[i].col++;entityList[i].direction=4;}}elseif(entityList[i].directio50elseif(entityList[i].direction==2){if(terrain[r][c-1]==1){entityList[i].col--;entityList[i].direction=8;}e