簡單的尋路演算法

❶ 游戲中的常用的尋路演算法有哪些

f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點，
直到最終達到目的結點
– A*演算法的成功很大程度依賴於h(n)函數的構建
?;) = g(n? 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
A*演算法
? h(n) = 從結點n到目的結點的耗費評估值，啟發函數
?，程序返回n
else 生成結點n的每一個後繼結點n;
foreach 結點n的後繼結點n;{
將n』的父結點設置為n
計算啟發式評估函數h(n『)值，評估從n『到node_goal的費用
計算g(n『) = g(n) + 從n』到n的開銷
計算f(n?? 在演算法啟動時，Closed列表為空 A* 演算法偽代碼初始化OPEN列表
初始化CLOSED列表
創建目的結點；稱為node_goal
創建起始結點；稱為node_start
將node_start添加到OPEN列表
while OPEN列表非空{
從OPEN列表中取出f(n)值最低的結點n
將結點n添加到CLOSED列表中
if 結點n與node_goal相等then 我們找到了路徑;)
if n『位於OPEN或者CLOSED列表and 現有f(n)較優then丟棄n』 ;) + h(n?? 包含我們還沒有處理到的結點
? g(n) = 從初始結點到結點n的耗費
?? 包含我們已經處理過的結點
，處理後繼n』
將結點n『從OPEN和CLOSED中刪除
添加結點n『到OPEN列表
}
}
return failure （我們已經搜索了所有的結點?? 啟發式搜索
– 在搜索中涉及到三個函數
??? 我們最開始將起始結點放入到Open列表中
– Closed列表
?

❷ 模擬游戲一般用什麼演算法

用尋路演算法。
1.小型游戲可以用的簡單的尋路演算法；
2.隨機尋路演算法:當NPC不管是遇到障礙物還是遇到了邊界(利用碰撞檢測),都會隨機選取一個前進的方向,繼續行走
3.跟蹤演算法:當游戲中的主角進入到NPC 的「警戒區域」後,游戲的AI 可輕易獲得目
4.大型游戲一般使用A*尋路演算法:使用最廣泛的一種尋路演算法,簡單說一下A*尋路演算法；
5.DFS、BFS也常用於求最優方法這類問題。

❸ 即時戰略游戲中實用的尋路演算法都有哪些

Potential Field，它是將地圖用一個矩陣來表示，矩陣儲存著大小不同的電勢（整數）。例如，正電勢表示吸引，負電勢表示排斥。而游戲中的單位本身是一個負電勢，游戲以一個數組儲存所有單位的電勢和位置。這樣，在計算一個單位需要怎麼從A點到B點時，我們可以用一個新的矩陣將目的地B點設成正電勢，並以不同方式（如圓形、四邊形等）輻射開來，離B點越遠電勢越低，直到0。然後將地圖矩陣，目的地矩陣，和所有單位數組的電勢相加，得出一個新的、反映當前游戲世界的電勢矩陣，然後單位再選擇周圍所有電勢點中的最高電勢點去走。不過這里坑很多，因為它本質上是Greedy Algorithm，所以它未必能找出解。然而在某些設定中，例如在沒有過於復雜地形，並且需要單位自動不相互覆蓋的情況下，Potential Field還是可以完成任務。

Flocking Behavior，在對於一大群單位的尋路，計算量是很大的，而且往往會有很多的重復，這些都是可以避免的。如果單位的移動是利用Steering Behavior來實現的話，那麼就可以為其中一個單位，稱之為Leader，計算路徑（例如用導航網格），然後其他單位按照以下Flocking原則來移動：1. 分離，避開相鄰單位2. 一致，和整體的移動方向一致，這里應該是Leader的移動方向3. 聚合，向整體的平均位置靠攏這樣的話，就可以降低尋路的計算量，並且得到更加真實的群體單位行進效果。

❹ 星際爭霸2的尋路演算法思路是怎樣的

首先地圖整體開始前，會用多層可達矩陣演算法，算出路徑關鍵點
2，創建關鍵節點可達矩陣
3，再每個兵當前位置對關鍵節點進行路徑計算
這樣可以最小化資源佔用就可以完成路徑計算了，高數的離散數學，挺容易解的

❺ A* 尋路演算法

A*演算法
�6�1 啟發式搜索
– 在搜索中涉及到三個函數
�6�1 g(n) = 從初始結點到結點n的耗費
�6�1 h(n) = 從結點n到目的結點的耗費評估值，啟發函數
�6�1 f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點，
直到最終達到目的結點
– A*演算法的成功很大程度依賴於h(n)函數的構建
�6�1 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
�6�1 包含我們還沒有處理到的結點
�6�1 我們最開始將起始結點放入到Open列表中
– Closed列表
�6�1 包含我們已經處理過的結點
�6�1 在演算法啟動時，Closed列表為空 A* 演算法偽代碼初始化OPEN列表
初始化CLOSED列表
創建目的結點；稱為node_goal
創建起始結點；稱為node_start
將node_start添加到OPEN列表
while OPEN列表非空{
從OPEN列表中取出f(n)值最低的結點n
將結點n添加到CLOSED列表中
if 結點n與node_goal相等then 我們找到了路徑，程序返回n
else 生成結點n的每一個後繼結點n'
foreach 結點n的後繼結點n'{
將n』的父結點設置為n
計算啟發式評估函數h(n『)值，評估從n『到node_goal的費用
計算g(n『) = g(n) + 從n』到n的開銷
計算f(n') = g(n') + h(n')
if n『位於OPEN或者CLOSED列表and 現有f(n)較優then丟棄n』 ，處理後繼n』
將結點n『從OPEN和CLOSED中刪除
添加結點n『到OPEN列表
}
}
return failure （我們已經搜索了所有的結點，但是仍然沒有找到一條路徑）

❻ 游戲尋路演算法

1.四種演算法是DFS,BFS,Heuristic DFS, Heuristic BFS 這是建立在VC基礎上的

2.高數和線代是必須的，還牽涉到數分和運籌學的知識

❼ C++尋路演算法

迷宮尋找路徑要不。。。。。。#include <iostream>
#include<iomanip>
using namespace std;
#define M 10
#define N 10
typedef enum{X=0,up,dn,rt,lt} tDir; //搜索方向
class Migong
{
public:
int tag; /*0 1*/
tDir comeDir; /*退回*/
int up,rt,dn,lt; //方向
int back;
};int m[M][N]={ //初始化通道數據
{0,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,0,0,0,1,0,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,1,1},
{1,0,1,1,1,0,1,0,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,0,0,1,1,0,1,0,1},
{1,1,1,1,1,1,0,1,0,1},
{1,1,1,1,1,1,1,1,0,0},
}; int ini=0,inj=0; //入點
int outi=9,outj=9; //出口
int cnt=0; //從入口到出口需多少步
int path[M][N]; //記錄找到路徑後的迷宮
Migong maze[10][10]; void initmaze(Migong mz[][10]) //初始化迷宮數據
{
int i;
int j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
mz[i][j].tag=m[i][j];
mz[i][j].comeDir=X;
mz[i][j].up=0;
mz[i][j].dn=0;
mz[i][j].rt=0;
mz[i][j].lt=0;
mz[i][j].back=0;
}
}int find(Migong mz[][10],int i,int j,tDir dir) //搜索路徑
{
if(i==outi&&j==outj)
return 1; ////if 當前節點是出口 then return 1;
if(dir!=X) //if 不是是回退到本節點,then 記錄來的方向 根據來的方向設定其相對方向已走
{
mz[i][j].comeDir=dir;
if(dir==up)
mz[i][j].dn=1; //向N方向沒有走&&可以走，則向N遞歸走
if(dir==dn)
mz[i][j].up=1; //向E方向沒有走&&可以走，則向N遞歸走
if(dir==rt)
mz[i][j].lt=1; //向S方向沒有走&&可以走，則向N遞歸走
if(dir==lt)
mz[i][j].rt=1; //向W方向沒有走&&可以走，則向N遞歸走
}
if(mz[i][j].up==0) //if 向up方向沒走&&不越界&&可以走 則向up遞歸走
{
int ni;
int nj;
mz[i][j].up=1; //記錄本節點
ni=i-1;
nj=j; //ni,nj表示i,j的上一個坐標
if(ni>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,up))
return 1;
}
if(mz[i][j].dn==0) //if 向dn方向沒走&&不越界&&可以走 則向dn遞歸走
{
int ni;
int nj;
mz[i][j].dn=1; //記錄本節點
ni=i+1;
nj=j; //ni,nj表示i,j的下一個坐標
if(ni<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,dn))
return 1;
}
if(mz[i][j].rt==0) //if 向rt方向沒走&&不越界&&可以走 則向rt遞歸走
{
int ni;
int nj;
mz[i][j].rt=1; //記錄本節點
ni=i;
nj=j+1; //ni,nj表示i,j的右一個坐標
if(nj<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,rt))
return 1;
}
if(mz[i][j].lt==0) //if 向lt方向沒走&&不越界&&可以走 則向lt遞歸走
{
int ni;
int nj;
mz[i][j].lt=1; //記錄本節點
ni=i;
nj=j-1; //ni,nj表示i,j的左一個坐標
if(nj>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,lt))
return 1;
}

