注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

眼睛想旅行

技术就是我的生命与信仰!

 
 
 

日志

 
 
关于我

精通C,C++,python,Erlang。并熟悉各种其他编程语言,用cocos2dx游戏引擎作过几个项目。会MySQL增删改查,了解OpenGL渲染原理。懂单片机,能设计数字电路系统,会画电路图和设计电路板。喜欢了解最新前沿技术,并持续关注和学习新技术。

网易考拉推荐

A*(AStar)或者也叫A星算法的寻路问题  

2012-06-02 02:02:32|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

最近在学作游戏,需要了解一种很好很强大的,也很实用的地图有障碍物时寻找最隹路径的方法。

我发现这个方法不是只能用在游戏中,觉得机器人在室内或者室外自行移动,也完全适用这种算法。

下边开始学习:

在学习之前,要先了解一下A*算法中的专用术语:

1.节点:在基于区块的世界中这实际是一个区块。但,A*中没有使用区块(tile)、单元(cell)、点(potint),而是使用了术语节点(node)来指定所检查的路径,所以一个路径会包含起始节点,终止节点或目标节点,以及构成二者之间最隹路径的一个节点列表。

2.代价:这是根据各个节点对于路径的适宜度而为节点指定的等级值。较低代价的节点比较高代价的节点更可取。代价(cost)由两部分组成,从起始节点到达某个节点的代价,以及从该节点到达目标节点的估计代价。代价元素通常用变量f、g和h表示,下面将逐一介绍。

3.f:一个特定节点的总代价,定义为g+h。

4.g:从起始节点到达某个特定节点的代价。可以准确计算,因为你往往知道从起始节点到达该节点所选取的具体路径。

5.h:从一个特定节点到达终止节点的估计代价。这个估计通过一个启发函数完成。这只是一个估计,因为你不知道要选取的具体路径。这是你要确定的。

6.启发函数:估计从一个特定节点到达终止节点所需代价的函数。存在多种常用的启发函数,它们在速度、效率等方面会有不同的结果。

7.待查列表:已经访问并已指定代价的节点的列表。这个列表中的最低代价节点将用于下一次搜索迭代。

8.已查列表:所有相邻节点都已经访问的节点的列表。

9.父节点:迭代处理到一个节点时,其相邻的各个节点都会得到检查,并将该节点指定为父节点。所以到达目标节点时,可以沿着父节点链回溯到起始节点。由于父节点总是待查列表中的最低代价节点,所以肯定能得到最佳路径。


下边是一个面向对象的A*算法类:

第一个:Grid类,这个类中包含一个启始节点,一个终止节点,一个地图节点(node)数组,以及地图的行和列大小几个属性参数,包含的方法主要是对这些参数的初始化操作,和get,set方法。

