2009 九月 | 专注Java .Net技术

存档

2009年9月的存档

A*寻路算法

2009年9月18日 admin 1 条评论

效果如下：

程序入口： Game.as

package
{
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.events.MouseEvent;

public class Game extends Sprite
{
private var _cellSize:int = 20;
private var _grid:Grid;
private var _player:Sprite;
private var _index:int;
private var _path:Array;

public function Game()
{
   stage.align = StageAlign.TOP_LEFT;
   stage.scaleMode = StageScaleMode.NO_SCALE;

   makePlayer();
   makeGrid();
   stage.addEventListener(MouseEvent.CLICK, onGridClick);
}

/**
   * Creates the player sprite. Just a circle here.
   */
private function makePlayer():void
{
   _player = new Sprite();
   _player.graphics.beginFill(0xff0000);
   _player.graphics.drawCircle(0, 0, 5);
   _player.graphics.endFill();
   _player.x = Math.random() * 600;
   _player.y = Math.random() * 600;
   addChild(_player);
}

/**
   * Creates a grid with a bunch of random unwalkable nodes.
   */
private function makeGrid():void
{
   _grid = new Grid(30, 30);
   for(var i:int = 0; i < 200; i++)
   {
   _grid.setWalkable(Math.floor(Math.random() * 30),
   Math.floor(Math.random() * 30),
   false);
   }
   drawGrid();
}

/**
   * Draws the given grid, coloring each cell according to its state.
   */
private function drawGrid():void
{
   graphics.clear();
   for(var i:int = 0; i < _grid.numCols; i++)
   {
   for(var j:int = 0; j < _grid.numRows; j++)
   {
   var node:Node = _grid.getNode(i, j);
   graphics.lineStyle(0);
   graphics.beginFill(getColor(node));
   graphics.drawRect(i * _cellSize, j * _cellSize, _cellSize, _cellSize);
   }
   }
}

/**
   * Determines the color of a given node based on its state.
   */
private function getColor(node:Node):uint
{
   if(!node.walkable) return 0;
   if(node == _grid.startNode) return 0xcccccc;
   if(node == _grid.endNode) return 0xcccccc;
   return 0xffffff;
}

/**
   * Handles the click event on the GridView. Finds the clicked on cell and toggles its walkable state.
   */
private function onGridClick(event:MouseEvent):void
{
   var xpos:int = Math.floor(mouseX / _cellSize);
   var ypos:int = Math.floor(mouseY / _cellSize);
   _grid.setEndNode(xpos, ypos);

   xpos = Math.floor(_player.x / _cellSize);
   ypos = Math.floor(_player.y / _cellSize);
   _grid.setStartNode(xpos, ypos);

   drawGrid();
   findPath();
}

/**
   * Creates an instance of AStar and uses it to find a path.
   */
private function findPath():void
{
   var astar:AStar = new AStar();
   if(astar.findPath(_grid))
   {
   _path = astar.path;
   _index = 0;
   addEventListener(Event.ENTER_FRAME, onEnterFrame);
   }
}

/**
   * Finds the next node on the path and eases to it.
   */
private function onEnterFrame(event:Event):void
{
   var targetX:Number = _path[_index].x * _cellSize + _cellSize / 2;
   var targetY:Number = _path[_index].y * _cellSize + _cellSize / 2;
   var dx:Number = targetX - _player.x;
   var dy:Number = targetY - _player.y;
   var dist:Number = Math.sqrt(dx * dx + dy * dy);
   if(dist < 1)
   {
   _index++;
   if(_index >= _path.length)
   {
   removeEventListener(Event.ENTER_FRAME, onEnterFrame);
   }
   }
   else
   {
   _player.x += dx * .5;
   _player.y += dy * .5;
   }
}
}
}

核心算法 AStar.as

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 = 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);
   }
   }
   }

   _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);
}
}
}

布局：Grid.as

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;
}

}
}

展现：GridView.as

