基本路徑搜索和航點應用

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