//四個方向都走完了還沒有結果

if(i==ini && j==inj) // if 是入口 return 0
return 0;
else // else 則回退
{
mz[i][j].back=1;
if(mz[i][j].comeDir=up) //如果回退的值等於up的值，則向up方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j; //ni,nj表示i,j的下一個坐標
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=dn) //如果回退的值等於dn的值，則向dn方向搜索
{
int ni;
int nj;
ni=i-1;
nj=j; //ni,nj表示i,j的上一個坐標
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=rt) //如果回退的值等於rt的值，則向rt方向搜索
{
int ni;
int nj;
ni=i;
nj=j-1; //ni,nj表示i,j的左一個坐標
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=lt) //如果回退的值等於lt的值，則向lt方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j+1; //ni,nj表示i,j的左下角一個坐標
if(find(maze,ni,nj,X))
return 1;
}
}
return 0;
}int onway( Migong nd) //判斷點是否在路徑上
{
if(nd.tag!=0)
return 0; //牆
if(nd.up==0&&nd.dn==0&&nd.rt==0&&nd.lt==0)
return 0; //沒訪問過
if(nd.up==1&&nd.dn==1&&nd.rt==1&&nd.lt==1&&nd.back==1)
return 0; //訪問過但不通
return 1;
}//列印
void print( Migong mz[][10]) //列印原迷宮
{
int i;
int j;
cout<<"0表示可通過，1表示牆"<<endl;
cout<<"-------------------------------";
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)

