非常简单的 A* 算法实现

• 下载演示项目 - 9.01 KB

引言

本文是关于 A* 算法的实现，它讲述了如何找到两个位置之间的最佳路径。 我已经知道 CodeProject 网站上还有其他的 A* 实现。 它们很好，但我相信对于初学者来说，这个实现更简单，更容易理解。

在这个实现中没有不必要的代码，我只是按照 A* 算法的伪代码一步一步地以非常直观的方式实现。 就像你在上面的图片中看到的那样，'#' 表示墙，每个点表示可通行的道路，'o' 表示 AI 找到的路径。

关于 A* 算法

简而言之，A* 是最流行的寻路算法，用于从起点到目标点，基于移动成本的效率。

您可以访问“A* Pathfinding for Beginners”（http://www.policyalmanac.org/games/aStarTutorial.htm）来学习该算法的工作原理。

您可以在 Justin Heyes-Jones 的 A* 教程中看到我在此实现中使用的 A* 伪代码。 访问这里（http://www.geocities.com/jheyesjones/pseudocode.html）查看原始伪代码。 打印出此伪代码将对您理解此实现大有帮助。

类设计

此实现中有三个主要类。

• Map - 此类表示地图。
  
• Node - 此类表示地图上的每个图块。它有两个主要方法。
  • CompareTo - 此方法允许我们决定哪个节点更好。如果此方法返回负数，我们可以说当前节点更好，这意味着当前节点的成本低于正在比较的其他节点。
  • isMatch - 这使我们能够确定两个节点的几何位置是否相同。
    
• SortedCostNodeList - 这是一个存储 Node 对象列表的列表。我们需要从列表中获取最低成本的节点，因此此列表实现为按节点成本值排序的列表，我们不需要每次都检查列表中所有元素的成本，以弹出成本最低的节点，因为它们已经排序好了。只需弹出一个即可。此列表有两个主要方法。
  • push - 按节点成本在适当的位置将节点元素添加到列表中。
  • 节点的 CompareTo 方法在内部用于按成本排序。
    pop - 只是从列表中返回最低成本节点并将其从列表中删除。

实现

这是算法的核心循环。

 
 ArrayList SolutionPathList = new ArrayList();

 //Create a node containing the goal state node_goal
 Node node_goal = new Node(null,null,1,15,15);
 
 //Create a node containing the start state node_start
 Node node_start = new Node(null,node_goal,1,0,0);
 

 //Create OPEN and CLOSED list
 SortedCostNodeList OPEN = new SortedCostNodeList ();
 SortedCostNodeList CLOSED = new SortedCostNodeList ();
 
 
 //Put node_start on the OPEN list
 OPEN.push (node_start);

 //while the OPEN list is not empty
 while (OPEN.Count>0)
 {
  //Get the node off the open list 
  //with the lowest f and call it node_current
  Node node_current = OPEN.pop ();

  //if node_current is the same state as node_goal we
  //have found the solution;
  //break from the while loop;
  if (node_current.isMatch (node_goal))
  {
    node_goal.parentNode = node_current.parentNode ;
    break;
  }

  //Generate each state node_successor that can come after node_current
  ArrayList successors = node_current.GetSuccessors ();
   
  //for each node_successor or node_current
  foreach (Node node_successor in successors)
  {
    //Set the cost of node_successor to be the cost of node_current plus
    //the cost to get to node_successor from node_current
    //--> already set while we were getting successors

    //find node_successor on the OPEN list
    int oFound = OPEN.IndexOf (node_successor);
     
    //if node_successor is on the OPEN list but the existing one is as good
    //or better then discard this successor and continue
  
    if (oFound>0)
    {
      Node existing_node = OPEN.NodeAt (oFound);
      if (existing_node.CompareTo (node_current) <= 0)
        continue;
    }


    //find node_successor on the CLOSED list
    int cFound = CLOSED.IndexOf (node_successor);
    
    //if node_successor is on the CLOSED list 
    //but the existing one is as good
    //or better then discard this successor and continue;
    if (cFound>0)
    {
      Node existing_node = CLOSED.NodeAt (cFound);
      if (existing_node.CompareTo (node_current) <= 0 )
        continue;
    }

    //Remove occurences of node_successor from OPEN and CLOSED
    if (oFound!=-1)
       OPEN.RemoveAt (oFound);
    if (cFound!=-1)
       CLOSED.RemoveAt (cFound);

    //Set the parent of node_successor to node_current;
    //--> already set while we were getting successors
    
    //Set h to be the estimated distance to node_goal 
    //(Using heuristic function)
    //--> already set while we were getting successors

    //Add node_successor to the OPEN list
    OPEN.push (node_successor);

   }
   //Add node_current to the CLOSED list
   CLOSED.push (node_current);
 }

一旦我们到达目标，按照父节点找到解决方案路径。

 //follow the parentNode from goal to start node
 //to find solution
 Node p = node_goal;
 while(p != null) 
 {
  SolutionPathList.Insert(0,p);
  p = p.parentNode ;
 }

此 A* 实现非常简单，非常适合那些想知道 A* 算法如何工作的初学者。 以各种方式更改地图数据，并检查 AI 如何智能地找到好的路径。 祝您编程愉快。