A* 寻路 - 多层地图中的奇怪错误

Question

我正在尝试在 Java 中创建一个游戏 "dungeon" 地图生成器，其风格类似于 roguelike 等游戏。我随机生成房间，然后将它们与走廊连接起来。我正在尝试在走廊创建中使用 A* 寻路。如果有多个房间，我目前只在索引 1 和 2 的房间之间创建一条走廊。

出于某种原因，当我尝试生成超过 1 张地图时，走廊创建似乎失败了 ("floors")。楼层数指定为命令行参数。到目前为止，当我只生成一个楼层时，一切都完美无缺。我的直觉告诉我地板有什么东西打乱了我的算法。

我认为项目的外部视图可能会有所帮助。代码很多，但如果有人花时间审阅它，我将不胜感激。如果需要，我可以提供更多信息。

结果

如果正确，结果应该如下所示：

Map 1

# wall
. floor
+ door
$ corridor

..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
...........$$$$$$$$$$.........
...........$......##+#######..
.....######$......#........#..
.....#....#$......#........#..
.....#....#$......#........#..
.....#....#$......#........#..
.....#....#$......#........#..
.....#....#$......#........#..
.....#....#$......#........#..
.....##+###$......##########..
.......$$$$$..................
..............................

越野车的结果是这样的（走廊没有挨家挨户，它只是在一个随机位置结束）：

...........$$$...#########....
...........$#+##.#.......#....
...........$#..#.#.......#....
...........$#..#.#.......+....
###+###....$#..#.#.......#....
#.....#....$#..#.#.......#....
#.....#....$#..#.#.......#....
#.....#....$#..#.#########....
#.....#....$####..............
#.....#....$..................
#.....#....$..................
#######....$..................
...........$..................
...........$..................
...........$..................
...........$..................
...........$..................
...........$..................
.......$$$$$..................
..............................

代码

AStar.java:

/**
 * See https://www.raywenderlich.com/4946/introduction-to-a-pathfinding
 */
public class AStar {

    private List<AStarSquare> openList;
    private List<AStarSquare> closedList;

    private Exporter debugExporter;

    private static final Coords[] squareOffsetsToCheck = new Coords[] {
        new Coords(0, 1),
        new Coords(1, 0),
        new Coords(0, -1),
        new Coords(-1, 0)
    };

    public AStar() {
        openList = new ArrayList<>();
        closedList = new ArrayList<>();
        debugExporter = new Exporter();
    }

    public List<Coords> findPath(Coords start, Coords end, Map map) {

        List<Coords> path = new ArrayList<>(); // each square on the generated path

        AStarSquare currentSquare = new AStarSquare(start, null); // current square around which possible squares are evaluated - start point
        closedList.add(currentSquare); // add start point to closed list

        createUpdateOpenSquares(currentSquare, start, end, map); // create open squares for first iteration
        calculateScores(start, end, map); // calculate scores for first iteration

        int loopGuard = 0;

        // loop until break
        while(true) {
            if(openList.size() == 0) {
                break;
            }
            currentSquare = getLowestOpenSquare(); // get the square with the lowest score
            if(isAdjacentToDoor(currentSquare.getCoords(), end) /*|| currentSquare.getCoords().equalz(end) || loopGuard >= 1000*/) // end point reached or no possible next squares
                break;                                                          // - exclude last square (door)
            openList.remove(currentSquare);
            closedList.add(currentSquare);
            createUpdateOpenSquares(currentSquare, start, end, map); // create and/or update squares next to the current square
            calculateScores(start, end, map);
            map.setDebugCorridor(formulatePath(currentSquare));
            loopGuard++;
        }

        path = formulatePath(currentSquare);

        return path;
    }

    private void createUpdateOpenSquares(AStarSquare currentSquare, Coords start, Coords end, Map map) {

        for(Coords squareOffsetToCheck : squareOffsetsToCheck) {
            Coords coordsToCheck = currentSquare.getCoords().vectorAdd(squareOffsetToCheck); 
            if(map.isFloor(coordsToCheck) 
                    && !map.isInsideRoom(coordsToCheck)
                    && isWithinMap(map, coordsToCheck)
                    && !isClosed(coordsToCheck)) {
                AStarSquare openSquare = getOpen(coordsToCheck); 
                if(openSquare == null)
                    openList.add(new AStarSquare(coordsToCheck, currentSquare));
                else // is open
                    openSquare.setPrevious(currentSquare);
            }
        }
    }

