如图,绿方块是起点,红方块终点;蓝方块是水(障碍物)。想像在图的周围加上边界,建立坐标系,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
- 浏览 1405
- 评论(7)
- 论坛回复 / 浏览 (4 / 3054)
- 查看更多
相关推荐
a*寻路例子
标题 "A*寻路的AS实现例子" 指的是使用ActionScript(一种基于ECMAScript的脚本语言,常用于Adobe Flash开发)实现A*(A-star)寻路算法的一个示例项目。A*算法是一种广泛应用在路径规划中的启发式搜索算法,尤其在...
A*(发音为“A-star”)寻路算法是一种在图形中寻找从起点到终点最短路径的高效算法,尤其适用于游戏开发、地图导航等领域。它结合了Dijkstra算法的全局最优性和启发式搜索的效率,通过引入估计代价来快速找到最佳...
A* (A-star) 寻路算法是一种广泛应用在游戏开发、地图导航、路径规划等领域的高效搜索算法。它结合了Dijkstra算法的最短路径特性与优先队列的效率,通过引入启发式函数来指导搜索过程,使得路径查找更加智能且节省...
二叉堆实现A*寻路算法是计算机科学中一种经典的路径搜索方法,它结合了Dijkstra算法和优先级队列的特性,以高效的方式寻找从起点到目标点的最短路径。在这个C语言实例中,我们看到AStar.c、AStar.h、main.c和...
Unity3D A*项目例子 主要介绍在unity3d 平台上 各种不同地形A*寻路
这个是我个人自己写的Unity 2D环境中的寻路, 分别有两个文件夹,AIPath 是正面2D 环境,45AIPath 是斜45度角(2.5D)环境,本资源包含了一份PDF繁体中文教学文件,而在最后我也提出了一些问题,望高手解答。...
1. A*算法的寻路原理 A*算法将搜索区域简化为二维数组,每个元素代表一个网格方块。这个二维数组可以帮助我们简化搜索过程。在A*算法中,路径被描述为从起点到终点所经过的方块的集合。每个方块称为一个节点,节点...
在本文中,我们将详细讲解A*寻路算法的原理,并提供了一个例子程序包的下载链接,可以帮助读者更好地理解算法的实现。 一、搜索区域简化 在A*寻路算法中,我们首先需要将搜索区域简化为一个二维数组。我们假设某个...
这个"android寻路小例子"就是一个很好的起点,它涵盖了基础的寻路算法实现,并且提供了源代码供学习和参考。下面我们将深入探讨这个主题。 首先,我们需要理解寻路算法的基本概念。寻路算法是用来解决在图(graph)...
在这个例子中,A*算法被集成到C4环境中,可能用于实现角色的自动寻路功能。 Navmesh(导航网格)是A*算法常用的一种数据结构,它将复杂的空间划分为一系列可行走的多边形,每个多边形代表一个导航单元。角色可以只...
A星(A*)算法是一种在图形搜索中用于找到两点之间最短路径的高效算法,尤其在游戏开发中,用于实现角色或NPC的自动寻路功能。易语言是一种中文编程语言,它使得编程过程更加直观易懂,尤其适合初学者。在本案例中,...
Unity中的A*算法实例主要涉及游戏开发中的路径搜索和寻路技术。A*(A-star)算法是一种在图形网络中寻找最优路径的搜索算法,它结合了Dijkstra算法的最短路径特性与最佳优先搜索算法的效率。在这个实例中,我们将在...
CCSimplePathFinding 使用A *寻路算法为简单世界寻找简单路径。 对于cocos2dx v3文档:感谢Ray Wenderlich:如何使用: 1.创建一个二维矩阵世界: 例子:```c ++ std :: vector>矩阵std :: vector row1 = {1,1,1,1,1...
在这个例子中,A星算法被应用到一个45度角的地图上,用于游戏中的角色导航。 A*算法的核心在于它结合了Dijkstra算法的最短路径搜索和启发式信息来优化搜索效率。Dijkstra算法虽然能保证找到最短路径,但效率较低,...
在"A_寻路(AS3)"的示例中,可能包含了AS3代码实现的详细步骤,包括节点表示、启发式函数的定义、开放列表和关闭列表的管理以及路径的查找和返回。通过阅读和理解这段代码,你可以深入学习如何在实际项目中应用A*...
A*算法(A-star algorithm)是一种启发式搜索算法,用于在图形路径...在这个例子中,我们使用了曼哈顿距离作为启发式函数,但这可能不适用于所有情况。在实际应用中,选择合适的启发式函数对于A*算法的性能至关重要。
描述中提到这是一个包含源文件和源代码的实际例子,这为我们提供了学习和理解A星算法在AS3中的具体应用提供了宝贵的资源。通过查看和运行这些源代码,我们可以深入理解算法的内部工作原理,以及如何在实际项目中有效...
在学习了著名的A星算法之后,我便有了想法要把它实现出来。这是对A*算法的一整套详细实现,固定地图障碍物,自选起点和终点,实现最短最优路径搜索,可用在游戏自动寻路上(要用vs编译)
在许多实际应用中,比如电子游戏中角色的自动寻路、地图应用中的驾车路线规划以及机器人技术中的自主导航等场景,都需要高效地找到两点间的最短路径或最优路径。A*算法通过结合启发式搜索策略,能够在复杂的环境中...