如图,绿方块是起点,红方块终点;蓝方块是水(障碍物)。想像在图的周围加上边界,建立坐标系,x和y分别从1开始,则x取值[1,9],y取值[1,7],起点坐标(3,4),终点坐标(7,4);为简单起见,将坐标以一个整数标记:100 * y + x.
路径搜寻过程中,有一点与参考文章不同的是,障碍物的角被认为是可穿过的,只要穿过之后的坐标不是障碍物或边界。
参阅:http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html
英文原文:http://www.gamedev.net/reference/articles/article2003.asp
/**
* Author by metaphy
* Date Feb 20, 2008
*/
package astar;
import java.util.ArrayList;
public class Coordinate {
private int x;
private int y;
private int value;
private Coordinate parent;
public Coordinate(){}
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
this.value = 100 * y + x;
}
public Coordinate(int value) {
this.x = value % 100;
this.y = value / 100;
this.value = value;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getValue() {
return value;
}
public Coordinate getParent() {
return parent;
}
public void setParent(Coordinate parent) {
this.parent = parent;
}
/**
* Whether or not it's border
* @return
*/
public boolean isBorder(){
return x == 1 || x == 9 || y ==1 || y== 7 ;
}
/**
* Whether or not it's barrier
* @return
*/
public boolean isWater(){
return value == 305
|| value == 306
|| value == 405
|| value == 504
|| value == 505
;
}
/**
* @param xx
* @param yy
* @return
*/
public boolean valid(int xx, int yy){
return xx >=1 && xx<=9 && yy >=1 && yy<=7;
}
/**
* Get valid adjacent coordinate list
* @return
*/
public ArrayList<Coordinate> getValidAdjacent(){
ArrayList<Coordinate> list = new ArrayList<Coordinate>();
for (int t = -1; t<= 1; t ++){
for (int p = -1; p<= 1; p++){
if (valid(x + t,y + p)){
Coordinate c = new Coordinate (x+t, y+p);
if (!c.isBorder() && !c.isWater()){
list.add(c);
}
}
}
}
return list;
}
/**
* The G function
* @param c
* @return
*/
public int getCostG(){
if (parent != null){
if (Math.abs(parent.getX () -x)==1 && Math.abs(parent.getY() - y )==1){
return 14;
}else {
return 10;
}
}else {
return 0 ;
}
}
public int getCostG(Coordinate c){
if (Math.abs(c.getX () -x)==1 && Math.abs(c.getY() - y )==1){
return 14;
}else if (c.getX() == x && Math.abs(c.getY()-y) == 1|| c.getY() ==y && Math.abs(c.getX() -x) ==1){
return 10;
}else {
return Integer.MAX_VALUE;
}
}
/**
* The H function
* @param c
* @return
*/
public int getDistanceH(Coordinate c){
return (Math.abs(c.getX() - x) + Math.abs(c.getY() - y)) * 10;
}
/**
* The F function
* @param c
* @return
*/
public int getF(Coordinate c){
return getCostG() + getDistanceH(c);
}
}
/**
* Author by metaphy
* Date Feb 20, 2008
*/
package astar;
import java.util.ArrayList;
public class AStarSample {
private ArrayList<Coordinate> openList = new ArrayList<Coordinate>();
private ArrayList<Coordinate> closeList = new ArrayList<Coordinate>();
private Coordinate start = new Coordinate(403);
private Coordinate end = new Coordinate(407);
/**
* Try to find the path
* @return
*/
public boolean pathFinding(){
Coordinate current = null;
openList.add(start);
do{
current = lookForMinF();
openList.remove(current);
closeList.add(current);
ArrayList<Coordinate> list = current.getValidAdjacent();
for (Coordinate adjacent:list){
if (!inClosedList(adjacent)){
if (!inOpenedList(adjacent)){
adjacent.setParent(current);
openList.add(adjacent);
}else{
int g0 = current.getParent().getCostG(adjacent);
int g1 = current.getCostG() + current.getCostG(adjacent);
if (g1 < g0){
adjacent.setParent(current);
}
}
}
}
} while(!findTarget() && openList.size()>0);
end.setParent(current);
if (findTarget()){
Coordinate tmp = end;
while (tmp.getValue() != start.getValue()){
System.out.println(tmp.getValue());
tmp = tmp.getParent();
}
System.out.println(start.getValue());
return true;
}else{
System.out.println("Can't find the path.");
return false;
}
}
/**
* Look for the min F value coordinate from open list
* @return
*/
private Coordinate lookForMinF(){
Coordinate c = openList.get(0);
for (Coordinate tmp :openList){
if (tmp.getF(end) < c.getF(end)){
c = tmp ;
}
}
return c;
}
/**
* Find the target or not
* @return
*/
private boolean findTarget(){
for (Coordinate open: openList){
if (open.getValue() == end.getValue())
return true;
}
return false;
}
private boolean inClosedList(Coordinate c){
for (Coordinate close: closeList){
if (close.getValue() == c.getValue())
return true;
}
return false;
}
private boolean inOpenedList (Coordinate c){
for (Coordinate open: openList){
if (open.getValue() == c.getValue())
return true;
}
return false;
}
public static void main(String[] args) {
new AStarSample().pathFinding();
}
}
分享到:
- 2008-02-21 12:37
- 浏览 1365
- 评论(7)
- 论坛回复 / 浏览 (4 / 3040)
- 查看更多
相关推荐
a*寻路例子
一个简单的A*寻路算法 适合初学寻路算法者阅读
NULL 博文链接:https://xltank.iteye.com/blog/1045834
很不错的Astar寻路的例子,值得拥有。呵呵
Unity3D A*项目例子 主要介绍在unity3d 平台上 各种不同地形A*寻路
此代码包含多个文件,AStar.c、 AStar.h、main.c以及makefile相关文件,例子默认是在linux下编译实现,也可直接将三个代码文件移植到window开发平台下编译实现
A星寻路最经典的的实例.E易语言例子!A星寻路最经典的的实例.E易语言例子!
这个是我个人自己写的Unity 2D环境中的寻路, 分别有两个文件夹,AIPath 是正面2D 环境,45AIPath 是斜45度角(2.5D)环境,本资源包含了一份PDF繁体中文教学文件,而在最后我也提出了一些问题,望高手解答。...
A星算法,游戏自动寻路源码例子
寻星p5.js a *寻路应用程序例子有完整的可用示例。 以下是该网站的屏幕截图。
一个寻路算法的实现类源代码,采用A*算法实现,有一个类库和一个小的例子组成
CCSimplePathFinding 使用A *寻路算法为简单世界寻找简单路径。 对于cocos2dx v3文档:感谢Ray Wenderlich:如何使用: 1.创建一个二维矩阵世界: 例子:```c ++ std :: vector>矩阵std :: vector row1 = {1,1,1,1,1...
基于C4的A*例子,不错的,可以拿来研究一下
在学习了著名的A星算法之后,我便有了想法要把它实现出来。这是对A*算法的一整套详细实现,固定地图障碍物,自选起点和终点,实现最短最优路径搜索,可用在游戏自动寻路上(要用vs编译)
A星寻路算法,文档介绍加代码小例子,帮助想做游戏的人掌握寻路算法
一个生成r行c列地图、随机起始点终点、障碍,及地图显示路径的简单例子。 算法学习总结: 1.初始化开列表,关列表; 2.起点计算周围节点f值(g+h);周围节点放入开列表,起点加入关列表; 3.从开列表取f值最小值作为...
=========================== A* Pathfinder - Basics Demo =========================== By Patrick Lester, pwlester@policyalmanac.org ...A* 的一个例子 8方向 对存储进行了2叉堆优化,反倒造成不好理解A*本身.
使用例子: require "astar" local way=AstarFindWay(1,1,2,2,{}) print("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"..tostring(way)) way就是寻路的内容了输入参数分别是起始点x,y,目标点x,y,生物集合 地图信息在astar...
一个不错的A星算法的例子,包含源文件和源代码!绝对值得下载!包你不后悔!