    private boolean isClosed(Coords coords) {
        for(AStarSquare closed : closedList) {
            if(closed.getCoords().equalz(coords))
                return true;
        }
        return false;
    }

    private AStarSquare getOpen(Coords coords) {
        for(AStarSquare open : openList) {
            if(open.getCoords().equalz(coords))
                return open;
        }
        return null;
    }

    private boolean isWithinMap(Map map, Coords coords) {
        if(coords.getX() < 0 
                || coords.getY() < 0 
                || coords.getX() >= map.getW()
                || coords.getY() >= map.getH())
            return false;
        return true;
    }

    private boolean isAdjacentToDoor(Coords coords, Coords end) {
        for(Coords squareOffset : squareOffsetsToCheck) {
            Coords offsetSquare = coords.vectorAdd(squareOffset);
            if(offsetSquare.equalz(end))
                return true;
        }
        return false;
    }

    private void calculateScores(Coords start, Coords end, Map map) {
        for(AStarSquare square : openList) {
            square.calculateScores(map, start, end);
        }
    }

    private AStarSquare getLowestOpenSquare() {

        AStarSquare lowestScore = null;

        for(AStarSquare square : openList) {
            // if lowestScore not set or if square.f is lower than lowestScore.f, set square to lowestScore
            if(lowestScore == null || lowestScore.getF() > square.getF())
                lowestScore = square;
        }

        return lowestScore;
    }

    // exclude first square (door)
    private List<Coords> formulatePath(AStarSquare currentSquare) {
        List<Coords> path = new ArrayList<>();
        while(currentSquare.getPrevious() != null) {
            path.add(currentSquare.getCoords());
            currentSquare = currentSquare.getPrevious();
        }
        return path;
    }
}

AStarSquare.java:

/**
 * See https://www.raywenderlich.com/4946/introduction-to-a-pathfinding
 */
public class AStarSquare {

    private Coords coords;
    private AStarSquare previous;

    private int g, h;
    private boolean calculated;

    public AStarSquare() {
        g = h = 0;
        calculated = false;
    }

    public AStarSquare(Coords coords) {
        this();
        this.coords = coords;
        previous = null;
    }

    public AStarSquare(Coords coords, AStarSquare previous) {
        this();
        this.coords = coords;
        this.previous = previous;
    }

    public void calculateScores(Map map, Coords start, Coords destination) {
        g = previous.getG() + 1; // g = distance from start point
        h = destination.getDistance(coords); // h = estimated (=shortest) distance from the current location to the destination
        calculated = true;
    }
}

主要class:

public class DungeonMapGenerator {

    public static void main(String[] args) {

        List<String> argsList = Arrays.asList(args);

        if(!argsList.contains("-w") 
                || !argsList.contains("-h") 
                || !argsList.contains("-f")) {
            System.out.println("Usage: java -jar DungeonMapGenerator.jar -w [width] -h [height] -f [floors] -[export option]");
            System.exit(1);
        }

        int width = 0, height = 0, floors = 0;

        for(int i = 0; i < args.length; i++) {
            if(args[i].equalsIgnoreCase("-w"))
                width = tryParseInt(args, i + 1, 30);
            else if(args[i].equalsIgnoreCase("-h"))
                height = tryParseInt(args, i + 1, 20);
            else if(args[i].equalsIgnoreCase("-f"))
                floors = tryParseInt(args, i + 1, 1);
        }

        Generator mapGenerator = new Generator(width, height, floors);
        List<Map> maps = mapGenerator.generateMaps();

        Exporter mapExporter = new Exporter();

        if(argsList.contains("-c"))
            mapExporter.exportToConsole(maps);
        else
            System.out.println("No export option selected, quitting");
    }

    private static int tryParseInt(String[] args, int index, int deflt) {
        int res;
        if(index >= args.length) // index out of range
            res = deflt;
        try {
            res = Integer.parseInt(args[index], 10);
        } catch(NumberFormatException ex) {
            res = deflt;
        }
        return res;
    }
}

Generator.java

public class Generator {

    private static final int
        MIN_ROOMS = 1,
        MAX_ROOMS = 5,
        MIN_DIM = 3, // dim = min and max room dimensions
        MAX_DIM = 10;

