title: A* Pathfinding - Weird Bug in Multi-Floored Maps
body: <p>I'm attempting to create a game "dungeon" map generator in Java in the style of roguelike etc. games. I generate rooms randomly, and then connect them with corridors. I'm trying to use A* pathfinding in corridor creation. I currently am creating just one corridor between rooms in the indices 1 and 2, if there is more than one room. </p>
  
  <p>For some reason, the corridor creation seems to fail when I try to generate more than 1 maps ("floors"). The amount of floors is specified as a command-line parameter. Thus far, when I've generated just one floor, everything works perfectly. My gut feeling says that there's something about the floors that messes up my algorithm.</p>
  
  <p>I thought that maybe an outside view of the project could help. There is quite a lot of code, but I'd be very grateful if someone took the time to review it. I can provide more information if it's needed.</p>
  
  <p>THE RESULTS</p>
  
  <p>The result, when correct, should look like this:</p>
  
  <pre><code>Map 1
  
  # wall
  . floor
  + door
  $ corridor
  
  ..............................
  ..............................
  ..............................
  ..............................
  ..............................
  ..............................
  ..............................
  ..............................
  ...........$$$$$$$$$$.........
  ...........$......##+#######..
  .....######$......#........#..
  .....#....#$......#........#..
  .....#....#$......#........#..
  .....#....#$......#........#..
  .....#....#$......#........#..
  .....#....#$......#........#..
  .....#....#$......#........#..
  .....##+###$......##########..
  .......$$$$$..................
  ..............................
  </code></pre>
  
  <p>The buggy result looks like this (the corridor does not go door-to-door, it just ends in a random location):</p>
  
  <pre><code>...........$$$...#########....
  ...........$#+##.#.......#....
  ...........$#..#.#.......#....
  ...........$#..#.#.......+....
  ###+###....$#..#.#.......#....
  #.....#....$#..#.#.......#....
  #.....#....$#..#.#.......#....
  #.....#....$#..#.#########....
  #.....#....$####..............
  #.....#....$..................
  #.....#....$..................
  #######....$..................
  ...........$..................
  ...........$..................
  ...........$..................
  ...........$..................
  ...........$..................
  ...........$..................
  .......$$$$$..................
  ..............................
  </code></pre>
  
  <p>THE CODE</p>
  
  <p>AStar.java:</p>
  
  <pre><code>/**
   * See https://www.raywenderlich.com/4946/introduction-to-a-pathfinding
   */
  public class AStar {
  
      private List&lt;AStarSquare&gt; openList;
      private List&lt;AStarSquare&gt; 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&lt;&gt;();
          closedList = new ArrayList&lt;&gt;();
          debugExporter = new Exporter();
      }
  
      public List&lt;Coords&gt; findPath(Coords start, Coords end, Map map) {
  
          List&lt;Coords&gt; path = new ArrayList&lt;&gt;(); // 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 &gt;= 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) 
                      &amp;&amp; !map.isInsideRoom(coordsToCheck)
                      &amp;&amp; isWithinMap(map, coordsToCheck)
                      &amp;&amp; !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() &lt; 0 
                  || coords.getY() &lt; 0 
                  || coords.getX() &gt;= map.getW()
                  || coords.getY() &gt;= 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() &gt; square.getF())
                  lowestScore = square;
          }
  
          return lowestScore;
      }
  
      // exclude first square (door)
      private List&lt;Coords&gt; formulatePath(AStarSquare currentSquare) {
          List&lt;Coords&gt; path = new ArrayList&lt;&gt;();
          while(currentSquare.getPrevious() != null) {
              path.add(currentSquare.getCoords());
              currentSquare = currentSquare.getPrevious();
          }
          return path;
      }
  }
  </code></pre>
  
  <p>AStarSquare.java:</p>
  
  <pre><code>/**
   * 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;
      }
  }
  </code></pre>
  
  <p>Main class:</p>
  
  <pre><code>public class DungeonMapGenerator {
  
      public static void main(String[] args) {
  
          List&lt;String&gt; 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 &lt; 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&lt;Map&gt; 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 &gt;= args.length) // index out of range
              res = deflt;
          try {
              res = Integer.parseInt(args[index], 10);
          } catch(NumberFormatException ex) {
              res = deflt;
          }
          return res;
      }
  }
  </code></pre>
  
  <p>Generator.java</p>
  
  <pre><code>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&lt;Map&gt; generateMaps() {
  
          List&lt;Map&gt; mapList = new ArrayList&lt;&gt;();
  
          for(int i = 0; i &lt; 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&lt;Room&gt; generateRooms(int mapWidth, int mapHeight) {
  
          List&lt;Room&gt; roomList = new ArrayList&lt;&gt;();
          int nRooms = random.nextInt(5) + 1;
  
          for(int i = 0; i &lt; 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&lt;Room&gt; 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&lt;Room&gt; roomList) {
  
          for(int i = 0; i &lt; 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 
                  &amp;&amp; (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 
                  &amp;&amp; (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 
                  &amp;&amp; (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 
                  &amp;&amp; (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
          )); 
      }
  }
  </code></pre>
  
  <p>Room.java</p>
  
  <pre><code>public class Room {
  
      private Coords topLeft;
      private int w, h;
      private List&lt;Door&gt; 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&lt;&gt;();
      }
  
      public boolean overlapsWithRoom(Room otherRoom) {
          return !(otherRoom.getLeft() &gt; this.getRight()
                  || otherRoom.getRight() &lt; this.getLeft()
                  || otherRoom.getTop() &gt; this.getBottom()
                  || otherRoom.getBottom() &lt; 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) 
                      &amp;&amp; coords.getY() &gt;= topLeft.getY() &amp;&amp; coords.getY() &lt; 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)
                      &amp;&amp; coords.getX() &gt;= topLeft.getX() &amp;&amp; coords.getX() &lt; topLeft.getX() + w)
                  )
              return true;
          return false;
      }
  }
  </code></pre>
  
  <p>Door.java</p>
  
  <p>(Cardinal is a simple enum containing NORTH, EAST, SOUTH and WEST)</p>
  
  <pre><code>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;
      }
  }
  </code></pre>