---

map.h

/*
 *   EasySok --- A(nother) sokoban game for KDE.
 *
 *   Copyright (C) 2001 by Ralf Schmelter (ralfs@pc2a.chemie.uni-dortmund.de).
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License version 2 as
 *   published by the Free Software Foundation.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */


#ifndef EASYSOK_MAP_INC_GUARD_H
#define EASYSOK_MAP_INC_GUARD_H


#include <vector.h>

#include <qglobal.h>
#include <qpoint.h>
#include <qregexp.h>
#include <qstring.h>

#include "movements.h"


class CompressedMap;
class Move;
class QDataStream;
class QStringList;




class Map
{

public:


    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
    };


    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 bool isMapLine(QString const & line);


    static bool pieceContainsKeeper(int piece);


    static bool pieceContainsGem(int piece);


    static  bool pieceContainsGoal(int piece);


    static bool canDropKeeperOnPiece(int piece);


    static bool canDropGemOnPiece(int piece);


private:

    bool areValidSolutionMovesImpl(Movements const & moves, bool & is_solution,
                                   int & number_of_pushes, int & number_of_moves) const;


    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
    };


    void calcTrivialDeadlocks() const;


    bool isPossibleDeadlock(int index) const;


    void setupOffsets();


    void setupNumberOfEmptyGoals() const;


    void setupKeeperAndEmptyGoals();


    void createOutsidePieces();


    void createOutsidePiecesHelper(int x, int y);


    int m_width;


    int m_height;


    int m_size;


    QPoint m_keeper;


    mutable MapValidity m_validity;


    mutable int m_empty_goals;


    mutable bool m_deadlocks_valid;


    mutable bool m_reachable_valid;


    mutable bool m_empty_goals_valid;


    mutable bool m_validity_valid;


    mutable std::vector<int> m_pieces;


    int m_xy_offsets[4];


    static char const s_piece_to_text[8];


    static bool const s_piece_contains_gem[8];


    static bool const s_piece_contains_goal[8];


    static bool const s_can_drop_keeper[24];


    static bool const s_can_drop_gem[8];


    static QRegExp s_map_regexp;
};


#endif

---