bool Map::isLookPossible(const Position& pos)
{
    TilePtr tile = m_tiles[pos];
    if(tile)
        return tile->isLookPossible();
    return true;
}

std::vector<CreaturePtr> Map::getSpectatorsInRangeEx(const Position& centerPos, bool multiFloor, int minXRange, int maxXRange, int minYRange, int maxYRange)
{
    int minZRange = 0;
    int maxZRange = 0;
    std::vector<CreaturePtr> creatures;

    if(multiFloor) {
        minZRange = 0;
        maxZRange = Otc::MAX_Z;
    }

    //TODO: optimize
    //TODO: get creatures from other floors corretly
    //TODO: delivery creatures in distance order

    for(int iz=-minZRange; iz<=maxZRange; ++iz) {
        for(int iy=-minYRange; iy<=maxYRange; ++iy) {
            for(int ix=-minXRange; ix<=maxXRange; ++ix) {
                TilePtr tile = getTile(centerPos.translated(ix,iy,iz));
                if(!tile)
                    continue;

                auto tileCreatures = tile->getCreatures();
                creatures.insert(creatures.end(), tileCreatures.rbegin(), tileCreatures.rend());
            }
        }
    }

    return creatures;
}

void Creature::updateWalkingTile()
{
    // determine new walking tile
    TilePtr newWalkingTile;
    Rect virtualCreatureRect(Otc::TILE_PIXELS + (m_walkOffset.x - getDisplacementX()),
                             Otc::TILE_PIXELS + (m_walkOffset.y - getDisplacementY()),
                             Otc::TILE_PIXELS, Otc::TILE_PIXELS);
    for(int xi = -1; xi <= 1 && !newWalkingTile; ++xi) {
        for(int yi = -1; yi <= 1 && !newWalkingTile; ++yi) {
            Rect virtualTileRect((xi+1)*Otc::TILE_PIXELS, (yi+1)*Otc::TILE_PIXELS, Otc::TILE_PIXELS, Otc::TILE_PIXELS);

            // only render creatures where bottom right is inside tile rect
            if(virtualTileRect.contains(virtualCreatureRect.bottomRight())) {
                newWalkingTile = g_map.getOrCreateTile(m_position.translated(xi, yi, 0));
            }
        }
    }

    if(newWalkingTile != m_walkingTile) {
        if(m_walkingTile)
            m_walkingTile->removeWalkingCreature(static_self_cast<Creature>());
        if(newWalkingTile)
            newWalkingTile->addWalkingCreature(static_self_cast<Creature>());
        m_walkingTile = newWalkingTile;
    }
}

void Map::setCentralPosition(const Position& centralPosition)
{
    if(m_centralPosition == centralPosition)
        return;

    m_centralPosition = centralPosition;

    removeUnawareThings();

    // this fixes local player position when the local player is removed from the map,
    // the local player is removed from the map when there are too many creatures on his tile,
    // so there is no enough stackpos to the server send him
    g_dispatcher.addEvent([this] {
        LocalPlayerPtr localPlayer = g_game.getLocalPlayer();
        if(!localPlayer || localPlayer->getPosition() == m_centralPosition)
            return;
        TilePtr tile = localPlayer->getTile();
        if(tile && tile->hasThing(localPlayer))
            return;

        Position oldPos = localPlayer->getPosition();
        Position pos = m_centralPosition;
        if(oldPos != pos) {
            if(!localPlayer->isRemoved())
                localPlayer->onDisappear();
            localPlayer->setPosition(pos);
            localPlayer->onAppear();
            g_logger.debug("forced player position update");
        }
    });

    for(const MapViewPtr& mapView : m_mapViews)
        mapView->onMapCenterChange(centralPosition);
}

