基于JAVA的迷宫自动寻路算法实现

package FindPath; import java.awt.Point; import java.util.LinkedList; import java.util.List; public class PathSearch { public static List<Point> findPath(int[][] map, Point start, Point goal) { // 转换成node StarNode startNode = new StarNode(start); StarNode goalNode = new StarNode(goal); // open list LinkedList<StarNode> open = new LinkedList<StarNode>(); LinkedList<StarNode> close = new LinkedList<StarNode>(); // init startNode.searchParent = null; open.add(startNode); close.add(startNode); while (!open.isEmpty()) { StarNode node = open.removeFirst(); //将open中第一个成员删掉，并返回给node if (node.equals(goalNode)) { //判断取出的点是否是Destination return construct(node); //若是，则调用construct（）方法，返回一个LinkedList } else { //若否，则执行添加节点操作如下 for (StarNode n : node.getNeighbors()) { if (!open.contains(n) && !close.contains(n) && n.isHit(map)) { //在node的neighbors()中， n.searchParent = node; //若open,close中均不含有该点 open.add(n); //而且该点上没有障碍物则将该点作为基点 close.add(n); //并且在open和close中都添加上该节点 } } } } return null; } public static List<Point> construct(StarNode node) { LinkedList<Point> path = new LinkedList<Point>(); while (node != null) { path.addFirst(node.location); node = node.searchParent; } return path; } public static void main(String[] args) { int[][] map = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; List<Point> list = findPath(map, new Point(5, 1), new Point(10, 13)); for (Point p : list) { try { Thread.sleep(300); }catch(InterruptedException e){} System.out.println(p.x + "," + p.y); } } }