先上圖
文章目錄
- 一、實驗內容
- 二、深度優先演算法生成迷宮
- 三、A*演算法走迷宮
- 四、結果測驗
- 五、源代碼
- 六、參考文獻
一、實驗內容
1、要求：
1）迷宮隨機生成
2）系統用A*演算法尋路，輸出路徑
3) 實作基本游戲界面
2、解決問題：
1）如何顯示迷宮的圖形界面
2）如何生成隨機的迷宮
3）怎樣移動游戲中走迷宮的“玩家”
4）用A*演算法求解迷宮
二、深度優先演算法生成迷宮
1、整體思路
1）利用深度遍歷的思想，訪問到一個節點時，搜索這個節點沒有被訪問過的相鄰節點，選擇一個繼續做同樣的操作，直到沒有鄰節點為止再回溯到上一個訪問的節點，并選擇另外的鄰節點，
2）這種方案生成的迷宮會有一條明顯的主路，這條主路特別長，貫穿大部磁區域的路線，同時，迷宮的路線一般比較扭曲，這種采用深度優先演算法（遞回回溯演算法）生成的迷宮稱之為“主路扭曲型”迷宮，
2、步驟
（1）把陣列地圖初始化為如下結構，選擇一個靠近邊緣的1作為起點，在它的周圍隨機找另一個黃色的1（這里的“周圍”指的是上下左右4個方向），找到就把他們聯通，并且把兩個1之間的0（灰色墻）也變成通路，這里用紅色來表示，
（2）選擇一個靠近邊緣的1作為起點，在它的周圍隨機找另一個黃色的1（這里的“周圍”指的是上下左右4個方向），找到就把他們聯通，并且把兩個1之間的0（灰色墻）也變成通路，這里用紅色來表示，
（3）把上一步”終點”的格子作為新的一個“起點”格子，不斷回圈第2步的程序……
直到，找不到周圍有黃色的1，就回溯，回到之前的位置，看看周圍是否有黃色的1，如果有，就按照2步驟，不斷將黃色1變聯通，接下來就是不停地重復上面的步驟，找到就聯通，找不到就往回走，
（4）遍歷完所有的點即可生成一個迷宮，然后再選擇出口與入口，一個完整的迷宮就形成了，
三、A*演算法走迷宮
1、演算法概述
在計算機科學中，A*演算法作為Dijkstra（迪杰斯特拉）演算法的擴展，是一種靜態路網中求解最短路徑有效的直接搜索方法，因其高效性被廣泛應用于尋路及圖的遍歷中，
搜索區域（The Search Area）：搜索區域被劃分為簡單的二維陣列，陣列每個元素對應一個結點，
開放串列（Open List）:將尋路程序中待檢測的結點存放于Open List中，而已檢測過的結點則存放于Close List中，
路徑排序（Path Sorting）：下一步怎么移動由以下公式確定；F(n)=G+H，F(n)為估價函式，G代表的是從初始位置Start沿著已生成的路徑到指定待檢測結點移動開銷，H表示待檢測結點到目標節點B的估計移動開銷，
啟發函式（Heuristics Function）: H為啟發函式，可以看作是一種試探，由于在找到唯一路徑前，不確定在前面會出現什么障礙物，因此用了一種計算H的演算法，具體可以根據實際情況決定，為了簡化問題，H采用的是傳統的曼哈頓距離，也就是橫縱向走的距離之和，
2、演算法流程
重復以下步驟，直到遍歷到終點 End：
1）選取當前 open 串列中評價值 F 最小的節點，將這個節點稱為 S；
2）將 S 從 open串列移除，然后添加 S 到 closed 串列中； 3）對于與 S 相鄰的每一塊可移動的相鄰節點 T：如果 T 在 closed串列中，忽略；
如果 T 不在 open 串列中，添加它然后計算它的 F值；
如果 T 已經在 open 串列中，當我們從 S 到達 T時：檢查是否能得到更小的 F 值，
如果是，更新它的 F 值和它的前繼(parent = S)，
3、演算法原理
（1）兩個串列:
open： 一個記錄下所有被考慮來尋找最短路徑的方塊
closed： 一個記錄下不會再被考慮的方塊
（2) 路徑增量 ： F(n)=G+H
G:是從開始點A到當前方塊的移動量，所以從開始點A到相鄰小方塊的移動量為1，該 值會隨著離開始點越來越遠而增大，
H:是從當前方塊到目標點(我們把它稱為點B，代表小花! )的移動量估算值，這個 常被稱為探視，因為我們不確定移動量是多少，只是一-個估算值，
為了讓它更簡單，我們將使用“曼哈頓距離方法”(也叫“曼哈頓長”或者“城市街區距離”)，它只是計算出距離點B，剩下的水平和垂直的方塊數量，略去了障礙物或者不同陸地型別的數量，
(3)找到最短路徑:
重復之前的步驟，當目標方塊在open串列中，即找到路徑，
然后回溯，計算出最終的路徑!
四、結果測驗
1、視頻演示：
迷宮游戲演示
2、界面：
3、控制臺輸出：
五、源代碼
1、類結構和檔案結構
2、圖片鏈接
鏈接: https://pan.baidu.com/s/1GEWiuwxf1i99Tck3sshZ8g
提取碼: mvda
3、完整源代碼
（1）Test類
package Maez;
import java.awt.Toolkit;
import javax.swing.JFrame;
public class Test {
public static void main(String[] args) {
JFrame frame = new JFrame();//新建視窗
int width = Toolkit.getDefaultToolkit().getScreenSize().width;// 取得螢屏寬度
int height = Toolkit.getDefaultToolkit().getScreenSize().height;// 取得螢屏高度
frame.setSize(600, 600);// 設定表單大小
frame.setLocation((width - 600) / 2, (height - 600) / 2);// 設定表單出現大小
frame.setResizable(false);// 設定表單大小不可變
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);// 設定表單關閉方式
frame.add(new Panel());
frame.setFocusable(true);//為螢屏添加焦點
frame.setVisible(true);// 設定表單可視
frame.requestFocus();
}
}
（2）Panel類
package Maez;
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import javax.swing.JButton;
import javax.swing.JPanel;
public class Panel extends JPanel implements MouseListener, KeyListener{
Maze M = new Maze();//定義一個Maze類物件，生成地圖
AStart A = new AStart();//定義一個AStart類，畫出迷宮路徑
private JPanel jp = new JPanel();
private JButton answer = new JButton("畫出路徑");
private JButton hide = new JButton("隱藏路徑");
private JButton reset = new JButton("重置地圖");
private JButton exit = new JButton("退出游戲");
private JButton start = new JButton("開始游戲");
BufferedImage wall = null;
BufferedImage bj = null;
BufferedImage victory = null;
BufferedImage my = null;
int myx = 1;// 定義角色橫坐標并初始化
int myy = 1;// 定義角色縱坐標
int endx;// 定義終點橫縱坐標
int endy;
boolean isStarted = false;
boolean isVictory = false;
boolean ans = false;// 用于顯示路徑
public Panel() {
this.setName("迷宮");// 設定標題
this.setLayout(null);
answer.setBounds(470, 130, 90, 30);
hide.setBounds(470, 210, 90, 30);
reset.setBounds(470, 290, 90, 30);
exit.setBounds(470, 370, 90, 30);
start.setBounds(470, 450, 90, 30);
answer.addMouseListener(this);
hide.addMouseListener(this);
reset.addMouseListener(this);
exit.addMouseListener(this);
start.addMouseListener(this);
start.addKeyListener(this);
this.add(jp);
this.add(start);
this.add(answer);
this.add(hide);
this.add(reset);
this.add(exit);
try {
bj = ImageIO.read(new File("images/bj.jpg"));// 放視窗背景圖片
victory=ImageIO.read(new File("images/victory.png"));
wall = ImageIO.read(new File("images/wall.jpg"));// 放墻的圖片
my = ImageIO.read(new File("images/my.png"));// 放墻的圖片
} catch (IOException e) {
e.printStackTrace();
}
}
// 畫組件
public void paintComponent(Graphics g) {
super.paintComponent(g);
g.fillRect(20, 80, 420, 420);
g.drawImage(bj, 0, 0, this);
g.setColor(Color.white);
g.setFont(new Font("華文行楷", Font.BOLD, 40));
g.drawString("迷宮游戲", 120, 50);
// 畫迷宮
for (int i = 0; i < M.LabId.length; i++) {
for (int j = 0; j < M.LabId[0].length; j++) {
if (M.LabId[i][j] == 0) {
g.drawImage(wall, 20 + i * 20, 80 + j * 20, this);
}
}
}
// 畫A*路徑
if (ans) {
g.setColor(Color.green);
for (int i = 0; i < A.NODES.length; i++) {
for (int j = 0; j < A.NODES[0].length; j++) {
if (A.NODES[i][j] == 2) {
g.fillOval(20 + 20 * i, 80 + 20 * j, 18, 18);
}
}
}
}
g.setColor(Color.white);
g.fillRect(40, 100, 20, 20);// 畫起點
g.fillRect(400, 460, 20, 20);// 畫終點
g.drawImage(my, 20 + 20 * myx, 80 + 20 * myy, this);// 畫角色
// 判斷是否到達終點
if (this.myx ==19 && this.myy ==19) {
isVictory = true;
}
// 畫游戲勝利界面
if (isVictory) {
g.drawImage(victory, 60,180, this);// 畫角色
}
}
// 滑鼠監聽
@Override
public void mouseClicked(MouseEvent e) {
if (e.getSource().equals(answer)) {
ans = true;
isVictory=false;
}
if (e.getSource().equals(hide)) {
ans = false;
isVictory=false;
}
if (e.getSource().equals(reset)) {
ans = false;
isVictory=false;
myx = 1;
myy = 1;
new Panel();
}
if (e.getSource().equals(exit)) {
System.exit(0);
}
if (e.getSource().equals(start)) {
ans = false;
isVictory=false;
myx = 1;// 開始游戲，角色從起點開始出發
myy = 1;
}
repaint();
}
// 鍵盤監聽
@Override
public void keyTyped(KeyEvent e) {
}
@Override
public void keyPressed(KeyEvent e) {
int k = e.getKeyCode();
if (k == KeyEvent.VK_SPACE) {
System.out.print("按下空格");
}
if (k == KeyEvent.VK_LEFT && A.NODES[myx - 1][myy] != 0 && myx - 1 >= 1) {
myx--;
}
if (k == KeyEvent.VK_RIGHT && A.NODES[myx + 1][myy] != 0 && myx + 1 <= 21) {
myx++;
}
if (k == KeyEvent.VK_UP && A.NODES[myx][myy - 1] != 0 && myy - 1 >= 1) {
myy--;
}
if (k == KeyEvent.VK_DOWN && A.NODES[myx][myy + 1] != 0 && myy + 1 <= 21) {
myy++;
}
repaint();
}
@Override
public void keyReleased(KeyEvent e) {
}
@Override
public void mousePressed(MouseEvent e) {
}
@Override
public void mouseReleased(MouseEvent e) {
}
@Override
public void mouseEntered(MouseEvent e) {
}
@Override
public void mouseExited(MouseEvent e) {
}
}
（3）Maze類
package Maez;
import java.util.Random;
public class Maze {
public static int row = 10;// 初始地圖有路的迷宮單元行數
public static int column = 10;// 初始地圖有路的迷宮單元列數
public static int r = 2 * row + 1;// 迷宮單元行數，保證是奇數
public static int c = 2 * column + 1;// 迷宮單元列數，保證是奇數
public static int[][] LabId;// 存放迷宮的陣列,迷宮單元陣列
Random rand = new Random();
public Maze() {
LabId = new int[r][c];
System.out.println("初始化地圖:");
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
LabId[i][j] = 0;// 將所有格子都設為墻, 0 為墻 1為路
if (i % 2 == 1 && j % 2 == 1)// 將奇數行奇數列設為路，1為路，0為墻
LabId[i][j] = 1;
System.out.print(LabId[i][j] + " ");// 列印初始化地圖，在控制臺輸出查看
}
System.out.println();
}
// 呼叫深度優先搜索演算法
accLabDFS();
System.out.println("\n" + "深度優先演算法生成的迷宮:");
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
System.out.print(LabId[i][j] + " ");// 列印生成的深度優先演算法生成的迷宮，在控制臺輸出查看
}
System.out.println();
}
}
// 實作深度優先演算法
public void accLabDFS() {
int[] lab;// 訪問佇列
int count = row * column;// 所有的迷宮單元數，不包括墻
lab = new int[count];
for (int i = 0; i < count; i++)
lab[i] = 0;// 設定所有單元都為未訪問過的，0表示未訪問過，1表示已訪問過
for (int v = 0; v < count; v++) {// 從第0個點開始遍歷
if (lab[v] != 1) {// 如果該單元還未被訪問，則遞回呼叫深度優先演算法遍歷
DFS(lab, v);
}
}
}
// 使用DFS演算法,借助遞回思想訪問某一頂點v,找v點附近且未被訪問的點w,在找w附近未被訪問的點(回圈...),直到沒有繼續能找下去的點,
// 依次退回最近被訪問的點,如果還有該頂點的其他鄰居沒有被訪問,就從鄰居點開始繼續搜索,把相鄰的部分格子打通
public void DFS(int[] LabG, int v) {
LabG[v] = 1;// 訪問頂點
int[] neighbor = { v + row, v - row, v - 1, v + 1 };// 該點的四個鄰居 上下左右
int[] offR = { 0, 0, -1, 1 }, offC = { 1, -1, 0, 0 };// Row上個方向的偏移 Column上各方向的偏移，上下左右
int[] tag = { -1, -1, -1, -1 };// 記錄打通位置
int n = 0;// 打通的次數
while (n < 4) {// 上下左右四個方向都遍歷，
int i = rand.nextInt(4);// 隨機打通一個方向
if (tag[i] == 1)
continue;// 進入下一輪回圈
tag[i] = 1;// 打通墻，設為1
n++;
int w = neighbor[i];// 定義一個該方向上的鄰居
if (w > LabG.length - 1 || w < 0)
continue; // w不存在,即該方向上沒有鄰居
// 取出現在的v點的位置
int x = v % row;
int y = v / row;
// 遍歷到四個邊界時再往邊界方向就沒有鄰居了，進入下一輪回圈
if (i == 0 && y == column - 1)
continue;// 上方向
if (i == 1 && y == 0)
continue;// 下方向
if (i == 2 && x == 0)
continue;// 左方向
if (i == 3 && x == row - 1)
continue;// 右方向
// 如果該點有未訪問的鄰居，則把該點與其鄰居間的墻打通，即相鄰的格子中間的位置放1
if (LabG[w] == 0) {
LabId[2 * x + 1 + offR[i]][2 * y + 1 + offC[i]] = 1;
DFS(LabG, w);// 遞回
}
}
}
}
（4）AStart類
package Maez;
import java.util.ArrayList;
import java.util.List;
public class AStart {
public static int[][] NODES;//定義一個迷宮單元陣列
public int STEP = 10;//設每一步的權值為10
private ArrayList<Node> openList = new ArrayList<Node>();//維護一個開放串列
private ArrayList<Node> closeList = new ArrayList<Node>();//維護一個關閉串列
public AStart() {
NODES=Maze.LabId;//初始化迷宮單元為新生成的對應地圖，把Maze2類里面生成的地圖傳給NODES，再在此地圖基礎上用A*演算法尋路徑
Node startNode = new Node(1, 1);//起點
Node endNode = new Node(19, 19);//終點
Node parent = findPath(startNode, endNode); //父節點
ArrayList<Node> arrayList = new ArrayList<Node>();
while (parent != null) {
arrayList.add(new Node(parent.x, parent.y));
parent = parent.parent;
}
//列印有路徑的地圖，在控制臺輸出查看
System.out.println("\n"+"列印有路徑的地圖:");
for (int i = 0; i < NODES.length; i++) {
for (int j = 0; j < NODES.length; j++) {
if (exists(arrayList, i, j)) {
NODES[i][j]=2;//標記關閉串列里的方格為2，為了方便后面在界面畫系統尋路路徑
}
System.out.print(NODES[i][j] + " ");
}
System.out.println();
}
}
//尋找開放串列里F值最小的節點的方法
public Node findMinFNodeInOpneList() {
Node tempNode = openList.get(0);
for (Node node : openList) {
if (node.F < tempNode.F) {
tempNode = node;
}
}
return tempNode;
}
//遍歷當前節點上下左右四個鄰居的方法，
public ArrayList<Node> findNeighborNodes(Node currentNode) {
ArrayList<Node> arrayList = new ArrayList<Node>();
// 只考慮上下左右，不考慮斜對角
int topX = currentNode.x;
int topY = currentNode.y - 1;
if (canReach(topX, topY) && !exists(closeList, topX, topY)) {
arrayList.add(new Node(topX, topY));
}
int bottomX = currentNode.x;
int bottomY = currentNode.y + 1;
if (canReach(bottomX, bottomY) && !exists(closeList, bottomX, bottomY)) {
arrayList.add(new Node(bottomX, bottomY));
}
int leftX = currentNode.x - 1;
int leftY = currentNode.y;
if (canReach(leftX, leftY) && !exists(closeList, leftX, leftY)) {
arrayList.add(new Node(leftX, leftY));
}
int rightX = currentNode.x + 1;
int rightY = currentNode.y;
if (canReach(rightX, rightY) && !exists(closeList, rightX, rightY)) {
arrayList.add(new Node(rightX, rightY));
}
return arrayList;
}
//判斷此處坐標是否可達，若超界或者是墻則不可達
public boolean canReach(int x, int y) {
if (x >=0 && x < NODES.length && y >=0 && y < NODES.length && NODES[x][y]==1) {
return true;
}
return false;
}
//A*尋路程序
public Node findPath(Node startNode, Node endNode) {
openList.add(startNode);// 把起點加入 open list
while (openList.size() > 0) {
Node currentNode = findMinFNodeInOpneList();// 遍歷 open list ，查找 F值最小的節點，把它作為當前要處理的節點
openList.remove(currentNode);// 從open list中移除
closeList.add(currentNode);// 把這個節點移到 close list
ArrayList<Node> neighborNodes = findNeighborNodes(currentNode);
for (Node node : neighborNodes) {//遍歷四個鄰居
if (exists(openList, node)) {
foundPoint(currentNode, node);
} else {
notFoundPoint(currentNode, endNode, node);
}
}
if (find(openList, endNode) != null) {
return find(openList, endNode);//找到終點了并回傳
}
}
return find(openList, endNode);
}
//在串列里可以找到節點后的情況
private void foundPoint(Node tempStart, Node node) {
int G = calcG(tempStart, node);
if (G < node.G) {
node.parent = tempStart;
node.G = G;
node.calcF();
}
}
//在節點里找不到節點的情況
private void notFoundPoint(Node tempStart, Node end, Node node) {
node.parent = tempStart;
node.G = calcG(tempStart, node);
node.H = calcH(end, node);
node.calcF();
openList.add(node);
}
//計算G值的方法
private int calcG(Node start, Node node) {
int G = STEP;
int parentG = node.parent != null ? node.parent.G : 0;
return G + parentG;
}
//計算H值的方法
private int calcH(Node end, Node node) {
int step = Math.abs(node.x - end.x) + Math.abs(node.y - end.y);
return step * STEP;
}
//找到終點的方法
public static Node find(List<Node> nodes, Node point) {
for (Node n : nodes)
if ((n.x == point.x) && (n.y == point.y)) {
return n;
}
return null;
}
//下面兩個是exist方法的多載，判斷不同引數情況時節點是否在串列里
public static boolean exists(List<Node> nodes, Node node) {
for (Node n : nodes) {
if ((n.x == node.x) && (n.y == node.y)) {
return true;
}
}
return false;
}
public static boolean exists(List<Node> nodes, int x, int y) {
for (Node n : nodes) {
if ((n.x == x) && (n.y == y)) {
return true;
}
}
return false;
}
//節點類，定義了每一個節點的屬性
public static class Node {
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int x;
public int y;
public int F;
public int G;
public int H;
public void calcF() {
this.F = this.G + this.H;
}
public Node parent;
}
}
六、參考文獻
1、深度優先演算法生成迷宮
https://blog.csdn.net/qq_38064109/article/details/93554529
2、A*演算法走迷宮
https://blog.csdn.net/qq_36946274/article/details/81982691
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240469.html
標籤：其他
上一篇：mysql索引優化助記口訣