int MapView::calcFirstVisibleFloor()
{
    int z = 7;
    // return forced first visible floor
    if(m_lockedFirstVisibleFloor != -1) {
        z = m_lockedFirstVisibleFloor;
    } else {
        Position cameraPosition = getCameraPosition();

        // this could happens if the player is not known yet
        if(cameraPosition.isValid()) {
            // avoid rendering multifloors in far views
            if(!m_multifloor) {
                z = cameraPosition.z;
            } else {
                // if nothing is limiting the view, the first visible floor is 0
                int firstFloor = 0;

                // limits to underground floors while under sea level
                if(cameraPosition.z > Otc::SEA_FLOOR)
                    firstFloor = std::max(cameraPosition.z - Otc::AWARE_UNDEGROUND_FLOOR_RANGE, (int)Otc::UNDERGROUND_FLOOR);

                // loop in 3x3 tiles around the camera
                for(int ix = -1; ix <= 1 && firstFloor < cameraPosition.z; ++ix) {
                    for(int iy = -1; iy <= 1 && firstFloor < cameraPosition.z; ++iy) {
                        Position pos = cameraPosition.translated(ix, iy);

                        // process tiles that we can look through, e.g. windows, doors
                        if((ix == 0 && iy == 0) || (/*(std::abs(ix) != std::abs(iy)) && */g_map.isLookPossible(pos))) {
                            Position upperPos = pos;
                            Position coveredPos = pos;

                            while(coveredPos.coveredUp() && upperPos.up() && upperPos.z >= firstFloor) {
                                // check tiles physically above
                                TilePtr tile = g_map.getTile(upperPos);
                                if(tile && tile->limitsFloorsView()) {
                                    firstFloor = upperPos.z + 1;
                                    break;
                                }

                                // check tiles geometrically above
                                tile = g_map.getTile(coveredPos);
                                if(tile && tile->limitsFloorsView()) {
                                    firstFloor = coveredPos.z + 1;
                                    break;
                                }
                            }
                        }
                    }
                }
                z = firstFloor;
            }
        }
    }

    // just ensure the that the floor is in the valid range
    z = std::min(std::max(z, 0), (int)Otc::MAX_Z);
    return z;
}

bool Map::isCovered(const Position& pos, int firstFloor)
{
    // check for tiles on top of the postion
    Position tilePos = pos;
    while(tilePos.coveredUp() && tilePos.z >= firstFloor) {
        TilePtr tile = getTile(tilePos);
        // the below tile is covered when the above tile has a full ground
        if(tile && tile->isFullGround())
            return true;
    }
    return false;
}

bool Map::isCovered(const Position& pos, int firstFloor)
{
    Position tilePos = pos;
    tilePos.perspectiveUp();
    while(tilePos.z >= firstFloor) {
        TilePtr tile = m_tiles[tilePos];
        if(tile && tile->isFullGround())
            return true;
        tilePos.perspectiveUp();
    }
    return false;
}

void Map::addThing(const ThingPtr& thing, const Position& pos, int stackPos)
{
    if(!thing)
        return;

    Position oldPos = thing->getPos();
    bool teleport = false;
    if(oldPos.isValid() && !oldPos.isInRange(pos,1,1,0))
        teleport = true;

    TilePtr tile = getTile(pos);

    if(CreaturePtr creature = thing->asCreature()) {
        tile->addThing(thing, stackPos);
        m_creatures[creature->getId()] = creature;

        if(teleport)
            g_game.processCreatureTeleport(creature);
    }
    else if(MissilePtr shot = thing->asMissile()) {
        m_missilesAtFloor[shot->getPos().z].push_back(shot);
    }
    else if(AnimatedTextPtr animatedText = thing->asAnimatedText()) {
        m_animatedTexts.push_back(animatedText);
    }
    else if(StaticTextPtr staticText = thing->asStaticText()) {
        bool mustAdd = true;
        for(auto it = m_staticTexts.begin(), end = m_staticTexts.end(); it != end; ++it) {
            StaticTextPtr cStaticText = *it;
            if(cStaticText->getPos() == pos) {
                // try to combine messages
                if(cStaticText->addMessage(staticText->getName(), staticText->getMessageType(), staticText->getFirstMessage())) {
                    mustAdd = false;
                    break;
                }
                else {
                    // must add another message and rearrenge current
                }
            }

        }

        if(mustAdd)
            m_staticTexts.push_back(staticText);
    }
    else {
        tile->addThing(thing, stackPos);
    }

    thing->start();
    thing->setPos(pos);
}

