Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 1 | daniel-mar | 1 | package gdi1sokoban.game; |
| 2 | |||
| 3 | import gdi1sokoban.exceptions.ParameterOutOfRangeException; |
||
| 4 | import gdi1sokoban.exceptions.ParseException; |
||
| 5 | import gdi1sokoban.globals.Point; |
||
| 6 | |||
| 7 | import java.io.BufferedReader; |
||
| 8 | import java.io.File; |
||
| 9 | import java.io.FileReader; |
||
| 10 | import java.io.IOException; |
||
| 11 | import java.net.URISyntaxException; |
||
| 12 | import java.util.ArrayList; |
||
| 13 | import java.util.Arrays; |
||
| 14 | import java.util.HashMap; |
||
| 15 | import java.util.LinkedList; |
||
| 16 | |||
| 17 | /** |
||
| 18 | * GameLevel class |
||
| 19 | * |
||
| 20 | * Holds level information and supplies functions |
||
| 21 | * for manipulating objects |
||
| 22 | */ |
||
| 23 | public class GameLevel { |
||
| 24 | |||
| 25 | private char[][] gameMap = new char[0][0]; // array to save game-field |
||
| 26 | private int height = 0; // level-height in fields |
||
| 27 | private int width = 0; // level-width in fields |
||
| 28 | private int steps = 0; // completed valid steps |
||
| 29 | // HashMap to store the meaning of the chars |
||
| 30 | private final HashMap<Character, String> charRepresentation = new HashMap<Character, String>(); |
||
| 31 | private final GameLevelHistory history = new GameLevelHistory(); |
||
| 32 | |||
| 33 | /** |
||
| 34 | * Reads a File and parses the level |
||
| 35 | * |
||
| 36 | * @param lvl |
||
| 37 | * Levelfile to read |
||
| 38 | * @throws IOException |
||
| 39 | */ |
||
| 40 | public GameLevel(final File lvl) throws IOException, ParseException { |
||
| 41 | init(lvl); |
||
| 42 | } |
||
| 43 | |||
| 44 | /** |
||
| 45 | * Reads a filename, opens the file and parses the level |
||
| 46 | * |
||
| 47 | * @param fileName |
||
| 48 | * fileName of the file the level is saved in |
||
| 49 | * @throws URISyntaxException |
||
| 50 | * @throws IOException |
||
| 51 | */ |
||
| 52 | public GameLevel(final String fileName) throws URISyntaxException, IOException, ParseException { |
||
| 53 | final File lvl = new File(ClassLoader.getSystemClassLoader().getResource( |
||
| 54 | fileName).toURI()); |
||
| 55 | init(lvl); |
||
| 56 | } |
||
| 57 | |||
| 58 | /** |
||
| 59 | * Reads a File and parses the level |
||
| 60 | * |
||
| 61 | * @param lvl |
||
| 62 | * Levelfile to read |
||
| 63 | * @throws IOException |
||
| 64 | */ |
||
| 65 | private void init(final File lvl) throws IOException, ParseException{ |
||
| 66 | fillCharRepresentation(); |
||
| 67 | parse(lvl); |
||
| 68 | history.setStart(gameMap); // set history start |
||
| 69 | } |
||
| 70 | |||
| 71 | /** |
||
| 72 | * fills the HashMap of chars and their objectnames |
||
| 73 | * |
||
| 74 | */ |
||
| 75 | private void fillCharRepresentation() { |
||
| 76 | charRepresentation.put('@', "player"); |
||
| 77 | charRepresentation.put(' ', "field"); |
||
| 78 | charRepresentation.put('#', "wall"); |
||
| 79 | charRepresentation.put('$', "crate"); |
||
| 80 | charRepresentation.put('.', "goal"); |
||
| 81 | charRepresentation.put('*', "crateOnGoal"); |
||
| 82 | charRepresentation.put('+', "playerOnGoal"); |
||
| 83 | } |
||
| 84 | |||
| 85 | /** |
||
| 86 | * returns the height of the level |
||
| 87 | * |
||
| 88 | * @return level-height (in fields) |
||
| 89 | */ |
||
| 90 | public int getHeight() { |
||
| 91 | return height; |
||
| 92 | } |
||
| 93 | |||
| 94 | /** |
||
| 95 | * returns the width of the level |
||
| 96 | * |
||
| 97 | * @return level-width (in fields) |
||
| 98 | */ |
||
| 99 | public int getWidth() { |
||
| 100 | return width; |
||
| 101 | } |
||
| 102 | |||
| 103 | /** |
||
| 104 | * returns the object which is placed on the given field |
||
| 105 | * |
||
| 106 | * @param top |
||
| 107 | * top-pos of field |
||
| 108 | * @param left |
||
| 109 | * left-pos of field |
||
| 110 | * @return Name of object on this field |
||
| 111 | * @throws ParameterOutOfRangeException |
||
| 112 | */ |
||
| 113 | public String getObject(final int top, final int left) throws ParameterOutOfRangeException { |
||
| 114 | if ((top < 0) || (top >= height) || (left < 0) || (left >= width)) |
||
| 115 | throw new ParameterOutOfRangeException("Koordinaten ausserhalb des Spielfelds"); |
||
| 116 | return charRepresentation.get(gameMap[top][left]); |
||
| 117 | } |
||
| 118 | |||
| 119 | /** |
||
| 120 | * returns the current position of the Player |
||
| 121 | * @return an Integer Array containing the position of the player (top, left) |
||
| 122 | * @throws ParameterOutOfRangeException |
||
| 123 | */ |
||
| 124 | public Point getPlayerPos() throws ParameterOutOfRangeException { |
||
| 125 | for (int top = 0; top < gameMap.length; top++) |
||
| 126 | for (int left = 0; left < gameMap[0].length; left++) |
||
| 127 | if ((getObject(top, left) == "player") |
||
| 128 | || (getObject(top, left) == "playerOnGoal")) |
||
| 129 | return new Point(top, left); |
||
| 130 | // no player on field |
||
| 131 | return new Point(-1, -1); |
||
| 132 | } |
||
| 133 | |||
| 134 | /** |
||
| 135 | * Parses a level from a given Levelfile |
||
| 136 | * |
||
| 137 | * @param lvl |
||
| 138 | * @throws IOException |
||
| 139 | * @throws URISyntaxException |
||
| 140 | */ |
||
| 141 | private void parse(final File lvlFile) throws IOException, ParseException { |
||
| 142 | final BufferedReader in = new BufferedReader(new FileReader(lvlFile)); |
||
| 143 | StringBuffer levelCode = new StringBuffer(128); |
||
| 144 | String line = null; |
||
| 145 | while ((line = in.readLine()) != null) // read every line |
||
| 146 | levelCode.append(line).append("\n"); |
||
| 147 | in.close(); |
||
| 148 | // parse level code |
||
| 149 | parseString(levelCode.toString()); |
||
| 150 | } |
||
| 151 | /** |
||
| 152 | * Parses a level file from a string |
||
| 153 | * @param lvlString |
||
| 154 | */ |
||
| 155 | protected void parseString(final String lvlString) throws IOException, ParseException { |
||
| 156 | final String[] levelLines = lvlString.split("\n"); |
||
| 157 | final ArrayList<String> lines = new ArrayList<String>(0); |
||
| 158 | height = 0; |
||
| 159 | width = 0; |
||
| 160 | for(int i = 0; i < levelLines.length; i++){ |
||
| 161 | //cut unneccessary spaces from right |
||
| 162 | String line = levelLines[i]; |
||
| 163 | if (chopSpaces(line).isEmpty()) { // check if this line, which only exists of spaces, can be removed |
||
| 164 | boolean canChop = true; |
||
| 165 | for (int k = i+1; k < levelLines.length; k++) { // check if there are more lines with level code |
||
| 166 | if (! chopSpaces(levelLines[k]).isEmpty()) |
||
| 167 | canChop = false; // there exists a line with level code, so don't chop this line |
||
| 168 | } |
||
| 169 | if (canChop) |
||
| 170 | line = ""; // remove line from level code |
||
| 171 | } |
||
| 172 | |||
| 173 | // get maximum width |
||
| 174 | if (width < line.length()) |
||
| 175 | width = line.length(); |
||
| 176 | // Add line to ArrayList of lines if it is not empty |
||
| 177 | if(line.length() > 0){ |
||
| 178 | lines.add(line); |
||
| 179 | // the height is the number of lines |
||
| 180 | height++; |
||
| 181 | } |
||
| 182 | } |
||
| 183 | // Set gamemap to right height and size |
||
| 184 | gameMap = new char[height][width]; |
||
| 185 | // copy characters into of gameMap-fields |
||
| 186 | for (int i = 0; i < height; i++) { |
||
| 187 | // Fill all fields with blanks (empty fields) |
||
| 188 | Arrays.fill(gameMap[i], ' '); |
||
| 189 | // copy all characters of this line into the current row of gameMap |
||
| 190 | System.arraycopy(lines.get(i).toCharArray(), 0, gameMap[i], 0, |
||
| 191 | lines.get(i).length()); |
||
| 192 | } |
||
| 193 | // check level syntax |
||
| 194 | if (! checkSyntax()) |
||
| 195 | throw new ParseException("Fehler: Leveldatei ist syntaktisch nicht korrekt!"); |
||
| 196 | } |
||
| 197 | |||
| 198 | /** |
||
| 199 | * Checks the Level-Array for syntactical correctness |
||
| 200 | * |
||
| 201 | * @return true when syntax is correct else false |
||
| 202 | */ |
||
| 203 | private boolean checkSyntax() { |
||
| 204 | try { |
||
| 205 | return ( (countCrates() > 0) && (countGoals() == countCrates()) && (countPlayer() == 1) && (containsOnlyAllowedChars()) && (checkWallBounding()) ); |
||
| 206 | } catch (ParameterOutOfRangeException e) { |
||
| 207 | System.err.println("Interner Fehler: Fehler beim Prüfen der Levelsyntax!"); |
||
| 208 | return false; |
||
| 209 | } |
||
| 210 | } |
||
| 211 | |||
| 212 | /** |
||
| 213 | * removes all tailing spaces from a given string |
||
| 214 | * @param s the string |
||
| 215 | * @return the string s without tailing spaces |
||
| 216 | */ |
||
| 217 | private String chopSpaces(String s){ |
||
| 218 | while(s.endsWith(" ")) |
||
| 219 | s = s.substring(0, s.length() - 1); |
||
| 220 | return s; |
||
| 221 | } |
||
| 222 | |||
| 223 | /** |
||
| 224 | * helper function to count how many times the given character is in gameMap |
||
| 225 | * |
||
| 226 | * @param c |
||
| 227 | * Character to count |
||
| 228 | * @return number of given character in GameMap |
||
| 229 | */ |
||
| 230 | private int countCharacter(final char c) { |
||
| 231 | int counter = 0; |
||
| 232 | for (final char[] rows : gameMap) |
||
| 233 | for (final char element : rows) |
||
| 234 | if (element == c) |
||
| 235 | counter++; |
||
| 236 | return counter; |
||
| 237 | } |
||
| 238 | |||
| 239 | /** |
||
| 240 | * checks if the gameMap only consists of chars used in the |
||
| 241 | * format-description |
||
| 242 | * |
||
| 243 | * @return true if all chars are correct, false otherwise |
||
| 244 | */ |
||
| 245 | private boolean containsOnlyAllowedChars() { |
||
| 246 | // check for every element if it is in the list of allowed chars |
||
| 247 | for (final char[] rows : gameMap) |
||
| 248 | for (final char element : rows) |
||
| 249 | // if a element is not in the list the method returns false |
||
| 250 | if (!charRepresentation.containsKey(element)) { |
||
| 251 | return false; |
||
| 252 | } |
||
| 253 | return true; |
||
| 254 | } |
||
| 255 | |||
| 256 | /** |
||
| 257 | * checks if an element is in a corner |
||
| 258 | * @param top top-position of element |
||
| 259 | * @param left left-position of element |
||
| 260 | * @return true if element is in a corner, false otherwise |
||
| 261 | * @throws ParameterOutOfRangeException |
||
| 262 | */ |
||
| 263 | private boolean isInCorner(final int top, final int left) throws ParameterOutOfRangeException{ |
||
| 264 | final boolean isTopLeftCorner = (isWall(top, left-1) && isWall(top-1, left)); |
||
| 265 | final boolean isTopRightCorner = (isWall(top, left+1) && isWall(top-1, left)); |
||
| 266 | final boolean isDownLeftCorner = (isWall(top, left-1) && isWall(top+1, left)); |
||
| 267 | final boolean isDownRightCorner = (isWall(top, left+1) && isWall(top+1, left)); |
||
| 268 | return (isTopLeftCorner || isTopRightCorner || isDownLeftCorner || isDownRightCorner); |
||
| 269 | } |
||
| 270 | |||
| 271 | /** |
||
| 272 | * checks the level for deadlocks |
||
| 273 | * the level contains a deadlock |
||
| 274 | * when at least one crate is in a corner |
||
| 275 | * or four elements (of which at least one is a crate) |
||
| 276 | * form a square |
||
| 277 | * @return true if level is in deadlock situation |
||
| 278 | * false otherwise |
||
| 279 | * @throws ParameterOutOfRangeException |
||
| 280 | */ |
||
| 281 | public boolean hasDeadlock() throws ParameterOutOfRangeException{ |
||
| 282 | // iterate through every element of gameMap |
||
| 283 | for(int top=0; top<gameMap.length; top++) |
||
| 284 | for(int left=0; left<gameMap[0].length; left++) |
||
| 285 | // if element is a crate |
||
| 286 | if(getObject(top, left) == "crate"){ |
||
| 287 | // there are four possibilities to form a square with the current crate |
||
| 288 | final boolean square1 = (!isFree(top, left-1) && !isFree(top-1, left) && !isFree(top-1, left-1)); |
||
| 289 | final boolean square2 = (!isFree(top, left+1) && !isFree(top-1, left) && !isFree(top-1, left+1)); |
||
| 290 | final boolean square3 = (!isFree(top, left-1) && !isFree(top+1, left) && !isFree(top+1, left-1)); |
||
| 291 | final boolean square4 = (!isFree(top, left+1) && !isFree(top+1, left) && !isFree(top+1, left+1)); |
||
| 292 | // if a crate is placed in a corner or one of the four possibilities to form a square are true |
||
| 293 | // the level contains a deadlock and true has to be returned |
||
| 294 | if(isInCorner(top, left) || square1 || square2 || square3 || square4) // || futureSquare1 && futureSquare2 && futureSquare3 && futureSquare4) |
||
| 295 | return true; |
||
| 296 | } |
||
| 297 | return false; |
||
| 298 | } |
||
| 299 | |||
| 300 | /** |
||
| 301 | * sets an object to a certain field without changing the type of the field |
||
| 302 | * (i.e. field is goal or normal field) |
||
| 303 | * |
||
| 304 | * @param top |
||
| 305 | * @param left |
||
| 306 | * @param object |
||
| 307 | * @throws ParameterOutOfRangeException |
||
| 308 | * @TODO difference between normal fields and goal fields (e.g. a Class for |
||
| 309 | * field or a second HashMap containing goals) |
||
| 310 | */ |
||
| 311 | private void setObject(final int top, final int left, final String object) throws ParameterOutOfRangeException { |
||
| 312 | // if the field is a goal (i.e. goal, playerOnGoal, cateOnGoal) this |
||
| 313 | // attribute has to be saved and reassigned to the new field |
||
| 314 | final String oldObj = getObject(top, left); |
||
| 315 | // Hashmaps to store the key-value pair of object's old name and |
||
| 316 | // object's new name |
||
| 317 | final HashMap<String, String> newObjNames = new HashMap<String, String>(); |
||
| 318 | // if this field is a goal all characters in the Map have to be replaced |
||
| 319 | // by their equivalent standing on a Goal (e.g. player => playerOnGoal) |
||
| 320 | if ((oldObj == "goal") || (oldObj == "crateOnGoal") |
||
| 321 | || (oldObj == "playerOnGoal")) { |
||
| 322 | newObjNames.put("field", "goal"); |
||
| 323 | newObjNames.put("player", "playerOnGoal"); |
||
| 324 | newObjNames.put("crate", "crateOnGoal"); |
||
| 325 | newObjNames.put("goal", "goal"); |
||
| 326 | newObjNames.put("playerOnGoal", "playerOnGoal"); |
||
| 327 | newObjNames.put("crateOnGoal", "crateOnGoal"); |
||
| 328 | } else { |
||
| 329 | newObjNames.put("goal", "field"); |
||
| 330 | newObjNames.put("playerOnGoal", "player"); |
||
| 331 | newObjNames.put("crateOnGoal", "crate"); |
||
| 332 | newObjNames.put("field", "field"); |
||
| 333 | newObjNames.put("player", "player"); |
||
| 334 | newObjNames.put("crate", "crate"); |
||
| 335 | } |
||
| 336 | for (final char possibleChar : charRepresentation.keySet()) |
||
| 337 | if (charRepresentation.get(possibleChar) == newObjNames.get(object)) |
||
| 338 | gameMap[top][left] = possibleChar; |
||
| 339 | } |
||
| 340 | |||
| 341 | /** |
||
| 342 | * checks if the given field is free (i.e. goal or empty field) |
||
| 343 | * @param top |
||
| 344 | * @param left |
||
| 345 | * @return true if field is free, else otherwise |
||
| 346 | * @throws ParameterOutOfRangeException |
||
| 347 | */ |
||
| 348 | private boolean isFree(final int top, final int left) throws ParameterOutOfRangeException{ |
||
| 349 | if((top < 0) || (left < 0) || (top >= getHeight()) || (left >= getWidth())) |
||
| 350 | return false; |
||
| 351 | return ((getObject(top, left) == "field") |
||
| 352 | || (getObject(top, left) == "goal") |
||
| 353 | || (getObject(top, left) == "player") |
||
| 354 | || (getObject(top, left) == "playerOnGoal") ); |
||
| 355 | } |
||
| 356 | |||
| 357 | /** |
||
| 358 | * checks if the field on the given point is free |
||
| 359 | * @param p point containing the position of the field |
||
| 360 | * @return true if field is free, else otherwise |
||
| 361 | * @throws ParameterOutOfRangeException |
||
| 362 | */ |
||
| 363 | private boolean isFree(final Point p) throws ParameterOutOfRangeException{ |
||
| 364 | return isFree(p.top, p.left); |
||
| 365 | } |
||
| 366 | |||
| 367 | /** |
||
| 368 | * sets an object of the map to another position if the field is free |
||
| 369 | * |
||
| 370 | * @param top |
||
| 371 | * Top-Pos. of element |
||
| 372 | * @param left |
||
| 373 | * Left-Pos. of element |
||
| 374 | * @param destTop |
||
| 375 | * new Top-Pos. |
||
| 376 | * @param destLeft |
||
| 377 | * new Left-Pos. |
||
| 378 | * @return true if the field is free and the new position is set, false |
||
| 379 | * otherwise |
||
| 380 | * @throws ParameterOutOfRangeException |
||
| 381 | */ |
||
| 382 | public boolean setPosition(final int top, final int left, final int destTop, final int destLeft) throws ParameterOutOfRangeException { |
||
| 383 | final boolean canMove = isFree(destTop, destLeft); |
||
| 384 | if (canMove) { |
||
| 385 | setObject(destTop, destLeft, getObject(top, left)); |
||
| 386 | setObject(top, left, "field"); |
||
| 387 | // if an object is moved the history may not contain any entries after that move |
||
| 388 | history.deleteAfterCurrent(); |
||
| 389 | } |
||
| 390 | return canMove; |
||
| 391 | } |
||
| 392 | |||
| 393 | /** |
||
| 394 | * helper function needed to check if the player number is correct |
||
| 395 | * @return number of players in Level |
||
| 396 | */ |
||
| 397 | private int countPlayer() { |
||
| 398 | return countCharacter('@') + countCharacter('+'); |
||
| 399 | } |
||
| 400 | |||
| 401 | /** |
||
| 402 | * counts the number of Crates (all crates) |
||
| 403 | * |
||
| 404 | * @return number of crates in this level |
||
| 405 | */ |
||
| 406 | public int countCrates() { |
||
| 407 | return countCharacter('$') + countCharacter('*'); |
||
| 408 | } |
||
| 409 | |||
| 410 | /** |
||
| 411 | * counts the number of Crates (only crates on goals) |
||
| 412 | * |
||
| 413 | * @return number of crates in this level |
||
| 414 | */ |
||
| 415 | public int countCratesOnGoal() { |
||
| 416 | return countCharacter('*'); |
||
| 417 | } |
||
| 418 | |||
| 419 | /** |
||
| 420 | * counts the number of Walls |
||
| 421 | * |
||
| 422 | * @return number of walls in this level |
||
| 423 | */ |
||
| 424 | public int countWalls() { |
||
| 425 | return countCharacter('#'); |
||
| 426 | } |
||
| 427 | |||
| 428 | /** |
||
| 429 | * counts the number of (free) Goals |
||
| 430 | * |
||
| 431 | * @return number of Goals in level |
||
| 432 | */ |
||
| 433 | public int countGoals() { |
||
| 434 | return countCharacter('.') + countCharacter('+') + countCharacter('*'); |
||
| 435 | } |
||
| 436 | |||
| 437 | /** |
||
| 438 | * returns if the element is a crate |
||
| 439 | * |
||
| 440 | * @param top |
||
| 441 | * top position of element |
||
| 442 | * @param left |
||
| 443 | * left position of element |
||
| 444 | * @return true if element is crate false otherwise |
||
| 445 | * @throws ParameterOutOfRangeException |
||
| 446 | */ |
||
| 447 | public boolean isCrate(final int top, final int left) throws ParameterOutOfRangeException { |
||
| 448 | return ((getObject(top, left) == "crate") |
||
| 449 | || (getObject(top, left) == "crateOnGoal")); |
||
| 450 | } |
||
| 451 | |||
| 452 | |||
| 453 | /** |
||
| 454 | * returns if the element is a goal |
||
| 455 | * |
||
| 456 | * @param top |
||
| 457 | * top position of element |
||
| 458 | * @param left |
||
| 459 | * left position of element |
||
| 460 | * @return true if element is goal false otherwise |
||
| 461 | * @throws ParameterOutOfRangeException |
||
| 462 | */ |
||
| 463 | public boolean isGoal(final int top, final int left) throws ParameterOutOfRangeException { |
||
| 464 | final String fieldType = getObject(top, left); |
||
| 465 | return (fieldType == "goal"); |
||
| 466 | } |
||
| 467 | |||
| 468 | /** |
||
| 469 | * returns if the element is a wall |
||
| 470 | * |
||
| 471 | * @param top |
||
| 472 | * top position of element |
||
| 473 | * @param left |
||
| 474 | * left position of element |
||
| 475 | * @return true if element is wall false otherwise |
||
| 476 | * @throws ParameterOutOfRangeException |
||
| 477 | */ |
||
| 478 | public boolean isWall(final int top, final int left) throws ParameterOutOfRangeException { |
||
| 479 | final String fieldType = getObject(top, left); |
||
| 480 | return (fieldType == "wall"); |
||
| 481 | } |
||
| 482 | |||
| 483 | /** |
||
| 484 | * returns if the element is a free field |
||
| 485 | * |
||
| 486 | * @param top |
||
| 487 | * top position of element |
||
| 488 | * @param left |
||
| 489 | * left position of element |
||
| 490 | * @return true if element is field, false otherwise |
||
| 491 | * @throws ParameterOutOfRangeException |
||
| 492 | */ |
||
| 493 | public boolean isField(final int top, final int left) throws ParameterOutOfRangeException { |
||
| 494 | final String fieldType = getObject(top, left); |
||
| 495 | return (fieldType == "field"); |
||
| 496 | } |
||
| 497 | |||
| 498 | /** |
||
| 499 | * returns the adjacency list (list of neighbors) for the level map |
||
| 500 | * neighbors are in this case all free fields (i.e. no crates or walls) that are |
||
| 501 | * left, right, top or down another field. |
||
| 502 | * @return adjacencyList as HashMap with String key (format "top,left") |
||
| 503 | * and Integer-Array as value (top = value[0] left = value[1]) |
||
| 504 | * @throws ParameterOutOfRangeException |
||
| 505 | */ |
||
| 506 | private HashMap<String, ArrayList<Point>> getAdjacencyList() throws ParameterOutOfRangeException{ |
||
| 507 | // HashMap to save a point as key and the neighbors it is connected to as value |
||
| 508 | final HashMap<String, ArrayList<Point>> adjacencyList = new HashMap<String, ArrayList<Point>>(); |
||
| 509 | // Fill HashMap |
||
| 510 | for(int top = 0; top < getHeight(); top++) |
||
| 511 | for(int left = 0; left < getWidth(); left++){ |
||
| 512 | // possible positions for neighbors |
||
| 513 | final Point pos = new Point(top, left); |
||
| 514 | final Point leftNeighbor = pos.moveDirection('L'); |
||
| 515 | final Point rightNeighbor = pos.moveDirection('R'); |
||
| 516 | final Point topNeighbor = pos.moveDirection('U'); |
||
| 517 | final Point downNeighbor = pos.moveDirection('D'); |
||
| 518 | // Add all neighbors to adjacency list |
||
| 519 | final ArrayList<Point> neighbors = new ArrayList<Point>(); // temporary list of neighbors |
||
| 520 | // check if the position a neighbor should be is free |
||
| 521 | // and if yes, add this neighbor to the list of neighbors |
||
| 522 | final boolean leftFree = isFree(leftNeighbor); |
||
| 523 | final boolean rightFree = isFree(rightNeighbor); |
||
| 524 | final boolean topFree = isFree(topNeighbor); |
||
| 525 | final boolean bottomFree = isFree(downNeighbor); |
||
| 526 | if(leftFree) |
||
| 527 | neighbors.add(leftNeighbor); |
||
| 528 | if(rightFree) |
||
| 529 | neighbors.add(rightNeighbor); |
||
| 530 | if(topFree) |
||
| 531 | neighbors.add(topNeighbor); |
||
| 532 | if(bottomFree) |
||
| 533 | neighbors.add(downNeighbor); |
||
| 534 | // add list of neighbors to adjacency list |
||
| 535 | adjacencyList.put(pos.toString(), neighbors); |
||
| 536 | } |
||
| 537 | return adjacencyList; |
||
| 538 | } |
||
| 539 | |||
| 540 | /** |
||
| 541 | * return the breadth-first tree for the level and a given start position |
||
| 542 | * the breadfirst tree contains all points of the level |
||
| 543 | * the path from the given start point to every other point is |
||
| 544 | * the shortest possible |
||
| 545 | * @param startTop start position top |
||
| 546 | * @param startLeft start position left |
||
| 547 | * @return BfsTree for given start position |
||
| 548 | * @throws ParameterOutOfRangeException |
||
| 549 | */ |
||
| 550 | private HashMap<String, Point> getBfsTree(final int startTop, final int startLeft) throws ParameterOutOfRangeException{ |
||
| 551 | // load Adjacency List |
||
| 552 | final HashMap<String, ArrayList<Point>> adjacencyList = getAdjacencyList(); |
||
| 553 | final LinkedList<Point> queue = new LinkedList<Point>(); |
||
| 554 | // HashMap to store every element passed when walking the shortest possible path |
||
| 555 | final HashMap<String, Point> tree = new HashMap<String, Point>(); |
||
| 556 | // ArrayList to store visited nodes |
||
| 557 | final ArrayList<String> visited = new ArrayList<String>(); |
||
| 558 | final Point startPos = new Point(startTop, startLeft); |
||
| 559 | queue.add(startPos); // Add start element to queue |
||
| 560 | while(!queue.isEmpty()){ |
||
| 561 | final Point act = queue.pop(); // removes element from queue |
||
| 562 | // Iterate through all neighbors of the current element |
||
| 563 | if(adjacencyList.containsKey(act.toString())) |
||
| 564 | for(final Point neighbor : adjacencyList.get(act.toString())) |
||
| 565 | // if the node is not visited yet |
||
| 566 | if(!visited.contains(neighbor.toString())){ |
||
| 567 | // add node to list of visited nodes |
||
| 568 | visited.add(neighbor.toString()); |
||
| 569 | // the predecessor of the neighbor is the currently visited node |
||
| 570 | tree.put(neighbor.toString(), act); |
||
| 571 | // add neighbor to queue to search for its neighbors |
||
| 572 | queue.add(neighbor); |
||
| 573 | } |
||
| 574 | } |
||
| 575 | return tree; |
||
| 576 | } |
||
| 577 | |||
| 578 | /** |
||
| 579 | * returns the shortest possible path from a given start position to a given destination in moves-commands. |
||
| 580 | * A move command is U, R, D or L. The letters represent the directions you have to walk to arrive at the destination. |
||
| 581 | * To compute the path, the method uses a given breadth-first tree. |
||
| 582 | * @param startTop top value of start position |
||
| 583 | * @param startLeft left value of start position |
||
| 584 | * @param destTop top value of destination |
||
| 585 | * @param destLeft left value of destination |
||
| 586 | * @param bfsTree breadth-first tree of the graph on which the path shall be found. |
||
| 587 | * @return LinkedList of Characters representing directions in which an object has to be moved to arrive the given destination |
||
| 588 | */ |
||
| 589 | private LinkedList<Character> getPath(final int startTop, final int startLeft, final int destTop, final int destLeft, final HashMap<String, Point> bfsTree){ |
||
| 590 | final Point dest = new Point(destTop, destLeft); // destination as point |
||
| 591 | final LinkedList<Character> path = new LinkedList<Character>(); |
||
| 592 | // if there is no path or the start and destination are equal, no steps can be made. |
||
| 593 | // Hence an empty list is returned |
||
| 594 | if(((startTop == destTop) && (startLeft == destLeft)) || (!bfsTree.containsKey(dest.toString()))) |
||
| 595 | return new LinkedList<Character>(); |
||
| 596 | else{ // there is a path |
||
| 597 | final Point pred = bfsTree.get(dest.toString()); // predecessor of destination |
||
| 598 | // recursively call the method with the predecessor as new destination |
||
| 599 | // until start and destination are equal and the whole path is found |
||
| 600 | // and the direction-chars can be added to the list |
||
| 601 | path.addAll(getPath(startTop, startLeft, pred.top, pred.left, bfsTree)); |
||
| 602 | // get char for the position |
||
| 603 | if(pred.top - destTop == 1) |
||
| 604 | path.add('U'); |
||
| 605 | else if(pred.top - destTop == -1) |
||
| 606 | path.add('D'); |
||
| 607 | else if(pred.left - destLeft == 1) |
||
| 608 | path.add('L'); |
||
| 609 | else if(pred.left - destLeft == -1) |
||
| 610 | path.add('R'); |
||
| 611 | } |
||
| 612 | return path; |
||
| 613 | } |
||
| 614 | |||
| 615 | /** |
||
| 616 | * returns the shortest possible path from a given start position to a given destination |
||
| 617 | * @param startTop top position of start |
||
| 618 | * @param startLeft left position of start |
||
| 619 | * @param destTop top position of destination |
||
| 620 | * @param destLeft left position of destination |
||
| 621 | * @return an LinkedList of Direction-Chars (U, R, D, L) you have to carry out to reach dest |
||
| 622 | * @throws ParameterOutOfRangeException |
||
| 623 | */ |
||
| 624 | public LinkedList<Character> getShortestPath(final int startTop, final int startLeft, final int destTop, final int destLeft) throws ParameterOutOfRangeException{ |
||
| 625 | // get Bfs Tree for given start position |
||
| 626 | final HashMap<String, Point> bfsTree = getBfsTree(startTop, startLeft); |
||
| 627 | // call and return getPath method |
||
| 628 | return getPath(startTop, startLeft, destTop, destLeft, bfsTree); |
||
| 629 | } |
||
| 630 | |||
| 631 | /** |
||
| 632 | * Checks if level is solved |
||
| 633 | * |
||
| 634 | * @return true if all crates are on a goal (e.g. the number of crates is 0) |
||
| 635 | * false otherwise |
||
| 636 | */ |
||
| 637 | public boolean isSolved() { |
||
| 638 | if (countCrates() == countCratesOnGoal()) |
||
| 639 | return true; |
||
| 640 | return false; |
||
| 641 | } |
||
| 642 | |||
| 643 | /** |
||
| 644 | * checks if the level is completely bordered by walls and |
||
| 645 | * no element is outside the walls |
||
| 646 | * @return true if every gameobject is inside a wall bounding, |
||
| 647 | * false otherwise |
||
| 648 | * @throws ParameterOutOfRangeException |
||
| 649 | */ |
||
| 650 | public boolean checkWallBounding() throws ParameterOutOfRangeException{ |
||
| 651 | // for every object in the game it has to be checked |
||
| 652 | // that no path to one of the outer fields exists |
||
| 653 | for(int i=1; i<gameMap.length-1; i++) |
||
| 654 | for(int j=1; j<gameMap[0].length-1; j++) |
||
| 655 | if(!isWall(i,j) && !isField(i, j)){ |
||
| 656 | // iterate through top and down border fields |
||
| 657 | for(int col = 0; col<gameMap[0].length-1; col++){ |
||
| 658 | // no object except a wall may be on one of the outer border fields |
||
| 659 | if((!isWall(0, col) && !isField(0, col)) || |
||
| 660 | (!isWall(getHeight()-1, col) && !isField(getHeight()-1, col))) |
||
| 661 | return false; |
||
| 662 | // check if a path exists to any position |
||
| 663 | // in the first and last row |
||
| 664 | if((!getShortestPath(i, j, 0, col).isEmpty()) || // top row |
||
| 665 | (!getShortestPath(i, j, getHeight()-1, col).isEmpty())) // down row |
||
| 666 | return false; |
||
| 667 | } |
||
| 668 | // iterate through right and left border fields |
||
| 669 | for(int row = 0; row<gameMap.length-1; row++){ |
||
| 670 | // no object except a wall may be on one of the outer border fields |
||
| 671 | if((!isWall(row, 0) && !isField(row, 0)) || |
||
| 672 | (!isWall(row, getWidth()-1) && !isField(row, getWidth()-1))) |
||
| 673 | return false; |
||
| 674 | // check if a path exists to any position |
||
| 675 | // in the left and right border-column |
||
| 676 | if ((!getShortestPath(i, j, row, 0).isEmpty()) || // left column |
||
| 677 | (!getShortestPath(i, j, row , getWidth()-1).isEmpty())) // right column |
||
| 678 | return false; |
||
| 679 | } |
||
| 680 | } |
||
| 681 | return true; |
||
| 682 | } |
||
| 683 | |||
| 684 | /** |
||
| 685 | * returns the String representation of the gameMap |
||
| 686 | * |
||
| 687 | * @return gameMap as String |
||
| 688 | */ |
||
| 689 | @Override |
||
| 690 | public String toString() { |
||
| 691 | final StringBuffer outBuf = new StringBuffer(128); |
||
| 692 | for (int i = 0; i < height; i++) { |
||
| 693 | String line=""; |
||
| 694 | for (int j = 0; j < width; j++) |
||
| 695 | line += gameMap[i][j]; |
||
| 696 | line = chopSpaces(line); |
||
| 697 | outBuf.append(line).append("\n"); |
||
| 698 | } |
||
| 699 | return outBuf.toString(); |
||
| 700 | } |
||
| 701 | |||
| 702 | /** |
||
| 703 | * getter-method for gameMap |
||
| 704 | * |
||
| 705 | * @return the gameMap |
||
| 706 | */ |
||
| 707 | public char[][] getMap() { |
||
| 708 | return gameMap; |
||
| 709 | } |
||
| 710 | |||
| 711 | /** |
||
| 712 | * @return steps |
||
| 713 | */ |
||
| 714 | public int getSteps() { |
||
| 715 | return steps; |
||
| 716 | } |
||
| 717 | |||
| 718 | protected void setSteps(final int i) { |
||
| 719 | steps = i; |
||
| 720 | } |
||
| 721 | |||
| 722 | protected void incSteps() { |
||
| 723 | steps++; |
||
| 724 | } |
||
| 725 | |||
| 726 | /** |
||
| 727 | * @return steps |
||
| 728 | */ |
||
| 729 | public int getHistorySteps() { |
||
| 730 | return history.getSteps(); |
||
| 731 | } |
||
| 732 | |||
| 733 | public void setHistorySteps(final int i){ |
||
| 734 | history.setSteps(i); |
||
| 735 | } |
||
| 736 | |||
| 737 | /** |
||
| 738 | * resets the level to the start position saved in the history |
||
| 739 | */ |
||
| 740 | protected void reset(){ |
||
| 741 | final char[][] historyMap = history.getStart(); |
||
| 742 | gameMap = historyMap; |
||
| 743 | history.setSteps(0); // resets the step counter |
||
| 744 | } |
||
| 745 | /** |
||
| 746 | * add move to History |
||
| 747 | */ |
||
| 748 | protected void addMove(final char direction) { |
||
| 749 | history.addMove(direction); |
||
| 750 | } |
||
| 751 | |||
| 752 | /** |
||
| 753 | * sets the history-entries to the given value |
||
| 754 | * @param listOfDirections LinkedList of directions |
||
| 755 | */ |
||
| 756 | protected void setHistory(final LinkedList<Character> listOfDirections){ |
||
| 757 | history.setHistory(listOfDirections); |
||
| 758 | } |
||
| 759 | /** |
||
| 760 | * resets the History and saves the current state of the level as start |
||
| 761 | * |
||
| 762 | */ |
||
| 763 | protected void setNewHistoryStart(){ |
||
| 764 | history.reset(); |
||
| 765 | history.setStart(gameMap); |
||
| 766 | } |
||
| 767 | |||
| 768 | /** |
||
| 769 | * returns the history start |
||
| 770 | * @return history start as String |
||
| 771 | * |
||
| 772 | */ |
||
| 773 | protected String getHistoryStart(){ |
||
| 774 | final char[][] start = history.getStart(); |
||
| 775 | final StringBuffer outBuf = new StringBuffer(128); |
||
| 776 | for (int i = 0; i < start.length; i++) { |
||
| 777 | String line=""; |
||
| 778 | for (int j = 0; j < start[0].length; j++) |
||
| 779 | line += start[i][j]; |
||
| 780 | line = chopSpaces(line); |
||
| 781 | outBuf.append(line).append("\n"); |
||
| 782 | } |
||
| 783 | return outBuf.toString(); |
||
| 784 | } |
||
| 785 | |||
| 786 | /** |
||
| 787 | * get the move History as LinkedList |
||
| 788 | * @return moveHistory |
||
| 789 | */ |
||
| 790 | protected LinkedList<Character> getMoveHistory(){ |
||
| 791 | return history.getMoveHistory(); |
||
| 792 | } |
||
| 793 | } |