prim算法实现最小生成树或迷宫可视化

package com.example.company; import java.util.ArrayList; import java.util.List; class AStar { public static int[][] NODES;//定义一个迷宫单元数组 public int STEP = 10;//设每一步的权值为10 private ArrayList<Node> openList = new ArrayList<Node>();//维护一个开放列表 private ArrayList<Node> closeList = new ArrayList<Node>();//维护一个关闭列表 AStar(int[][] map) { NODES=map;//初始化迷宫单元为新生成的对应地图，把Maze类里面生成的地图传给NODES，再在此地图基础上用A*算法寻路径 Node startNode = new Node(1, 1);//起点 Node endNode = new Node(map.length-2, map.length-2);//终点 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(); } } public static int[][] ans(){ return NODES; } //寻找开放列表里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; } }