Subversion Repositories sokoban

Rev

Blame | Last modification | View Log | RSS feed

  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. }
  794.