package gdi1sokoban.game;
import gdi1sokoban.exceptions.ParameterOutOfRangeException;
import gdi1sokoban.exceptions.ParseException;
import gdi1sokoban.globals.Point;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.net.URISyntaxException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
/**
* GameLevel class
*
* Holds level information and supplies functions
* for manipulating objects
*/
public class GameLevel {
private char[][] gameMap = new char[0][0]; // array to save game-field
private int height = 0; // level-height in fields
private int width = 0; // level-width in fields
private int steps = 0; // completed valid steps
// HashMap to store the meaning of the chars
private final GameLevelHistory history = new GameLevelHistory();
/**
* Reads a File and parses the level
*
* @param lvl
* Levelfile to read
* @throws IOException
*/
init(lvl);
}
/**
* Reads a filename, opens the file and parses the level
*
* @param fileName
* fileName of the file the level is saved in
* @throws URISyntaxException
* @throws IOException
*/
fileName).toURI());
init(lvl);
}
/**
* Reads a File and parses the level
*
* @param lvl
* Levelfile to read
* @throws IOException
*/
fillCharRepresentation();
parse(lvl);
history.setStart(gameMap); // set history start
}
/**
* fills the HashMap of chars and their objectnames
*
*/
private void fillCharRepresentation() {
charRepresentation.put('@', "player");
charRepresentation.put(' ', "field");
charRepresentation.put('#', "wall");
charRepresentation.put('$', "crate");
charRepresentation.put('.', "goal");
charRepresentation.put('*', "crateOnGoal");
charRepresentation.put('+', "playerOnGoal");
}
/**
* returns the height of the level
*
* @return level-height (in fields)
*/
public int getHeight() {
return height;
}
/**
* returns the width of the level
*
* @return level-width (in fields)
*/
public int getWidth() {
return width;
}
/**
* returns the object which is placed on the given field
*
* @param top
* top-pos of field
* @param left
* left-pos of field
* @return Name of object on this field
* @throws ParameterOutOfRangeException
*/
public String getObject
(final int top,
final int left
) throws ParameterOutOfRangeException
{
if ((top < 0) || (top >= height) || (left < 0) || (left >= width))
throw new ParameterOutOfRangeException("Koordinaten ausserhalb des Spielfelds");
return charRepresentation.get(gameMap[top][left]);
}
/**
* returns the current position of the Player
* @return an Integer Array containing the position of the player (top, left)
* @throws ParameterOutOfRangeException
*/
public Point getPlayerPos
() throws ParameterOutOfRangeException
{
for (int top = 0; top < gameMap.length; top++)
for (int left = 0; left < gameMap[0].length; left++)
if ((getObject(top, left) == "player")
|| (getObject(top, left) == "playerOnGoal"))
return new Point(top, left
);
// no player on field
return new Point(-
1, -
1);
}
/**
* Parses a level from a given Levelfile
*
* @param lvl
* @throws IOException
* @throws URISyntaxException
*/
while ((line = in.readLine()) != null) // read every line
levelCode.append(line).append("\n");
in.close();
// parse level code
parseString(levelCode.toString());
}
/**
* Parses a level file from a string
* @param lvlString
*/
final String[] levelLines = lvlString.
split("\n");
height = 0;
width = 0;
for(int i = 0; i < levelLines.length; i++){
//cut unneccessary spaces from right
if (chopSpaces(line).isEmpty()) { // check if this line, which only exists of spaces, can be removed
boolean canChop = true;
for (int k = i+1; k < levelLines.length; k++) { // check if there are more lines with level code
if (! chopSpaces(levelLines[k]).isEmpty())
canChop = false; // there exists a line with level code, so don't chop this line
}
if (canChop)
line = ""; // remove line from level code
}
// get maximum width
if (width < line.length())
width = line.length();
// Add line to ArrayList of lines if it is not empty
if(line.length() > 0){
lines.add(line);
// the height is the number of lines
height++;
}
}
// Set gamemap to right height and size
gameMap = new char[height][width];
// copy characters into of gameMap-fields
for (int i = 0; i < height; i++) {
// Fill all fields with blanks (empty fields)
// copy all characters of this line into the current row of gameMap
System.
arraycopy(lines.
get(i
).
toCharArray(),
0, gameMap
[i
],
0,
lines.get(i).length());
}
// check level syntax
if (! checkSyntax())
throw new ParseException("Fehler: Leveldatei ist syntaktisch nicht korrekt!");
}
/**
* Checks the Level-Array for syntactical correctness
*
* @return true when syntax is correct else false
*/
private boolean checkSyntax() {
try {
return ( (countCrates() > 0) && (countGoals() == countCrates()) && (countPlayer() == 1) && (containsOnlyAllowedChars()) && (checkWallBounding()) );
} catch (ParameterOutOfRangeException e) {
System.
err.
println("Interner Fehler: Fehler beim Prüfen der Levelsyntax!");
return false;
}
}
/**
* removes all tailing spaces from a given string
* @param s the string
* @return the string s without tailing spaces
*/
while(s.endsWith(" "))
s = s.substring(0, s.length() - 1);
return s;
}
/**
* helper function to count how many times the given character is in gameMap
*
* @param c
* Character to count
* @return number of given character in GameMap
*/
private int countCharacter(final char c) {
int counter = 0;
for (final char[] rows : gameMap)
for (final char element : rows)
if (element == c)
counter++;
return counter;
}
/**
* checks if the gameMap only consists of chars used in the
* format-description
*
* @return true if all chars are correct, false otherwise
*/
private boolean containsOnlyAllowedChars() {
// check for every element if it is in the list of allowed chars
for (final char[] rows : gameMap)
for (final char element : rows)
// if a element is not in the list the method returns false
if (!charRepresentation.containsKey(element)) {
return false;
}
return true;
}
/**
* checks if an element is in a corner
* @param top top-position of element
* @param left left-position of element
* @return true if element is in a corner, false otherwise
* @throws ParameterOutOfRangeException
*/
private boolean isInCorner(final int top, final int left) throws ParameterOutOfRangeException{
final boolean isTopLeftCorner = (isWall(top, left-1) && isWall(top-1, left));
final boolean isTopRightCorner = (isWall(top, left+1) && isWall(top-1, left));
final boolean isDownLeftCorner = (isWall(top, left-1) && isWall(top+1, left));
final boolean isDownRightCorner = (isWall(top, left+1) && isWall(top+1, left));
return (isTopLeftCorner || isTopRightCorner || isDownLeftCorner || isDownRightCorner);
}
/**
* checks the level for deadlocks
* the level contains a deadlock
* when at least one crate is in a corner
* or four elements (of which at least one is a crate)
* form a square
* @return true if level is in deadlock situation
* false otherwise
* @throws ParameterOutOfRangeException
*/
public boolean hasDeadlock() throws ParameterOutOfRangeException{
// iterate through every element of gameMap
for(int top=0; top<gameMap.length; top++)
for(int left=0; left<gameMap[0].length; left++)
// if element is a crate
if(getObject(top, left) == "crate"){
// there are four possibilities to form a square with the current crate
final boolean square1 = (!isFree(top, left-1) && !isFree(top-1, left) && !isFree(top-1, left-1));
final boolean square2 = (!isFree(top, left+1) && !isFree(top-1, left) && !isFree(top-1, left+1));
final boolean square3 = (!isFree(top, left-1) && !isFree(top+1, left) && !isFree(top+1, left-1));
final boolean square4 = (!isFree(top, left+1) && !isFree(top+1, left) && !isFree(top+1, left+1));
// if a crate is placed in a corner or one of the four possibilities to form a square are true
// the level contains a deadlock and true has to be returned
if(isInCorner(top, left) || square1 || square2 || square3 || square4) // || futureSquare1 && futureSquare2 && futureSquare3 && futureSquare4)
return true;
}
return false;
}
/**
* sets an object to a certain field without changing the type of the field
* (i.e. field is goal or normal field)
*
* @param top
* @param left
* @param object
* @throws ParameterOutOfRangeException
* @TODO difference between normal fields and goal fields (e.g. a Class for
* field or a second HashMap containing goals)
*/
private void setObject
(final int top,
final int left,
final String object
) throws ParameterOutOfRangeException
{
// if the field is a goal (i.e. goal, playerOnGoal, cateOnGoal) this
// attribute has to be saved and reassigned to the new field
final String oldObj = getObject
(top, left
);
// Hashmaps to store the key-value pair of object's old name and
// object's new name
// if this field is a goal all characters in the Map have to be replaced
// by their equivalent standing on a Goal (e.g. player => playerOnGoal)
if ((oldObj == "goal") || (oldObj == "crateOnGoal")
|| (oldObj == "playerOnGoal")) {
newObjNames.put("field", "goal");
newObjNames.put("player", "playerOnGoal");
newObjNames.put("crate", "crateOnGoal");
newObjNames.put("goal", "goal");
newObjNames.put("playerOnGoal", "playerOnGoal");
newObjNames.put("crateOnGoal", "crateOnGoal");
} else {
newObjNames.put("goal", "field");
newObjNames.put("playerOnGoal", "player");
newObjNames.put("crateOnGoal", "crate");
newObjNames.put("field", "field");
newObjNames.put("player", "player");
newObjNames.put("crate", "crate");
}
for (final char possibleChar : charRepresentation.keySet())
if (charRepresentation.get(possibleChar) == newObjNames.get(object))
gameMap[top][left] = possibleChar;
}
/**
* checks if the given field is free (i.e. goal or empty field)
* @param top
* @param left
* @return true if field is free, else otherwise
* @throws ParameterOutOfRangeException
*/
private boolean isFree(final int top, final int left) throws ParameterOutOfRangeException{
if((top < 0) || (left < 0) || (top >= getHeight()) || (left >= getWidth()))
return false;
return ((getObject(top, left) == "field")
|| (getObject(top, left) == "goal")
|| (getObject(top, left) == "player")
|| (getObject(top, left) == "playerOnGoal") );
}
/**
* checks if the field on the given point is free
* @param p point containing the position of the field
* @return true if field is free, else otherwise
* @throws ParameterOutOfRangeException
*/
private boolean isFree
(final Point p
) throws ParameterOutOfRangeException
{
return isFree(p.top, p.left);
}
/**
* sets an object of the map to another position if the field is free
*
* @param top
* Top-Pos. of element
* @param left
* Left-Pos. of element
* @param destTop
* new Top-Pos.
* @param destLeft
* new Left-Pos.
* @return true if the field is free and the new position is set, false
* otherwise
* @throws ParameterOutOfRangeException
*/
public boolean setPosition(final int top, final int left, final int destTop, final int destLeft) throws ParameterOutOfRangeException {
final boolean canMove = isFree(destTop, destLeft);
if (canMove) {
setObject(destTop, destLeft, getObject(top, left));
setObject(top, left, "field");
// if an object is moved the history may not contain any entries after that move
history.deleteAfterCurrent();
}
return canMove;
}
/**
* helper function needed to check if the player number is correct
* @return number of players in Level
*/
private int countPlayer() {
return countCharacter('@') + countCharacter('+');
}
/**
* counts the number of Crates (all crates)
*
* @return number of crates in this level
*/
public int countCrates() {
return countCharacter('$') + countCharacter('*');
}
/**
* counts the number of Crates (only crates on goals)
*
* @return number of crates in this level
*/
public int countCratesOnGoal() {
return countCharacter('*');
}
/**
* counts the number of Walls
*
* @return number of walls in this level
*/
public int countWalls() {
return countCharacter('#');
}
/**
* counts the number of (free) Goals
*
* @return number of Goals in level
*/
public int countGoals() {
return countCharacter('.') + countCharacter('+') + countCharacter('*');
}
/**
* returns if the element is a crate
*
* @param top
* top position of element
* @param left
* left position of element
* @return true if element is crate false otherwise
* @throws ParameterOutOfRangeException
*/
public boolean isCrate(final int top, final int left) throws ParameterOutOfRangeException {
return ((getObject(top, left) == "crate")
|| (getObject(top, left) == "crateOnGoal"));
}
/**
* returns if the element is a goal
*
* @param top
* top position of element
* @param left
* left position of element
* @return true if element is goal false otherwise
* @throws ParameterOutOfRangeException
*/
public boolean isGoal(final int top, final int left) throws ParameterOutOfRangeException {
final String fieldType = getObject
(top, left
);
return (fieldType == "goal");
}
/**
* returns if the element is a wall
*
* @param top
* top position of element
* @param left
* left position of element
* @return true if element is wall false otherwise
* @throws ParameterOutOfRangeException
*/
public boolean isWall(final int top, final int left) throws ParameterOutOfRangeException {
final String fieldType = getObject
(top, left
);
return (fieldType == "wall");
}
/**
* returns if the element is a free field
*
* @param top
* top position of element
* @param left
* left position of element
* @return true if element is field, false otherwise
* @throws ParameterOutOfRangeException
*/
public boolean isField(final int top, final int left) throws ParameterOutOfRangeException {
final String fieldType = getObject
(top, left
);
return (fieldType == "field");
}
/**
* returns the adjacency list (list of neighbors) for the level map
* neighbors are in this case all free fields (i.e. no crates or walls) that are
* left, right, top or down another field.
* @return adjacencyList as HashMap with String key (format "top,left")
* and Integer-Array as value (top = value[0] left = value[1])
* @throws ParameterOutOfRangeException
*/
// HashMap to save a point as key and the neighbors it is connected to as value
// Fill HashMap
for(int top = 0; top < getHeight(); top++)
for(int left = 0; left < getWidth(); left++){
// possible positions for neighbors
final Point leftNeighbor = pos.
moveDirection('L');
final Point rightNeighbor = pos.
moveDirection('R');
final Point topNeighbor = pos.
moveDirection('U');
final Point downNeighbor = pos.
moveDirection('D');
// Add all neighbors to adjacency list
// check if the position a neighbor should be is free
// and if yes, add this neighbor to the list of neighbors
final boolean leftFree = isFree(leftNeighbor);
final boolean rightFree = isFree(rightNeighbor);
final boolean topFree = isFree(topNeighbor);
final boolean bottomFree = isFree(downNeighbor);
if(leftFree)
neighbors.add(leftNeighbor);
if(rightFree)
neighbors.add(rightNeighbor);
if(topFree)
neighbors.add(topNeighbor);
if(bottomFree)
neighbors.add(downNeighbor);
// add list of neighbors to adjacency list
adjacencyList.put(pos.toString(), neighbors);
}
return adjacencyList;
}
/**
* return the breadth-first tree for the level and a given start position
* the breadfirst tree contains all points of the level
* the path from the given start point to every other point is
* the shortest possible
* @param startTop start position top
* @param startLeft start position left
* @return BfsTree for given start position
* @throws ParameterOutOfRangeException
*/
private HashMap<String,
Point> getBfsTree
(final int startTop,
final int startLeft
) throws ParameterOutOfRangeException
{
// load Adjacency List
// HashMap to store every element passed when walking the shortest possible path
// ArrayList to store visited nodes
final Point startPos =
new Point(startTop, startLeft
);
queue.add(startPos); // Add start element to queue
while(!queue.isEmpty()){
final Point act = queue.
pop(); // removes element from queue
// Iterate through all neighbors of the current element
if(adjacencyList.containsKey(act.toString()))
for(final Point neighbor : adjacencyList.
get(act.
toString()))
// if the node is not visited yet
if(!visited.contains(neighbor.toString())){
// add node to list of visited nodes
visited.add(neighbor.toString());
// the predecessor of the neighbor is the currently visited node
tree.put(neighbor.toString(), act);
// add neighbor to queue to search for its neighbors
queue.add(neighbor);
}
}
return tree;
}
/**
* returns the shortest possible path from a given start position to a given destination in moves-commands.
* A move command is U, R, D or L. The letters represent the directions you have to walk to arrive at the destination.
* To compute the path, the method uses a given breadth-first tree.
* @param startTop top value of start position
* @param startLeft left value of start position
* @param destTop top value of destination
* @param destLeft left value of destination
* @param bfsTree breadth-first tree of the graph on which the path shall be found.
* @return LinkedList of Characters representing directions in which an object has to be moved to arrive the given destination
*/
final Point dest =
new Point(destTop, destLeft
); // destination as point
// if there is no path or the start and destination are equal, no steps can be made.
// Hence an empty list is returned
if(((startTop == destTop) && (startLeft == destLeft)) || (!bfsTree.containsKey(dest.toString())))
else{ // there is a path
final Point pred = bfsTree.
get(dest.
toString()); // predecessor of destination
// recursively call the method with the predecessor as new destination
// until start and destination are equal and the whole path is found
// and the direction-chars can be added to the list
path.addAll(getPath(startTop, startLeft, pred.top, pred.left, bfsTree));
// get char for the position
if(pred.top - destTop == 1)
path.add('U');
else if(pred.top - destTop == -1)
path.add('D');
else if(pred.left - destLeft == 1)
path.add('L');
else if(pred.left - destLeft == -1)
path.add('R');
}
return path;
}
/**
* returns the shortest possible path from a given start position to a given destination
* @param startTop top position of start
* @param startLeft left position of start
* @param destTop top position of destination
* @param destLeft left position of destination
* @return an LinkedList of Direction-Chars (U, R, D, L) you have to carry out to reach dest
* @throws ParameterOutOfRangeException
*/
public LinkedList<Character> getShortestPath
(final int startTop,
final int startLeft,
final int destTop,
final int destLeft
) throws ParameterOutOfRangeException
{
// get Bfs Tree for given start position
// call and return getPath method
return getPath(startTop, startLeft, destTop, destLeft, bfsTree);
}
/**
* Checks if level is solved
*
* @return true if all crates are on a goal (e.g. the number of crates is 0)
* false otherwise
*/
public boolean isSolved() {
if (countCrates() == countCratesOnGoal())
return true;
return false;
}
/**
* checks if the level is completely bordered by walls and
* no element is outside the walls
* @return true if every gameobject is inside a wall bounding,
* false otherwise
* @throws ParameterOutOfRangeException
*/
public boolean checkWallBounding() throws ParameterOutOfRangeException{
// for every object in the game it has to be checked
// that no path to one of the outer fields exists
for(int i=1; i<gameMap.length-1; i++)
for(int j=1; j<gameMap[0].length-1; j++)
if(!isWall(i,j) && !isField(i, j)){
// iterate through top and down border fields
for(int col = 0; col<gameMap[0].length-1; col++){
// no object except a wall may be on one of the outer border fields
if((!isWall(0, col) && !isField(0, col)) ||
(!isWall(getHeight()-1, col) && !isField(getHeight()-1, col)))
return false;
// check if a path exists to any position
// in the first and last row
if((!getShortestPath(i, j, 0, col).isEmpty()) || // top row
(!getShortestPath(i, j, getHeight()-1, col).isEmpty())) // down row
return false;
}
// iterate through right and left border fields
for(int row = 0; row<gameMap.length-1; row++){
// no object except a wall may be on one of the outer border fields
if((!isWall(row, 0) && !isField(row, 0)) ||
(!isWall(row, getWidth()-1) && !isField(row, getWidth()-1)))
return false;
// check if a path exists to any position
// in the left and right border-column
if ((!getShortestPath(i, j, row, 0).isEmpty()) || // left column
(!getShortestPath(i, j, row , getWidth()-1).isEmpty())) // right column
return false;
}
}
return true;
}
/**
* returns the String representation of the gameMap
*
* @return gameMap as String
*/
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++)
line += gameMap[i][j];
line = chopSpaces(line);
outBuf.append(line).append("\n");
}
return outBuf.toString();
}
/**
* getter-method for gameMap
*
* @return the gameMap
*/
public char[][] getMap() {
return gameMap;
}
/**
* @return steps
*/
public int getSteps() {
return steps;
}
protected void setSteps(final int i) {
steps = i;
}
protected void incSteps() {
steps++;
}
/**
* @return steps
*/
public int getHistorySteps() {
return history.getSteps();
}
public void setHistorySteps(final int i){
history.setSteps(i);
}
/**
* resets the level to the start position saved in the history
*/
protected void reset(){
final char[][] historyMap = history.getStart();
gameMap = historyMap;
history.setSteps(0); // resets the step counter
}
/**
* add move to History
*/
protected void addMove(final char direction) {
history.addMove(direction);
}
/**
* sets the history-entries to the given value
* @param listOfDirections LinkedList of directions
*/
history.setHistory(listOfDirections);
}
/**
* resets the History and saves the current state of the level as start
*
*/
protected void setNewHistoryStart(){
history.reset();
history.setStart(gameMap);
}
/**
* returns the history start
* @return history start as String
*
*/
protected String getHistoryStart
(){
final char[][] start = history.getStart();
for (int i = 0; i < start.length; i++) {
for (int j = 0; j < start[0].length; j++)
line += start[i][j];
line = chopSpaces(line);
outBuf.append(line).append("\n");
}
return outBuf.toString();
}
/**
* get the move History as LinkedList
* @return moveHistory
*/
return history.getMoveHistory();
}
}