الگوریتم path finding A_star یا مسیریابی A star یا A* در یونیتی

منبع :gameover.blog.ir

توی یونیتی این روش رو میشه با way points ایجاد کرد که بالاتر درس دادم.

روش کار A star اینه که تمام مسیر ها رو باید توی آرایه یا یه لیستی ذخیره کنیم و فاصله ها رو محاسبه کنیم.(جستجوی مکاشفه ای یا huristic)

بعدش نزدیک ترین راه رو انتخاب می کنیم.

محاسبات قبلی برای پیدا کردن مسیر بهینه وجود داره که اونا رو دیگه خودتون می تونید با هر روشی انجام بدید.

مثلا زمانی که player بیکار هست یا ایستاده می تونید محاسبات اضافه رو انجام بدید. یا وقتی کاراکتر روی فلان نقطه ( onCollisionEnter یا ...) هست فاصله ی نزدیک ترین مسیر و بهینه ترین مسیر رو پیدا کنیم بعدش دشمن رو حرکت بدیم بیاد سمت ما(player)

مثلا این عکس رو ببینید :

نزدیک ترین مسیر از A به G با الگوریتم A star میشه: از A به B و سپس B به D و نهایتا D به G

-

البته روش dikjstra هم هست که از روش کنکور( غلبه) استفاده می کنه. حالا اگه مقایسشو دوستان خواستید می تونید توی google ببینید.
در مورد دایجسترا(دیکسترا یا چیزای دیگه هم می گن) اینجا رو بخونید :
http://fa.wikipedia.org/wiki/%D8%A7%D9%8...8%B1%D8%A7
در مورد روش A star هم اینجا رو بخونید:
http://en.wikipedia.org/wiki/A*_search_algorithm
-
پکیج هایی برای یونیتی برای مسیر یابی آ استار هست که دوستانی که لینکشو دارن می تونن بذارن

یه فیلم گذاشتم اینجا از یوتیوب گرفتم :
البته این فیلم واسه گیم میکر هست فکر کنم اونایی که حجم محدود دارن نگیرن بیخود حجم هدر میده. منم فعلا نگرفتمش چون یکی بی کیفیتشو با حجم حدود 34 مگ گرفتم فهمید گیم میکر هست :
http://01.00ll00.com/iTube%2f16565174-Co...inding.3gp
اینم با کیفییت:

http://0000.00ll00.com/ibjdfeg
اگه expire شد بگید لینک رو عوض کنم

---

البته یه چیز تحت عنوان Pro Navmesh and Pathfinding system هم فکر کنم توی خود یونیتی باشه.
اما خودتون اگه way point و کمی با فکرتون مخلوط کنید و نگاه کلی داشته باشید و اول درک کنید خودتون می تونید هوش بسازید.



در گراف های جدولی فوق چند تا روش های حرکت رو نشون داده که کدنویسیش دلخواه خودتون هست.
اینم یکی دیگه :


سورس سیشارپ هم که توسط Aron Granberg نوشته شده اینه :

کد PHP:

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using Pathfinding;
using Pathfinding.RVO;