package
{
 /**
  * Holds a two-dimensional array of Nodes methods to manipulate them, start node and end node for finding a path.
  */
 public class Grid
 {
  private var _startNode:Node;
  private var _endNode:Node;
  private var _nodes:Array;
  private var _numCols:int;
  private var _numRows:int;
  
  /**
   * Constructor.
   */
  public function Grid(numCols:int, numRows:int)
  {
   _numCols = numCols;
   _numRows = numRows;
   _nodes = new Array();
   
   for(var i:int = 0; i < _numCols; i++)
   {
    _nodes[i] = new Array();
    for(var j:int = 0; j < _numRows; j++)
    {
     _nodes[i][j] = new Node(i, j);
    }
   }
  }
  
  
  ////////////////////////////////////////
  // public methods
  ////////////////////////////////////////
  
  /**
   * Returns the node at the given coords.
   * @param x The x coord.
   * @param y The y coord.
   */
  public function getNode(x:int, y:int):Node
  {
   return _nodes[x][y] as Node;
  }
  
  /**
   * Sets the node at the given coords as the end node.
   * @param x The x coord.
   * @param y The y coord.
   */
  public function setEndNode(x:int, y:int):void
  {
   _endNode = _nodes[x][y] as Node;
  }
  
  /**
   * Sets the node at the given coords as the start node.
   * @param x The x coord.
   * @param y The y coord.
   */
  public function setStartNode(x:int, y:int):void
  {
   _startNode = _nodes[x][y] as Node;
  }
  
  /**
   * Sets the node at the given coords as walkable or not.
   * @param x The x coord.
   * @param y The y coord.
   */
  public function setWalkable(x:int, y:int, value:Boolean):void
  {
   _nodes[x][y].walkable = value;
  }
  
  
  
  ////////////////////////////////////////
  // getters / setters
  ////////////////////////////////////////
  
  /**
   * Returns the end node.
   */
  public function get endNode():Node
  {
   return _endNode;
  }
  
  /**
   * Returns the number of columns in the grid.
   */
  public function get numCols():int
  {
   return _numCols;
  }
  
  /**
   * Returns the number of rows in the grid.
   */
  public function get numRows():int
  {
   return _numRows;
  }
  
  /**
   * Returns the start node.
   */
  public function get startNode():Node
  {
   return _startNode;
  }
  
 }

第二个类:Node类,这个类主要包含与单个节点有关的信息,如节点坐标,节点的三个代价f、g、h,是否为可通过节点,以及节点间单位代价和当前节点的父节点信息。所包含的方法也就是这些参数的初始化操作。

package
{
 /**
  * Represents a specific node evaluated as part of a pathfinding algorithm.
  */
 public class Node
 {
  public var x:int;
  public var y:int;
  public var f:Number;
  public var g:Number;
  public var h:Number;
  public var walkable:Boolean = true;
  public var parent:Node;
  public var costMultiplier:Number = 1.0;
  
  public function Node(x:int, y:int)
  {
   this.x = x;
   this.y = y;
  }
 }
}

 
第三个类,也是AStar算法中最主要的类,即,AStar类,这个类中包含的参数有,一个已查列表(数组),一个待查列表(数组),一个地图Grid实例,开始节点,终止节点,最佳路径(数组),启发函数(实际上是指向启发函数的指针),还有上下左右相邻节点代价和四个斜角的代价。包含的方法有从Gide实际地图中找到最佳路径,如果有则返回真,并在最佳路径参数中保存最佳路径。以及三个常见启发函数。这三个启发函数可以在参数中按程序需要选择设置(只要取掉相应启发函数注释就可以了)。
 

package
{
 public class AStar
 {
  private var _open:Array;
  private var _closed:Array;
  private var _grid:Grid;
  private var _endNode:Node;
  private var _startNode:Node;
  private var _path:Array;
//  private var _heuristic:Function = manhattan;
//  private var _heuristic:Function = euclidian;
  private var _heuristic:Function = diagonal;
  private var _straightCost:Number = 1.0;
  private var _diagCost:Number = Math.SQRT2;
  
  
  public function AStar()
  {
  }
  
  public function findPath(grid:Grid):Boolean
  {
   _grid = grid;
   _open = new Array();
   _closed = new Array();
   
   _startNode = _grid.startNode;
   _endNode = _grid.endNode;
   
   _startNode.g = 0;
   _startNode.h = _heuristic(_startNode);
   _startNode.f = _startNode.g + _startNode.h;
   
   return search();
  }
  
  public function search():Boolean
  {
   var node:Node = _startNode;
   while(node != _endNode)
   {
    var startX:int = Math.max(0, node.x - 1);
    var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
    var startY:int = Math.max(0, node.y - 1);
    var endY:int = Math.min(_grid.numRows - 1, node.y + 1);
    
    for(var i:int = startX; i <= endX; i++)
    {
     for(var j:int = startY; j <= endY; j++)
     {
      var test:Node = _grid.getNode(i, j);
      if(test == node ||
         !test.walkable ||
         !_grid.getNode(node.x, test.y).walkable ||
         !_grid.getNode(test.x, node.y).walkable)
      {
       continue;
      }
      
      var cost:Number = _straightCost;
      if(!((node.x == test.x) || (node.y == test.y)))
      {
       cost = _diagCost;
      }
      var g:Number = node.g + cost * test.costMultiplier;
      var h:Number = _heuristic(test);
      var f:Number = g + h;
      if(isOpen(test) || isClosed(test))
      {
       if(test.f > f)
       {
        test.f = f;
        test.g = g;
        test.h = h;
        test.parent = node;
       }
      }
      else
      {
       test.f = f;
       test.g = g;
       test.h = h;
       test.parent = node;
       _open.push(test);
      }
     }
    }
    for(var o:int = 0; o < _open.length; o++)
    {
    }
    _closed.push(node);
    if(_open.length == 0)
    {
     trace("no path found");
     return false
    }
    _open.sortOn("f", Array.NUMERIC);
    node = _open.shift() as Node;
   }
   buildPath();
   return true;
  }
  
  private function buildPath():void
  {
   _path = new Array();
   var node:Node = _endNode;
   _path.push(node);
   while(node != _startNode)
   {
    node = node.parent;
    _path.unshift(node);
   }
  }
  
  public function get path():Array
  {
   return _path;
  }
  
  private function isOpen(node:Node):Boolean
  {
   for(var i:int = 0; i < _open.length; i++)
   {
    if(_open[i] == node)
    {
     return true;
    }
   }
   return false;
  }
  
  private function isClosed(node:Node):Boolean
  {
   for(var i:int = 0; i < _closed.length; i++)
   {
    if(_closed[i] == node)
    {
     return true;
    }
   }
   return false;
  }
  
  private function manhattan(node:Node):Number
  {
   return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
  }
  
  private function euclidian(node:Node):Number
  {
   var dx:Number = node.x - _endNode.x;
   var dy:Number = node.y - _endNode.y;
   return Math.sqrt(dx * dx + dy * dy) * _straightCost;
  }
  
  private function diagonal(node:Node):Number
  {
   var dx:Number = Math.abs(node.x - _endNode.x);
   var dy:Number = Math.abs(node.y - _endNode.y);
   var diag:Number = Math.min(dx, dy);
   var straight:Number = dx + dy;
   return _diagCost * diag + _straightCost * (straight - 2 * diag);
  }
  
  public function get visited():Array
  {
   return _closed.concat(_open);
  }
 }
}


在网上也看了另两个相关文章,觉得也写的不错:
http://we.zuisg.com/?p=378
http://wonderfl.net/c/aWCe
  评论这张
 
阅读(880)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017