    private AStar pathfinder;
    private Random random;

    private int mapWidth, mapHeight, floors;

    public Generator(int mapWidth, int mapHeight, int floors) {
        pathfinder = new AStar();
        random = new Random(System.currentTimeMillis());
        this.mapWidth = mapWidth;
        this.mapHeight = mapHeight;
        this.floors = floors;
    }

    public List<Map> generateMaps() {

        List<Map> mapList = new ArrayList<>();

        for(int i = 0; i < floors; i++) {
            Map map = new Map(i + 1, mapWidth, mapHeight, generateRooms(mapWidth, mapHeight), null);
            generateDoors(map, map.getRooms());
            debugFindPath(map);
            mapList.add(map);
        }

        return mapList;
    }

    private List<Room> generateRooms(int mapWidth, int mapHeight) {

        List<Room> roomList = new ArrayList<>();
        int nRooms = random.nextInt(5) + 1;

        for(int i = 0; i < nRooms; i++) {

            Room room = null;

            do {

                int w = 0, h = 0, x = 0, y = 0;

                w = getRandomDim();
                h = getRandomDim();
                x = random.nextInt(mapWidth - w);
                y = random.nextInt(mapHeight - h);

                room = new Room(x, y, w, h);

            } while(roomsOverlap(room, roomList));

            roomList.add(room);
        }

        return roomList;
    }

    private boolean roomsOverlap(Room room, List<Room> rooms) {

        for(Room listRoom : rooms) {
            if(room.overlapsWithRoom(listRoom))
                return true;
        }

        return false;
    }

    private int getRandomDim() {
        return random.nextInt(MAX_DIM - MIN_DIM + 1) + MIN_DIM;
    }

    private void generateDoors(Map map, List<Room> roomList) {

        for(int i = 0; i < roomList.size(); i++) {

            Door door = new Door(roomList.get(i));

            do {
                door.setSide(getRandomCardinal());
                door.setDistNW(getRandomDistNW(roomList.get(i), door.getSide()));
            } while(!validateDoor(map, door));

            roomList.get(i).setDoors(Arrays.asList(new Door[] { door }));

            map.getDoors().add(door);
        }
    }

    private Cardinal getRandomCardinal() {
        int cardinalInt = random.nextInt(4);
        Cardinal cardinal;
        switch(cardinalInt) {
        case 1:
            cardinal = Cardinal.EAST;
            break;
        case 2:
            cardinal = Cardinal.SOUTH;
            break;
        case 3:
            cardinal = Cardinal.WEST;
        case 0:
        default:
            cardinal = Cardinal.NORTH;
            break;
        }
        return cardinal;
    }

    private int getRandomDistNW(Room room, Cardinal cardinal) {
        int distNW = 0;
        if(cardinal == Cardinal.NORTH || cardinal == Cardinal.SOUTH)
            distNW = random.nextInt(room.getW() - 2) + 1; // exclude corners
        else if(cardinal == Cardinal.EAST || cardinal == Cardinal.WEST)
            distNW = random.nextInt(room.getH() - 2) + 1; // exclude corners
        return distNW;
    }

    private boolean validateDoor(Map map, Door door) {

        Coords doorCoordsOnMap = door.getCoordsOnMap(); 

        if(door.getSide() == Cardinal.NORTH 
                && (door.getParent().getTop() == 0 
                    // check if adjacent to another room
                    || map.isWall(new Coords(doorCoordsOnMap.getX(), doorCoordsOnMap.getY() - 1))))
            return false;
        else if(door.getSide() == Cardinal.EAST 
                && (door.getParent().getRight() == mapWidth - 1 
                    // check if adjacent to another room
                    || map.isWall(new Coords(doorCoordsOnMap.getX() + 1, doorCoordsOnMap.getY()))))
            return false;
        else if(door.getSide() == Cardinal.SOUTH 
                && (door.getParent().getBottom() == mapHeight - 1
                    // check if adjacent to another room
                    || map.isWall(new Coords(doorCoordsOnMap.getX(), doorCoordsOnMap.getY() + 1))))
            return false;
        else if(door.getSide() == Cardinal.WEST 
                && (door.getParent().getLeft() == 0
                    // check if adjacent to another room
                    || map.isWall(new Coords(doorCoordsOnMap.getX() - 1, doorCoordsOnMap.getY()))))
            return false;

        return true;
    }

