[AStar寻路]为游戏脚本编写的A星寻路功能 #算法 #游戏

AStarDemo.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.lang.StringBuilder;

/**
 * Created by AItsuki on 2017/6/20.
 * A星自动寻路功能
 *
 *
 */
public class AStarDemo {
    private static int[][] map = {
            {0, 0, 0, 0, 0, 2, 2, 2},
            {0, 0, 0, 0, 1, 0, 2, 2},
            {2, 0, 1, 0, 0, 1, 0, 3},
            {0, 0, 0, 1, 0, 0, 0, 1}
    };

    public static void main(String[] args) {

        System.out.println("地图：1是怪物，2是障碍物，3是boss");
        printMap(map);
        System.out.println("寻路开始：");
        List<Position> path = seekRoad(3,0, 2,7, true);
        System.out.println("寻路结束：4是到boss的最短路径");
        for (int i = 0; i< path.size() ; i ++) {
            Position position = path.get(i);
            map[position.x][position.y] = 4;
        }
        printMap(map);
    }

    private static void printMap(int[][] map) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i< map.length ; i++ ) {
            for (int j = 0;j < map[i].length ; j++ ) {
                sb.append(map[i][j]).append("  ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }


    /**
     * include1，是否可以走小怪。
     */
    private static List<Position> seekRoad(int x, int y, int endX, int endY, boolean include1) {
        List<Node> openList = new ArrayList<>();
        List<Node> closedList = new ArrayList<>();
        // 初始化起点
        openList.add(createNode(x,y,endX,endY, null, false));
        Node desNode = createNode(endX, endY, endX, endY, null, false);

        do {
            Node currentNode = Collections.min(openList);
            openList.remove(currentNode);
            closedList.add(currentNode);

            if (closedList.contains(desNode)) {
                // 回溯
               return findPath(closedList.get(closedList.size() - 1));
            }

            List<Node> adjacentNodes = findWalkableAdjacent(currentNode, endX, endY, map, include1);
            for (Node adjacentNode : adjacentNodes) {
                // 在closed列表了
                if (closedList.contains(adjacentNode)) {
                    continue;
                }

                if (openList.contains(adjacentNode)) {
                    // 如果已经在开放列表, 比较他们的G值
                    Node originalNode = getNode(openList, adjacentNode.x, adjacentNode.y);
                    if (originalNode != null) {
                        if (adjacentNode.g < originalNode.g) {
                            // 将adjacentNode替代originalNode
                            System.out.println("adjacentNode.g = " + adjacentNode.g +", originalNode.g = " +originalNode.g);
                            openList.remove(originalNode);
                            openList.add(adjacentNode);
                        }
                    }

                } else {
                    // 添加进开放列表
                    openList.add(adjacentNode);
                }
            }

        } while (openList.size() > 0);
        return null;
    }

    private static Node getNode(List<Node> list, int x, int y) {
        for (Node node : list) {
            if (node.x == x && node.y == y) {
                return node;
            }
        }
        return null;
    }

    private static List<Position> findPath(Node endNode) {
        List<Position> path = new ArrayList<>();
        Node node = endNode;
        while(node.parent != null) {
            path.add(new Position(node.x, node.y));
            node = node.parent;
        }
        path.add(new Position(node.x, node.y));
        return path;
    }


    private static List<Node> findWalkableAdjacent(Node node, int endX, int endY, int[][] flagMap, boolean include1) {
        List<Node> nodes = new ArrayList<>();
        if (node.x > 0 && flagMap[node.x - 1][node.y] != 2) {
            nodes.add(createNode(node.x - 1, node.y, endX, endY, node, flagMap[node.x - 1][node.y] == 1 && include1));
        }

        if (node.x < flagMap.length - 1 && flagMap[node.x + 1][node.y] != 2) {
            nodes.add(createNode(node.x + 1, node.y, endX, endY, node, flagMap[node.x + 1][node.y] == 1 && include1));
        }

        if (node.y > 0 && flagMap[node.x][node.y - 1] != 2) {
            nodes.add(createNode(node.x, node.y- 1, endX, endY, node, flagMap[node.x][node.y - 1] == 1 && include1));
        }

        if (node.y < flagMap[0].length - 1 && flagMap[node.x][node.y + 1] != 2) {
            nodes.add(createNode(node.x, node.y + 1, endX, endY, node, flagMap[node.x][node.y + 1] == 1 && include1));
        }
        return nodes;
    }

    /** 
     *  关于include1,参数说明：
     *  正常情况下，1是不可以走的，因为那里有小怪。但是，有时候boss可能被一堆小怪挡住了，那小怪你是必须打的。
     *  给小怪所在的Node添加一个更高的G值，经过该小怪，需要花费我平时10倍的时间，所以我+10。具体这种情况要
     *  看地图大小，如果地图非常大，绕路不止10步的话，还是会认为打怪是最短路径。所以G值得考虑好。
     *  
     *  在以下这个例子中，*是出发点，要走到3，会经过 [0,1][0,0][1,0][2,0][2,1][2,2][2,3][1,3]
     *  完美选择了路径，只需要打一只怪。
     *  0 * 1 2
     *  0 1 1 3
     *  0 1 0 0
     */
    private static Node createNode(int x, int y, int endX, int endY, Node parent, boolean include1) {

        int g = parent == null? 1 : include1 ? parent.g +10 : parent.g + 1;
        int h = Math.abs(endX - x) + Math.abs(endY - y);
        Node node = new Node(x, y, g, h);
        node.parent = parent;
        return node;
    }

    private static class Position {
        public int x;
        public int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return x+","+y;
        }
    }

    private static class Node implements Comparable<Node> {
        public int x;
        public int y;
        public int g;
        public int h;
        public int f;
        public Node parent;

        public Node(int x, int y, int g, int h) {
            this.x = x;
            this.y = y;
            this.g = g;
            this.h = h;
            this.f = g + h;
        }


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node node = (Node) o;

            if (x != node.x) return false;
            return y == node.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }

        @Override
        public int compareTo(Node node) {
            return f - node.f;
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer();
            sb.append("[");
            sb.append(x);
            sb.append(", ").append(y);
            sb.append(", ").append(g);
            sb.append(", ").append(h);
            sb.append(", ").append(f);
            sb.append(", parent = ");
            if (parent != null) {
                sb.append(parent.x);
                sb.append(", ").append(parent.y);
            } else {
                sb.append("null"); 
            }
            sb.append("]");
            return sb.toString();
        }
    }
}