cout<<mz[i][j].tag;
cout<<" ▎"<<endl;

}
cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print1( Migong mz[][10]) //列印含路徑迷宮
{
int i;
int j;
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;

for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)
{
if(i==9 && j==9) //出口
{
cnt++;
cout<<"*";
path[i][j]=0;
}
else
if(onway(mz[i][j]))
{
cout<<"*"; //*表示路徑
cnt++;
path[i][j];
}
else
{
cout<<mz[i][j].tag;
path[i][j]=1; //path[i][j]=0表示可通過，path[i][j]=1表示牆
} }
cout<<" ▎"<<endl;
}cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print2( Migong mz[][10]) //列印路徑坐標
{
int i;
int j;
int di;
int dj; //di,dj的值為-1，0，1，為了搜索坐標i,j附近的坐標
int pi;
int pj; //pi,pj為上一個路徑坐標
int r;
int count; //統計輸出了多少個坐標
i=0;
j=0;
pi=1;
pj=0;
count=0; cout<<endl<<"路徑坐標為:"<<endl<<endl;
for(r=0;r<cnt;r++)
{
if(i>=10 || j>=10) //i,j的值不可能大於10
continue;
else
{
for(di=-1;di<2;di++)
for(dj=-1;dj<2;dj++)
{
if(di==dj ) //path[i][j]的下一步不可能在它的左上角和右下角
continue;
if(di==1 && dj==-1) //path[i][j]的下一步不可能在它的左下角
continue;
if(di==-1 && dj==1) //path[i][j]的下一步不可能在它的右上角
continue;
if((i+di)<0 ||(j+dj)<0) //i+di,j+dj小於0時不符
continue;
if(path[i+di][j+dj]!=0) //i+di,j+dj不是路徑上的坐標
continue;
if((i+di)==i && (j+dj)==j ) //path[i][j]的下一步不可能是它本身
continue;
else
if((i+di)==pi && (j+dj)==pj) //path[i][j]的下一步不可能是它的上一步
continue;
else
{if(i==9&&j==9)<br> cout<<"(9,9)";<br> else<br> {<br> <br> cout<<"("<<i<<","<<j<<")"<<"->";<br> count++;<br> if(count%5==0)<br> cout<<endl;<br> }
pi=i;
pj=j;
i=i+di;
j=j+dj; }
}
}
}
}int main()
{
initmaze(maze); //初始化迷宮
cout<<endl<<endl<<"原迷宮如下："<<endl;
print(maze); //列印原迷宮
if (find(maze,ini,inj,rt)) //如果迷宮有路徑
{

cout<<"-------------------------------";
cout<<endl<<"含路徑的迷宮,*表示通道"<<endl;
cout<<"-------------------------------";
print1(maze); // 輸出含路徑的迷宮
cout<<endl<<"-------------------------------"<<endl;
print2(maze); //輸出路徑坐標
}
else
cout<<"no way!"; //如果迷宮沒路徑，輸出no way
cout<<endl<<endl<<endl;
cout<<"從入口到出口需"<<cnt<<"步";
cout<<endl<<endl;
return 0;
}