---

Map Class Reference

This class represents a sokoban map. More...

#include <map.h>

List of all members.

Public Types
enum	Piece {   KEEPER = 0, KEEPER_ON_GOAL = 1, GEM = 2, GEM_ON_GOAL = 3,   EMPTY = 4, GOAL = 5, WALL = 6, OUTSIDE = 7 }
enum	MapValidity {   IS_VALID, NO_KEEPER, TOO_MANY_KEEPERS, NO_GEMS,   MORE_GEMS_THAN_GOALS, MORE_GOALS_THAN_GEMS, MAP_LEAKS, MAP_SOLVED,   MAP_INVALID }
Public Methods
	Map (int width, int height, std::vector< int > const &pieces)
	Map (QDataStream &stream)
	Map (QStringList &lines)
	Map (CompressedMap const &compressed_map)
void	writeToStream (QDataStream &stream)
int	width () const
int	height () const
std::vector< int > const &	pieces () const
bool	isValid () const
MapValidity	validity () const
bool	isSolved () const
int	numberOfEmptyGoals () const
int	getIndex (QPoint position) const
QPoint	getPoint (int index) const
bool	isValidPosition (QPoint position) const
bool	isValidIndex (int index) const
Piece	getPiece (QPoint position) const
Piece	getPiece (int index) const
void	setPiece (QPoint position, int piece)
void	setPiece (int index, int piece)
void	mirrorVertically ()
void	mirrorHorizontally ()
void	rotateLeft ()
void	rotateRight ()
bool	isCrossed (QPoint position) const
bool	isCrossed (int index) const
void	uncrossAll ()
bool	isReachable (QPoint position) const
bool	isReachable (int index) const
void	calcReachable () const
void	calcReachable (QPoint position) const
void	calcReachable (int index) const
void	clearReachable () const
bool	isDeadlock (QPoint position) const
bool	isDeadlock (int index) const
void	clearDeadlocks () const
void	calcDeadlocks () const
void	crossDeadlocks () const
QPoint	keeper () const
void	setKeeper (QPoint position)
void	setKeeper (int index)
void	setKeeperToFirstReachable ()
void	moveGem (QPoint from, QPoint to)
void	moveGem (int from, int to)
bool	containsKeeper (QPoint position) const
bool	containsKeeper (int index) const
bool	containsGem (QPoint position) const
bool	containsGem (int index) const
bool	containsGoal (QPoint position) const
bool	containsGoal (int index) const
bool	canDropKeeper (QPoint position) const
bool	canDropKeeper (int index) const
bool	canDropGem (QPoint position) const
bool	canDropGem (int index) const
void	doMove (Move const &move, bool retro_mode)
void	doUndoMove (Move const &move, bool retro_mode)
bool	isValidMove (Move const &move, bool retro_mode) const
bool	isValidNonPushMove (Move const &move) const
bool	isValidPushMove (Move const &move, bool retro_mode) const
bool	isValidAtomicPushMove (Move const &move, bool retro_mode) const
Movements	getShortestPath (QPoint from, QPoint to) const
Movements	getShortestPathForGem (QPoint from, QPoint to, bool retro) const
std::vector< int >	getDistanceMap (QPoint const &position, int unsolvable, bool retro_mode=false) const
std::vector< int >	getDistanceMap (int index, int unsolvable, bool retro_mode=false) const
Movements	expandMove (Move const &move, bool retro_mode) const
Movements	expandUndoMove (Move const &move) const
Movements	expandMoves (Movements moves, bool retro_mode) const
Movements	collapseMoves (Movements moves) const
bool	areValidMoves (Movements const &moves) const
bool	areValidSolutionMoves (Movements const &moves, int &number_of_pushes, int &number_of_moves) const
Map	adjustSize () const
Map	fillEdges () const
Map	simplify () const
QString	toText () const
QString	toServerFormat () const
Static Public Methods
bool	isMapLine (QString const &line)
bool	pieceContainsKeeper (int piece)
bool	pieceContainsGem (int piece)
bool	pieceContainsGoal (int piece)
bool	canDropKeeperOnPiece (int piece)
bool	canDropGemOnPiece (int piece)
Private Types
enum	PieceFlags { CROSSED = 8, REACHABLE = 16, DEADLOCK = 32 }
enum	Mask {   PIECE = 7, ALL = PIECE + CROSSED + REACHABLE + DEADLOCK, CLEAR_PIECE = ALL - PIECE, CLEAR_CROSSED = ALL - CROSSED,   CLEAR_REACHABLE = ALL - REACHABLE, CLEAR_DEADLOCK = ALL - DEADLOCK }
Private Methods
bool	areValidSolutionMovesImpl (Movements const &moves, bool &is_solution, int &number_of_pushes, int &number_of_moves) const
void	calcTrivialDeadlocks () const
bool	isPossibleDeadlock (int index) const
void	setupOffsets ()
void	setupNumberOfEmptyGoals () const
void	setupKeeperAndEmptyGoals ()
void	createOutsidePieces ()
void	createOutsidePiecesHelper (int x, int y)
Private Attributes
int	m_width
int	m_height
int	m_size
QPoint	m_keeper
MapValidity	m_validity
int	m_empty_goals
bool	m_deadlocks_valid
bool	m_reachable_valid
bool	m_empty_goals_valid
bool	m_validity_valid
std::vector< int >	m_pieces
int	m_xy_offsets [4]
Static Private Attributes
char const	s_piece_to_text [8]
bool const	s_piece_contains_gem [8]
bool const	s_piece_contains_goal [8]
bool const	s_can_drop_keeper [24]
bool const	s_can_drop_gem [8]
QRegExp	s_map_regexp