void Map::addThing(const ThingPtr& thing, const Position& pos, int stackPos)
{
    if(!thing)
        return;

    if(MissilePtr shot = thing->asMissile()) {
        m_missilesAtFloor[shot->getPosition().z].push_back(shot);
        return;
    }

    TilePtr tile = getTile(pos);
    tile->addThing(thing, stackPos);

    if(CreaturePtr creature = thing->asCreature())
        m_creatures[creature->getId()] = creature;
}

HeroPtr find_hero(MonsterPtr monster) {
    auto stats = monster->get_stats();
    int sight = stats->area_of_sight;

    TilePtr my_pos = monster->get_pos();
    Coord my_coord = my_pos->get_coord();

    for (int x = my_coord.x - sight; x < my_coord.x + sight; ++x) {
        for (int y = my_coord.y - sight; y < my_coord.y + sight; ++y) {
            TilePtr tile = main_core->get_tile(Coord(x, y));
            UnitPtr unit = tile->get_unit();
            if (unit == main_core->get_hero()) {
                return Hero::to_Ptr(unit);
            }
        }
    }
    return HeroPtr();
}

void Game::autoWalk(std::vector<Otc::Direction> dirs)
{
    if(!canPerformGameAction())
        return;

    // protocol limits walk path up to 255 directions
    if(dirs.size() > 127) {
        g_logger.error("Auto walk path too great, the maximum number of directions is 127");
        return;
    }

    if(dirs.size() == 0)
        return;

    // must cancel follow before any new walk
    if(isFollowing())
        cancelFollow();

    auto it = dirs.begin();
    Otc::Direction direction = *it;
    if(!m_localPlayer->canWalk(direction))
        return;

    TilePtr toTile = g_map.getTile(m_localPlayer->getPosition().translatedToDirection(direction));
    if(toTile && toTile->isWalkable() && !m_localPlayer->isServerWalking()) {
        m_localPlayer->preWalk(direction);

        if(getFeature(Otc::GameForceFirstAutoWalkStep)) {
            forceWalk(direction);
            dirs.erase(it);
        }
    }

    g_lua.callGlobalField("g_game", "onAutoWalk", dirs);

    m_protocolGame->sendAutoWalk(dirs);
}

