A*搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。
速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体（units）的数量、物体的重要性、组（group）的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是，建立一个启发式函数用于假定通过一个网格空间的最小代价是1，然后建立一个代价函数（cost function）用于测量（scales）： g’(n) = 1 + alpha * ( g(n) – 1 ) 如果alpha是0，则改进后的代价函数的值总是1。这种情况下，地形代价被完全忽略，A*工作变成简单地判断一个网格可否通过。如果alpha是1，则最初的代价函数将起作用，然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。 你也可以考虑对启发式函数的返回值做选择：绝对最小代价或者期望最小代价。例如，如果你的地图大部分地形是代价为2的草地，其它一些地方是代价为1的道路，那么你可以考虑让启发式函数不考虑道路，而只返回2*距离。 速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。 在游戏中，路径潜在地花费了许多存储空间，特别是当路径很长并且有很多物体需要寻路时。路径压缩，导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.如果路径仍然用了许多存储空间，可以限制路径长度，这就回到了经典的时间-空间折衷法：为了节省空间，信息可以被丢弃，稍后才重新计算它。

下面是原来写的代码:

package astart;
import java.awt.*;
import java.awt.event.*;
// Referenced classes of package game:
//			MyCanvas
public class GUI implements ActionListener {
	Frame f;
	MyCanvas c;
	Thread t;
	public GUI() {
		f = new Frame("title");
		c = new MyCanvas();
		c.setSize(201, 201);
		c.setBackground(Color.yellow);
		t = new Thread(c);
		Button start = new Button("start");
		Button pause = new Button("pause");
		Button again = new Button("again");
		start.addActionListener(this);
		pause.addActionListener(this);
		again.addActionListener(this);
		f.add(start);
		f.add(c);
		f.addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent e) {
				System.exit(1);
			}
		});
		f.setSize(300, 300);
		f.setLayout(new FlowLayout());
		f.setLocation(new Point(900, 600));
		f.setVisible(true);
	}
	public static void main(String args[]) {
		new GUI();
	}
	public void actionPerformed(ActionEvent e) {
		synchronized (t) {
			if (e.getActionCommand().equals("start"))
				t.start();
			else if (e.getActionCommand().equals("pause"))
				System.out.println("pause");
			else if (e.getActionCommand().equals("again"))
				System.out.println("again");
		}
	}
}

package astart;
class Node {
	public int x;
	public int y;
	public int f;
	public int g;
	public int h;
	public Node parent;
	public Node children[];
	public Node(int x, int y) {
		children = new Node[8];
		this.x = x;
		this.y = y;
	}
	public void show() {
		System.out.println((new StringBuilder("Node:x=")).append(x).append(
				",y=").append(y).append(",f=").append(f).append(",g=")
				.append(g).append(",h=").append(h).toString());
	}
}