---

Detailed Description

This class represents a sokoban map.

Note that there exists two version of most functions. One taking a point (x-, y-values) and one an index (x + y * width()).

Warning:

The height and width of the map must be smaller than 128.

Author:

Ralf Schmelter (ralfs@pc2a.chemie.uni-dortmund.de).

Version:

0.1

---

Member Enumeration Documentation

enum Map::MapValidity

Defines some reasons, why a map is not valid. Enumeration values: IS_VALID   The map is valid. NO_KEEPER   The map contains no keeper. TOO_MANY_KEEPERS   The map contains more than one keeper. NO_GEMS   The map contains no gems. MORE_GEMS_THAN_GOALS   The map contains more gems than goals. MORE_GOALS_THAN_GEMS   The map contains more goals than gems. MAP_LEAKS   The map is not closed (an outside field next to a non wall field). MAP_SOLVED   The map is already solved. MAP_INVALID   Any other reason why the map is invalid.

enum Map::Mask [private]

Used to map out the different informations on the fields. Enumeration values: PIECE   Mask out the piece. ALL   All attributes. CLEAR_PIECE   Clear all pieces. CLEAR_CROSSED   Clear crossed. CLEAR_REACHABLE   Clear reachable. CLEAR_DEADLOCK   Clear deadlocks.

enum Map::Piece

Here we define the pieces of a field. Enumeration values: KEEPER   A keeper on an empty field. KEEPER_ON_GOAL   A keeper on a goal field. GEM   A gem on an empty field. GEM_ON_GOAL   A gem on an empty field. EMPTY   An empty field. GOAL   A goal field. WALL   A wall field. OUTSIDE   An outside field.

enum Map::PieceFlags [private]

Defines some additional flags for a piece. Enumeration values: CROSSED   The field is crossed. REACHABLE   The field is reachable. DEADLOCK   The field is a deadlock field.

---

Constructor & Destructor Documentation

Map::Map (  int width, int height, std::vector< int > const & pieces )

Creates a new map. Parameters: width   The width of the map. height   The height of the map. pieces   A vector containing the pieces (a combination of FieldContent flags).

Map::Map (  QDataStream & stream )

Constructs a map from a data stream. Parameters: stream   The stream to use.

Map::Map (  QStringList & lines )

Constructs the map from a list of lines in xsb format. The constructor removes all lines in the string list, which were before the actual map and the lines of the actual map itself. Be sure to call isValid() afterwards. Parameters: lines   The list with the lines.

Map::Map (  CompressedMap const & compressed_map )

Constructs a map from a compressed map. Parameters: compressed_map   The compressed map.

---

