A* Algoritması

Giriş
A start algoritması, Dijkstra's Shortest Path bulunurken arada engeller var ise kullanılır. Açıklaması şöyle

Dijkstra is just A* with dijkstra_heuristic(x) = 0

Açıklaması şöyle.

A* is basically the same as Dijkstra with one simple modification.

Edges are prioritized also with respect to how much closer that edge leads to a straight-line distance to the goal. So before running an A* search, the straight-line distance to the final destination has to be measured for every node, which is easy if you know each nodes coordinate.

Örnek
Şöyle yaparız.

private void AstarSearch()
{
  Start.MinCostToStart = 0;
  var prioQueue = new List<Node>();
  prioQueue.Add(Start);
  do {
    prioQueue = prioQueue.OrderBy(x => x.MinCostToStart + x.StraightLineDistanceToEnd).ToList();
    var node = prioQueue.First();
    prioQueue.Remove(node);
    NodeVisits++;
    foreach (var cnn in node.Connections.OrderBy(x => x.Cost))
    {
      var childNode = cnn.ConnectedNode;
      if (childNode.Visited)
        continue;
      if (childNode.MinCostToStart == null ||
            node.MinCostToStart + cnn.Cost < childNode.MinCostToStart)
      {
        childNode.MinCostToStart = node.MinCostToStart + cnn.Cost;
        childNode.NearestToStart = node;
        if (!prioQueue.Contains(childNode))
          prioQueue.Add(childNode);
        }
      }
      node.Visited = true;
      if (node == End)
        return;
  } while (prioQueue.Any());
}

Deadlock ve Livelock
Farkı şöyle

A deadlock is when both wait for the other to move and none move.

A livelock is when both (or more <- this is important to consider) move to avoid the other in the same direction and end up going back and forth with no progress.

Solving livelocks can become very complex and that depends entirely on your game's collision rules and mechanics (e.g.: should they fight and destroy the obstacle?).

Manhattan Mesafesi
Açıklaması şöyle

The Manhattan distance only works when you have a well-defined distance metric that you can apply to pairs of nodes, such as with points in a 2D plane.

Diğer Algoritmalar
Açıklaması şöyle

There are multiple algorithms that are much faster than A* when you need to recalculate a path with moving obstacles. See here under "Simple Recalculations".

However, you're not likely going to find an off-the-shelf solution for any of them, so in 99% of cases they're overkill for a game.