package astart;
import java.util.*;
public class SearchDemo {
	int curX;
	int curY;
	static int size = 20;
	static int percentStore = 40;
	static long startTime = 0L;
	static long endTime = 0L;
	Node curNode;
	Vector<Node> openNodeList;
	Vector<Node> closeNodeList;
	Vector<Node> roadList;
	Random random;
	int world[][];
	int world_bak[][];
	Node start;
	Node goal;
	public int[][] getWorld() {
		return world;
	}
	public int[][] getWorld_bak() {
		return world_bak;
	}
	public Vector<Node> getRoad() {
		return roadList;
	}
	public SearchDemo(Node start, Node goal) {
		openNodeList = new Vector<Node>();
		closeNodeList = new Vector<Node>();
		roadList = new Vector<Node>();
		random = new Random();
		world = new int[size][size];
		world_bak = new int[size][size];
		this.start = start;
		this.goal = goal;
		openNodeList.removeAllElements();
		closeNodeList.removeAllElements();
		openNodeList.clear();
		closeNodeList.clear();
		openNodeList.add(start);
		curX = start.x;
		curY = start.y;
		start.g = 0;
		start.h = getHByNode(start);
		start.f = start.g + start.h;
	}
	int[][] search() {
		startTime = System.currentTimeMillis();
		do {
			curNode = getBesetNode();
			if (curNode == null) {
				System.out.println("I am lost!I can not find the way!");
				return null;
			}
			if (curNode.x == goal.x && curNode.y == goal.y) {
				endTime = System.currentTimeMillis();
				showThePath(curNode);
				System.out.println("I did it!");
				break;
			}
			getNodesAround(curNode);
		} while (true);
		return null;
	}
	void showThePath(Node node) {
		System.out.println((new StringBuilder("showThePath")).append(node.x)
				.append("-").append(node.y).toString());
		while (node != null) {
			roadList.add(new Node(node.x, node.y));
			node = node.parent;
			if (node != null)
				world[node.x][node.y] = 8;
		}
	}
	void getNodesAround(Node tempNode) {
		int row;
		int col;
		if (isCanMove(row = tempNode.x - 1, col = tempNode.y))
			creatSuccessionNode(tempNode, row, col, 10);
		if (isCanMove(row = tempNode.x + 1, col = tempNode.y))
			creatSuccessionNode(tempNode, row, col, 10);
		if (isCanMove(row = tempNode.x, col = tempNode.y - 1))
			creatSuccessionNode(tempNode, row, col, 10);
		if (isCanMove(row = tempNode.x, col = tempNode.y + 1))
			creatSuccessionNode(tempNode, row, col, 10);
		if (isCanMove(row = tempNode.x - 1, col = tempNode.y - 1))
			creatSuccessionNode(tempNode, row, col, 14);
		if (isCanMove(row = tempNode.x - 1, col = tempNode.y + 1))
			creatSuccessionNode(tempNode, row, col, 14);
		if (isCanMove(row = tempNode.x + 1, col = tempNode.y - 1))
			creatSuccessionNode(tempNode, row, col, 14);
		if (isCanMove(row = tempNode.x + 1, col = tempNode.y + 1))
			creatSuccessionNode(tempNode, row, col, 14);
		closeNodeList.addElement(tempNode);
		for (int i = 0; i < openNodeList.size(); i++) {
			if (((Node) openNodeList.elementAt(i)).x != tempNode.x
					|| ((Node) openNodeList.elementAt(i)).y != tempNode.y)
				continue;
			openNodeList.removeElementAt(i);
			break;
		}
	}
	boolean isCanMove(int x, int y) {
		if (x < 0 || y < 0 || x > size - 1 || y > size - 1)
			return false;
		return world[x][y] != 1;
	}
	void creatSuccessionNode(Node node, int x, int y, int value) {
		Node tempNode = null;
		int tempNodeG = node.g + value;
		if (!isInCloseNodeList(x, y))
			if ((tempNode = checkOpen(x, y)) != null) {
				if (tempNode.g > tempNodeG) {
					tempNode.parent = node;
					tempNode.g = tempNodeG;
					tempNode.f = tempNodeG + tempNode.h;
				}
			} else {
				Node newNode = new Node(x, y);
				newNode.parent = node;
				newNode.g = tempNodeG;
				newNode.h = getHByXY(x, y);
				newNode.f = newNode.g + newNode.h;
				openNodeList.addElement(newNode);
			}
	}
	boolean isInCloseNodeList(int x, int y) {
		for (Iterator<Node> iterator = closeNodeList.iterator(); iterator
				.hasNext();) {
			Node node = (Node) iterator.next();
			if (node.x == x && node.y == y)
				return true;
		}
		return false;
	}
	private Node checkOpen(int x, int y) {
		Node node = null;
		for (int i = 0; i < openNodeList.size(); i++)
			if (((Node) openNodeList.elementAt(i)).x == x
					&& ((Node) openNodeList.elementAt(i)).y == y) {
				node = (Node) openNodeList.elementAt(i);
				return node;
			}
		return node;
	}
	private Node getBesetNode() {
		Node bestNode = null;
		int f = 0x3b9ac9ff;
		for (Iterator<Node> iterator = openNodeList.iterator(); iterator
				.hasNext();) {
			Node fMinNode = (Node) iterator.next();
			if (f > fMinNode.f)
				bestNode = fMinNode;
		}
		return bestNode;
	}
	private int getHByNode(Node node) {
		return Math.abs(curX - node.x) + Math.abs(curY - node.y);
	}
	private int getHByXY(int x, int y) {
		return Math.abs(curX - x) + Math.abs(curY - y);
	}
	public SearchDemo() {
		openNodeList = new Vector<Node>();
		closeNodeList = new Vector<Node>();
		roadList = new Vector<Node>();
		random = new Random();
		world = new int[size][size];
		world_bak = new int[size][size];
	}
	void init() {
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				world[i][j] = random.nextInt(100) <= percentStore - 1 ? 1 : 0;
				world_bak[i][j] = world[i][j];
			}
		}
		world[0][0] = 0;
		world[size - 1][size - 1] = 0;
		world_bak[0][0] = 0;
		world_bak[size - 1][size - 1] = 0;
	}
	void showWorld() {
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				String str = world[i][j] >= 2 ? "X " : world[i][j] != 0 ? "● "
						: "  ";
				System.out.print(str);
			}
			System.out.println();
		}
		System.out.println((new StringBuilder("It takes ")).append(
				(double) (endTime - startTime) / 1000D).append(" sec.")
				.toString());
	}
	void show(int i) {
		Vector<Node> tempList = null;
		String tempStr = "";
		if (i == 3) {
			tempList = roadList;
			tempStr = "roadList:(";
		} else if (i == 2) {
			tempList = closeNodeList;
			tempStr = "closeNodeList:(";
		} else if (i == 3) {
			tempList = openNodeList;
			tempStr = "openNodeList:(";
		}
		System.out.println((new StringBuilder(String.valueOf(tempStr))).append(
				tempList.size()).append(")").toString());
		Node node;
		for (Iterator<Node> iterator = tempList.iterator(); iterator.hasNext(); System.out
				.print((new StringBuilder("(")).append(node.x).append(",")
						.append(node.y).append(")").toString()))
			node = (Node) iterator.next();
		System.out.println();
	}
	public static void main(String args[]) {
		SearchDemo demo = new SearchDemo(new Node(0, 0), new Node(size - 1,
				size - 1));
		demo.init();
		demo.showWorld();
		startTime = System.currentTimeMillis();
		demo.search();
		demo.showWorld();
		demo.show(3);
	}
}

