这是教程教你建立路径查找算法的第一步。
路径查找就是在两点之间查找最短路径的算法，你可以在很多地方应用，例如：玩家控制角色时通过点击设置目的地时，就需要用到。
在开始前，我们需要明确一点：路径查找是在终点给定的情况下才会工作。另外这只是系列教程中的第一步，因此我将说明一些最基本且效率不高的算法，然后我们会利用启发式方法一起研究出著名的A*算法。
我不想发布另一个A*算法，按照下面的步骤你会掌握路径查找的基本知识而不只是拷贝代码。这也是我用动画演示的原因。
让我们分析下一个简单基本路径查找算法。
* 给定一个起始点并知道终点，我会检测所有邻近起始点的点看是否在路径上，然后挨个检测下面的三个值。
G: 从起始点到检测点的成本。我一般用1.
H:检测点到终点之间可能的距离。我说可能因为我只能稼穑当前点到终点的距离，因为它会随着墙或者移动的成本而改变。最简单计算可能距离的方法就是用曼哈坦距离。我会在例子中使用。如果想知道更多曼哈坦距离的知识，可以查看下《两点之间查找距离的最快方法》这篇博文。
F:简单的G+H
*一旦检查完所有相邻瓦块后，我选择F值最小的并设为已经访问过。
*重新琢磨下后使用选择的瓦块作为起始点。
几步后，我会遇到下面两种情况：
*找到终点，过关喽
*没有合法移动。这种情况我就必须回溯到一个有效的移动才能继续运行或者直接回溯到其实地方，当然那也意味着永远到不了终点。
第一次没经过优化的算法用AS3写法如下：
package {
import flash.display.Sprite;
import flash.geom.Point;
import flash.events.MouseEvent;
import flash.utils.Timer;
import flash.events.TimerEvent;
public class Main extends Sprite {
private var canvas:Sprite;
private var startPoint:Point;
private var endPoint:Point;
private var currPoint:Point;
private var tileVector:Vector.<Object>;
private var path:Vector.<Point>;
private var timer:Timer;
public function Main() {
canvas=new Sprite();
addChild(canvas);
fieldSetup();
drawGrid();
findPath();
stage.addEventListener(MouseEvent.CLICK,addWall);
}
// fieldSetup prepares the field. Each tile in the field is set to its default value:
// * it's walkable
// * it's not the start point
// * it's not the end point
// * it has not been visited
private function fieldSetup():void {
timer=new Timer(100);
canvas.graphics.clear();
tileVector=new Vector.<Object>();
for (var i:Number=0; i<16; i++) {
tileVector[i]=new Vector.<Object>();
for (var j:Number=0; j<12; j++) {
tileVector[i][j]=new Object();
tileVector[i][j].walkable=true;
tileVector[i][j].startPoint=false;
tileVector[i][j].endPoint=false;
tileVector[i][j].visited=false;
}
}
// while the starting point is choosen absolutely random...
startPoint=new Point(Math.floor(Math.random()*16),Math.floor(Math.random()*12));
tileVector[startPoint.x][startPoint.y].startPoint=true;
tileVector[startPoint.x][startPoint.y].visited=true;
// ... we want the end point to be at least 10 tiles away from start point.
// jsut to make things interesting
do {
endPoint=new Point(Math.floor(Math.random()*16),Math.floor(Math.random()*12));
} while (manhattan(startPoint,endPoint)<10);
tileVector[endPoint.x][endPoint.y].endPoint=true;
}
// findPath function initializes the field and sets the time listener to draw the path
private function findPath():void {
path=new Vector.<Point>();
path.push(startPoint);
for (var i:Number=0; i<16; i++) {
for (var j:Number=0; j<12; j++) {
tileVector[i][j].visited=false;
}
}
currPoint=new Point(startPoint.x,startPoint.y);
timer.addEventListener(TimerEvent.TIMER,step);
timer.start();
}
// step is the core function. Let's explain it deeply
private function step(e:TimerEvent):void {
// f will be the variable which minimum value will decide which direction to take.
// I created a minF variable with an high value to store the minimum f value found
var minF:Number=10000;
// initializing a temporary Point variable
var savedPoint:Point;
for (var i:Number=-1; i<=1; i++) {
for (var j:Number=-1; j<=1; j++) {
// these two for loops together with this if statement will scan for all four directions. No diagonals at the moment.
if ((i!=0 && j==0)||(i==0 && j!=0)) {
// we consider a tile only if:
// * is inside the tile field
// * is walkable (not a wall)
// * has not been already visited
if (insideField(currPoint,i,j) && tileVector[currPoint.x+i][currPoint.y+j].walkable && !tileVector[currPoint.x+i][currPoint.y+j].visited) {
// now, core of the loop: let's determine g, h and f
// g represents the cost to move from the starting tile to the current tile. At the moment we aren't using this variable
// so getG function will always return 1
var g:Number=getG(i,j);
// h is the presumable distance from the current tile and the ending tile. One of the quickest way to determine it is
// using manhattan distance
var h:Number=manhattan(new Point(currPoint.x+i,currPoint.y+j),endPoint);
// f is just the sum of g and h
var f:Number=g+h;
// if the current f value is lower than the minimum f value found so far...
if (f<minF) {
// ... we update minF value and we save the current tile
minF=f;
savedPoint=new Point(currPoint.x+i,currPoint.y+j);
}
}
}
}
}
// once all neighbor tiles have been scanned, we can have two situations:
// * we found a candidate (savedPoint) for the next tile, and we continue the process
// * we did not found a candidate, so we are on a dead end and we must backtrack
if (savedPoint) {
// continue...
if (savedPoint.x!=endPoint.x||savedPoint.y!=endPoint.y) {
drawTile(savedPoint.x,savedPoint.y,0x0000ff);
}
tileVector[savedPoint.x][savedPoint.y].visited=true;
currPoint=savedPoint;
path.push(currPoint);
if (path.length>2) {
drawTile(path[path.length-2].x,path[path.length-2].y,0xcccccc);
}
if (currPoint.x==endPoint.x&&currPoint.y==endPoint.y) {
// solved
timer.removeEventListener(TimerEvent.TIMER,step);
}
}
else {
// backtrack
if (path.length>1) {
currPoint=path[path.length-2];
drawTile(path[path.length-1].x,path[path.length-1].y,0xffffff);
path.pop();
}
else {
// can't be solved
drawTile(currPoint.x,currPoint.y,0xff00ff);
timer.removeEventListener(TimerEvent.TIMER,step);
}
}
}
// getG function will become really important during next steps, but at the moment just returns 1
private function getG(n1:Number,n2:Number) {
return 1;
}
// function to find manhattan distance between two points
private function manhattan(p1:Point,p2:Point):Number {
return Math.abs(p1.x-p2.x)+Math.abs(p1.y-p2.y);
}
// insideField checks if a given point inside the field will remain inside the field after adding a x and y offset
private function insideField(p:Point,n1:Number,n2:Number):Boolean {
if (p.x+n1>15||p.x+n1<0||p.y+n2>11||p.y+n2<0) {
return false;
}
return true;
}
// function to add/remove a wall or generate another random grid
private function addWall(e:MouseEvent):void {
var row:Number=Math.floor(mouseY/40);
var col:Number=Math.floor(mouseX/40);
if (! tileVector[col][row].startPoint&&! tileVector[col][row].endPoint) {
tileVector[col][row].walkable=! tileVector[col][row].walkable;
}
else {
timer.removeEventListener(TimerEvent.TIMER,step);
fieldSetup();
}
drawGrid();
findPath();
}
// drawTile function just draws a tile in a given position with a given color
private function drawTile(pX:Number,pY:Number,color:Number):void {
canvas.graphics.beginFill(color,1);
canvas.graphics.drawRect(pX*40,pY*40,40,40);
canvas.graphics.endFill();
}
// function to draw the entire grid;
private function drawGrid() {
canvas.graphics.clear();
canvas.graphics.lineStyle(1,0x999999);
for (var i:Number=0; i<16; i++) {
for (var j:Number=0; j<12; j++) {
drawTile(i,j,0xffffff);
if (tileVector[i][j].walkable==false) {
drawTile(i,j,0x000000);
}
if (tileVector[i][j].startPoint==true) {
drawTile(i,j,0x00ff00);
}
if (tileVector[i][j].endPoint==true) {
drawTile(i,j,0xff0000);
}
}
}
}
}
}
复制代码
这是结果…有时候路径会比预期的长很多，但是还是会正常工作。
![]()
每个方块的含义：
绿色方块:起始点
红色方块：终点
黑色方块：墙
灰色方块：路径
蓝色方块：当前位置
紫色方块：放弃了，终点找不到哦
来看下如何进行交互：
点击空或者路径瓦块：添加墙
点击黑色瓦块：消除墙
点击开始或结束瓦块：随机生成另一个起始点
今天到此为止，下次我们会进行优化。
下载源码：
http://www.emanueleferonato.com/wp-content/uploads/2012/11/astar.zip
原文链接：http://www.emanueleferonato.com/2012/11/26/the-basics-of-pathfinding-animated-example/
