天天夜碰日日摸日日澡,国产一级黄片,性色欧美

在游戲開發中，AI的最基本問題之一就是尋路算法或稱路徑規劃算法，在三年前，我曾實現過基于“圖算法”的最短路徑規劃算法，然而在游戲中，我們通常將地圖抽象為有單元格構成的矩形，如：

（本圖源于這里）

這個微型地圖由3*3的單元格構成，當然，實際游戲中的地圖通常比它大很多，這里只是給出一個示例。

由于游戲地圖通常由單元格構成，所以，基于“圖算法”的路徑規劃便不再那么適用，我們需要采用基于單元格的路徑規劃算法。A*算法是如今游戲所采用的尋路算法中相當常用的一種算法，它可以保證在任何起點和任何終點之間找到最佳的路徑（如果存在的話），而且，A*算法相當有效。

關于A*算法的原理的詳細介紹，可以參考這篇文章。當你明白A*算法的原理之后，在來看接下來的A*算法的實現就會比較容易了。

現在，讓我們轉入正題，看看如何在C#中實現A*算法。

首先，我們把地圖劃分為單元格，如此，一個地圖就可以由（M行*N列）個單元格構成。我們使用AStarNode類來抽象單元格，表示一個節點，而節點的位置用Point表示，其X坐標表示Column Index，Y坐標表示Line Index。AStarNode的定義如下：

/// <summary>
/// AStarNode用于保存規劃到當前節點時的各個Cost值以及父節點。
/// 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節點所在的位置，其X值代表ColumnIndex，Y值代表LineIndex
/// </summary>
public PointLocation
{
get { return location;}
}
#endregion

#region PreviousNode
private AStarNodepreviousNode = null ;
/// <summary>
/// PreviousNode父節點，即是由哪個節點導航到當前節點的。
/// </summary>
public AStarNodePreviousNode
{
get { return previousNode;}
}
#endregion

#region CostF
/// <summary>
/// CostF從起點導航經過本節點然后再到目的節點的估算總代價。
/// </summary>
public int CostF
{
get
{
return this .costG + this .costH;
}
}
#endregion

#region CostG
private int costG = 0 ;
/// <summary>
/// CostG從起點導航到本節點的代價。
/// </summary>
public int CostG
{
get { return costG;}
}
#endregion

#region CostH
private int costH = 0 ;
/// <summary>
/// CostH使用啟發式方法估算的從本節點到目的節點的代價。
/// </summary>
public int CostH
{
get { return costH;}
}
#endregion

#region ResetPreviousNode
/// <summary>
/// ResetPreviousNode當從起點到達本節點有更優的路徑時，調用該方法采用更優的路徑。
/// </summary>
public void ResetPreviousNode(AStarNodeprevious, int _costG)
{
this .previousNode = previous;
this .costG = _costG;
}
#endregion

public override string ToString()
{
return this .location.ToString();
}
}

如果，你看過上面提到的那篇參考文章，那么類中的各個屬性的定義就不難理解了。

我們假設，從某個節點出發，最多可以有8個方向移動，這8個方向定義為CompassDirections：

public enum CompassDirections
{
NotSet = 0 ,
North = 1 , // UP
NorthEast = 2 , // UPRight
East = 3 ,
SouthEast = 4 ,
South = 5 ,
SouthWest = 6 ,
West = 7 ,
NorthWest = 8
}

CompassDirections遵守“左西右東，上北下南”的地圖方位原則。

而從某個節點出發，朝8個方向之中的某個方向移動是有代價（Cost）的，而且朝每個方向移動的代價可能是不相同的，而我們的尋路算法正是要找到起點和終點之間總代價最小的路徑。我們使用一個接口ICostGetter來獲取從某個節點開始朝8個方向移動的代價值。

/// <summary>
/// ICostGetter獲取從當前節點向某個方向移動時的代價。
/// </summary>
public interface ICostGetter
{
int GetCost( Point currentNodeLoaction, CompassDirections moveDirection);
}

之所以將其定義為接口，是因為不同的游戲中的對移動代價賦值是不一樣的。不同的游戲可以自己實現這個接口，以表明自己的代價賦值策略。

盡管如此，我們還是給出一個最簡單的ICostGetter實現以方便我們測試，這個實現表示從當前節點向上、下、左、右四個方向的移動的代價是一樣的。

/// <summary>
/// SimpleCostGetterICostGetter接口的簡化實現。直線代價為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
}

我們知道，如果定義上、下、左、右的代價為1，那么斜線的代價應為根號2，為了提高計算效率，我們將根號2取近似值為1.4，并將單位放大10倍（計算機對整數的運算比對浮點數的運算要快很多）。

我們還需要一個結構來保存在路徑規劃過程中的中間結果：

