本文實例為大家分享了java實現推箱子游戲的具體代碼,供大家參考,具體內容如下
運行示例:
圖形界面由swing組件構成
生成地圖的算法如下
創建地圖算法(produceMap):先將二維數組全置為1,代表初始狀態全為牆。先隨機產生兩個不重合的點,一個作為人的起點,另一個作為箱子的起點。從起點開始,隨機朝四個方向走一定的步數,若走到的點不是空地,即對應數組元素不為0,則將該點設為空地,即數組元素設為0。將地圖分為左上、左下、右上和右下四個區域,並設置四個變量記錄四個區域已開闢空地的數量。每開闢一塊空地,代表該空地所在區域的變量加1。走完規定的步數後,在四個區域中找到開闢空地數量最小的區域,在該區域內隨機產生一個點,以該點作為起點循環執行上述操作,直到開闢的空地的總數大於地圖總面積的一半,創建完成。
解決地圖算法(solveMap):創建一個狀態類,將箱子的一個位置和在搜索這個箱子的過程中人的一個位置以及箱子走到這個位置的步數表示為一個狀態。建立一個優先隊列,隊列元素為狀態類的對象,步數小的狀態的優先級高。從起點開始按照上下左右的順序進行廣度優先搜索。建立一個HashMap,鍵為狀態類,值為布爾類,用來保存每個狀態的是否被走過,再建立一個HashMap,鍵為點類,值也為點類,保存箱子的每一個位置的前一個位置,用於最後輸出路徑。使用優先隊列可以使推動箱子次數多的狀態推遲出隊,從而保證箱子每個能推動的方向都被訪問到並推動,若直接使用隊列,則無法使每種情況都走到。而當地圖較大的時候,採用HashMap存儲訪問信息可以節省較大的空間。優先隊列每次執行出隊操作的時候記錄出隊狀態的步數,噹噹前出隊狀態的步數和上一個出隊狀態的步數不同的時候,將保存狀態訪問信息的HashMap清空。另設置一個HashMap鍵為點類,值為整型類,保存每個點箱子訪問過幾次,若超過四次,則不訪問該點。由優先隊列的性質可知,出隊的狀態的步數是隊列中步數最小的狀態,即噹噹前出隊的狀態的步數和前一個不同的時候,箱子前一步的狀態已全部出隊。這時箱子之前的訪問狀態已經不再需要,及時清空保存訪問狀態的HashMap可以節省很大的內存空間。當廣搜搜到箱子在終點位置的狀態,則搜索結束。若結束狀態的步數小於規定的最小步數,則返回解決失敗,否則返回解決成功。若未搜到箱子在終點位置的狀態並且隊列已空,則返回解決失敗。
記錄路徑算法(recordPath):根據在解決地圖的過程中建立的記錄箱子每個位置前一個位置的一個HashMap,從終點開始,一步步找回起點,並將在這過程中找到的點按順序入棧,然後再將棧中的點逐個出棧並記錄在一個點的數組中,以實現路徑的正序輸出。
Main_Class.java
public class Main_Class { public static void main(String args[]) { PTB_Frame frame=new PTB_Frame("Push The Box"); frame.setBounds(0,0,1200,1200); } }
PTB_Frame.java
import java.awt.*; import java.awt.event.*; import javax.swing.*; @SuppressWarnings("serial") public class PTB_Frame extends JFrame { private Font font = new Font("宋體", Font.PLAIN, 23); private Map_Manager map_manager=new Map_Manager(); private ConsolePanel console = new ConsolePanel(map_manager); private JButton creat_map=new JButton("創建地圖"); private MapPanel map=new MapPanel(map_manager); PTB_Frame(String title) { init(); this.setTitle(title); this.setVisible(true); this.setDefaultCloseOperation(EXIT_ON_CLOSE); } void init() { this.setLayout(null); console.setBounds(0, 0, 1200,250); console.add(creat_map); this.add(console); map.setBounds(80, 250, 1200, 800); this.add(map); creat_map.setFont(font); creat_map.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { console.creatMap(); map.setMap(map_manager.getHeight(), map_manager.getWidth(), map_manager.getStepOfMap(), map_manager.getMap()); map.creatMap(); } }); } }
ConsolePanel.java
import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; @SuppressWarnings("serial") public class ConsolePanel extends JPanel { Font font = new Font("宋體", Font.PLAIN, 23); JTextField t_height = new JTextField(3); JTextField t_width = new JTextField(3); JTextField t_diff = new JTextField(5); JButton get_path = new JButton("查看最短路徑"); JTextArea show_path = new JTextArea(5, 40); int height, width; double diff; Map_Manager map_manager; ConsolePanel(Map_Manager map_manager) { this.map_manager = map_manager; UIManager.put("Label.font", font); this.add(new JLabel("地圖高度:")); t_height.setFont(font); this.add(t_height); this.add(new JLabel("(3~100的整數)")); this.add(new JLabel("地圖寬度:")); t_width.setFont(font); this.add(t_width); this.add(new JLabel("(3~100的整數)")); this.add(new JLabel("地圖難度:")); t_diff.setFont(font); this.add(t_diff); this.add(new JLabel("(1.0~10.0之間的小數)")); this.add(new JLabel("注:地圖高度和寬度以及難度越大,生成地圖時間越長")); get_path.setFont(font); this.add(get_path); show_path.setFont(font); show_path.setLineWrap(true);// 自動換行 show_path.setWrapStyleWord(true);// 換行不斷字 JPanel show_path_panel = new JPanel(); show_path_panel.add(new JScrollPane(show_path));//滾動窗口 this.add(show_path_panel); get_path.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { Map_Manager.Point path[] = map_manager.getPath(); if (path != null) { show_path.setText(null); for (int i = 0; i<map_manager.getStepOfMap(); ++i) show_path.append(path[i] + " "); } } }); } public void creatMap() { try { height = Integer.valueOf(t_height.getText()); width = Integer.valueOf(t_width.getText()); diff = Double.valueOf(t_diff.getText()); if (height < 3 || height >100 || width < 3 || width > 100 || diff < 1 || diff > 10) throw new NumberFormatException(); map_manager.setMap(height, width, diff); map_manager.creatMap(); show_path.setText(null); } catch (NumberFormatException ex) { JOptionPane.showMessageDialog(getRootPane(), "參數格式不正確"); } } }
MapPanel.java
import javax.swing.*; import java.awt.*; import java.awt.event.*; import java.util.*; @SuppressWarnings("serial") public class MapPanel extends JPanel { private Font font = new Font("宋體", Font.PLAIN, 23); private JPanel map_area; JPanel control_bar = new JPanel(); private JButton drawback, restart,start; private JLabel l_min_step, l_left_step, l_passed_step; private JLabel show_cur_point; private JLabel show_cur_box; private Point person = new Point(); private Point start_of_person = new Point(); private Point start_of_box = new Point(); private Point end = new Point(); private Point box = new Point(); private int width, height; private int map[][] = new int[100][100]; private int di[][] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; private int min_step, passed_step = 0; private Stackoperation_recorder = new Stack(); private JButton block[][] = new JButton[100][100]; private Map_Manager map_manager; private class Point implements Cloneable { int x, y; public boolean equals(Object obj) { if (!(obj instanceof Point)) return false; Point point = (Point) obj; return this.x == point.x && this.y == point.y; } public Object clone() { Point newPoint = null; try { newPoint = (Point) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return newPoint; } public String toString() { return "(" + (this.x + 1) + "," + (this.y + 1) + ")"; } } public void setMap(int height, int width, int min_step, int map[][]) { this.height = height; this.width = width; this.min_step = min_step; this.map = map; } private class PtbKeyAdapter extends KeyAdapter { public void keyPressed(KeyEvent e) { int keycode = e.getKeyCode(); if (keycode == KeyEvent.VK_UP) { pointMove(0); } else if (keycode == KeyEvent.VK_DOWN) { pointMove(1); } else if (keycode == KeyEvent.VK_LEFT) { pointMove(2); } else if (keycode == KeyEvent.VK_RIGHT) { pointMove(3); } } } private class Operation { int stuff;// 1代表箱子,0代表人 int dir;// 0代表上,1代表下,2代表左,3代表右 Operation(int stuff, int dir) { this.stuff = stuff; this.dir = dir; } } private boolean accessible(Point point) {// point可走則返回true if (point.x < 0 || point.x >= height || point.y < 0 || point.y >= width)// 越界 return false; if (map[point.x][point.y] == 1)// 走到牆上 return false; return true; } private void pointMove(int dir) { if(passed_step>=min_step) return; // 先判斷能否進行交換,若能,則交換兩按鈕顏色值 Point cur_point = new Point(); cur_point.x = person.x + di[dir][0]; cur_point.y = person.y + di[dir][1]; if (!accessible(cur_point))// 當前點不可走 return; if (cur_point.equals(box)) { // 當人前進方向上前一個點是箱子 Point next_box = new Point(); next_box.x = box.x + di[dir][0]; next_box.y = box.y + di[dir][1]; if (!accessible(next_box))// 箱子無法推動 return; // 如果箱子能前進,則人也前進,不能則人不能前進 go(box, dir); ++this.passed_step; updateStep(); operation_recorder.push(new Operation(1, dir)); } go(person, dir); show_cur_point.setText(" "+person.toString()+" "); operation_recorder.push(new Operation(0, dir)); if (box.equals(end)) JOptionPane.showMessageDialog(this.getRootPane(), "WINNER WINNER CHICKEN DINNER!"); else if(this.passed_step==this.min_step) JOptionPane.showMessageDialog(this.getRootPane(), "江河猶在,命數已盡,悲哉!"); } private void go(Point point, int dir) {// 實現前進部分的代碼 Color color = block[point.x][point.y].getBackground(); if (point.equals(end)) block[point.x][point.y].setBackground(Color.GREEN); else block[point.x][point.y].setBackground(Color.WHITE); point.x += di[dir][0]; point.y += di[dir][1]; block[point.x][point.y].setBackground(color); } private void updateStep() { l_passed_step.setText(Integer.toString(passed_step)); l_left_step.setText(Integer.toString(min_step - passed_step)); show_cur_box.setText(" "+box.toString()+" "); } public void paintMap() { map_area = new JPanel(new GridLayout(this.height, this.width)); for (int i = 0; i < this.height; i++) for (int j = 0; j < this.width; j++) { block[i][j] = new JButton(); if (map[i][j] == 0)// 數組中0為路 block[i][j].setBackground(Color.WHITE); else if (map[i][j] == 1)// 數組中1為牆 block[i][j].setBackground(Color.BLACK); else if (map[i][j] == 2)// 數組中2為箱子位置 { block[i][j].setBackground(Color.BLUE); start_of_box.x = i; start_of_box.y = j; } else if (map[i][j] == 3)// 數組中3為終點 { block[i][j].setBackground(Color.GREEN); end.x = i; end.y = j; } else if (map[i][j] == 4) {// 數組中4為人的位置 block[i][j].setBackground(Color.RED); start_of_person.x = i; start_of_person.y = j; } map_area.add(block[i][j]); } person = (Point) start_of_person.clone(); box = (Point) start_of_box.clone(); l_min_step.setText(Integer.toString(min_step)); show_cur_point.setText(" "+person.toString()+" "); passed_step=0; updateStep(); int map_height=750,map_width=750; if(this.height>this.width) map_width=(750/this.height)*this.width; else if(this.width>this.height) map_height=(750/this.width)*this.height; map_area.setBounds(0, 0, map_width, map_height); this.add(map_area); } public MapPanel(Map_Manager map_manager) { this.map_manager = map_manager; init(); } private void init() { this.setLayout(null); map_manager.setMap(20, 20, 7.0); map_manager.creatMap(); this.height = map_manager.getHeight(); this.width = map_manager.getWidth(); this.min_step = map_manager.getStepOfMap(); this.map = map_manager.getMap(); UIManager.put("Label.font", font); drawback = new JButton("後退一步"); restart = new JButton("重新開始"); start=new JButton("開始"); control_bar.add(new JLabel("當前箱子的位置")); show_cur_box=new JLabel(); control_bar.add(show_cur_box); control_bar.add(new JLabel("當前人的位置")); show_cur_point=new JLabel(); control_bar.add(show_cur_point); control_bar.add(new JLabel("最短步數:")); l_min_step = new JLabel(); l_min_step.setFont(font); control_bar.add(l_min_step); control_bar.add(new JLabel("已走步數:")); l_passed_step = new JLabel(); l_passed_step.setFont(font); control_bar.add(l_passed_step); control_bar.add(new JLabel("剩餘步數:")); l_left_step = new JLabel(); l_left_step.setFont(font); control_bar.add(l_left_step); control_bar.add(new JLabel("注:這裡的步數是")); control_bar.add(new JLabel("箱子移動的步數")); control_bar.add(new JLabel("紅色代表人")); control_bar.add(new JLabel("藍色代表箱子")); control_bar.add(new JLabel("綠色代表終點")); restart.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { block[person.x][person.y].setBackground(Color.WHITE); person = (Point) start_of_person.clone(); block[box.x][box.y].setBackground(Color.WHITE); box = (Point) start_of_box.clone(); block[person.x][person.y].setBackground(Color.RED); block[box.x][box.y].setBackground(Color.BLUE); block[end.x][end.y].setBackground(Color.GREEN); passed_step = 0; show_cur_point.setText(" "+person.toString()+" "); updateStep(); } }); drawback.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { if (operation_recorder.empty()) return; Operation cur_op = operation_recorder.peek(); operation_recorder.pop(); int dir; switch (cur_op.dir) {// 得到相反方向 case 0: dir = 1; break; case 1: dir = 0; break; case 2: dir = 3; break; default: dir = 2; } // 推箱子的時候,箱子先走,人再走 // 不推箱子的時候直接就是人走,所以棧頂元素始終是人的操作 go(person, dir);// 人相反方向走一步 show_cur_point.setText(" "+person.toString()+" "); if (!operation_recorder.empty()&&operation_recorder.peek().stuff == 1) { // 下一個是箱子,即人從該位置推動的箱子 go(box, dir);// 箱子相反方向走一步 operation_recorder.pop(); --passed_step; updateStep(); } } }); PtbKeyAdapter ptbkeyadapter=new PtbKeyAdapter(); start.addKeyListener(ptbkeyadapter); restart.addKeyListener(ptbkeyadapter); drawback.addKeyListener(ptbkeyadapter); start.setFont(font); restart.setFont(font); drawback.setFont(font); control_bar.add(start); control_bar.add(restart); control_bar.add(drawback); control_bar.setBounds(850, 100, 200, 600); this.paintMap(); this.add(control_bar); } public void creatMap() { this.setLayout(null); this.map_area.removeAll(); this.map_area.setVisible(false); paintMap(); this.revalidate(); this.map_area.setVisible(true); } }
Map_Manager.java
import java.util.*; public class Map_Manager { private PTB_Map ptb_map = new PTB_Map(); private int di[][] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; private double search_limit; private int area[] = new int[4]; private Mapvisit_of_status = new HashMap(); private Mapvisit_of_box = new HashMap(); private PriorityQueueq = new PriorityQueue(new Comparator() { public int compare(Status s1, Status s2) { return s1.step - s2.step; } }); private class PTB_Map { private int width; private int height; private int step_of_map; private int accessible_point; private Point end_p = new Point(); private Status start = new Status(); private int matrix[][] = new int[100][100]; private Mappath_map = new HashMap(); private Point[] path = new Point[1000]; private double ratio_of_space; private double ratio_of_step; } public class Point implements Cloneable { int x, y; public boolean equals(Object obj) { if (!(obj instanceof Point)) return false; Point point = (Point) obj; return this.x == point.x && this.y == point.y; } public int hashCode() { return this.x * ptb_map.width + this.y; } public Object clone() { Point newPoint = null; try { newPoint = (Point) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return newPoint; } public String toString() { return "(" + (this.x + 1) + "," + (this.y + 1) + ")"; } } private class Status implements Cloneable { Point box = new Point(); Point person = new Point(); int step; public int hashCode() { return this.box.hashCode() * this.person.hashCode() + this.step; } public boolean equals(Object obj) { if (!(obj instanceof Status)) return false; Status status = (Status) obj; return this.box.equals(status.box) && this.person.equals(status.person) && this.step == status.step; } public Object clone() { Status newStatus = null; try { newStatus = (Status) super.clone(); newStatus.box = (Point) box.clone(); newStatus.person = (Point) person.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return newStatus; } } public void setMap(int height, int width, double degree_of_difficulty) { this.ptb_map.height = height; this.ptb_map.width = width; this.ptb_map.ratio_of_space = 0.5; double ratio = 1; if (height + width < 20) ratio = 0.05 * (height + width); this.ptb_map.ratio_of_step = 0.5 + degree_of_difficulty * 0.05 * ratio; this.search_limit = (this.ptb_map.height * this.ptb_map.width) / 10; } public int getHeight() { return ptb_map.height; } public int getWidth() { return ptb_map.width; } public int getStepOfMap() { return ptb_map.step_of_map; } private boolean accessible(Point point) {// point可走則返回true if (point.x < 0 || point.x >= ptb_map.height || point.y < 0 || point.y >= ptb_map.width)// 越界 return false; if (ptb_map.matrix[point.x][point.y] == 1)// 走到牆上 return false; return true; } private void creatSpace(Point point) { Random random = new Random(); int l = 0; while (l <= search_limit) { int dir = random.nextInt(4); if (point.x + di[dir][0] < 0 || point.x + di[dir][0] >= ptb_map.height || point.y + di[dir][1] < 0 || point.y + di[dir][1] >= ptb_map.width) continue;// 若往該方向走一步越界,則換個方向 point.x += di[dir][0]; point.y += di[dir][1]; if (this.ptb_map.matrix[point.x][point.y] != 0) { if (point.y < ptb_map.width / 2) { if (point.x < ptb_map.height / 2) ++area[0];// 該點在左上方 else ++area[1];// 該點在左下方 } else { if (point.x < ptb_map.height / 2) ++area[2];// 該點在右上方 else ++area[3];// 該點在右下方 } this.ptb_map.matrix[point.x][point.y] = 0; ++this.ptb_map.accessible_point; } ++l; } } private boolean produceMap() {// 返回值為地圖是否創建成功 Random random = new Random(); // 重置地圖的矩陣 for (int i = 0; i < ptb_map.height; ++i) for (int j = 0; j < ptb_map.width; ++j) ptb_map.matrix[i][j] = 1; do// 隨機設置人和箱子的初始位置 { ptb_map.start.box.x = random.nextInt(ptb_map.height); ptb_map.start.box.y = random.nextInt(ptb_map.width); ptb_map.start.person.x = random.nextInt(ptb_map.height); ptb_map.start.person.y = random.nextInt(ptb_map.width); } while (ptb_map.start.box.equals(ptb_map.start.person)); ptb_map.accessible_point = 0; ptb_map.matrix[ptb_map.start.person.x][ptb_map.start.person.x] = 0; // 設置一定的牆 ptb_map.accessible_point = 0; Point start = (Point) ptb_map.start.person.clone();// 最開始走的位置為人的初始位置 area[0] = area[1] = area[2] = area[3] = 0; creatSpace(start); while (ptb_map.accessible_point < (ptb_map.height * ptb_map.width) * ptb_map.ratio_of_space) { int min = 10000, min_area = 0; for (int i = 0; i < 4; ++i) if (area[i] < min) { min = area[i]; min_area = i; } switch (min_area) { case 0:// 左上 start.x = random.nextInt(ptb_map.height / 2); start.y = random.nextInt(ptb_map.width / 2); break; case 1:// 左下 start.x = random.nextInt(ptb_map.height / 2) + ptb_map.height / 2; start.y = random.nextInt(ptb_map.width / 2); break; case 2:// 右上 start.x = random.nextInt(ptb_map.height / 2); start.y = random.nextInt(ptb_map.width / 2) + ptb_map.width / 2; break; case 3:// 右下 start.x = random.nextInt(ptb_map.height / 2) + ptb_map.height / 2; start.y = random.nextInt(ptb_map.width / 2) + ptb_map.width / 2; break; } creatSpace(start); } ptb_map.end_p = (Point) start.clone(); ptb_map.matrix[ptb_map.start.person.x][ptb_map.start.person.y] = 4; ptb_map.matrix[ptb_map.start.box.x][ptb_map.start.box.y] = 2; ptb_map.matrix[ptb_map.end_p.x][ptb_map.end_p.y] = 3; return true; } private boolean solveMap() {// 返回值為當前地圖是否有路徑 q.clear(); visit_of_box.clear(); ptb_map.path_map.clear(); ptb_map.step_of_map = 0; ptb_map.start.step = 0; int pre_step = -1; q.add(ptb_map.start); visit_of_status.put(ptb_map.start, true); while (!q.isEmpty()) { Status pre_Status = (Status) q.peek().clone(); if (pre_Status.step != pre_step) { visit_of_status.clear(); pre_step = pre_Status.step; } for (int i = 0; i < 4; ++i) { Status cur_Status = (Status) pre_Status.clone(); cur_Status.person.x += di[i][0]; cur_Status.person.y += di[i][1]; if (!accessible(cur_Status.person))// 該點不可走 continue; if (visit_of_status.containsKey(cur_Status))// 該點已經走過 continue; // 保存當前點的前一個,用於輸出路徑 if (cur_Status.person.equals(cur_Status.box))// 走到箱子上 { Point next_box = new Point();// 當前人會把箱子推到的位置 next_box.x = cur_Status.box.x + di[i][0]; next_box.y = cur_Status.box.y + di[i][1]; if (!accessible(next_box))// 該點不可走 continue; if (ptb_map.path_map.containsKey(next_box)) continue; if (visit_of_box.containsKey(next_box)) { if (visit_of_box.get(next_box) > 4)// 當前位置箱子已走過四次 continue; } // 箱子可以走到該點,則箱子走一步 ptb_map.path_map.put(next_box, cur_Status.box); cur_Status.box = next_box; ++cur_Status.step; if (!visit_of_box.containsKey(cur_Status.box)) visit_of_box.put(cur_Status.box, 1); else { int t = visit_of_box.get(cur_Status.box); ++t; visit_of_box.put(cur_Status.box, t); } if (cur_Status.box.equals(ptb_map.end_p))// 箱子走到終點 { ptb_map.step_of_map = cur_Status.step; q.clear(); if (ptb_map.step_of_map < (ptb_map.height + ptb_map.width) * ptb_map.ratio_of_step) return false; else return true; } } q.add(cur_Status); visit_of_status.put(cur_Status, true); } pre_Status = null; q.poll(); } return false; } public void recordPath() {// 記錄路徑 Stackoutput_path = new Stack();// 用於輸出路徑 Point cur_point = (Point) ptb_map.end_p.clone();// 從終點開始 int step = -1; while (step != ptb_map.step_of_map) { ++step; output_path.push(cur_point); cur_point = ptb_map.path_map.get(cur_point); if (cur_point == null) break; } int i = 0; while (!output_path.empty())// 將路徑保存在點數組裡 { ptb_map.path[i] = output_path.peek(); output_path.pop(); ++i; } } public void creatMap() { int i = 0; do { while (!produceMap()) ; ++i; } while (!solveMap()); recordPath(); printMap();// System.out.println(i);// } public int[][] getMap() { return ptb_map.matrix; } public Point getStartBoxPoint() { return ptb_map.start.box; } public Point getStartPersonPoint() { return ptb_map.start.person; } public Point getEndPoint() { return ptb_map.end_p; } private void printMap() { for (int i = 0; i < ptb_map.height; ++i) { System.out.print(ptb_map.matrix[i][0]); for (int j = 1; j < ptb_map.width; ++j) System.out.print(" " + ptb_map.matrix[i][j]); System.out.println(); } } public Point[] getPath() { return ptb_map.path; } }
[wooen ] java實現推箱子小遊戲已經有259次圍觀