package astart;
import java.awt.*;
import java.util.Vector;
public class MyCanvas extends Canvas implements Runnable {
	private static final long serialVersionUID = 1L;
	public int SIZE;
	public int lenght;
	Color c;
	Graphics g;
	SearchDemo demo;
	int world_bak[][];
	int world[][];
	Vector<Node> roadList;
	public MyCanvas() {
		SIZE = 20;
		lenght = 10;
		c = Color.BLACK;
		demo = new SearchDemo(new Node(0, 0), new Node(SIZE - 1, SIZE - 1));
		demo.init();
		demo.search();
		world_bak = demo.getWorld_bak();
		roadList = demo.getRoad();
		System.out.println((new StringBuilder("closeNodeList size=")).append(
				roadList.size()).toString());
		demo.show(3);
	}
	public void paint(Graphics g) {
		this.g = g;
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 20; j++)
				switch (world_bak[i][j]) {
				case 0: // ''
					g.setColor(Color.black);
					g.drawRect(i * 10, j * 10, 8, 8);
					break;
				case 1: // '01'
					g.setColor(Color.pink);
					g.fillRect(i * 10, j * 10, 8, 8);
					g.drawRect(i * 10, j * 10, 8, 8);
					break;
				case 8: // 'b'
					g.setColor(Color.red);
					g.fillRect(i * 10, j * 10, 8, 8);
					g.drawRect(i * 10, j * 10, 8, 8);
					break;
				}
		}
	}
	public void setColor(Color c) {
		this.c = c;
	}
	public void run() {
		try {
			Thread.sleep(1000L);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		for (int i = roadList.size() - 1; i >= 0; i--) {
			Node node = (Node) roadList.get(i);
			System.out.println((new StringBuilder("Running ...(")).append(
					node.x).append(",").append(node.y).toString());
			world_bak[node.x][node.y] = 8;
			repaint();
			try {
				Thread.sleep(50L);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}
}

本文链接:http://www.it72.com/1117.htm