std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult> Map::findPath(const Position& startPos, const Position& goalPos, int maxComplexity, int flags)
{
    // pathfinding using A* search algorithm
    // as described in http://en.wikipedia.org/wiki/A*_search_algorithm

    struct Node {
        Node(const Position& pos) : cost(0), totalCost(0), pos(pos), prev(nullptr), dir(Otc::InvalidDirection) { }
        float cost;
        float totalCost;
        Position pos;
        Node *prev;
        Otc::Direction dir;
    };

    struct LessNode : std::binary_function<std::pair<Node*, float>, std::pair<Node*, float>, bool> {
        bool operator()(std::pair<Node*, float> a, std::pair<Node*, float> b) const {
            return b.second < a.second;
        }
    };

    std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult> ret;
    std::vector<Otc::Direction>& dirs = std::get<0>(ret);
    Otc::PathFindResult& result = std::get<1>(ret);

    result = Otc::PathFindResultNoWay;

    if(startPos == goalPos) {
        result = Otc::PathFindResultSamePosition;
        return ret;
    }

    if(startPos.z != goalPos.z) {
        result = Otc::PathFindResultImpossible;
        return ret;
    }

    // check the goal pos is walkable
    if(g_map.isAwareOfPosition(goalPos)) {
        const TilePtr goalTile = getTile(goalPos);
        if(!goalTile || !goalTile->isWalkable()) {
            return ret;
        }
    }
    else {
        const MinimapTile& goalTile = g_minimap.getTile(goalPos);
        if(goalTile.hasFlag(MinimapTileNotWalkable)) {
            return ret;
        }
    }

    std::unordered_map<Position, Node*, PositionHasher> nodes;
    std::priority_queue<std::pair<Node*, float>, std::vector<std::pair<Node*, float>>, LessNode> searchList;

    Node *currentNode = new Node(startPos);
    currentNode->pos = startPos;
    nodes[startPos] = currentNode;
    Node *foundNode = nullptr;
    while(currentNode) {
        if((int)nodes.size() > maxComplexity) {
            result = Otc::PathFindResultTooFar;
            break;
        }

        // path found
        if(currentNode->pos == goalPos && (!foundNode || currentNode->cost < foundNode->cost))
            foundNode = currentNode;

        // cost too high
        if(foundNode && currentNode->totalCost >= foundNode->cost)
            break;

        for(int i=-1;i<=1;++i) {
            for(int j=-1;j<=1;++j) {
                if(i == 0 && j == 0)
                    continue;

                bool wasSeen = false;
                bool hasCreature = false;
                bool isNotWalkable = true;
                bool isNotPathable = true;
                int speed = 100;

                Position neighborPos = currentNode->pos.translated(i, j);
                if(g_map.isAwareOfPosition(neighborPos)) {
                    wasSeen = true;
                    if(const TilePtr& tile = getTile(neighborPos)) {
                        hasCreature = tile->hasCreature();
                        isNotWalkable = !tile->isWalkable();
                        isNotPathable = !tile->isPathable();
                        speed = tile->getGroundSpeed();
                    }
                } else {
                    const MinimapTile& mtile = g_minimap.getTile(neighborPos);
                    wasSeen = mtile.hasFlag(MinimapTileWasSeen);
                    isNotWalkable = mtile.hasFlag(MinimapTileNotWalkable);
                    isNotPathable = mtile.hasFlag(MinimapTileNotPathable);
                    if(isNotWalkable || isNotPathable)
                        wasSeen = true;
                    speed = mtile.getSpeed();
                }
//.........这里部分代码省略.........

void House::setTile(const TilePtr& tile)
{
    tile->setFlags(TILESTATE_HOUSE);
    m_tiles.insert(std::make_pair(tile->getPosition(), tile));
}

bool Game::dashWalk(Otc::Direction direction)
{
    if(!canPerformGameAction())
        return false;

    // must cancel follow before any new walk
    if(isFollowing())
        cancelFollow();

    // must cancel auto walking
    if(m_localPlayer->isAutoWalking()) {
        m_protocolGame->sendStop();
        m_localPlayer->stopAutoWalk();
    }

    if(m_localPlayer->isWalking() && m_dashTimer.ticksElapsed() < std::max<int>(m_localPlayer->getStepDuration(false, direction) - m_ping, 30))
        return false;

    Position toPos = m_localPlayer->getPosition().translatedToDirection(direction);
    TilePtr toTile = g_map.getTile(toPos);
    // only do prewalks to walkable tiles (like grounds and not walls)
    if(toTile && toTile->isWalkable()) {
        if(!m_localPlayer->isWalking() && m_localPlayer->getWalkTicksElapsed() >= m_localPlayer->getStepDuration() + 100)
            m_localPlayer->preWalk(direction);
    // check walk to another floor (e.g: when above 3 parcels)
    } else {
        // check if can walk to a lower floor
        auto canChangeFloorDown = [&]() -> bool {
            Position pos = toPos;
            if(!pos.down())
                return false;
            TilePtr toTile = g_map.getTile(pos);
            if(toTile && toTile->hasElevation(3))
                return true;
            return false;
        };

        // check if can walk to a higher floor
        auto canChangeFloorUp = [&]() -> bool {
            TilePtr fromTile = m_localPlayer->getTile();
            if(!fromTile || !fromTile->hasElevation(3))
                return false;
            Position pos = toPos;
            if(!pos.up())
                return false;
            TilePtr toTile = g_map.getTile(pos);
            if(!toTile || !toTile->isWalkable())
                return false;
            return true;
        };

        if(canChangeFloorDown() || canChangeFloorUp() ||
            (!toTile || toTile->isEmpty())) {
            m_localPlayer->lockWalk();
        } else
            return false;
    }

    forceWalk(direction);
    m_dashTimer.restart();
    m_lastWalkDir = direction;
    return true;
}