人工智能課件第四次課

基本路徑搜索和航點應(yīng)用

BasicPathfindingandWaypointsAtitsmostbasiclevel,pathfindingissimplytheprocessofmovingthepositionofagamecharacterfromitsinitiallocationtoadesireddestination.基本路徑搜索是從初始位置移動到目標位置的過程。基本路徑搜索和航點應(yīng)用

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.

如何從追蹤狀態(tài)轉(zhuǎn)換為路徑搜索狀態(tài)？Onewayofaccomplishingthisistocalculatealinefromthepointthetracingstartstothedesireddestination.

解決方法-計算從追蹤開始點到目標點的直線距離。存在的問題

ProblemwithtracingDeci9改進的追蹤

Improvedtracing改進的追蹤

Improvedtracing10改進的追蹤

ImprovedtracingTracingtheoutskirtsoftheobstacleuntilthelineconnectingthestartingpointanddesireddestinationiscrossedensuresthatthepathdoesn’tloopbacktothestaringpoint.沿著障礙物外圍追蹤時，穿過障礙物連接開始點和目標點，防止追蹤路徑又回到起點。改進的追蹤

ImprovedtracingTracing11視線追蹤

Tracingwithlineofsight視線追蹤

Tracingwithlineofsigh12視線追蹤

TracingwithlineofsightWefollowtheoutskirtsoftheobstacle,butateachstepwechecktoseeifthedestinationisinthecomputer-controlledcharacter’slineofsight.

每一步檢測是否處在視線之內(nèi)。Ifso,weswitchfromatracingstatetoaline-of-sightpathfindingstate.

處在視線之內(nèi)，路徑搜索從追蹤狀態(tài)轉(zhuǎn)換為視線搜索狀態(tài)。視線追蹤

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.

設(shè)置kMaxTrailLength為玩家標記軌跡的最大步驟數(shù)。trailRow,trailColarraysstoretherowandcolumncoordinatesoftheprevious15stepstakenbytheplayer.trailRow,trailCol保存由玩家標記的15步的橫、縱坐標。變量說明#definestatementsetsthe17標記數(shù)組的初始化

Trailarrayinitializationinti;for(i=0;i<kMaxTrailLength;i++){trailRow[i]=-1;trailCol[i]=-1;}標記數(shù)組的初始化

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設(shè)置標記

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;}設(shè)置標記

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.當角色更新到新的位置時，對前一次的方向加一權(quán)值。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.

最好是能夠系統(tǒng)地遍歷整個環(huán)境。Ifthetrollalwaysmovestoitsleft,itwilldoathoroughjobofexploringitsenvironment.

設(shè)定巡視者總是向左移動。左手方法

LefthandedapproachAbett45面向玩家的右側(cè)

Facingplayer’sright面向玩家的右側(cè)

Facingplayer’sright46左手移動方法