Member Function Documentation

Map Map::adjustSize (  )  const

Return a new map, which has the minimum possible size of the current map.

bool Map::areValidMoves (  Movements const & moves )  const

Returns true, if the given moves are valid starting from this map. Note that the moves must be atomic! Parameters: moves   The moves to check.

bool Map::areValidSolutionMoves (  Movements const & moves, int & number_of_pushes, int & number_of_moves )  const

Returns true, if the given moves are valid starting from this map and solve this map. Note that the moves must be atomic! Parameters: moves   The moves to check. number_of_pushes   Here we store the number of pushes. number_of_moves   Here we store the number of moves.

bool Map::areValidSolutionMovesImpl (  Movements const & moves, bool & is_solution, int & number_of_pushes, int & number_of_moves )  const [private]

Implementation of areValidSolutionMoves(). Also used in areValidMoves(). Note that the moves must be atomic! Parameters: moves   The moves to check. is_solution   Set to true, if the moves are a solution. number_of_pushes   Here we store the number of pushes. number_of_moves   Here we store the number of moves.

void Map::calcDeadlocks (  )  const

Calculates all deadlock fields.

void Map::calcReachable (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

void Map::calcReachable (  QPoint position )  const

Calculates all reachable fields if the keeper stands on the specified position. Parameters: position   The position of the keeper.

void Map::calcReachable (  )  const

Calculates all reachable fields. Note that the position of the keeper is important.

void Map::calcTrivialDeadlocks (  )  const [private]

Calculates all trivial deadlocks (positions in which a stone can not be moved).

bool Map::canDropGem (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::canDropGem (  QPoint position )  const

Returns true, if a gem can be dropped to the given position. Parameters: position   The position to test.

bool Map::canDropGemOnPiece (  int piece )  [static]

Returns true, if a gem can be dropped on the given piece. A field with the keeper is also considered a valid gem drop field. Parameters: piece   The piece to test.

bool Map::canDropKeeper (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::canDropKeeper (  QPoint position )  const

Returns true, if a keeper can be dropped on the field. Note that a field with a keeper is also considered a valid keeper drop field. Parameters: position   The field to test.

bool Map::canDropKeeperOnPiece (  int piece )  [static]

Returns true, if the keeper can be dropped in the piece. Parameters: piece   The piece to test.

void Map::clearDeadlocks (  )  const

Clears all deadlocks.

void Map::clearReachable (  )  const

Clears all reachable fields.

Movements Map::collapseMoves (  Movements moves )  const

Returns the movements given in a collapsed form. This means simple keeper moves are combined und ston pushes in one direction also. Note the we don't check, if the moves are valid, so it may be the best to call expandMoves first. Parameters: moves   The moves to collapse (must be all simple moves).

bool Map::containsGem (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::containsGem (  QPoint position )  const

Returns true, if the piece at the given position contains a gem. Parameters: position   The position to test.

bool Map::containsGoal (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::containsGoal (  QPoint position )  const

Returns true, if the piece at the given position contains a goal. Parameters: position   The position to test.

bool Map::containsKeeper (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::containsKeeper (  QPoint position )  const

Returns true, if the piece at the given position contains a keeper. Parameters: position   The position to test.

void Map::createOutsidePieces (  )  [private]

Creates the outside pieces.

void Map::createOutsidePiecesHelper (  int x, int y )  [private]

Helper function needed by createOutsidePieces().

void Map::crossDeadlocks (  )  const

Crosses all deadlocks.

void Map::doMove (  Move const & move, bool retro_mode )

Performs the given move. Parameters: move   The move to perform. retro_mode   If true, the move is in retro mode.

void Map::doUndoMove (  Move const & move, bool retro_mode )

Performs the given undo move. An undo move is the reverse of a normal move. Parameters: move   The undo move to perform. retro_mode   If true, the move is in retro mode.

Movements Map::expandMove (  Move const & move, bool retro_mode )  const

Returns a sequence of atomic moves for a given move. The move must be legal. Parameters: move   The move to make atomic. retro_mode   If true, the move is in retro mode.

Movements Map::expandMoves (  Movements moves, bool retro_mode )  const

Returns the movements given in an explicit form (meaning all moves are simple moves). If the moves are illegal starting from the current map, an empty moves list ist returned. Parameters: moves   The moves to expand. retro_mode   If true, the move is in retro mode.

Movements Map::expandUndoMove (  Move const & move )  const

Returns a sequence of atomic moves for a given undo move. The undo move must be legal. Parameters: move   The move undo to make atomic.

Map Map::fillEdges (  )  const

Returns a version of the map with filled edges.

std::vector<int> Map::getDistanceMap (  int index, int unsolvable, bool retro_mode = false )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

std::vector<int> Map::getDistanceMap (  QPoint const & position, int unsolvable, bool retro_mode = false )  const

Returns the distance map for a given field. The value of the returned map at [d + 4 * gem_pos] is the number of moves required, to move a gem at position gem_pos to the given field, when the keeper stands left (d = 0), right (d = 1), above (d = 2) or down (d = 3) the gem. Parameters: position   The position of the field to reach. max_distance   The distance to indicate unreachable positions. retro_mode   If true, the move is in retro mode.

int Map::getIndex (  QPoint position )  const

Returns the index for the given position. Parameters: position   The position for which to create the index.

Piece Map::getPiece (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Piece Map::getPiece (  QPoint position )  const

Returns the piece at the given position. Parameters: position   The position of the piece.

QPoint Map::getPoint (  int index )  const

Returns the point for the given index. Parameters: index.

Movements Map::getShortestPath (  QPoint from, QPoint to )  const

Gets the shortes path for a keeper (if it exists) between two points. If no path exists, we return Movements with no moves. Parameters: from   The start point. to   The end point.

Movements Map::getShortestPathForGem (  QPoint from, QPoint to, bool retro )  const

Gets the shortes path (if it exists) for moving a gem from one position to another. If no path exists, we return Movements with no moves. Note that the position of the keeper matters. Parameters: from   The gem start point. to   The gem end point. retro   If true, we are in retro mode.

int Map::height (  )  const

Returns the height of the map.

bool Map::isCrossed (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::isCrossed (  QPoint position )  const

Returns true, if the piece at the given position is crossed.

bool Map::isDeadlock (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::isDeadlock (  QPoint position )  const

Returns true, if the given field is a deadlock field. Parameters: position   The position of the field to test.

bool Map::isMapLine (  QString const & line )  [static]

Returns true, if the given string is a map line. Parameters: line   The string of the line.

bool Map::isPossibleDeadlock (  int index )  const [private]

Returns true, if the field is a possible deadlock field. This means it must be EMPTY, GEM or KEEPER. Parameters: index   The field to test.

bool Map::isReachable (  int index )  const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Map::isReachable (  QPoint position )  const

Returns true, if the field is reachable. Note that you should have called calcReachable() before.

bool Map::isSolved (  )  const

Returns true, if the map is solved.

bool Map::isValid (  )  const

Returns true, if the map is valid.

bool Map::isValidAtomicPushMove (  Move const & move, bool retro_mode )  const

Returns true, if the given stone push move is valid (meaning the stone can be pushed). Parameters: move   The move to test. retro_mode   If true, the move is in retro mode.

bool Map::isValidIndex (  int index )  const

Returns true, if the index is valid. Parameters: index   The index to test.

bool Map::isValidMove (  Move const & move, bool retro_mode )  const

Returns true, if the given move is valid. Parameters: move   The move to test. retro_mode   If true, the move is in retro mode.

bool Map::isValidNonPushMove (  Move const & move )  const

Returns true, if the given (not push move) is valid. Parameters: move   The move to test.

bool Map::isValidPosition (  QPoint position )  const

Returns true, if the given position is valid (corresponds to a field of the map). Parameters: position   The position to test.

bool Map::isValidPushMove (  Move const & move, bool retro_mode )  const

Returns true, if the given stone push move is valid (meaning the stone can be pushed). Parameters: move   The move to test. retro_mode   If true, the move is in retro mode.

QPoint Map::keeper (  )  const

Returns the position of the keeper.

void Map::mirrorHorizontally (  )

Mirrors the map horizontally.

void Map::mirrorVertically (  )

Mirrors the map vertically.

void Map::moveGem (  int from, int to )

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

void Map::moveGem (  QPoint from, QPoint to )

Moves a gem from one to another position. Parameters: from   The original position of the gem. to   The new position of the gem (may be equal to from).

int Map::numberOfEmptyGoals (  )  const

Returns the number of goals without gems.

bool Map::pieceContainsGem (  int piece )  [static]

Returns true, if the piece contains a gem. Parameters: piece   The piece to test.

bool Map::pieceContainsGoal (  int piece )  [static]

Returns true, of the piece contains a goal. Parameters: piece   The piece to test.

bool Map::pieceContainsKeeper (  int piece )  [static]

Returns true, if the piece contains a keeper. Parameters: piece   The piece to test.

std::vector<int> const& Map::pieces (  )  const

Returns a vector with the raw piece codes.

void Map::rotateLeft (  )

Rotates the map left by 90 deg. This is implemented by 3 times rotateRight().

void Map::rotateRight (  )

Rotates the map right by 90 deg.

void Map::setKeeper (  int index )

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

void Map::setKeeper (  QPoint position )

Sets the position of the keeper. Removes the keeper from the old position (if it still was at the old position). Note that the keeper is 'beamed'. Parameters: position   The new position of the keeper.

void Map::setKeeperToFirstReachable (  )

Sets the keeper to the first reachable field.

void Map::setPiece (  int index, int piece )

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

void Map::setPiece (  QPoint position, int piece )

Sets the piece at the given position. If you want to set the keeper, you better use setKeeper(). Parameters: position   The position. piece   The Piece to set.

void Map::setupKeeperAndEmptyGoals (  )  [private]

Finds and set the keeper and the number of empty goals.

void Map::setupNumberOfEmptyGoals (  )  const [private]

Sets up the numer of empty goals.

void Map::setupOffsets (  )  [private]

Sets up the offsets.

Map Map::simplify (  )  const

Returns a simplified version of the map. In the simplified version we deleted as much as possible walls and gems, without changing the solution of the map.

QString Map::toServerFormat (  )  const

Returns a representation of the map which is understandable by the highscore server.

QString Map::toText (  )  const

Returns a human readable representation of the map in xsokoban format.

void Map::uncrossAll (  )

Clears all crossed fields.

MapValidity Map::validity (  )  const

Returns the validity of the map. You should call this after creation of the map, when you can not be sure if the map is valid.

int Map::width (  )  const

Returns the width of the map.

void Map::writeToStream (  QDataStream & stream )

Writes the map to a data stream. Parameters: stream   The stream to use.

---

Member Data Documentation

bool Map::m_deadlocks_valid [private]

If true, we have already calculated the deadlocks.

int Map::m_empty_goals [private]

The number of empty goals.

bool Map::m_empty_goals_valid [private]

If true, the numer of empty goals is valid.

int Map::m_height [private]

The height of the map.

QPoint Map::m_keeper [private]

Here we store the position of the keeper.

std::vector<int> Map::m_pieces [private]

Here we store the pieces and additional information of the fields.

bool Map::m_reachable_valid [private]

If true, the reachable fields are up to date.

int Map::m_size [private]

This is m_width * m_height.

MapValidity Map::m_validity [private]

The validity of the map.

bool Map::m_validity_valid [private]

If true, the validity is valid :).

int Map::m_width [private]

The width of the map.

int Map::m_xy_offsets[4] [private]

Here we store the offset to go one in x- or y-direction.

bool const Map::s_can_drop_gem[8] [static, private]

Used to determine, if we can drop a gem on the piece.

bool const Map::s_can_drop_keeper[24] [static, private]

Used to determine, if we can drop the keeper on the piece.

QRegExp Map::s_map_regexp [static, private]

The regexp used to identify map lines.

bool const Map::s_piece_contains_gem[8] [static, private]

Used to determine, if a piece contains a gem.

bool const Map::s_piece_contains_goal[8] [static, private]

Used to determine, if a piece contains a goal.

char const Map::s_piece_to_text[8] [static, private]

Used to convert compressed piece values to characters used by xsokoban.

---

The documentation for this class was generated from the following file:

• map.h

---