/*************************************************************************** * Copyright (C) 2005-2019 by the FIFE team * * http://www.fifengine.net * * This file is part of FIFE. * * * * FIFE is free software; you can redistribute it and/or * * modify it under the terms of the GNU Lesser General Public * * License as published by the Free Software Foundation; either * * version 2.1 of the License, or (at your option) any later version. * * * * This library 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 * * Lesser General Public License for more details. * * * * You should have received a copy of the GNU Lesser General Public * * License along with this library; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * ***************************************************************************/ // Standard C++ library includes // 3rd party library includes // FIFE includes // These includes are split up in two parts, separated by one empty line // First block: files included from the FIFE root src directory // Second block: files included from the same folder #include "model/metamodel/grids/cellgrid.h" #include "util/log/logger.h" #include "util/structures/purge.h" #include "cellcache.h" #include "cell.h" #include "layer.h" #include "instance.h" #include "map.h" #include "instancetree.h" namespace FIFE { static Logger _log(LM_STRUCTURES); class CellCacheChangeListener : public LayerChangeListener { public: CellCacheChangeListener(Layer* layer) { m_layer = layer; } virtual ~CellCacheChangeListener() { } virtual void onLayerChanged(Layer* layer, std::vector& instances) { for(std::vector::iterator i = instances.begin(); i != instances.end(); ++i) { if ((*i)->isMultiCell()) { bool rotchange = ((*i)->getChangeInfo() & ICHANGE_ROTATION) == ICHANGE_ROTATION; bool locchange = ((*i)->getChangeInfo() & ICHANGE_LOC) == ICHANGE_LOC; bool celchange = ((*i)->getChangeInfo() & ICHANGE_CELL) == ICHANGE_CELL; bool blochange = ((*i)->getChangeInfo() & ICHANGE_BLOCK) == ICHANGE_BLOCK; if (!rotchange && !locchange && !celchange && !blochange) { continue; } int32_t oldrotation = (*i)->getOldRotation(); int32_t newrotation = (*i)->getRotation(); if (!rotchange) { oldrotation = newrotation; } if (rotchange || locchange || celchange) { // update visual positions (*i)->updateMultiInstances(); } if (rotchange || celchange) { // update cache positions ModelCoordinate oldmc; ModelCoordinate newmc; if (m_layer == layer) { oldmc = (*i)->getOldLocationRef().getLayerCoordinates(); newmc = (*i)->getLocationRef().getLayerCoordinates(); } else { oldmc = m_layer->getCellGrid()->toLayerCoordinates( layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef())); newmc = m_layer->getCellGrid()->toLayerCoordinates( layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef())); } if (!celchange) { oldmc = newmc; } CellGrid* cg = m_layer->getCellGrid(); const std::vector& multiinstances = (*i)->getMultiInstances(); std::vector::const_iterator it = multiinstances.begin(); for (; it != multiinstances.end(); ++it) { // remove std::vector coordinates = cg->toMultiCoordinates(oldmc, (*it)->getObject()->getMultiPartCoordinates(oldrotation)); std::vector::iterator mcit = coordinates.begin(); for (; mcit != coordinates.end(); ++mcit) { Cell* cell = m_layer->getCellCache()->getCell(*mcit); if (cell) { cell->removeInstance(*it); } } // add coordinates = cg->toMultiCoordinates(newmc, (*it)->getObject()->getMultiPartCoordinates(newrotation)); mcit = coordinates.begin(); for (; mcit != coordinates.end(); ++mcit) { Cell* cell = m_layer->getCellCache()->getCell(*mcit); if (cell) { cell->addInstance(*it); } } } if (celchange) { // leader instance Cell* oldcell = m_layer->getCellCache()->getCell(oldmc); Cell* newcell = m_layer->getCellCache()->getCell(newmc); if (oldcell == newcell) { continue; } if (oldcell) { oldcell->removeInstance(*i); } if (newcell) { newcell->addInstance(*i); } } } continue; } if ((*i)->getObject()->isMultiPart()) { continue; } if (((*i)->getChangeInfo() & ICHANGE_BLOCK) == ICHANGE_BLOCK) { ModelCoordinate mc; if (m_layer == layer) { mc = (*i)->getLocationRef().getLayerCoordinates(); } else { mc = m_layer->getCellGrid()->toLayerCoordinates( layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef())); } Cell* cell = m_layer->getCellCache()->getCell(mc); if (cell) { cell->changeInstance(*i); } } if (((*i)->getChangeInfo() & ICHANGE_CELL) == ICHANGE_CELL) { ModelCoordinate oldmc; ModelCoordinate newmc; if (m_layer == layer) { oldmc = (*i)->getOldLocationRef().getLayerCoordinates(); newmc = (*i)->getLocationRef().getLayerCoordinates(); } else { oldmc = m_layer->getCellGrid()->toLayerCoordinates( layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef())); newmc = m_layer->getCellGrid()->toLayerCoordinates( layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef())); } Cell* oldcell = m_layer->getCellCache()->getCell(oldmc); Cell* newcell = m_layer->getCellCache()->getCell(newmc); if (oldcell == newcell) { continue; } if (oldcell) { oldcell->removeInstance(*i); } if (newcell) { newcell->addInstance(*i); } } } } virtual void onInstanceCreate(Layer* layer, Instance* instance) { ModelCoordinate mc; if (m_layer == layer) { mc = instance->getLocationRef().getLayerCoordinates(); } else { mc = m_layer->getCellGrid()->toLayerCoordinates( layer->getCellGrid()->toMapCoordinates(instance->getLocationRef().getExactLayerCoordinatesRef())); } CellCache* cache = m_layer->getCellCache(); Location loc(m_layer); loc.setLayerCoordinates(mc); if (!cache->isInCellCache(loc)) { cache->resize(); } if (instance->isMultiCell()) { instance->updateMultiInstances(); CellGrid* cg = m_layer->getCellGrid(); const std::vector& multiinstances = instance->getMultiInstances(); std::vector::const_iterator it = multiinstances.begin(); for (; it != multiinstances.end(); ++it) { std::vector coordinates = cg->toMultiCoordinates(mc, (*it)->getObject()->getMultiPartCoordinates(instance->getRotation())); std::vector::iterator mcit = coordinates.begin(); for (; mcit != coordinates.end(); ++mcit) { loc.setLayerCoordinates(*mcit); if (!cache->isInCellCache(loc)) { cache->resize(); } Cell* cell = cache->getCell(*mcit); if (cell) { cell->addInstance(*it); } } } } Cell* cell = cache->getCell(mc); if (cell) { cell->addInstance(instance); } } virtual void onInstanceDelete(Layer* layer, Instance* instance) { ModelCoordinate mc; if (m_layer == layer) { mc = instance->getLocationRef().getLayerCoordinates(); } else { mc = m_layer->getCellGrid()->toLayerCoordinates( layer->getCellGrid()->toMapCoordinates(instance->getLocationRef().getExactLayerCoordinatesRef())); } CellCache* cache = m_layer->getCellCache(); if (instance->isMultiCell()) { instance->updateMultiInstances(); CellGrid* cg = m_layer->getCellGrid(); const std::vector& multiinstances = instance->getMultiInstances(); std::vector::const_iterator it = multiinstances.begin(); for (; it != multiinstances.end(); ++it) { std::vector coordinates = cg->toMultiCoordinates(mc, (*it)->getObject()->getMultiPartCoordinates(instance->getRotation())); std::vector::iterator mcit = coordinates.begin(); for (; mcit != coordinates.end(); ++mcit) { Cell* cell = cache->getCell(*mcit); if (cell) { cell->removeInstance(*it); } } } } Cell* cell = cache->getCell(mc); if (cell) { cell->removeInstance(instance); } // updates size on the next cache update (happens on same pump) cache->setSizeUpdate(true); } private: Layer* m_layer; }; Zone::Zone(uint32_t id): m_id(id) { } Zone::~Zone() { for (std::set::iterator i = m_cells.begin(); i != m_cells.end(); ++i) { (*i)->resetZone(); } } void Zone::addCell(Cell* cell) { if (!cell->getZone()) { cell->setZone(this); m_cells.insert(cell); } } void Zone::removeCell(Cell* cell) { std::set::iterator i = m_cells.find(cell); if (i != m_cells.end()) { (*i)->resetZone(); m_cells.erase(i); } } void Zone::mergeZone(Zone* zone) { const std::set& cells = zone->getCells(); m_cells.insert(cells.begin(), cells.end()); for (std::set::const_iterator it = cells.begin(); it != cells.end(); ++it) { (*it)->setZone(this); } zone->resetCells(); } const std::set& Zone::getCells() const { return m_cells; } void Zone::resetCells() { m_cells.clear(); } uint32_t Zone::getId() const { return m_id; } uint32_t Zone::getCellCount() const { return static_cast(m_cells.size()); } std::vector Zone::getTransitionCells(Layer* layer) { std::vector transitions; std::set::iterator it = m_cells.begin(); for (; it != m_cells.end(); ++it) { TransitionInfo* trans = (*it)->getTransition(); if (!trans) { continue; } if (layer) { if (layer == (*it)->getLayer()) { transitions.push_back(*it); } } else { transitions.push_back(*it); } } return transitions; } class ZoneCellChangeListener : public CellChangeListener { public: ZoneCellChangeListener(CellCache* cache) { m_cache = cache; } virtual ~ZoneCellChangeListener() { } virtual void onInstanceEnteredCell(Cell* cell, Instance* instance) { } virtual void onInstanceExitedCell(Cell* cell, Instance* instance) { } virtual void onBlockingChangedCell(Cell* cell, CellTypeInfo type, bool blocks) { if (blocks) { cell->setZoneProtected(true); m_cache->splitZone(cell); } else { Zone* z1 = cell->getZone(); Zone* z2 = NULL; const std::vector& neighbors = cell->getNeighbors(); std::vector::const_iterator it = neighbors.begin(); for (; it != neighbors.end(); ++it) { Zone* z = (*it)->getZone(); if (z && z != z1) { z2 = z; } } if (z1 && z2) { cell->setZoneProtected(false); m_cache->mergeZones(z1, z2); } } } private: CellCache* m_cache; }; CellCache::CellCache(Layer* layer): m_layer(layer), m_defaultCostMulti(1.0), m_defaultSpeedMulti(1.0), m_neighborZ(-1), m_blockingUpdate(false), m_sizeUpdate(false), m_searchNarrow(true), m_staticSize(false) { // create cell change listener m_cellZoneListener = new ZoneCellChangeListener(this); // set base size ModelCoordinate min, max; m_layer->getMinMaxCoordinates(min, max); m_size.w = max.x; m_size.h = max.y; m_size.x = min.x; m_size.y = min.y; // create and add layer listener m_cellListener = new CellCacheChangeListener(m_layer); m_layer->addChangeListener(m_cellListener); const std::vector& interacts = m_layer->getInteractLayers(); if (!interacts.empty()) { std::vector::const_iterator layit = interacts.begin(); for(; layit != interacts.end(); ++layit) { // set size (*layit)->getMinMaxCoordinates(min, max, m_layer); m_size.w = std::max(max.x, m_size.w); m_size.h = std::max(max.y, m_size.h); m_size.x = std::min(min.x, m_size.x); m_size.y = std::min(min.y, m_size.y); // add listener (*layit)->addChangeListener(m_cellListener); } } m_width = ABS(m_size.w - m_size.x) + 1; m_height = ABS(m_size.h - m_size.y) + 1; m_cells.resize(m_width); for (uint32_t i = 0; i < m_width; ++i) { m_cells[i].resize(m_height, NULL); } } CellCache::~CellCache() { // reset cache reset(); // remove listener from layers m_layer->removeChangeListener(m_cellListener); const std::vector& interacts = m_layer->getInteractLayers(); if (!interacts.empty()) { std::vector::const_iterator layit = interacts.begin(); for(; layit != interacts.end(); ++layit) { (*layit)->removeChangeListener(m_cellListener); } } // delete listener delete m_cellListener; delete m_cellZoneListener; } void CellCache::reset() { // delete zones if (!m_zones.empty()) { std::vector::iterator it = m_zones.begin(); for (; it != m_zones.end(); ++it) { delete *it; } m_zones.clear(); } // clear all containers m_costsToCells.clear(); m_costsTable.clear(); m_costMultipliers.clear(); m_speedMultipliers.clear(); m_narrowCells.clear(); m_cellAreas.clear(); // delete cells if (!m_cells.empty()) { std::vector >::iterator it = m_cells.begin(); for (; it != m_cells.end(); ++it) { std::vector::iterator cit = (*it).begin(); for (; cit != (*it).end(); ++cit) { delete *cit; } } m_cells.clear(); } // reset default cost and speed m_defaultCostMulti = 1.0; m_defaultSpeedMulti = 1.0; // reset size m_size.x = 0; m_size.y = 0; m_size.w = 0; m_size.h = 0; m_width = 0; m_height = 0; } void CellCache::resize() { if (m_staticSize) { return; } // get new size and check if it has changed Rect newsize = calculateCurrentSize(); resize(newsize); } void CellCache::resize(const Rect& rec) { // check if size has changed Rect newsize = rec; if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) { uint32_t w = ABS(newsize.w - newsize.x) + 1; uint32_t h = ABS(newsize.h - newsize.y) + 1; std::vector > cells; cells.resize(w); for (uint32_t i = 0; i < w; ++i) { cells[i].resize(h, NULL); } const std::vector& interacts = m_layer->getInteractLayers(); for(uint32_t y = 0; y < h; ++y) { for(uint32_t x = 0; x < w; ++x) { // transfer cells ModelCoordinate mc(newsize.x+x, newsize.y+y); Cell* cell = NULL; int32_t old_x = mc.x - m_size.x; int32_t old_y = mc.y - m_size.y; // out of range in the old size, so we create a new cell if (old_x < 0 || old_x >= static_cast(m_width) || old_y < 0 || old_y >= static_cast(m_height)) { int32_t coordId = x + y * w; cell = new Cell(coordId, mc, m_layer); cells[x][y] = cell; std::list cell_instances; m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances); if (!interacts.empty()) { // fill interact Instances into Cell std::vector::const_iterator it = interacts.begin(); std::list interact_instances; for(; it != interacts.end(); ++it) { // convert coordinates ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); // check interact layer for instances (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); if (!interact_instances.empty()) { cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end()); interact_instances.clear(); } } } if (!cell_instances.empty()) { // add instances to cell cell->addInstances(cell_instances); } // transfer ownership } else { cell = m_cells[static_cast(old_x)][static_cast(old_y)]; m_cells[static_cast(old_x)][static_cast(old_y)] = NULL; cells[x][y] = cell; int32_t coordId = x + y * w; cell->setCellId(coordId); cell->resetNeighbors(); } } } // delete old unused cells std::vector >::iterator it = m_cells.begin(); for (; it != m_cells.end(); ++it) { std::vector::iterator cit = (*it).begin(); for (; cit != (*it).end(); ++cit) { if (*cit) { delete *cit; *cit = NULL; } } } // use new values m_cells = cells; m_size = newsize; m_width = w; m_height = h; bool zCheck = m_neighborZ != -1; // fill neighbors into cells it = m_cells.begin(); for (; it != m_cells.end(); ++it) { std::vector::iterator cit = (*it).begin(); for (; cit != (*it).end(); ++cit) { int32_t cellZ = (*cit)->getLayerCoordinates().z; std::vector coordinates; m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates); for (std::vector::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) { Cell* c = getCell(*mi); if (*cit == c || !c) { continue; } if (zCheck) { if (ABS(c->getLayerCoordinates().z - cellZ) > m_neighborZ) { continue; } } (*cit)->addNeighbor(c); } } } } } void CellCache::createCells() { const std::vector& interacts = m_layer->getInteractLayers(); for(uint32_t y = 0; y < m_height; ++y) { for(uint32_t x = 0; x < m_width; ++x) { ModelCoordinate mc(m_size.x+x, m_size.y+y); Cell* cell = getCell(mc); if (!cell) { cell = new Cell(convertCoordToInt(mc), mc, m_layer); m_cells[x][y] = cell; } // fill Instances into Cell std::list cell_instances; m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances); if (!interacts.empty()) { // fill interact Instances into Cell std::vector::const_iterator it = interacts.begin(); std::list interact_instances; for(; it != interacts.end(); ++it) { // convert coordinates ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); // check interact layer for instances (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); if (!interact_instances.empty()) { cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end()); interact_instances.clear(); } } } if (!cell_instances.empty()) { // add instances to cell cell->addInstances(cell_instances); } } } // fill neighbors into cells std::vector >::iterator it = m_cells.begin(); for (; it != m_cells.end(); ++it) { std::vector::iterator cit = (*it).begin(); for (; cit != (*it).end(); ++cit) { uint8_t accessible = 0; bool selfblocker = (*cit)->getCellType() == CTYPE_STATIC_BLOCKER || (*cit)->getCellType() == CTYPE_CELL_BLOCKER; std::vector coordinates; m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates); for (std::vector::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) { Cell* c = getCell(*mi); if (*cit == c || !c) { continue; } if (!selfblocker && c->getCellType() != CTYPE_STATIC_BLOCKER && c->getCellType() != CTYPE_CELL_BLOCKER) { ++accessible; } (*cit)->addNeighbor(c); } // add cell to narrow cells and add listener for zone change if (m_searchNarrow && !selfblocker && accessible < 3) { addNarrowCell(*cit); } } } // create Zones it = m_cells.begin(); for (; it != m_cells.end(); ++it) { std::vector::iterator cit = (*it).begin(); for (; cit != (*it).end(); ++cit) { Cell* cell = *cit; if (cell->getZone() || cell->isInserted()) { continue; } if (cell->getCellType() == CTYPE_STATIC_BLOCKER || cell->getCellType() == CTYPE_CELL_BLOCKER) { continue; } Zone* zone = createZone(); cell->setInserted(true); std::stack cellstack; cellstack.push(cell); while(!cellstack.empty()) { Cell* c = cellstack.top(); cellstack.pop(); zone->addCell(c); const std::vector& neighbors = c->getNeighbors(); for (std::vector::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) { Cell* nc = *nit; if (!nc->isInserted() && nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) { nc->setInserted(true); cellstack.push(nc); } } } } } } void CellCache::forceUpdate() { std::vector >::iterator it = m_cells.begin(); for (; it != m_cells.end(); ++it) { std::vector::iterator cit = (*it).begin(); for (; cit != (*it).end(); ++cit) { (*cit)->updateCellInfo(); } } } void CellCache::addCell(Cell* cell) { ModelCoordinate mc = cell->getLayerCoordinates(); m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell; } Cell* CellCache::createCell(const ModelCoordinate& mc) { Cell* cell = getCell(mc); if (!cell) { cell = new Cell(convertCoordToInt(mc), mc, m_layer); m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell; } return cell; } Cell* CellCache::getCell(const ModelCoordinate& mc) { int32_t x = mc.x - m_size.x; int32_t y = mc.y - m_size.y; if (x < 0 || x >= static_cast(m_width) || y < 0 || y >= static_cast(m_height)) { return NULL; } return m_cells[static_cast(x)][static_cast(y)]; } const std::vector >& CellCache::getCells() { return m_cells; } void CellCache::removeCell(Cell* cell) { if (!m_costsToCells.empty()) { removeCellFromCost(cell); } if (!m_costMultipliers.empty()) { resetCostMultiplier(cell); } if (!m_speedMultipliers.empty()) { resetSpeedMultiplier(cell); } if (!m_narrowCells.empty()) { removeNarrowCell(cell); } if (!m_cellAreas.empty()) { removeCellFromArea(cell); } } void CellCache::addInteractOnRuntime(Layer* interact) { interact->setInteract(true, m_layer->getId()); m_layer->addInteractLayer(interact); interact->addChangeListener(m_cellListener); Rect newsize = calculateCurrentSize(); if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) { resize(); } // not optimal but needed if the grids have different geometry for(uint32_t y = 0; y < m_height; ++y) { for(uint32_t x = 0; x < m_width; ++x) { ModelCoordinate mc(m_size.x+x, m_size.y+y); Cell* cell = getCell(mc); if (cell) { // convert coordinates ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); ModelCoordinate inter_mc = interact->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); // check interact layer for instances std::list interact_instances; interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); if (!interact_instances.empty()) { // fill interact Instances into Cell cell->addInstances(interact_instances); } } } } } void CellCache::removeInteractOnRuntime(Layer* interact) { interact->setInteract(false, ""); m_layer->removeInteractLayer(interact); Rect newsize = calculateCurrentSize(); if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) { resize(); } // not optimal but needed if the grids have different geometry for(uint32_t y = 0; y < m_height; ++y) { for(uint32_t x = 0; x < m_width; ++x) { ModelCoordinate mc(m_size.x+x, m_size.y+y); Cell* cell = getCell(mc); if (cell) { // convert coordinates ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); ModelCoordinate inter_mc = interact->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); // check interact layer for instances std::list interact_instances; interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); if (!interact_instances.empty()) { // remove interact Instances from Cell for (std::list::iterator it = interact_instances.begin(); it != interact_instances.end(); ++it) { cell->removeInstance(*it); } } } } } } LayerChangeListener* CellCache::getCellCacheChangeListener() { return m_cellListener; } Layer* CellCache::getLayer() { return m_layer; } const Rect& CellCache::getSize() { return m_size; } void CellCache::setSize(const Rect& rec) { resize(rec); } uint32_t CellCache::getWidth() { return m_width; } uint32_t CellCache::getHeight() { return m_height; } bool CellCache::isInCellCache(const Location& location) const { if (m_layer != location.getLayer()) { return false; } int32_t x = location.getLayerCoordinates().x - m_size.x; int32_t y = location.getLayerCoordinates().y - m_size.y; if (x < 0 || x >= static_cast(m_width) || y < 0 || y >= static_cast(m_height)) { return false; } return true; } int32_t CellCache::convertCoordToInt(const ModelCoordinate& coord) const { ModelCoordinate newcoords(coord.x - m_size.x, coord.y - m_size.y); return newcoords.x + newcoords.y*m_width; } ModelCoordinate CellCache::convertIntToCoord(const int32_t cell) const { ModelCoordinate coord((cell % m_width) + m_size.x, (cell / m_width) + m_size.y); return coord; } int32_t CellCache::getMaxIndex() const { int32_t max_index = m_width*m_height; return max_index; } void CellCache::setMaxNeighborZ(int32_t z) { m_neighborZ = z; } int32_t CellCache::getMaxNeighborZ() { return m_neighborZ; } std::vector CellCache::getCellsInLine(const ModelCoordinate& pt1, const ModelCoordinate& pt2, bool blocker) { std::vector cells; std::vector coords = m_layer->getCellGrid()->getCoordinatesInLine(pt1, pt2); for (std::vector::iterator it = coords.begin(); it != coords.end(); ++it) { Cell* c = getCell(*it); if (c) { if (blocker && c->getCellType() != CTYPE_NO_BLOCKER) { return cells; } cells.push_back(c); } else { return cells; } } return cells; } std::vector CellCache::getCellsInRect(const Rect& rec) { std::vector cells; cells.reserve(rec.w * rec.h); ModelCoordinate current(rec.x, rec.y); ModelCoordinate target(rec.x+rec.w, rec.y+rec.h); for (; current.y < target.y; ++current.y) { current.x = rec.x; for (; current.x < target.x; ++current.x) { Cell* c = getCell(current); if (c) { cells.push_back(c); } } } return cells; } std::vector CellCache::getBlockingCellsInRect(const Rect& rec) { std::vector cells; cells.reserve(rec.w * rec.h); ModelCoordinate current(rec.x, rec.y); ModelCoordinate target(rec.x + rec.w, rec.y + rec.h); for (; current.y < target.y; ++current.y) { current.x = rec.x; for (; current.x < target.x; ++current.x) { Cell* c = getCell(current); if (c && c->getCellType() != CTYPE_NO_BLOCKER) { cells.push_back(c); } } } return cells; } std::vector CellCache::getCellsInCircle(const ModelCoordinate& center, uint16_t radius) { std::vector cells; //radius power 2 uint16_t radiusp2 = (radius+1) * radius; ModelCoordinate current(center.x-radius, center.y-radius); ModelCoordinate target(center.x+radius, center.y+radius); for (; current.y < center.y; current.y++) { current.x = center.x-radius; for (; current.x < center.x; current.x++) { Cell* c = getCell(current); if (c) { uint16_t dx = center.x - current.x; uint16_t dy = center.y - current.y; uint16_t distance = dx*dx + dy*dy; if (distance <= radiusp2) { cells.push_back(c); current.x = center.x + dx; c = getCell(current); if (c) cells.push_back(c); current.y = center.y + dy; c = getCell(current); if (c) cells.push_back(c); current.x = center.x-dx; c = getCell(current); if (c) cells.push_back(c); current.y = center.y-dy; } } } } current.x = center.x; current.y = center.y-radius; for (; current.y <= target.y; current.y++) { Cell* c = getCell(current); if (c) cells.push_back(c); } current.y = center.y; current.x = center.x-radius; for (; current.x <= target.x; current.x++) { Cell* c = getCell(current); if (c) cells.push_back(c); } return cells; } std::vector CellCache::getCellsInCircleSegment(const ModelCoordinate& center, uint16_t radius, int32_t sangle, int32_t eangle) { std::vector cells; ExactModelCoordinate exactCenter(center.x, center.y); std::vector tmpCells = getCellsInCircle(center, radius); int32_t s = (sangle + 360) % 360; int32_t e = (eangle + 360) % 360; bool greater = (s > e) ? true : false; for (std::vector::iterator it = tmpCells.begin(); it != tmpCells.end(); ++it) { int32_t angle = getAngleBetween(exactCenter, intPt2doublePt((*it)->getLayerCoordinates())); if (greater) { if (angle >= s || angle <= e) { cells.push_back(*it); } } else { if (angle >= s && angle <= e) { cells.push_back(*it); } } } return cells; } void CellCache::registerCost(const std::string& costId, double cost) { std::pair::iterator, bool> insertiter; insertiter = m_costsTable.insert(std::pair(costId, cost)); if (insertiter.second == false) { double& old_cost = insertiter.first->second; old_cost = cost; } } void CellCache::unregisterCost(const std::string& costId) { std::map::iterator it = m_costsTable.find(costId); if (it != m_costsTable.end()) { m_costsTable.erase(it); m_costsToCells.erase(costId); } } double CellCache::getCost(const std::string& costId) { std::map::iterator it = m_costsTable.find(costId); if (it != m_costsTable.end()) { return it->second; } return 0.0; } bool CellCache::existsCost(const std::string& costId) { std::map::iterator it = m_costsTable.find(costId); if (it != m_costsTable.end()) { return true; } return false; } std::list CellCache::getCosts() { std::list costs; std::map::iterator it = m_costsTable.begin(); for (; it != m_costsTable.end(); ++it) { costs.push_back((*it).first); } return costs; } void CellCache::unregisterAllCosts() { m_costsTable.clear(); m_costsToCells.clear(); } void CellCache::addCellToCost(const std::string& costId, Cell* cell) { if (existsCost(costId)) { StringCellPair result = m_costsToCells.equal_range(costId); StringCellIterator it = result.first; for (; it != result.second; ++it) { if ((*it).second == cell) { return; } } m_costsToCells.insert(std::pair(costId, cell)); } } void CellCache::addCellsToCost(const std::string& costId, const std::vector& cells) { std::vector::const_iterator it = cells.begin(); for (; it != cells.end(); ++it) { addCellToCost(costId, *it); } } void CellCache::removeCellFromCost(Cell* cell) { StringCellIterator it = m_costsToCells.begin(); for (; it != m_costsToCells.end();) { if ((*it).second == cell) { m_costsToCells.erase(it++); } else { ++it; } } } void CellCache::removeCellFromCost(const std::string& costId, Cell* cell) { StringCellPair result = m_costsToCells.equal_range(costId); StringCellIterator it = result.first; for (; it != result.second; ++it) { if ((*it).second == cell) { m_costsToCells.erase(it); break; } } } void CellCache::removeCellsFromCost(const std::string& costId, const std::vector& cells) { std::vector::const_iterator it = cells.begin(); for (; it != cells.end(); ++it) { removeCellFromCost(costId, *it); } } std::vector CellCache::getCostCells(const std::string& costId) { std::vector cells; StringCellPair result = m_costsToCells.equal_range(costId); StringCellIterator it = result.first; for (; it != result.second; ++it) { cells.push_back((*it).second); } return cells; } std::vector CellCache::getCellCosts(Cell* cell) { std::vector costs; StringCellIterator it = m_costsToCells.begin(); for (; it != m_costsToCells.end(); ++it) { if ((*it).second == cell) { costs.push_back((*it).first); } } return costs; } bool CellCache::existsCostForCell(const std::string& costId, Cell* cell) { StringCellPair result = m_costsToCells.equal_range(costId); StringCellIterator it = result.first; for (; it != result.second; ++it) { if ((*it).second == cell) { return true; } } return false; } double CellCache::getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next) { double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next); Cell* nextcell = getCell(next); if (nextcell) { if (!nextcell->defaultCost()) { cost *= nextcell->getCostMultiplier(); } else { cost *= m_defaultCostMulti; } } return cost; } double CellCache::getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next, const std::string& costId) { double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next); Cell* nextcell = getCell(next); if (nextcell) { if (existsCostForCell(costId, nextcell)) { cost *= getCost(costId); } else { if (!nextcell->defaultCost()) { cost *= nextcell->getCostMultiplier(); } else { cost *= m_defaultCostMulti; } } } return cost; } bool CellCache::getCellSpeedMultiplier(const ModelCoordinate& cell, double& multiplier) { Cell* nextcell = getCell(cell); if (nextcell) { if (!nextcell->defaultSpeed()) { multiplier = nextcell->getSpeedMultiplier(); return true; } } multiplier = m_defaultSpeedMulti; return false; } void CellCache::setDefaultCostMultiplier(double multi) { m_defaultCostMulti = multi; } double CellCache::getDefaultCostMultiplier() { return m_defaultCostMulti; } void CellCache::setDefaultSpeedMultiplier(double multi) { m_defaultSpeedMulti = multi; } double CellCache::getDefaultSpeedMultiplier() { return m_defaultSpeedMulti; } bool CellCache::isDefaultCost(Cell* cell) { std::map::iterator it = m_costMultipliers.find(cell); if (it != m_costMultipliers.end()) { return false; } return true; } void CellCache::setCostMultiplier(Cell* cell, double multi) { std::pair::iterator, bool> insertiter = m_costMultipliers.insert(std::pair(cell, multi)); if (insertiter.second == false) { double& old = insertiter.first->second; old = multi; } } double CellCache::getCostMultiplier(Cell* cell) { double cost = 1.0; std::map::iterator it = m_costMultipliers.find(cell); if (it != m_costMultipliers.end()) { cost = it->second; } return cost; } void CellCache::resetCostMultiplier(Cell* cell) { m_costMultipliers.erase(cell); } bool CellCache::isDefaultSpeed(Cell* cell) { std::map::iterator it = m_speedMultipliers.find(cell); if (it != m_speedMultipliers.end()) { return false; } return true; } void CellCache::setSpeedMultiplier(Cell* cell, double multi) { std::pair::iterator, bool> insertiter = m_speedMultipliers.insert(std::pair(cell, multi)); if (insertiter.second == false) { double& old = insertiter.first->second; old = multi; } } double CellCache::getSpeedMultiplier(Cell* cell) { double speed = 1.0; std::map::iterator it = m_speedMultipliers.find(cell); if (it != m_speedMultipliers.end()) { speed = it->second; } return speed; } void CellCache::resetSpeedMultiplier(Cell* cell) { m_speedMultipliers.erase(cell); } void CellCache::addTransition(Cell* cell) { m_transitions.push_back(cell); } void CellCache::removeTransition(Cell* cell) { std::vector::iterator it = m_transitions.begin(); for (; it != m_transitions.end(); ++it) { if (cell == *it) { m_transitions.erase(it); break; } } } std::vector CellCache::getTransitionCells(Layer* layer) { if (!layer) { return m_transitions; } std::vector cells; std::vector::iterator it = m_transitions.begin(); for (; it != m_transitions.end(); ++it) { TransitionInfo* trans = (*it)->getTransition(); if (trans) { if (trans->m_layer == layer) { cells.push_back(*it); } } } return cells; } Zone* CellCache::createZone() { uint32_t id = 0; bool search = true; while (search) { bool found = false; if (!m_zones.empty()) { for (std::vector::iterator i = m_zones.begin(); i != m_zones.end(); ++i) { if ((*i)->getId() == id) { found = true; ++id; break; } } } search = found; } Zone* zi = new Zone(id); m_zones.push_back(zi); return zi; } const std::vector& CellCache::getZones() { return m_zones; } Zone* CellCache::getZone(uint32_t id) { Zone* zi = 0; for (std::vector::iterator i = m_zones.begin(); i != m_zones.end(); ++i) { if ((*i)->getId() == id) { zi = (*i); break; } } if (!zi) { zi = new Zone(id); m_zones.push_back(zi); } return zi; } void CellCache::removeZone(Zone* zone) { for (std::vector::iterator i = m_zones.begin(); i != m_zones.end(); ++i) { if (*i == zone) { delete *i; m_zones.erase(i); break; } } } void CellCache::splitZone(Cell* cell) { Zone* currentZone = cell->getZone(); if (!currentZone) { return; } Zone* newZone = createZone(); std::stack cellstack; const std::vector& neighbors = cell->getNeighbors(); for (std::vector::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) { Cell* nc = *nit; if (nc->isInserted() && !nc->isZoneProtected() && nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) { cellstack.push(nc); break; } } while(!cellstack.empty()) { Cell* c = cellstack.top(); cellstack.pop(); currentZone->removeCell(c); newZone->addCell(c); c->setInserted(true); if (c->isZoneProtected()) { continue; } const std::vector& neigh = c->getNeighbors(); for (std::vector::const_iterator nit = neigh.begin(); nit != neigh.end(); ++nit) { Cell* nc = *nit; if (nc->getZone() == currentZone && nc->isInserted() && nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) { cellstack.push(nc); nc->setInserted(false); } } } if (currentZone->getCellCount() == 0) { removeZone(currentZone); } } void CellCache::mergeZones(Zone* zone1, Zone* zone2) { if (!zone1 || !zone2) { return; } Zone* addZone = zone2; Zone* oldZone = zone1; if (zone1->getCellCount() > zone2->getCellCount()) { addZone = zone1; oldZone = zone2; } addZone->mergeZone(oldZone); removeZone(oldZone); } void CellCache::addNarrowCell(Cell* cell) { std::pair::iterator, bool> insertiter = m_narrowCells.insert(cell); if (insertiter.second) { cell->addChangeListener(m_cellZoneListener); } } const std::set& CellCache::getNarrowCells() { return m_narrowCells; } void CellCache::removeNarrowCell(Cell* cell) { std::set::iterator it = m_narrowCells.find(cell); if (it != m_narrowCells.end()) { (*it)->removeChangeListener(m_cellZoneListener); m_narrowCells.erase(it); } } void CellCache::resetNarrowCells() { std::set::const_iterator it = m_narrowCells.begin(); for (; it != m_narrowCells.end(); ++it) { (*it)->removeChangeListener(m_cellZoneListener); } m_narrowCells.clear(); } bool CellCache::isSearchNarrowCells() { return m_searchNarrow; } void CellCache::setSearchNarrowCells(bool search) { m_searchNarrow = search; } void CellCache::addCellToArea(const std::string& id, Cell* cell) { m_cellAreas.insert(std::pair(id, cell)); } void CellCache::addCellsToArea(const std::string& id, const std::vector& cells) { std::vector::const_iterator it = cells.begin(); for (; it != cells.end(); ++it) { addCellToArea(id, *it); } } void CellCache::removeCellFromArea(Cell* cell) { StringCellIterator it = m_cellAreas.begin(); while (it != m_cellAreas.end()) { if ((*it).second == cell) { m_cellAreas.erase(it++); } else { ++it; } } } void CellCache::removeCellFromArea(const std::string& id, Cell* cell) { StringCellPair result = m_cellAreas.equal_range(id); StringCellIterator it = result.first; for (; it != result.second; ++it) { if ((*it).second == cell) { m_cellAreas.erase(it); break; } } } void CellCache::removeCellsFromArea(const std::string& id, const std::vector& cells) { std::vector::const_iterator it = cells.begin(); for (; it != cells.end(); ++it) { removeCellFromArea(id, *it); } } void CellCache::removeArea(const std::string& id) { m_cellAreas.erase(id); } bool CellCache::existsArea(const std::string& id) { StringCellIterator it = m_cellAreas.find(id); if (it == m_cellAreas.end()) { return false; } return true; } std::vector CellCache::getAreas() { std::vector areas; std::string last(""); StringCellIterator it = m_cellAreas.begin(); for (; it != m_cellAreas.end(); ++it) { if (last != (*it).first) { last = (*it).first; areas.push_back(last); } } return areas; } std::vector CellCache::getCellAreas(Cell* cell) { std::vector areas; StringCellIterator it = m_cellAreas.begin(); for (; it != m_cellAreas.end(); ++it) { if ((*it).second == cell) { areas.push_back((*it).first); } } return areas; } std::vector CellCache::getAreaCells(const std::string& id) { std::vector cells; StringCellPair result = m_cellAreas.equal_range(id); StringCellIterator it = result.first; for (; it != result.second; ++it) { cells.push_back((*it).second); } return cells; } bool CellCache::isCellInArea(const std::string& id, Cell* cell) { StringCellPair result = m_cellAreas.equal_range(id); StringCellIterator it = result.first; for (; it != result.second; ++it) { if ((*it).second == cell) { return true; } } return false; } Rect CellCache::calculateCurrentSize() { // set base size ModelCoordinate min, max; m_layer->getMinMaxCoordinates(min, max); Rect newsize(min.x, min.y, max.x, max.y); const std::vector& interacts = m_layer->getInteractLayers(); if (!interacts.empty()) { std::vector::const_iterator layit = interacts.begin(); for(; layit != interacts.end(); ++layit) { // set size (*layit)->getMinMaxCoordinates(min, max, m_layer); newsize.w = std::max(max.x, newsize.w); newsize.h = std::max(max.y, newsize.h); newsize.x = std::min(min.x, newsize.x); newsize.y = std::min(min.y, newsize.y); } } return newsize; } void CellCache::setStaticSize(bool staticSize) { m_staticSize = staticSize; } bool CellCache::isStaticSize() { return m_staticSize; } void CellCache::setBlockingUpdate(bool update) { m_blockingUpdate = update; } void CellCache::setSizeUpdate(bool update) { m_sizeUpdate = update; } void CellCache::update() { if (m_sizeUpdate) { resize(); m_sizeUpdate = false; } m_blockingUpdate = false; } } // FIFE