package
{
import flash.display.Sprite;
import flash.events.MouseEvent;

/**
* Serves as a visual representation of a grid of nodes used in a pathfinding solution.
*/
public class GridView extends Sprite
{
private var _cellSize:int = 20;
private var _grid:Grid;

/**
   * Constructor.
   */
public function GridView(grid:Grid)
{
   _grid = grid;
   drawGrid();
   findPath();
   addEventListener(MouseEvent.CLICK, onGridClick);
}

/**
   * Draws the given grid, coloring each cell according to its state.
   */
public function drawGrid():void
{
   graphics.clear();
   for(var i:int = 0; i < _grid.numCols; i++)
   {
   for(var j:int = 0; j < _grid.numRows; j++)
   {
   var node:Node = _grid.getNode(i, j);
   graphics.lineStyle(0);
   graphics.beginFill(getColor(node));
   graphics.drawRect(i * _cellSize, j * _cellSize, _cellSize, _cellSize);
   }
   }
}

/**
   * Determines the color of a given node based on its state.
   */
private function getColor(node:Node):uint
{
   if(!node.walkable) return 0;
   if(node == _grid.startNode) return 0x666666;
   if(node == _grid.endNode) return 0x666666;
   return 0xffffff;
}

/**
   * Handles the click event on the GridView. Finds the clicked on cell and toggles its walkable state.
   */
private function onGridClick(event:MouseEvent):void
{
   var xpos:int = Math.floor(event.localX / _cellSize);
   var ypos:int = Math.floor(event.localY / _cellSize);

   _grid.setWalkable(xpos, ypos, !_grid.getNode(xpos, ypos).walkable);
   drawGrid();
   findPath();
}

/**
   * Creates an instance of AStar and uses it to find a path.
   */
private function findPath():void
{
   var astar:AStar = new AStar();
   if(astar.findPath(_grid))
   {
   showVisited(astar);
   showPath(astar);
   }
}

/**
   * Highlights all nodes that have been visited.
   */
private function showVisited(astar:AStar):void
{
   var visited:Array = astar.visited;
   for(var i:int = 0; i < visited.length; i++)
   {
   graphics.beginFill(0xcccccc);
   graphics.drawRect(visited[i].x * _cellSize, visited[i].y * _cellSize, _cellSize, _cellSize);
   graphics.endFill();
   }
}

/**
   * Highlights the found path.
   */
private function showPath(astar:AStar):void
{
   var path:Array = astar.path;
   for(var i:int = 0; i < path.length; i++)
   {
   graphics.lineStyle(0);
   graphics.beginFill(0);
   graphics.drawCircle(path[i].x * _cellSize + _cellSize / 2,
   path[i].y * _cellSize + _cellSize / 2,
   _cellSize / 3);
   }
}
}
}

节点：Node.as

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;
}
}
}

最后把源码贴出来：点击下载

Popularity: unranked [?]

分类: FLex, Flash 标签: A*寻路算法

曼哈顿距离

2009年9月16日 admin 没有评论

首先介绍一下曼哈顿，曼哈顿是一个极为繁华的街区，高楼林立，街道纵横，从A地点到达B地点没有直线路径，必须绕道，而且至少要经C地点，走AC和CB才能到达，由于街道很规则，ACB就像一个直角3角形，AB是斜边，AC和CB是直角边，根据毕达格拉斯定理，或者向量理论，都可以知道用AC和CB可以表达AB的长度。
在早期的计算机图形学中，屏幕是由像素构成，是整数，点的坐标也一般是整数，原因是浮点运算很昂贵，很慢而且有误差，如果直接使用AB的距离，则必须要进行浮点运算，如果使用AC和CB，则只要计算加减法即可，这就大大提高了运算速度，而且不管累计运算多少次，都不会有误差。因此，计算机图形学就借用曼哈顿来命名这一表示方法。
在我们常用的平面CAD中，都会有格点，他是基本单位，定义了格点大小后，就可以使用整数来表示和运算，不会引入计算误差，又快又精确。
与此类似，在3维图形学中，空间向量也是用3个单位向量的和来表示的。