/** Adds a GridGraph as RVO obstacles.
* Add this to a scene in which has a GridGrah based graph, when scanning (or loading from cache) the graph
* it will be added as RVO obstacles to the RVOSimulator (which must exist in the scene).
*
* \astarpro
*/
[AddComponentMenu("Local Avoidance/RVOGridGraph")]
public class RVOGridGraph : GraphModifier
{
/** Height of the walls added for each obstacle edge.
* If a graph contains overlapping you should set this low enough so
* that edges on different levels do not interfere, but high enough so that
* agents cannot move over them by mistake.
*/
public float wallHeight = 5;

/** Obstacles currently added to the simulator */
private List<ObstacleVertex> obstacles = new List<ObstacleVertex>();

/** Last simulator used */
private Simulator lastSim = null;

public override void OnPostCacheLoad()
{
OnLatePostScan();
}

public override void OnLatePostScan()
{
if (!Application.isPlaying)
return;

RemoveObstacles();

NavGraph[] graphs = AstarPath.active.graphs;

RVOSimulator rvosim = FindObjectOfType(typeof(RVOSimulator)) as RVOSimulator;
if (rvosim == null)
throw new System.NullReferenceException("No RVOSimulator could be found in the scene. Please add one to any GameObject");

Pathfinding.RVO.Simulator sim = rvosim.GetSimulator();

for (int i = 0; i < graphs.Length; i++)
{
AddGraphObstacles(sim, graphs[i]);
}

sim.UpdateObstacles();
}

/** Removes obstacles which were added with AddGraphObstacles */
public void RemoveObstacles()
{
if (lastSim == null)
return;

Pathfinding.RVO.Simulator sim = lastSim;
lastSim = null;

for (int i = 0; i < obstacles.Count; i++)
sim.RemoveObstacle(obstacles[i]);

obstacles.Clear();
}

/** Adds RVO obstacles for a Grid Graph */
public void AddGraphObstacles(Pathfinding.RVO.Simulator sim, NavGraph graph)
{
if (obstacles.Count > 0 && lastSim != null && lastSim != sim)
{
Debug.LogError("Simulator has changed but some old obstacles are still added for the previous simulator. Deleting previous obstacles.");
RemoveObstacles();
}

//Remember which simulator these obstacles were added to
lastSim = sim;

GridGraph gg = graph as GridGraph;

if (gg == null)
{
return;
}

Node[] nodes = graph.nodes;

for (int w = 0; w < gg.width; w++)
{
for (int d = 0; d < gg.depth; d++)
{
int iA = d * gg.width + w;
if (nodes[iA].walkable == false)
{
/*
* Quarters order ("A" is the tested node) :
* 3 | 4
* --A--B
* 2 | 1
* C D
*/

// Quarter 1
if ((w < (gg.width - 1)) && (d > 0))
{
ComputeQuarter(sim, gg, w, d, 1, 0, 0, -1, 1, -1);
}

// Quarter 2
if ((w > 0) && (d > 0))
{
ComputeQuarter(sim, gg, w, d, 0, -1, -1, 0, -1, -1);
}

// Quarter 3
if ((w > 0) && (d < (gg.depth - 1)))
{
ComputeQuarter(sim, gg, w, d, -1, 0, 0, 1, -1, 1);
}

// Quarter 4
if ((w < (gg.width - 1)) && (d < (gg.depth - 1)))
{
ComputeQuarter(sim, gg, w, d, 0, 1, 1, 0, 1, 1);
}
}
}
}
Debug.Log(string.Format("RVOGridGraph.AddGraphObstacles() : {0} obstacles", obstacles.Count));
}

/** Compute a quarter of 4 nodes (A, B, C, D) where A is unwalkable and add AB or AD ObstacleVertex if needed */
private void ComputeQuarter(Pathfinding.RVO.Simulator sim, GridGraph gg, int w, int d, int wB, int dB, int wC, int dC, int wD, int dD)
{
Node[] nodes = gg.nodes;

int iA = (d + 0) * gg.width + w + 0;
int iB = (d + dB) * gg.width + w + wB;
int iC = (d + dC) * gg.width + w + wC;
int iD = (d + dD) * gg.width + w + wD;

bool nodeB = nodes[iB].walkable;
bool nodeC = nodes[iC].walkable;
bool nodeD = nodes[iD].walkable;

if ((nodeB == false) && (nodeC == true) && (nodeD == true))
{
obstacles.Add(sim.AddObstacle((Vector3)nodes[iA].position, (Vector3)nodes[iB].position, wallHeight));
}

if ((nodeB == false) && (nodeC == true) && (nodeD == false))
{
obstacles.Add(sim.AddObstacle((Vector3)nodes[iA].position, (Vector3)nodes[iD].position, wallHeight));
}
}

/** Draws Gizmos */
public void OnDrawGizmos()
{
OnDrawGizmos(false);
}

/** Draws Gizmos */
public void OnDrawGizmosSelected()
{
OnDrawGizmos(true);
}

/** Draws Gizmos */
public void OnDrawGizmos(bool selected)
{
Gizmos.color = new Color(0.615f, 1, 0.06f, selected ? 1.0f : 0.7f);

foreach (ObstacleVertex ov in obstacles)
{
if (ov.next == null)
throw new System.InvalidOperationException("RVOGridGraph.OnDrawGizmos() : obstacles[...].next == null");

Vector3 a = ov.position;
Vector3 b = ov.next.position;

Gizmos.DrawLine(a, b);

if (selected)
{
// Draw the little arrow to show the direction of the obstacle
Vector3 avg = (a + b) * 0.5f;
Vector3 tang = (b - a).normalized;
if (tang != Vector3.zero)
{
Vector3 normal = Vector3.Cross(Vector3.up, tang);

Gizmos.DrawLine(avg, avg + normal);
Gizmos.DrawLine(avg + normal, avg + normal * 0.5f + tang * 0.5f);
Gizmos.DrawLine(avg + normal, avg + normal * 0.5f - tang * 0.5f);
}
}
}
}
} 


منبع :
http://www.aftermoon.net/2013-news.html#news-20130216
http://arongranberg.com/vanillaforums/di...ide#latest

-

بازم برای اطلاعات بیشتر توی google بزنید :
path finding a star unity3d
-

نکته ی مهم :
در مرحله ی اول مستقیم روی کدنویسی فکر نمی خواد کنید. یکم چیزای کلی رو درک کنید و بعدش یکم برنامه نویسی و حلقه ی تکرار و آرایه و این چیزا رو بلد باشید و همون درسایی که در بخش مقالات یونیتی هست رو دنبال کنید تا بین هزاران پکیج و پلاگین گم نشید.

از پکیج و پلاگین ها می تونید استفاده کنید ولی خودتون بعدا به سورس ها نگاه کنید.

اگه یه سورس قلمبه می بینید یه دفعه لازم نیست هضمش کنید. ابتدا شما دنبال برنامه نویسی خودتون باشید و کم کم با تحقیق، چیزای بزرگ تری رو درک خواهید کرد
http://arongranberg.com/astar/