/// <summary>
/// RoutePlanData用于封裝一次路徑規劃過程中的規劃信息。
/// </summary>
public class RoutePlanData
{
#region CellMap
private RectanglecellMap;
/// <summary>
/// CellMap地圖的矩形大小。經過單元格標準處理。
/// </summary>
public Rectangle CellMap
{
get { return cellMap;}
}
#endregion

#region ClosedList
private IList < AStarNode > closedList = new List < AStarNode > ();
/// <summary>
/// ClosedList關閉列表，即存放已經遍歷處理過的節點。
/// </summary>
public IList < AStarNode > ClosedList
{
get { return closedList;}
}
#endregion

#region OpenedList
private IList < AStarNode > openedList = new List < AStarNode > ();
/// <summary>
/// OpenedList開放列表，即存放已經開發但是還未處理的節點。
/// </summary>
public IList < AStarNode > OpenedList
{
get { return openedList;}
}
#endregion

#region Destination
private Point destination;
/// <summary>
/// Destination目的節點的位置。
/// </summary>
public Point Destination
{
get { return destination;}
}
#endregion

#region Ctor
public RoutePlanData( Rectangle map,Point_destination)
{
this .cellMap = map;
this .destination = _destination;
}
#endregion
}

有了上述這些基礎結構，我們便可以開始實現算法的核心功能了：

/// <summary>
/// AStarRoutePlannerA*路徑規劃。每個單元格Cell的位置用Point表示
/// F=G+H。
/// G=從起點A，沿著產生的路徑，移動到網格上指定方格的移動耗費。
/// H=從網格上那個方格移動到終點B的預估移動耗費。使用曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數量總和，忽略對角線方向。
/// zhuweisky2008.10.18
/// </summary>
public class AStarRoutePlanner
{
private int lineCount = 10 ; // 反映地圖高度，對應Y坐標
private int columnCount = 10 ; // 反映地圖寬度，對應X坐標
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將所有位置均標記為無障礙物。
/// </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在路徑規劃之前先設置障礙物位置。
/// </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;

// 從起始節點開始進行遞歸調用
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)) // 相鄰點已經在地圖之外
{
continue ;
}

if ( this .obstacles[nextCell.X][nextCell.Y]) // 下一個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，表示相鄰點就是目的點，規劃完成，構造結果路徑
{
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)
{
// 如果新的路徑代價更小，則更新該位置上的節點的原始路徑
existNode. ResetPreviousNode (currenNode,costG);
}
}
else
{
AStarNodenewNode = new AStarNode(nextCell,currenNode,costG,costH);
routePlanData.OpenedList.Add(newNode);
}
}

// 將已遍歷過的節點從開放列表轉移到關閉列表
routePlanData.OpenedList.Remove(currenNode);
routePlanData.ClosedList.Add(currenNode);

AStarNodeminCostNode = this .GetMinCostNode(routePlanData.OpenedList);
if (minCostNode == null ) // 表明從起點到終點之間沒有任何通路。
{
return null ;
}

// 對開放列表中的下一個代價最小的節點作遞歸調用
return this .DoPlan(routePlanData,minCostNode);
}
#endregion

#region GetNodeOnLocation
/// <summary>
/// GetNodeOnLocation目標位置location是否已存在于開放列表或關閉列表中
/// </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從開放列表中獲取代價F最小的節點，以啟動下一次遞歸
/// </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
}

代碼中已經加了詳盡的注釋，要注意的有以下幾點：

1.Initialize方法用于初始化障礙物的位置，所謂“障礙物”，是指導航時無法穿越的物體，比如，游戲中的墻、河流等。

2.標記為紅色的 ResetPreviousNode 方法調用處，說明，到達當前節點的當前路徑比已存在的路徑代價更小，所以要選擇更優的路徑。

3.標記為黑體的 route.Insert( 0 ,tempNode.PreviousNode.Location); 方法調用，表示已經找到最優路徑，此處便可通過 反向迭代 的方式整理出從起點到終點的最終路徑。

4.CostH 的計算使用曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數量總和，忽略對角線方向。

5.在該算法中，至少還有一個地方可以優化，那就是 GetMinCostNode 方法所實現的內容，如果在路徑搜索的過程中，我們就將OpenList中的各個節點按照Cost從小到大進行排序，那么每次GetMinCostNode時，就只需要取出第一個節點即可，而不必在遍歷OpenList中的每一個節點了。在地圖很大的時候，此法可以大幅提升算法效率。

最后，給出一個例子，感受一下：

AStarRoutePlanner aStarRoutePlanner = new AStarRoutePlanner ();
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 ));

運行后，返回的route結果如下：

{3,3}, {2,3}, {1,3}, {1,4}, {1,5}, {2,5}, {2,6}, {3,6}, {4,6}

2008-10-13：附上CompassDirectionsHelper和GeometryHelper源碼。

public static class CompassDirectionsHelper
{
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
}

public static class GeometryHelper
{
#region GetAdjacentPoint
/// <summary>
/// GetAdjacentPoint獲取某個方向上的相鄰點
/// </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
}

A*算法的C#實現

更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索：z360901061

微信掃一掃加我為好友

QQ號聯系： 360901061

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。

【本文對您有幫助就好】元

2元

5元

10元

20元

自定義

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频