    private void debugFindPath(Map map) {
        if(map.getRooms().size() == 1)
            return;
        map.setDebugCorridor(pathfinder.findPath(
                map.getRooms().get(0).getDoors().get(0).getCoordsOnMap(), 
                map.getRooms().get(1).getDoors().get(0).getCoordsOnMap(), 
                map
        )); 
    }
}

Room.java

public class Room {

    private Coords topLeft;
    private int w, h;
    private List<Door> doors;

    public Room(int topLeftX, int topLeftY, int w, int h) {
        topLeft = new Coords(topLeftX, topLeftY);
        this.w = w;
        this.h = h;
        doors = new ArrayList<>();
    }

    public boolean overlapsWithRoom(Room otherRoom) {
        return !(otherRoom.getLeft() > this.getRight()
                || otherRoom.getRight() < this.getLeft()
                || otherRoom.getTop() > this.getBottom()
                || otherRoom.getBottom() < this.getTop());
    }

    @Override
    public String toString() {
        return "Room ~ top: " + getTop() + " right: " + getRight() 
            + " bottom: " + getBottom() + " left: " + getLeft()
            + " width: " + w + " height: " + h;
    }

    public boolean isWall(Coords coords) { /*** TESTAA!!! ***/
        if(
                // x is either left or right, y is between top and bottom 
                ((coords.getX() == topLeft.getX() || coords.getX() == topLeft.getX() + w) 
                    && coords.getY() >= topLeft.getY() && coords.getY() < topLeft.getY() + h + 1)
                ||
                // y is either top or bottom, x is between left and right
                ((coords.getY() == topLeft.getY() || coords.getY() == topLeft.getY() + h)
                    && coords.getX() >= topLeft.getX() && coords.getX() < topLeft.getX() + w)
                )
            return true;
        return false;
    }
}

Door.java

（Cardinal 是一个包含 NORTH、EAST、SOUTH 和 WEST 的简单枚举）

public class Door {

    private Room parent;
    private Cardinal side;

    private int distNW = 0;

    public Door(Room parent) {
        this.parent = parent;
        this.side = null;
    }

    public Door(Room parent, Cardinal side) {
        this.parent = parent;
        this.side = side;
    }

    public Coords getCoordsOnMap() {
        Coords coords = null;
        if(side == Cardinal.NORTH)
            coords = new Coords(parent.getLeft() + distNW, parent.getTop());
        else if(side == Cardinal.EAST)
            coords = new Coords(parent.getRight(), parent.getTop() + distNW);
        else if(side == Cardinal.SOUTH)
            coords = new Coords(parent.getLeft() + distNW, parent.getBottom());
        else if(side == Cardinal.WEST)
            coords = new Coords(parent.getLeft(), parent.getTop() + distNW);
        return coords;
    }
}

Answer 1

在 AStar 中，您的 A* 寻路算法在返回所选路径之前添加到其打开和关闭列表中

当使用不同的 start/end 目的地或不同的地图进行寻路时，需要重新设置这些列表

问题是您正在为您尝试查找的每个路径重复使用 AStar 对象，导致与旧搜索发生冲突

要修复它，请为您搜索的每个路径使用一个新的 AStar 对象，或者添加一个方法来清除旧数据

Answer 2

我从生成器构造函数中删除了这一行：

public Generator(int mapWidth, int mapHeight, int floors) {
    // pathfinder = new AStar(); // REMOVED THIS LINE
    ...
}

并且我在 Generator.generateMaps 方法中添加了以下行：

public List<Map> generateMaps() {

    List<Map> mapList = new ArrayList<>();

    for(int i = 0; i < floors; i++) {
        pathfinder = new AStar(); // ADDED THIS LINE
        Map map = new Map(i + 1, mapWidth, mapHeight, generateRooms(mapWidth, mapHeight), null);
        generateDoors(map, map.getRooms());
        debugFindPath(map);
        mapList.add(map);
    }

    return mapList;
}

现在一切似乎都正常了。

另一种选择是将以下行添加到 AStar.findPath():

public List<Coords> findPath(Coords start, Coords end, Map map) {

    openList = new ArrayList<>();
    closedList = new ArrayList<>();
    ...
}

A* 寻路 - 多层地图中的奇怪错误

A* Pathfinding - Weird Bug in Multi-Floored Maps

java

algorithm

a-star