lefthandedmovementapproachThetrollalwayswilltrytomovetoitsleftfirst.總是沿著左側(cè)移動。Ifitcan’tmovetoitsleft,itwilltrytomovestraightahead.不能轉(zhuǎn)向左側(cè)時，直行。Ifthatisblocked,itwilltrytomovetoitsrightnext.如果是障礙，移向右側(cè)。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;}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(terrain[r+1][c]==1){entityList[i].row++;entityList[i].direction=6;}}elseif(entityList[i].directio51Relativedirections

Thisrequiresbecausethetiletothetroll’sleftisdependentonthedirectionit’sfacing.

巡視者的左邊依賴于它的朝向。RelativedirectionsThisreq52Wall-tracingpathWall-tracingpath53（6）WaypointNavigation

航點導航PlacingnodesEverypointonthemapisinthelineofsightofatleastonenode.（6）WaypointNavigation

航點導航Pla54LabelingnodesLabelingnodes55BuildingapathBuildingapath56EmptynodetableEmptynodetable57FillinginthenodetableFillinginthenodetable58CompletednodetableCompletednodetable59FindingthepathFindingthepath60小結(jié)RandomMovementObstacleAvoidance隨機移動避開障礙物TracingAroundObstacles繞行障礙物BreadcrumbPathfinding以面包屑尋找路徑PathFollowing遵循路徑走WallTracing沿著墻走WaypointNavigation航點導航小結(jié)RandomMovementObstacleAvo61思考題在基本路徑搜索中障礙物較少情況下采用了什么方式解決避開障礙物問題？為什么必須在較少障礙物情況使用這種方式？視線追蹤與穿過障礙算得的直線追蹤方式有何不同？哪一個更好一些？為什么？在RoadPath中利用權(quán)值方式有什么好處？不使用會采用何種方式處理不同可能方向？思考題在基本路徑搜索中障礙物較少情況下采用了什么方式解決避開62本次實驗設(shè)計一、二個障礙，并實現(xiàn)如何避開障礙尋找目標點；最好實現(xiàn)Tracingwithlineofsight,可以結(jié)合BresenhamAlgorithm算法?？梢試L試一下BreadcrumbPathfinding的思想。可利用二維數(shù)組形式實現(xiàn)Waypoint方法。本次實驗設(shè)計一、二個障礙，并實現(xiàn)如何避開障礙尋找目標點；63基本路徑搜索和航點應(yīng)用

BasicPathfindingandWaypointsAtitsmostbasiclevel,pathfindingissimplytheprocessofmovingthepositionofagamecharacterfromitsinitiallocationtoadesireddestination.基本路徑搜索是從初始位置移動到目標位置的過程。基本路徑搜索和航點應(yīng)用

BasicPathfinding64基本路徑搜索

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

Basicpathfindingalgor65限制條件

SomelimitationsSimplepathmovementLine-of-sightpathmovement限制條件

SomelimitationsSimplepa66障礙問題

Problemswithobstacles障礙問題

Problemswithobstacles67（1）隨機運動避開障礙

RandomMovementObstacleAvoidanceRandommovementcanbeasimpleandeffectivemethodofobstacleavoidance.隨機運動能夠簡單而有效地解決避開障礙。（1）隨機運動避開障礙

RandomMovementOb68Randommovementobstacleavoidancealgorithmifplayerinlineofsight{followingstraightpathtoplayer}else{moveinrandomdirection}Randommovementobstacleavoid69（2）圍繞障礙物的追蹤

TracingAroundObstaclesThismethodcanbeeffectivewhenattemptingtofindapatharoundlargeobstacles,suchasamountainrangeinastrategyorrole-playinggame.解決圍繞大障礙物尋找路徑的問題。（2）圍繞障礙物的追蹤

TracingAroundObs70基本追蹤

BasictracingComputer-controlledcharacterItsgoal基本追蹤

BasictracingComputer-con71存在的問題

ProblemwithtracingDecidingwhentostoptracing?

什么時候停止追蹤？Weneedawaytodeterminewhenweshouldswitchfromthetracingstatebacktoasimplepathfindingstate.

如何從追蹤狀態(tài)轉(zhuǎn)換為路徑搜索狀態(tài)？Onewayofaccomplishingthisistocalculatealinefromthepointthetracingstartstothedesireddestination.

解決方法-計算從追蹤開始點到目標點的直線距離。存在的問題

ProblemwithtracingDeci72改進的追蹤

Improvedtracing改進的追蹤

Improvedtracing73改進的追蹤

ImprovedtracingTracingtheoutskirtsoftheobstacleuntilthelineconnectingthestartingpointanddesireddestinationiscrossedensuresthatthepathdoesn’tloopbacktothestaringpoint.沿著障礙物外圍追蹤時，穿過障礙物連接開始點和目標點，防止追蹤路徑又回到起點。改進的追蹤

ImprovedtracingTracing74視線追蹤

Tracingwithlineofsight視線追蹤

Tracingwithlineofsigh75視線追蹤

TracingwithlineofsightWefollowtheoutskirtsoftheobstacle,butateachstepwechecktoseeifthedestinationisinthecomputer-controlledcharacter’slineofsight.

每一步檢測是否處在視線之內(nèi)。Ifso,weswitchfromatracingstatetoaline-of-sightpathfindingstate.

處在視線之內(nèi)，路徑搜索從追蹤狀態(tài)轉(zhuǎn)換為視線搜索狀態(tài)。視線追蹤

Tracingwithlineofsigh76（3）標記路徑搜索

BreadcrumbPathfindingBreadcrumbpathfindingcanmakecomputer-controlledcharactersseemveryintelligentbecausetheplayerisunknowinglycreatingthepathforthecomputer-controlledcharacter.

帶標記的路徑搜索是玩家無意地留下軌跡。Eachtimetheplayertakesastep,heunknowinglyleavesaninvisiblemarker,orbreadcrumb,onthegameworld.

每次玩家走一步，它就留下一個不可見的標記。（3）標記路徑搜索

BreadcrumbPathfindi77BreadcrumbtrailAtrollrandomlymovesaboutthetile-basedenvironmentuntilitdetectsabreadcrumbonanadjacentlocation.BreadcrumbtrailAtrollrandom78ai_Entityclass#definekMaxTrailLength15classai_Entity{public:introw;intcol;inttype;intstate;inttrailRow[kMaxTrailLength];inttrailCol[kMaxTrailLength];ai_Entity();~ai_Entity();};ai_Entityclass#definekMaxTra79變量說明#definestatementsetsthemaximumnumberofplayerstepstotrack.

設(shè)置kMaxTrailLength為玩家標記軌跡的最大步驟數(shù)。trailRow,trailColarraysstoretherowandcolumncoordinatesoftheprevious15stepstakenbytheplayer.trailRow,trailCol保存由玩家標記的15步的橫、縱坐標。變量說明#definestatementsetsthe80標記數(shù)組的初始化

Trailarrayinitializationinti;for(i=0;i<kMaxTrailLength;i++){trailRow[i]=-1;trailCol[i]=-1;}標記數(shù)組的初始化

Trailarrayinitializ81記錄玩家的位置

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();}記錄玩家的位置

