尋路演算法
Ⅰ 游戲中的常用的尋路演算法有哪些
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列表
?
Ⅱ 有關A* 尋路演算法。 看了這個演算法 大致都明白。就是有點不大清楚。
1. B的G值是指從起點A開始，到達該點的最短距離，和B在不在最短路徑上沒有關系。
2. 不是遍歷所有路徑，而是所有點。對於m*n的矩陣， 遍歷所有點的復雜度是m*n（多項式復雜度），而遍歷所有路徑的復雜度是4的(m*n)次冪(每個點都有4個可能的方向)。從冪指數復雜度降低到多項式復雜度，這就是A*演算法的意義所在。
3. 最優路徑是要從終點一步步倒退回來。比如終點的G值是k，那麼最多需要4*k次查找，依然是多項式復雜度。但多數問題(對於純演算法題來說)只是需要知道到達終點的步驟，很少要你找出固定路徑的。
Ⅲ 夢幻西遊自動尋路的尋路演算法怎麼算
A*尋路演算法 A*（A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的
節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價
中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最
好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價
函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎？肯定沒懂。接著看。
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是
。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函
數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計
算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}
Ⅳ 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;
}
Ⅳ 夢幻西遊 尋路演算法
[HOTKEY]A [NAME]壓鏢大大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至獅王洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 65 35 [SCRIPT]MOVETO 65 6 [SCRIPT]MOVETO 112 20 [SCRIPT]REM 進獅王洞 [SCRIPT]MOVEOUT 118 25 35 [SCRIPT]REM 到達大大王跟前 [SCRIPT]MOVETO 22 12
－－－－－－－－－－－－－－－－－－
[HOTKEY]B [NAME]壓鏢二大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至大象洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 52 78 [SCRIPT]MOVETO 20 82 [SCRIPT]REM 進大象洞 [SCRIPT]MOVEOUT 28 84 37 [SCRIPT]REM 到達二大王跟前 [SCRIPT]MOVETO 20 10
－－－－－－－－－－－－－－－－
[HOTKEY]C [NAME]壓鏢三大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至老雕洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 55 60 [SCRIPT]MOVETO 30 48 [SCRIPT]REM 進老雕洞 [SCRIPT]MOVEOUT 13 43 36 [SCRIPT]REM 到達三大王跟前 [SCRIPT]MOVETO 15 12
－－－－－－－－－－－－－－－－
[HOTKEY]D [NAME]壓鏢牛魔王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至牛魔寨線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 35 42 [SCRIPT]MOVETO 72 105 [SCRIPT]REM 進牛魔寨 [SCRIPT]MOVEOUT 54 116 38 [SCRIPT]REM 獅陀嶺至魔王居線路 [SCRIPT]MOVETO 35 65 [SCRIPT]MOVETO 78 65 [SCRIPT]MOVETO 88 70 [SCRIPT]REM 進魔王居 [SCRIPT]MOVEOUT 93 73 39 [SCRIPT]REM 到達牛魔王跟前 [SCRIPT]MOVETO 20 12
－－－－－－－－－－－－－－－－
[HOTKEY]E [NAME]壓鏢楊戩 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至天宮線路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 對話天將 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宮至靈宵寶殿線路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 進靈宵寶殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到達楊戩身旁 [SCRIPT]MOVETO 56 28
－－－－－－－－－－－－－－－－－
[HOTKEY]F [NAME]壓鏢李靖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至天宮線路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 對話天將 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宮至靈宵寶殿線路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 進靈宵寶殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到達李靖身旁 [SCRIPT]MOVETO 32 36
－－－－－－－－－－－－－－－－－
[HOTKEY]G [NAME]壓鏢普提老祖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至長壽村線路 [SCRIPT]MOVETO 45 30 [SCRIPT]MOVETO 60 65 [SCRIPT]MOVETO 125 90 [SCRIPT]MOVETO 150 152 [SCRIPT]REM 進長壽村 [SCRIPT]MOVEOUT 154 162 28 [SCRIPT]REM 長壽村至方寸山線路 [SCRIPT]MOVETO 132 166 [SCRIPT]MOVETO 102 195 [SCRIPT]REM 出長壽村 [SCRIPT]MOVEOUT 111 206 29 [SCRIPT]REM 方寸山至靈台宮線路 [SCRIPT]MOVETO 126 26 [SCRIPT]MOVETO 135 60 [SCRIPT]MOVETO 55 90 [SCRIPT]MOVETO 125 130 [SCRIPT]REM 進靈台宮 [SCRIPT]MOVEOUT 125 136 30 [SCRIPT]MOVETO 39 25
如果是這個腳本 請採納我的 謝謝
Ⅵ A星尋路演算法和Unity自帶的尋路相比有什麼優勢
並沒一種尋路適合所有場合，選擇都是基於需求而定的。
1. A* 演算法與貪婪演算法不一樣，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。
A*是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。
與啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。
使用的地方：
a. 策略游戲的策略搜索
b. 方塊格子游戲中的格子尋路
2. Unity 自帶的導航網格系統
Unity 內置了NavMesh導航網格系統，一般來說導航網格演算法大多是「拐角點演算法」。
效率是比較高的，但是不保證最優解演算法。
使用的地方：
a.游戲場景的怪物尋路
b.動態規避障礙
Ⅶ 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 （我們已經搜索了所有的結點，但是仍然沒有找到一條路徑）
Ⅷ 星際爭霸2的尋路演算法思路是怎樣的
首先地圖整體開始前，會用多層可達矩陣演算法，算出路徑關鍵點
2，創建關鍵節點可達矩陣
3，再每個兵當前位置對關鍵節點進行路徑計算
這樣可以最小化資源佔用就可以完成路徑計算了，高數的離散數學，挺容易解的
Ⅸ 求RMXP尋路演算法（八方向）的紙娃娃系統
找到如下內容：
case Input.dir4
when 2
move_down
when 4
move_left
when 6
move_right
when 8
move_up
end
改為如下內容：
case Input.dir8
when 2
move_down
when 4
move_left
when 6
move_right
when 8
move_up
when 1
move_lower_left
when 3
move_lower_right
when 7
move_upper_left
when 9
move_upper_right
end
就直接變成偽八方向走了。此修改方法支持絕大多數腳本，包括人物跟隨原版。
還有一個腳本叫多幀修正。
我在網路文庫上傳了一個腳本集合，裡面有。
名叫 rmxp腳本 rm類
多幀修正的是吧？可以用原素材復制粘貼把4幀復製成8幀。
那個紙娃娃我知道，真的沒有那種。
你也不必就非要用八幀的，偽的不行嗎？黑暗聖劍傳說都用的這個。
Ⅹ RMXP尋路演算法
#==============================================================================
# ■ Find_Path
#------------------------------------------------------------------------------
# 尋路演算法--完整滑鼠系統（四方向）專用版
# By whbm
#==============================================================================
class Find_Path
#--------------------------------------------------------------------------
def initialize #初始化
@open_list = []
@close_lise = []
@path = []
end #結束初始化
#--------------------------------------------------------------------------
def fp_passable?(x, y, d, tr_x = -2, tr_y = -2) #開始判定通行
return false if (tr_x == @unable_xa or
tr_x == @unable_xb or
tr_y == @unable_ya or
tr_y == @unable_yb)
if $game_player.passable?(x, y, d)
return true
else
return false
end
end #結束判定通行
#--------------------------------------------------------------------------
def get_g(now_point) #開始計算G值
d = now_point[2]
return 0 if d == 5
father_point = get_father_point(now_point)
g = father_point[3] + 10
return g
end #結束計算G值
#--------------------------------------------------------------------------
def get_h(now_point) #開始計算H值
now_x = now_point[0]
now_y = now_point[1]
#print @trg_x,now_x,@trg_y,now_y
h = (@trg_x - now_x).abs + (@trg_y - now_y).abs
return h * 10
end #結束計算H值
#--------------------------------------------------------------------------
def get_f(now_point) #開始計算F值
f = now_point[3] + now_point[4]
return f
end #結束計算F值
#--------------------------------------------------------------------------
def get_point(x, y) #取已知坐標點
if @open_list.size != 0
@open_list.each do |point|
if point[0] == x and point[1] == y
return point
break
end
end
end
if @close_list.size != 0
@close_list.each do |point|
if point[0] == x and point[1] == y
return point
break
end
end
end
end #結束取已知坐標點
#--------------------------------------------------------------------------
def get_father_point(now_point) #取已知點的父節點
d = now_point[2]
return now_point if d == 5
x = now_point[0] + (d == 6 ? 1 : (d == 4 ? -1 : 0))
y = now_point[1] + (d == 2 ? 1 : (d == 8 ? -1 : 0))
return get_point(x, y)
end #結束取已知點的父節點
#--------------------------------------------------------------------------
def new_point(x, y, d) #開始建立新節點
#print x,y,d
point = [x, y, d]
point.push get_g(point)
point.push get_h(point)
point.push get_f(point)
return point
end #結束建立新節點
#--------------------------------------------------------------------------
def get_direction(self_x, self_y, trg_x, trg_y)
if trg_x > self_x
if trg_y - self_y > - ( trg_x - self_x ) and
trg_y - self_y < ( trg_x - self_x )
return 6
end
if trg_y - self_y > ( trg_x - self_x )
return 2
end
if trg_y - self_y < - ( trg_x - self_x )
return 8
end
end
if trg_x < self_x
if trg_y - self_y > - ( self_x - trg_x ) and
trg_y - self_y < ( self_x - trg_x )
return 4
end
if trg_y - self_y > ( self_x - trg_x )
return 2
end
if trg_y - self_y < - ( self_x - trg_x )
return 8
end
end
end
#--------------------------------------------------------------------------
def get_d_x_y(x, y, d)
d_x = x + (d == 6 ? 1 : (d == 4 ? -1 : 0))
d_y = y + (d == 2 ? 1 : (d == 8 ? -1 : 0))
return d_x, d_y
end
#--------------------------------------------------------------------------
def find_short_path_other(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y)
@self_x = self_x
@self_y = self_y
@now_x = self_x
@now_y = self_y
@trg_x = trg_x
@trg_y = trg_y
@path = []
direction = get_direction(real_self_x, real_self_y, real_trg_x, real_trg_y)
@now_trg_x, @now_trg_y = get_d_x_y(@self_x, @self_y, direction)
while fp_passable?(@now_x, @now_y, direction)
@path.push direction
@now_x = @now_trg_x
@now_y = @now_trg_y
@now_trg_x, @now_trg_y = get_d_x_y(@now_x, @now_y, direction)
end
return @path
end
#--------------------------------------------------------------------------
def find_short_path(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y) #開始搜索路徑
return find_short_path_other(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y) if not
(fp_passable?(trg_x, trg_y + 1, 8) or
fp_passable?(trg_x + 1, trg_y, 4) or
fp_passable?(trg_x - 1, trg_y, 6) or
fp_passable?(trg_x, trg_y - 1, 2)) and @goal_type != 1
#根據屏幕限定搜索麵積..加速
@unable_xa = $game_map.display_x / 128 - 1
@unable_ya = $game_map.display_y / 128 - 1
@unable_xb = $game_map.display_x / 128 + 20
@unable_yb = $game_map.display_y / 128 + 20
@self_x = self_x
@self_y = self_y
@now_x = self_x
@now_y = self_y
@trg_x = trg_x
@trg_y = trg_y
@open_list = []
@close_list = []
#准備搜索
#print @self_x,@self_y
@now_point = new_point(@self_x, @self_y, 5) #令起始點為當前點
@open_list.push @now_point #將當前點加入關閉列表
#開始搜索
begin
loop do
check_trg = check_around_point(@now_point)
if check_trg == true
@path = get_path
break
end
@now_point = get_lowest_f_point
if @now_point == [] or @now_point == nil
@path = []
break
end
end
rescue Hangup
retry
end
return @path
end #結束搜索路徑
#--------------------------------------------------------------------------
def find_player_short_path(trg_x, trg_y,
real_trg_x, real_trg_y) #尋找角色的最短路徑
self_x = $game_player.x
self_y = $game_player.y
real_self_x = $game_player.screen_x
real_self_y = $game_player.screen_y
@goal_type, event = $game_map.check_event_custom_exist(real_trg_x, real_trg_y)
if @goal_type == 1
trg_x = event.x
trg_y = event.y
end
return find_short_path(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y)
end #結束角色的尋找路徑
#--------------------------------------------------------------------------
def get_path #取得最終的路徑
path = []
now_point = @open_list[@open_list.size - 1]
path.push(10 - now_point[2])
last_point = now_point
loop do
now_point = get_father_point(now_point)
break if now_point[2] == 5
path.push(10 - now_point[2])
end
return path.reverse
end #結束取得最終的路徑
#--------------------------------------------------------------------------
def get_lowest_f_point #開始取得最低F值的點
if @open_list == []
return []
end
last_lowest_f_point = @open_list[0]
@open_list.each do |point|
last_lowest_f_point = point if point[5] < last_lowest_f_point[5]
end
return last_lowest_f_point
end #結束取得最低F值點
#--------------------------------------------------------------------------
def check_around_point(point) #開始檢查已知點的八方節點
for d in [2, 4, 6, 8]
x = point[0] + (d == 6 ? 1 : (d == 4 ? -1 : 0))
y = point[1] + (d == 2 ? 1 : (d == 8 ? -1 : 0))
if in_close_list?(x, y) #在關閉列表中
next
elsif in_open_list?(x, y) #在開啟列表中
get_new_g_point = new_point(x, y, 10 - d)
get_last_g_point = get_point(x, y)
if get_new_g_point[3] >= get_last_g_point[3]
next
else
#如果改變父節點是新G值更小則確定改變
@open_list[@open_list.index(get_last_g_point)] = get_new_g_point
end
else
if fp_passable?(point[0], point[1], d, x, y)
# 如果不在開啟列表中、且不在關閉列表中、且通行則添加它到新八周節點
@open_list.push new_point(x, y, 10 - d)
#如果將目標點添加到了開啟列表中就返回true
return true if x == @trg_x and y == @trg_y
return true if @goal_type == 1 and ([1, -1].include?(x - @trg_x) and y - @trg_y == 0) or ([1, -1].include?(y - @trg_y) and x - @trg_x == 0)
end
end
end
#此刻沒有找到目標點並將當前點加入關閉列表並在開啟列表中刪除
@close_list.push point
@open_list.delete(point)
#此刻沒找到目標點並返回false
return false
end #結束計算已知點的八方節點
#--------------------------------------------------------------------------
def in_open_list?(x, y) #開始檢查謀點是否在開啟列表中
@open_list.each do |point|
return true if point[0] == x and point[1] == y
end
return false
end #結束檢查謀點是否在開啟列表中
#--------------------------------------------------------------------------
def in_close_list?(x, y) #開始檢查謀點是否在關閉列表中
@close_list.each do |point|
return true if point[0] == x and point[1] == y
end
return false
end #結束檢查謀點是否在關閉列表中
#--------------------------------------------------------------------------
end