wikipedia的解释如下：
出租车几何或曼哈顿距离或方格线距离是由十九世纪的赫尔曼·闵可夫斯基所创词汇，是种使用在欧几里得几何度量空间的几何学用语，用以标明两个点上在标准座标系上的绝对轴距总和。

曼哈顿距离
我们可以定义曼哈顿距离的正式意义为L₁-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。

例如在平面上，座标（x₁, y₁）的点P₁与座标（x₂, y₂）的点P₂的曼哈顿距离为：

$\left|x_1 - x_2\right| + \left|y_1 - y_2\right|.$

要注意的是，曼哈顿距离依赖座标系统的转度，而非系统在座标轴上的平移或映射。

曼哈顿距离的命名原因是从规划为方型建筑区块的城市（如曼哈顿）间，最短的行车路径而来（忽略曼哈顿的单向车道以及只存在于3、14大道的斜向车道）。任何往东三区块、往北六区块的的路径一定最少要走九区块，没有其他捷径。

出租车几何学满足除了SAS全等定理之外的希伯特定理，SAS全等指任两个三角型两个边与一个角相等，则这两个三角型必全等。

在出租车几何学中，一个圆是由从圆心向各个固定曼哈顿距离标示出来的点围成的区域。因此这种圆其实就是旋转了45度的正方形。如果有一群圆，任两圆皆相交，则整群圆必在某点相交；因此曼哈顿距离会形成一个超凸度量空间（Injective metric space）。对一个半径为r 的圆来说，这个正方形的圆每边长√2r。此’”圆”的半径r对切比雪夫距离（L_∞空间）的二维平面来说，也是一个对座标轴来说边长为2r的正方形，因此二维切比雪夫距离可视为等同于旋转且放大过的二维曼哈顿距离。然而这种介于L₁与L_∞的相等关系并不能延伸到更高的维度。

在棋盘上的距离计量

在西洋棋里，车（城堡）是以曼哈顿距离来计算棋盘格上的距离；而王（国王）与后（皇后）使用切比雪夫距离，象（主教）则是用转了45度的曼哈顿距离来算（在同色的格子上），也就是说它以斜线为行走路径。只有国王需要一步一步走的方式移动，皇后、主教与城堡可以在一或两次移动走到任何一格（在没有阻碍物的情况下，且主教忽略它不能走到的另一类颜色）。

Popularity: unranked [?]

分类: FLex, Flash 标签: 曼哈顿距离, 曼哈顿距离公式

Flash经典画曲线

2009年9月5日 admin 没有评论

不多说了，把代码贴出来：

package
{
   import flash.display.Sprite;
   import flash.events.MouseEvent;

   public class DrawingApp extends Sprite
   {
   public function DrawingApp()
   {
   init();
   }
   private function init():void
   {
   graphics.lineStyle(1);
   stage.addEventListener(MouseEvent.MOUSE_DOWN,onMouseDowns);
   stage.addEventListener(MouseEvent.MOUSE_UP,onMouseUps);
   }

   private function onMouseDowns(e:MouseEvent)
   {
   graphics.moveTo(mouseX,mouseY);
   stage.addEventListener(MouseEvent.MOUSE_MOVE,onMouseMoves);
   }

   private function onMouseUps(e:MouseEvent)
   {
   stage.removeEventListener(MouseEvent.MOUSE_MOVE,onMouseMoves);
   }

   private function onMouseMoves(e:MouseEvent)
   {
   graphics.lineTo(mouseX,mouseY);
   }
   }
}

Popularity: unranked [?]

分类: FLex, Flash 标签: Actionscript画曲线, Flash经典画曲线

专注Java .Net技术

存档

A*寻路算法

曼哈顿距离

Flash经典画曲线

联系方式

分类目录

文章索引模板

友情链接

最近评论