在游戲開發(fā)中，AI的最基本問題之一就是尋路算法或稱路徑規(guī)劃算法，在三年前，我曾實(shí)現(xiàn)過 基于“圖算法”的最短路徑規(guī)劃算法 ，然而在游戲中，我們通常將地圖抽象為有單元格構(gòu)成的矩形，如：
（本圖源于 這里 ）
這個(gè)微型地圖由3*3的單元格構(gòu)成，當(dāng)然，實(shí)際游戲中的地圖通常比它大很多，這里只是給出一個(gè)示例。
由于游戲地圖通常由單元格構(gòu)成，所以，基于“圖算法”的路徑規(guī)劃便不再那么適用，我們需要采用基于單元格的路徑規(guī)劃算法。A*算法是如今游戲所采用的尋路算法中相當(dāng)常用的一種算法，它可以保證在任何起點(diǎn)和任何終點(diǎn)之間找到 最佳 的路徑（如果存在的話），而且，A*算法相當(dāng)有效。
關(guān)于A*算法的原理的詳細(xì)介紹，可以參考 這篇文章 。當(dāng)你明白A*算法的原理之后，在來看接下來的A*算法的實(shí)現(xiàn)就會(huì)比較容易了。
現(xiàn)在，讓我們轉(zhuǎn)入正題，看看如何在C#中實(shí)現(xiàn)A*算法。
首先，我們把地圖劃分為單元格，如此，一個(gè)地圖就可以由（M行*N列）個(gè)單元格構(gòu)成。我們使用AStarNode類來抽象單元格，表示一個(gè)節(jié)點(diǎn)，而節(jié)點(diǎn)的位置用Point表示，其X坐標(biāo)表示Column Index，Y坐標(biāo)表示Line Index。AStarNode的定義如下：
/// AStarNode用于保存規(guī)劃到當(dāng)前節(jié)點(diǎn)時(shí)的各個(gè)Cost值以及父節(jié)點(diǎn)。
/// zhuweisky2008.10.18
/// </summary>
public class AStarNode
{
#region Ctor
public AStarNode(Pointloc,AStarNodeprevious, int _costG, int _costH)
{
this .location = loc;
this .previousNode = previous;
this .costG = _costG;
this .costH = _costH;
}
#endregion
#region Location
private Pointlocation = new Point( 0 , 0 );
/// <summary>
/// Location節(jié)點(diǎn)所在的位置，其X值代表ColumnIndex，Y值代表LineIndex
/// </summary>
public PointLocation
{
get { return location;}
}
#endregion
#region PreviousNode
private AStarNodepreviousNode = null ;
/// <summary>
/// PreviousNode父節(jié)點(diǎn)，即是由哪個(gè)節(jié)點(diǎn)導(dǎo)航到當(dāng)前節(jié)點(diǎn)的。
/// </summary>
public AStarNodePreviousNode
{
get { return previousNode;}
}
#endregion
#region CostF
/// <summary>
/// CostF從起點(diǎn)導(dǎo)航經(jīng)過本節(jié)點(diǎn)然后再到目的節(jié)點(diǎn)的估算總代價(jià)。
/// </summary>
public int CostF
{
get
{
return this .costG + this .costH;
}
}
#endregion
#region CostG
private int costG = 0 ;
/// <summary>
/// CostG從起點(diǎn)導(dǎo)航到本節(jié)點(diǎn)的代價(jià)。
/// </summary>
public int CostG
{
get { return costG;}
}
#endregion
#region CostH
private int costH = 0 ;
/// <summary>
/// CostH使用啟發(fā)式方法估算的從本節(jié)點(diǎn)到目的節(jié)點(diǎn)的代價(jià)。
/// </summary>
public int CostH
{
get { return costH;}
}
#endregion
#region ResetPreviousNode
/// <summary>
/// ResetPreviousNode當(dāng)從起點(diǎn)到達(dá)本節(jié)點(diǎn)有更優(yōu)的路徑時(shí)，調(diào)用該方法采用更優(yōu)的路徑。
/// </summary>
public void ResetPreviousNode(AStarNodeprevious, int _costG)
{
this .previousNode = previous;
this .costG = _costG;
}
#endregion
public override string ToString()
{
return this .location.ToString();
}
}
如果，你看過上面提到的那篇參考文章，那么類中的各個(gè)屬性的定義就不難理解了。
我們假設(shè)，從某個(gè)節(jié)點(diǎn)出發(fā)，最多可以有8個(gè)方向移動(dòng)，這8個(gè)方向定義為CompassDirections：
{
NotSet = 0 ,
North = 1 , // UP
NorthEast = 2 , // UPRight
East = 3 ,
SouthEast = 4 ,
South = 5 ,
SouthWest = 6 ,
West = 7 ,
NorthWest = 8
}
CompassDirections遵守“左西右東，上北下南”的地圖方位原則。
而從某個(gè)節(jié)點(diǎn)出發(fā)，朝8個(gè)方向之中的某個(gè)方向移動(dòng)是有代價(jià)（Cost）的，而且朝每個(gè)方向移動(dòng)的代價(jià)可能是不相同的，而我們的尋路算法正是要找到起點(diǎn)和終點(diǎn)之間總代價(jià)最小的路徑。我們使用一個(gè)接口ICostGetter來獲取從某個(gè)節(jié)點(diǎn)開始朝8個(gè)方向移動(dòng)的代價(jià)值。
/// ICostGetter獲取從當(dāng)前節(jié)點(diǎn)向某個(gè)方向移動(dòng)時(shí)的代價(jià)。
/// </summary>
public interface ICostGetter
{
int GetCost( Point currentNodeLoaction, CompassDirections moveDirection);
}
之所以將其定義為接口，是因?yàn)椴煌挠螒蛑械膶σ苿?dòng)代價(jià)賦值是不一樣的。不同的游戲可以自己實(shí)現(xiàn)這個(gè)接口，以表明自己的代價(jià)賦值策略。
盡管如此，我們還是給出一個(gè)最簡單的ICostGetter實(shí)現(xiàn)以方便我們測試，這個(gè)實(shí)現(xiàn)表示從當(dāng)前節(jié)點(diǎn)向上、下、左、右四個(gè)方向的移動(dòng)的代價(jià)是一樣的。
/// SimpleCostGetterICostGetter接口的簡化實(shí)現(xiàn)。直線代價(jià)為10，斜線為14。
/// </summary>
public class SimpleCostGetter:ICostGetter
{
#region ICostGetter成員
public int GetCost(PointcurrentNodeLoaction,CompassDirectionsmoveDirection)
{
if (moveDirection == CompassDirections.NotSet)
{
return 0 ;
}
if (moveDirection == CompassDirections.East || moveDirection == CompassDirections.West || moveDirection == CompassDirections.South || moveDirection == CompassDirections.North)
{
return 10 ;
}
return 14 ;
}
#endregion
}
我們知道，如果定義上、下、左、右的代價(jià)為1，那么斜線的代價(jià)應(yīng)為根號2，為了提高計(jì)算效率，我們將根號2取近似值為1.4，并將單位放大10倍（計(jì)算機(jī)對整數(shù)的運(yùn)算比對浮點(diǎn)數(shù)的運(yùn)算要快很多）。
我們還需要一個(gè)結(jié)構(gòu)來保存在路徑規(guī)劃過程中的中間結(jié)果：
/// RoutePlanData用于封裝一次路徑規(guī)劃過程中的規(guī)劃信息。
/// </summary>
public class RoutePlanData
{
#region CellMap
private RectanglecellMap;
/// <summary>
/// CellMap地圖的矩形大小。經(jīng)過單元格標(biāo)準(zhǔn)處理。
/// </summary>
public Rectangle CellMap
{
get { return cellMap;}
}
#endregion
#region ClosedList
private IList < AStarNode > closedList = new List < AStarNode > ();
/// <summary>
/// ClosedList關(guān)閉列表，即存放已經(jīng)遍歷處理過的節(jié)點(diǎn)。
/// </summary>
public IList < AStarNode > ClosedList
{
get { return closedList;}
}
#endregion
#region OpenedList
private IList < AStarNode > openedList = new List < AStarNode > ();
/// <summary>
/// OpenedList開放列表，即存放已經(jīng)開發(fā)但是還未處理的節(jié)點(diǎn)。
/// </summary>
public IList < AStarNode > OpenedList
{
get { return openedList;}
}
#endregion
#region Destination
private Point destination;
/// <summary>
/// Destination目的節(jié)點(diǎn)的位置。
/// </summary>
public Point Destination
{
get { return destination;}
}
#endregion
#region Ctor
public RoutePlanData( Rectangle map,Point_destination)
{
this .cellMap = map;
this .destination = _destination;
}
#endregion
}
有了上述這些基礎(chǔ)結(jié)構(gòu)，我們便可以開始實(shí)現(xiàn)算法的核心功能了：
/// AStarRoutePlannerA*路徑規(guī)劃。每個(gè)單元格Cell的位置用Point表示
/// F=G+H。
/// G=從起點(diǎn)A，沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi)。
/// H=從網(wǎng)格上那個(gè)方格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)耗費(fèi)。使用曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向。
/// zhuweisky2008.10.18
/// </summary>
public class AStarRoutePlanner
{
private int lineCount = 10 ; // 反映地圖高度，對應(yīng)Y坐標(biāo)
private int columnCount = 10 ; // 反映地圖寬度，對應(yīng)X坐標(biāo)
private ICostGettercostGetter = new SimpleCostGetter();
private bool [][]obstacles = null ; // 障礙物位置，維度：Column*Line
#region Ctor
public AStarRoutePlanner(): this ( 10 , 10 , new SimpleCostGetter())
{
}
public AStarRoutePlanner( int _lineCount, int _columnCount,ICostGetter_costGetter)
{
this .lineCount = _lineCount;
this .columnCount = _columnCount;
this .costGetter = _costGetter;
this .InitializeObstacles();
}
/// <summary>
/// InitializeObstacles將所有位置均標(biāo)記為無障礙物。
/// </summary>
private void InitializeObstacles()
{
this .obstacles = new bool [ this .columnCount][];
for ( int i = 0 ;i < this .columnCount;i ++ )
{
this .obstacles[i] = new bool [ this .lineCount];
}
for ( int i = 0 ;i < this .columnCount;i ++ )
{
for ( int j = 0 ;j < this .lineCount;j ++ )
{
this .obstacles[i][j] = false ;
}
}
}
#endregion
#region Initialize
/// <summary>
/// Initialize在路徑規(guī)劃之前先設(shè)置障礙物位置。
/// </summary>
public void Initialize(IList < Point > obstaclePoints)
{
if (obstacles != null )
{
foreach (Pointpt in obstaclePoints)
{
this .obstacles[pt.X][pt.Y] = true ;
}
}
}
#endregion
#region Plan
public IList < Point > Plan(Pointstart,Pointdestination)
{
Rectanglemap = new Rectangle( 0 , 0 , this .columnCount, this .lineCount);
if (( ! map.Contains(start)) || ( ! map.Contains(destination)))
{
throw new Exception( " StartPointorDestinationnotinthecurrentmap! " );
}
RoutePlanDataroutePlanData = new RoutePlanData(map,destination);
AStarNodestartNode = new AStarNode(start, null , 0 , 0 );
routePlanData.OpenedList.Add(startNode);
AStarNodecurrenNode = startNode;
// 從起始節(jié)點(diǎn)開始進(jìn)行遞歸調(diào)用
return DoPlan(routePlanData,currenNode);
}
#endregion
#region DoPlan
private IList < Point > DoPlan(RoutePlanDataroutePlanData,AStarNodecurrenNode)
{
IList < CompassDirections > allCompassDirections = CompassDirectionsHelper.GetAllCompassDirections();
foreach (CompassDirectionsdirection in allCompassDirections)
{
PointnextCell = GeometryHelper.GetAdjacentPoint(currenNode.Location,direction);
if ( ! routePlanData.CellMap.Contains(nextCell)) // 相鄰點(diǎn)已經(jīng)在地圖之外
{
continue ;
}
if ( this .obstacles[nextCell.X][nextCell.Y]) // 下一個(gè)Cell為障礙物
{
continue ;
}
int costG = this .costGetter.GetCost(currenNode.Location,direction);
int costH = Math.Abs(nextCell.X - routePlanData.Destination.X) + Math.Abs(nextCell.Y - routePlanData.Destination.Y);
if (costH == 0 ) // costH為0，表示相鄰點(diǎn)就是目的點(diǎn)，規(guī)劃完成，構(gòu)造結(jié)果路徑
{
IList < Point > route = new List < Point > ();
route.Add(routePlanData.Destination);
route.Insert(0,currenNode.Location);
AStarNodetempNode = currenNode;
while (tempNode.PreviousNode != null )
{
route.Insert( 0 ,tempNode.PreviousNode.Location);
tempNode = tempNode.PreviousNode;
}
return route;
}
AStarNodeexistNode = this .GetNodeOnLocation(nextCell,routePlanData);
if (existNode != null )
{
if (existNode.CostG > costG)
{
// 如果新的路徑代價(jià)更小，則更新該位置上的節(jié)點(diǎn)的原始路徑
existNode. ResetPreviousNode (currenNode,costG);
}
}
else
{
AStarNodenewNode = new AStarNode(nextCell,currenNode,costG,costH);
routePlanData.OpenedList.Add(newNode);
}
}
// 將已遍歷過的節(jié)點(diǎn)從開放列表轉(zhuǎn)移到關(guān)閉列表
routePlanData.OpenedList.Remove(currenNode);
routePlanData.ClosedList.Add(currenNode);
AStarNodeminCostNode = this .GetMinCostNode(routePlanData.OpenedList);
if (minCostNode == null ) // 表明從起點(diǎn)到終點(diǎn)之間沒有任何通路。
{
return null ;
}
// 對開放列表中的下一個(gè)代價(jià)最小的節(jié)點(diǎn)作遞歸調(diào)用
return this .DoPlan(routePlanData,minCostNode);
}
#endregion
#region GetNodeOnLocation
/// <summary>
/// GetNodeOnLocation目標(biāo)位置location是否已存在于開放列表或關(guān)閉列表中
/// </summary>
private AStarNodeGetNodeOnLocation(Pointlocation,RoutePlanDataroutePlanData)
{
foreach (AStarNodetemp in routePlanData.OpenedList)
{
if (temp.Location == location)
{
return temp;
}
}
foreach (AStarNodetemp in routePlanData.ClosedList)
{
if (temp.Location == location)
{
return temp;
}
}
return null ;
}
#endregion
#region GetMinCostNode
/// <summary>
/// GetMinCostNode從開放列表中獲取代價(jià)F最小的節(jié)點(diǎn)，以啟動(dòng)下一次遞歸
/// </summary>
private AStarNodeGetMinCostNode(IList < AStarNode > openedList)
{
if (openedList.Count == 0 )
{
return null ;
}
AStarNodetarget = openedList[ 0 ];
foreach (AStarNodetemp in openedList)
{
if (temp.CostF < target.CostF)
{
target = temp;
}
}
return target;
}
#endregion
}
代碼中已經(jīng)加了詳盡的注釋，要注意的有以下幾點(diǎn)：
1.Initialize方法用于初始化障礙物的位置，所謂“障礙物”，是指導(dǎo)航時(shí)無法穿越的物體，比如，游戲中的墻、河流等。
2.標(biāo)記為紅色的 ResetPreviousNode 方法調(diào)用處，說明，到達(dá)當(dāng)前節(jié)點(diǎn)的當(dāng)前路徑比已存在的路徑代價(jià)更小，所以要選擇更優(yōu)的路徑。
3.標(biāo)記為黑體的 route.Insert( 0 ,tempNode.PreviousNode.Location); 方法調(diào)用，表示已經(jīng)找到最優(yōu)路徑，此處便可通過 反向迭代 的方式整理出從起點(diǎn)到終點(diǎn)的最終路徑。
4.CostH 的計(jì)算使用曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向。
5.在該算法中，至少還有一個(gè)地方可以優(yōu)化，那就是 GetMinCostNode 方法所實(shí)現(xiàn)的內(nèi)容，如果在路徑搜索的過程中，我們就將OpenList中的各個(gè)節(jié)點(diǎn)按照Cost從小到大進(jìn)行排序，那么每次GetMinCostNode時(shí)，就只需要取出第一個(gè)節(jié)點(diǎn)即可，而不必在遍歷OpenList中的每一個(gè)節(jié)點(diǎn)了。在地圖很大的時(shí)候，此法可以大幅提升算法效率。
最后，給出一個(gè)例子，感受一下：
IList < Point > obstaclePoints = new List < Point > ();
obstaclePoints.Add( new Point( 2 , 4 ));
obstaclePoints.Add( new Point( 3 , 4 ));
obstaclePoints.Add( new Point( 4 , 4 ));
obstaclePoints.Add( new Point( 5 , 4 ));
obstaclePoints.Add( new Point( 6 , 4 ));
aStarRoutePlanner.Initialize(obstaclePoints);
IList < Point > route = aStarRoutePlanner.Plan( new Point( 3 , 3 ), new Point( 4 , 6 ));
運(yùn)行后，返回的route結(jié)果如下：
{3,3}, {2,3}, {1,3}, {1,4}, {1,5}, {2,5}, {2,6}, {3,6}, {4,6}
2008-10-13：附上CompassDirectionsHelper和GeometryHelper源碼。
{
private static IList < CompassDirections > AllCompassDirections = new List < CompassDirections > ();
#region StaticCtor
static CompassDirectionsHelper()
{
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.East);
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.West);
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.South);
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.North);
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.SouthEast);
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.SouthWest);
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.NorthEast);
CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.NorthWest);
}
#endregion
#region GetAllCompassDirections
public static IList < CompassDirections > GetAllCompassDirections()
{
return CompassDirectionsHelper.AllCompassDirections;
}
#endregion
}
{
#region GetAdjacentPoint
/// <summary>
/// GetAdjacentPoint獲取某個(gè)方向上的相鄰點(diǎn)
/// </summary>
public static PointGetAdjacentPoint(Pointcurrent,CompassDirectionsdirection)
{
switch (direction)
{
case CompassDirections.North:
{
return new Point(current.X,current.Y - 1 );
}
case CompassDirections.South:
{
return new Point(current.X,current.Y + 1 );
}
case CompassDirections.East:
{
return new Point(current.X + 1 ,current.Y);
}
case CompassDirections.West:
{
return new Point(current.X - 1 ,current.Y);
}
case CompassDirections.NorthEast:
{
return new Point(current.X + 1 ,current.Y - 1 );
}
case CompassDirections.NorthWest:
{
return new Point(current.X - 1 ,current.Y - 1 );
}
case CompassDirections.SouthEast:
{
return new Point(current.X + 1 ,current.Y + 1 );
}
case CompassDirections.SouthWest:
{
return new Point(current.X - 1 ,current.Y + 1 );
}
default :
{
return current;
}
}
}
#endregion
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
