基本原理
- 简单的说，A*算法就是不停的从起点开始遍历周围的点，找出目前来说消耗最小的点作为新的起点，直到找到终点。
- 如何找到消耗最小的点
- f（消耗）=g（离起点距离）+h（离终点距离）
- g：从起点到达当前点要走的距离，上下左右都是1，斜边用勾股定理算出约为1.4
- h:按照曼哈顿距离计算（d(i,j)=|X1-X2|+|Y1-Y2| ）
- 开启列表：用来存储可以考虑行进的点，同时存放f、g、h、父对象（从哪个点来）的信息。
- 关闭列表：用来存储不再考虑的点，存放在关闭列表中的点需要从开启列表移除，同时存放f、g、h、父对象（从哪个点来）的信息。
- 如何确定路径：
- 虽然最优点都在关闭列表中，但是并不能直接使用关闭列表中的点作为路径。
- 而是在关闭列表中从终点开始查找父对象，再查找父对象的父对象
- 死路：当开启列表为空的时候，说明已经找遍了所有可能的点，寻路失败。
- 详细流程：
- 1、将起点记录为当前点a
- 2、将当前点a放入关闭列表，并设置父对象为空
- 3、将当前点a周围所有能行进的格子放入开启列表，如果周围的点已经在开启列表或者关闭列表中，就不用管它了
- 4、记录当前点a周围所有能行进的格子的f值和父对象（父对象为当前点）
- 5、寻找最优点将其放入关闭列表，并删除开启列表中的最优点，每次往关闭列表放点时，要判断该点是否为终点，如果是证明路径已经找完了，跳到步骤8，如果不是则继续步骤6
- 6、将最优点作为起点b
- 7、跳回步骤3
- 8、找到终点，寻路结束
- 拓展阅读：
题目要求
代码实现
Maze类
package Maze;
class Maze
{
static final int ROWS = 20;
static final int COLS = 20;
Node map[][] = new Node[ROWS][COLS];
Node start = null;
Node end = null;
//储存当前所有的测试点信息的集合
PathList test = new PathList();
//储存最短路径信息的集合
Path select = new Path();
//初始化地图
void init()
{
for(int i=0;i<ROWS;i++)
{
for(int j=0;j<COLS;j++)
{
map[i][j] = new Node(i,j,1);
}
}
}
void gameStart(MazePanel panel)
{
//node为当前点
Node node = start;
//将当前节点储存在列表中
select.addNode(start,0);
//死循环，直到到达end点
while(true)
{
System.out.println("当前坐标：(" + node.row + "," + node.col + ")" +
"
测试点的数量："+test.list.size() +
"
已经走了几步："+(select.list.size() -1) +
"
当前点是否被访问：" + node.visit);
//测试点测试：将当前点标记为被访问过，将未被访问的相邻点加入到表中并录入路径信息
test(node);
panel.repaint(0,0,700,700);
panel.update(panel.getGraphics());
//80ms刷新一次
try
{
Thread.sleep(80);
}
catch(Exception e)
{
e.printStackTrace();
}
//获取所有当前测试点中cost+forecast最小的点并设置为当前点
select = test.selectPath();
node = (Node)select.list.get(select.list.size()-1);
//如果找到已经到了目标点则将当前点设置为已访问并跳出死循环
if((Math.abs(node.row-end.row)<=1) && (Math.abs(node.col-end.col)<=1))
{
node.visit = 1;
break;
}
}
System.out.println("找到最短路径，下面为最短路径坐标");
select.addNode(end,0);
//遍历最短路径
for(int i=0;i<select.list.size();i++)
{
//输出最短路径的过程坐标
node = (Node)select.list.get(i);
System.out.println("(" + node.row + "," + node.col + ")");
}
}
//测试点
void test(Node node)
{
int row = node.row;
int col = node.col;
//标记当前位置已经到达
//node.visit = 1;
map[node.row][node.col].visit = 1;
for(int i=-1;i<=1;i++)
{
//行数-1小于0或者行+i大于20（超出地图）就跳出当前循环
if((row+i<0) || (row+i>=ROWS))
continue;
for(int j=-1;j<=1;j++)
{
if((col+j<0) || (col+j>=COLS))
continue;
//将当前点的周围标记为测试点
map[row+i][col+j].test = 1;
//若测试点没有被访问过（有的点可能在之前的遍历中被访问了）
if(map[row+i][col+j].visit == 0)
{
//将当前测试点坐标存入temp中
Node temp = map[row+i][col+j];
//将select中的cost和forecast、list存入新的路径path
Path path = new Path(select);
//算出预测点与终点的距离（曼哈顿距离）
int forecast = Math.abs(end.row - temp.row) + Math.abs(end.col - temp.col);
path.addNode(temp,forecast);
test.addPath(path);
}
}
}
}
}
MazeFrame类
package Maze;
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.nio.charset.StandardCharsets;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
//gui界面初始化、监听
class MazeFrame extends JFrame
{
//墙的数量
int count[] = new int[]{0,0};
String[] wallStr = new String[400];
MazePanel mazePanel = null;
Maze maze = null;
MazeFrame(Maze maze)
{
this.maze = maze;
mazePanel = new MazePanel(maze);
setTitle("Maze");
setSize(620,670);
//初始化GUI画面
initView();
setVisible(true);
}
void initView()
{
getContentPane().setLayout(new BorderLayout());
//鼠标点击监听、画图
mazePanel.addMouseListener(new MouseAdapter()
{
public void mouseClicked(MouseEvent e)
{
int x = e.getX();
int y = e.getY();
//鼠标点击某行列
int row = y / MazePanel.WIDTH;
int col = x / MazePanel.WIDTH;
//鼠标按第一次是开始点
if(mazePanel.clickCount == 0)
{
mazePanel.maze.start = mazePanel.maze.map[row][col];
}
else if(mazePanel.clickCount == 1)
{
mazePanel.maze.end = mazePanel.maze.map[row][col];
}
else
{
mazePanel.maze.map[row][col].cost = 100;
wallStr [count[0]] = "(" + String.valueOf(row) +"," + String.valueOf(col) + ")";
count[0] ++;
}
mazePanel.repaint(0,0,700,700);
mazePanel.clickCount++;
}
});
//在GUI窗口中增加迷宫面板和ok按钮
getContentPane().add(mazePanel,BorderLayout.CENTER);
JPanel bottomPanel = new JPanel(new FlowLayout());
JButton startButton = new JButton("Start");
JButton saveButton = new JButton("SaveMap");
JButton loadButton = new JButton("LoadMap");
TextField pathText = new TextField(30);
JButton restartButton = new JButton("ReStart");
add(bottomPanel,BorderLayout.SOUTH);
startButton.addActionListener(new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
//开始
mazePanel.repaint(0,0,700,700);
maze.gameStart(mazePanel);
}
});
bottomPanel.add(startButton);
bottomPanel.add(pathText);
//储存数据
saveButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
String path = pathText.getText();
try {
FileOutputStream fos = new FileOutputStream(path,false);
BufferedOutputStream bos = new BufferedOutputStream(fos);
String startStr = "("
+ String.valueOf(mazePanel.maze.start.row)
+","
+ String.valueOf(mazePanel.maze.start.col)
+ ")";
String endStr = "("
+ String.valueOf(mazePanel.maze.end.row)
+","
+ String.valueOf(mazePanel.maze.end.col)
+ ")";
byte[] startByte = new byte[16];
byte[] endByte = new byte[16];
byte[] wallByte = new byte[1024];
startByte = startStr.getBytes(StandardCharsets.UTF_8);
endByte = endStr.getBytes(StandardCharsets.UTF_8);
bos.write(startByte);
bos.write(endByte);
for (int i = 0;i < count[0];i++)
{
wallByte = wallStr[i].getBytes(StandardCharsets.UTF_8);
bos.write(wallByte);
}
bos.close();
}catch (Exception exception)
{
exception.printStackTrace();
}
}
});
bottomPanel.add(saveButton);
//加载数据
loadButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
String path = pathText.getText();
try {
FileInputStream fis = new FileInputStream(path);
byte[] bytes = new byte[10240];
int flag = 0;
fis.read(bytes);
String str = new String(bytes);
String regex="[0-9]+(\\.[0-9]+)?";
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(str);
int temp = 0;
while (m.find())
{
switch (flag)
{
case 0:
{
temp = Integer.parseInt(m.group());
flag = 1;
break;
}
case 1:
{
mazePanel.maze.start = mazePanel.maze.map[temp][Integer.parseInt(m.group())];
flag = 2;
break;
}
case 2:
{
temp = Integer.parseInt(m.group());
flag = 3;
break;
}
case 3:
{
mazePanel.maze.end = mazePanel.maze.map[temp][Integer.parseInt(m.group())];
flag = 4;
break;
}
case 4:
{
temp = Integer.parseInt(m.group());
flag = 5;
break;
}
case 5:
{
mazePanel.maze.map[temp][Integer.parseInt(m.group())].cost = 100;
count[1]++;
if (count[1] == count[0])
{
System.out.println(count[1]);
flag = 6;
break;
}else
{
flag = 4;
break;
}
}
}
if (flag == 6)
{
break;
}
}
mazePanel.repaint(0,0,700,700);
}catch (Exception exception)
{
exception.printStackTrace();
}
}
});
bottomPanel.add(loadButton);
//重启按钮
restartButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
setVisible(false);
Maze maze = new Maze();
maze.init();
MazeFrame frame = new MazeFrame(maze);
}
});
bottomPanel.add(restartButton);
}
}
MazePanel类
package Maze;
import javax.swing.*;
import java.awt.*;
//迷宫的GUI实现
class MazePanel extends JPanel
{
Maze maze = null;
int clickCount = 0;
//定义一系列常量
static final int WIDTH = 30;
static final Color START_COLOR = Color.green;
static final Color END_COLOR = Color.red;
static final Color DEFAULT_COLOR = Color.white;
static final Color WALL_COLOR = Color.gray;
static final Color TEST_COLOR = Color.yellow;
static final Color VISIT_COLOR = Color.pink;
static final Color PATH_COLOR = Color.blue;
//构造函数
MazePanel(Maze maze)
{
this.maze = maze;
}
public void paintComponent(Graphics g)
{
//默认边框
g.clearRect(0,0,700,700);
g.setColor(Color.black);
for(int i=0;i<=Maze.ROWS;i++)
{
g.drawLine(0,WIDTH*i,WIDTH* Maze.COLS,WIDTH*i);
}
for(int j = 0; j<= Maze.COLS; j++)
{
g.drawLine(WIDTH*j,0,WIDTH*j,WIDTH* Maze.ROWS);
}
//测试（当前点的四周）
g.setColor(TEST_COLOR);
for(int i = 0; i< Maze.ROWS; i++)
{
for(int j = 0; j< Maze.COLS; j++)
{
if(maze.map[i][j].test == 1)
{
//覆盖四周八个点
g.fillRect(maze.map[i][j].col*WIDTH+1,maze.map[i][j].row*WIDTH+1,WIDTH-1,WIDTH-1);
}
}
}
//已经到达的点
g.setColor(VISIT_COLOR);
for(int i = 0; i< Maze.ROWS; i++)
{
for(int j = 0; j< Maze.COLS; j++)
{
if(maze.map[i][j].visit == 1)
{
g.fillRect(maze.map[i][j].col*WIDTH+1,maze.map[i][j].row*WIDTH+1,WIDTH-1,WIDTH-1);
}
}
}
//墙壁的cost为一个巨大的值
g.setColor(WALL_COLOR);
for(int i = 0; i< Maze.ROWS; i++)
{
for(int j = 0; j< Maze.COLS; j++)
{
if(maze.map[i][j].cost == 100)
{
g.fillRect(maze.map[i][j].col*WIDTH+1,maze.map[i][j].row*WIDTH+1,WIDTH-1,WIDTH-1);
}
}
}
if(maze.start != null)
{
g.setColor(START_COLOR);
g.fillRect(maze.start.col*WIDTH+1,maze.start.row*WIDTH+1,WIDTH-1,WIDTH-1);
}
if(maze.end != null)
{
g.setColor(END_COLOR);
g.fillRect(maze.end.col*WIDTH+1,maze.end.row*WIDTH+1,WIDTH-1,WIDTH-1);
}
//画最短路径线
int length = maze.select.list.size();
if(length > 0)
{
//遍历中的当前点
Node node = (Node)maze.select.list.get(length - 1);
//只有找到最短路径才开始画线
if(node.equals(maze.end) == true)
{
Graphics2D g2d = (Graphics2D)g;
g2d.setColor(PATH_COLOR);
g2d.setStroke(new BasicStroke(2.0f));
int startX = maze.start.col * WIDTH + WIDTH/2;
int startY = maze.start.row * WIDTH + WIDTH/2;
for(int i=1;i<length;i++)
{
node = (Node)maze.select.list.get(i);
int endX = node.col * WIDTH + WIDTH/2;
int endY = node.row * WIDTH + WIDTH/2;
g2d.drawLine(startX,startY,endX,endY);
startX = endX;
startY = endY;
}
}
}
}
}
Node类
package Maze;
class Node
{
int row = 0;
int col = 0;
int cost = 0;
int test = 0;
int visit = 0;
//节点的构造函数，储存当前行列信息，cost为走一步的消耗
Node()
{
//
}
Node(int row,int col,int cost)
{
this.row = row;
this.col = col;
this.cost = cost;
}
//当前点与终点是否为一个点
public boolean equals(Object object)
{
if(!(object instanceof Node))
return false;
Node node = (Node)object;
if((node.row == row) && (node.col == col))
{
return true;
}
else
return false;
}
}
Path类
package Maze;
import java.util.Vector;
//路径信息类，forecast为测试点曼哈顿距离的值，cost为当前点已经经走过的路程+1
class Path
{
int cost = 0;
int forecast = 0;
Vector list = new Vector();
Path()
{
}
//将(select)节点的路径信息依次存进表中
Path(Path path)
{
for(int i=0;i<path.list.size();i++)
{
list.add(path.list.get(i));
}
this.cost = path.cost;
this.forecast = path.forecast;
}
void addNode(Node node,int forecast)
{
list.add(node);
//若经过墙壁cost+=100否则+1
this.cost += node.cost;
this.forecast = forecast;
}
}
PathList类
package Maze;
import java.util.Vector;
class PathList
{
Vector list = new Vector();
void addPath(Path path)//增加path并按照cost+forecast排序
{
int i = 0;
//将当前表中cost+forecast与传入的值做对比，若传入值小于原本位置的值就插入到表的当前位置
for(i=0;i<list.size();i++)
{
int cost = ((Path)list.get(i)).cost;
int forecast = ((Path)list.get(i)).forecast;
if((cost+forecast) > (path.cost+path.forecast))
{
break;
}
}
//插入
list.insertElementAt(path,i);
}
Path selectPath()// 找到首个在表中未被访问的点并返回该点在表中的位置（该点一定是cost+forecast最小的点）
{
int result = 0;
//遍历当前表
for(int i=0;i<list.size();i++)
{
//将各个路径信息存到新建的路径中
Path path = (Path)list.get(i);
//将各点的信息存到新建的节点中
Node node = (Node)path.list.get(path.list.size()-1);
//若当前点没有被访问则获得当前点的索引并返回
if(node.visit == 0)
{
result = i;
break;
}
}
return (Path)list.get(result);
}
}
TestMaze类
package Maze;
public class TestMaze
{
public static void main(String[] args)
{
Maze maze = new Maze();
//初始化地图
maze.init();
MazeFrame frame = new MazeFrame(maze);
}
}
结果演示
- 开始程序，在网格中点击鼠标绘制地图，其中第一次点击为起点（绿色），第二次为终点（红色），之后的点击为墙壁不可以穿过（灰色）
- 在文字框中输入需要储存地图数据的路径，如E://1.txt
- 点击SaveMap
- 点击Restart重启程序
- 在文本框中输入需要读取地图数据的路径
- 点击LoadMap即可读取之前存储的地图信息
加油