Recordingtheplayerp82if(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)83設(shè)置標記

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;}設(shè)置標記

DroppingabreadCrumbvoid84追蹤標記

FollowingthebreadcrumbsThegoalistodetermineifanyoftheeightpositionsadjacenttothecomputer-controlledtrollcontainabreadcrumb.是否在八個相鄰方向之一中有標記。追蹤標記

Followingthebreadcrumbs85Followingthebreadcrumbsfor(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(i86if((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].trailRo87if((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[88if(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)89Followingtheshortestpath{12,11,10,9,8,7,6,2}?Followingtheshortestpath{1290（4）PathFollowingItisnecessarytomovecomputer-controlledcharactersinagameenvironmentinarealisticwayeventhoughtheymightnothaveanultimatedestination.沒有目的地的移動Car-racinggame賽車

navigatearoadwaywantthecarstostayontheroad（4）PathFollowingItisnecessa91PathFollowing2-road1-outofboundsPathFollowing2-road1-outo92地域分析

TerrainanalysisWeneedtoanalyzethesurroundingterrainanddecideonthebestmove.

分析周圍的地域并決定選取最佳移動。Weexaminealleightdirectionsandtheneliminatethosethatarenotpartoftheroad.

對八個方向檢測，消除不在路上的部分。Theproblembecomesoneofdecidingwhichoftheremainingdirectionstotake.

決定選取哪一個方向移動？

地域分析

TerrainanalysisWeneed93地域分析

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;94for(j=1;j<=8;j++)if(terrainAnalysis[j]==1)terrainAnalysis[j]=0;elseterrainAnalysis[j]=10;

for(j=1;j<=8;j++)95PossibledirectionsPossibledirections96Directionanalysisif(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(entityLis97if(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)98if(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)99WeightingdirectionsThisenablesustogiveaddedweighttothepreviousdirectionwheneveritistimetoupdatethetroll’sposition.當角色更新到新的位置時，對前一次的方向加一權(quán)值。WeightingdirectionsThisenabl100ChoosingadirectionmaxTerrain=0;maxIndex=0;for(j=1;j<=8;j++)if(terrainAnalysis[j]>maxTerrain){maxTerrain=terrainAnalysis[j];maxIndex=j;}尋找最大值作為可能的方向。ChoosingadirectionmaxTerrai101更新位置

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

Updatepositionif(maxInde102if(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)103if(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)104RoadPathRoadPath105（5）WallTracingWalltracingismoreofanexplorationtechnique.It’smostusefulingameenvironmentsmadeofmanysmallrooms,althoughyoucanuseitinmaze-likegameenvironmentsaswell.

通常運用在一些小房子或迷宮游戲中。（5）WallTracingWalltracingis106WallTracingWallTracing107左手方法

LefthandedapproachAbetterapproachwouldbetomakethetrollsystematicallyexploretheentireenvironment.

最好是能夠系統(tǒng)地遍歷整個環(huán)境。Ifthetrollalwaysmovestoitsleft,itwilldoathoroughjobofexploringitsenvironment.

設(shè)定巡視者總是向左移動。左手方法

LefthandedapproachAbett108面向玩家的右側(cè)

Facingplayer’sright面向玩家的右側(cè)

Facingplayer’sright109左手移動方法

lefthandedmovementapproachThetrol