在游戏编程中广泛使用了A*算法。 就比如红警里面你框一辆坦克然后在目的地上点一下鼠标,不管多远坦克都会自动跑到目标点上(前提是目标点是可以到达的畅通路径)。在这个过程中坦克起始位置和终点位置中间的路径已经由程序计算完成。而这个程序的算法我们称之为最优路径算法。
是下面是最优算法A*原理的实现,当然只是原理算法的实现,只供学习和研究其效率一般,没有实现算法和数据结构的优化,负责的程序员应该进一步的优化它。 好了下面我们还是来看看如何实现吧。
地图中每一块都有3个属性
G = 移动代价。
H = 实际代价,离到终点的实际距离。
F = G+H
A* 就是寻找具有最小F值能到达终点的路径。
下面我们开始吧
先定义地图数据 0是可走1是不可行走
int[][] map = {
{
0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {
0, 1, 1, 1, 1, 0, 0, 1, 0, 0}, {
0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, {
0, 1, 0, 0, 1, 1, 1, 1, 1, 0}, {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
};
需要维护两个列表一个是开放列表还有一个封闭列表
Vector open = new Vector(); // 开放列表
Vector close = new Vector(); // 封闭列表
定义节点类
class Node {
int x;
int y;
int g; // G = 移动代价,沿着到父块而生成路径移动的代价。
int h; // H = 从格子中给定 的方块到最终目标 B点的评估移动代价。
int f; // 估价
Node father;
Node(Node node, int sx, int sy, int ex, int ey) {
if (node != null) { // 新建子节点
father = node; // 设置父节点
x = sx; // 当前x
y = sy; // 当前y
h = (getABS(sx - ex) + getABS(sy - ey))*10; // 实际代价 当前块移动到终点块的绝对距离。
g = node.g + 10; // 代价推算 当前块移动代价=父块移动代价+移动代价
f = g + h; // 估价
}
else { // 根节点
x = sx;
y = sy;
h = 0;
g = 0;
f = 9999;
}
}
}
private int getABS(int v) {
if (v < 0) {
return -v;
}
return v;
}
// 开始寻路
public void xunLu(int sx, int sy, int ex, int ey) {
boolean flag = true; // 是否存在于open list中
int minIndex = 0; // 具有最小F值对象的的open list下标
int newX = 0;
int newY = 0;
/**
* 1 添加开始方块到开放列表。
* 初始化根接点,把根节点放入开放列表.
*/
Node minNode = new Node(null, sx, sy, ex, ey);
open.add(minNode);
while (open.size() != 0) {
/**
* 2 查找开放列表中具有最小F值的方块。
*/
minNode = ((Node)open.get(0));
minIndex = 0;
for (int i = 1; i < open.size(); i++) {
if (minNode.f > ( (Node) open.get(i)).f) {
minNode = ( (Node) open.get(i));
minIndex = i;
}
}
/**
* 3 把最小F值的方块从开放列表中取出然后放入封闭列表。
*/
if (minNode != null) {
close.add(minNode);
open.remove(minIndex);
}
/**
* 4 如果目前找到的最小F值块是终点就返回。
*/
if (minNode.x == ex && minNode.y == ey) {
do {
minNode = minNode.father;
}
while (get != null);
return;
}
/**
* 5 对最小F值块(即上面刚刚放入封闭列表里面) 的8个相邻方块的进行判断.
* 将4或8个方向,可以走的放入开放列表内.
*/
for (int i = 0; i < 4; i++) {
flag = true;
newX = minNode.x + t[i][0];
newY = minNode.y + t[i][1];
/**
*5。1 地图是否越界 如果它不可行走,或者存在于封闭列表,忽略它。
*/
if(newY < 0 || newY > 4 || newX < 0 || newX > 9) {
continue;
}
if (map[newY][newX] == 0) { // 判断是否是可以移动
for (int k = 0; k < close.size(); k++) {
if ( (((Node) close.get(k)).x == newX) &&
(((Node) close.get(k)).y == newY) ) {
flag = false;
break;
}
}
if(flag) {
for(int ii = 0; ii < open.size(); ii++) {
if( ((Node)open.get(ii)).x == newX && ((Node)open.get(ii)).y == newY) {
open.remove(ii);
break;
}
}
open.add(new Node(minNode, newX,newY, ex, ey));
}
}
}
}
}
分享到:
相关推荐
人工智能A*算法实现+python+北邮人工智能实训作业
基于layaair引擎用typesript开发的吃豆人游戏A*算法的实现
在学习了著名的A星算法之后,我便有了想法要把它实现出来。这是对A*算法的一整套详细实现,固定地图障碍物,自选起点和终点,实现最短最优路径搜索,可用在游戏自动寻路上(要用vs编译)
自己写的用c++实现的简易八数码问题,搜索算法采用A*算法,搜索代价使用哈密顿路(可以自己更改,),资源是工程文件。在vs2008下运行通过,里面代码都进行了注释。
C++编写的使用A*算法解决8数码问题 1.输入初始状态,1~8数字,用空格隔开,0代表空格,顺序在矩阵中的位置为 1 2 3 4 5 6 7 8 9 如输入1 2 3 4 5 6 7 8 0,则初始矩阵为 1 2 3 4 5 6 7 8 0 2.输入目标状态,说明...
本程序利用A*算法模拟了机器人自动寻路的过程,程序中可以通过点击地图来设置/取消障碍位置,实现不同情况下的路径寻找。当然你也可以修改寻路的起点和终点以及地图的大小~
使用A*算法实现8数码问题的求解,以人格保证可以正确运行,并且运行时输出空格移动的步骤!文件使用VC++6.0打开,代码文件是1.cpp
用人工智能中的A*算法解决迷宫的路径寻找问题
迷宫 a*算法实现
A*算法实现8数码问题。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
用A*算法实现tsp旅行商问题,城市间的距离用txt文件表示,输出也用txt文件表示。压缩文件包括两个测试文件,一个结果文件,一个源代码
用a*算法实现八数码问题。随意输入一序列可以找到最佳路径编程1 2 3 8 4 7 6 5
该程序运用A*算法实现简单魔板,程序完整清晰,还附有实验报告和可执行程序,对A*算法的理解和运用都有所帮助
这里用的是经典的A*算法实现的路径最优寻找
A*算法实现代码,PYTHON
使用C++实现基于A*算法的N数码问题,是8数码问题的拓展。
本报告利用A*算法,给出了15数码问题的C++算法实现。 A*算法是一种预测算法,主要用于寻路等,根据当前状态和目标状态之间的差异,预测到达目标需要多少开销,根据这个开销来判断下一次选择以那个状态开始。这个开销...