1 /*************************************************************************** 2 * Copyright (C) 2005-2019 by the FIFE team * 3 * http://www.fifengine.net * 4 * This file is part of FIFE. * 5 * * 6 * FIFE is free software; you can redistribute it and/or * 7 * modify it under the terms of the GNU Lesser General Public * 8 * License as published by the Free Software Foundation; either * 9 * version 2.1 of the License, or (at your option) any later version. * 10 * * 11 * This library is distributed in the hope that it will be useful, * 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 14 * Lesser General Public License for more details. * 15 * * 16 * You should have received a copy of the GNU Lesser General Public * 17 * License along with this library; if not, write to the * 18 * Free Software Foundation, Inc., * 19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * 20 ***************************************************************************/ 21 22 // Standard C++ library includes 23 24 // 3rd party library includes 25 26 // FIFE includes 27 // These includes are split up in two parts, separated by one empty line 28 // First block: files included from the FIFE root src directory 29 // Second block: files included from the same folder 30 #include "model/metamodel/grids/cellgrid.h" 31 #include "util/log/logger.h" 32 #include "util/structures/purge.h" 33 34 #include "cellcache.h" 35 #include "cell.h" 36 #include "layer.h" 37 #include "instance.h" 38 #include "map.h" 39 #include "instancetree.h" 40 41 namespace FIFE { 42 43 static Logger _log(LM_STRUCTURES); 44 45 class CellCacheChangeListener : public LayerChangeListener { 46 public: CellCacheChangeListener(Layer * layer)47 CellCacheChangeListener(Layer* layer) { 48 m_layer = layer; 49 } ~CellCacheChangeListener()50 virtual ~CellCacheChangeListener() { 51 } 52 onLayerChanged(Layer * layer,std::vector<Instance * > & instances)53 virtual void onLayerChanged(Layer* layer, std::vector<Instance*>& instances) { 54 for(std::vector<Instance*>::iterator i = instances.begin(); i != instances.end(); ++i) { 55 if ((*i)->isMultiCell()) { 56 bool rotchange = ((*i)->getChangeInfo() & ICHANGE_ROTATION) == ICHANGE_ROTATION; 57 bool locchange = ((*i)->getChangeInfo() & ICHANGE_LOC) == ICHANGE_LOC; 58 bool celchange = ((*i)->getChangeInfo() & ICHANGE_CELL) == ICHANGE_CELL; 59 bool blochange = ((*i)->getChangeInfo() & ICHANGE_BLOCK) == ICHANGE_BLOCK; 60 61 if (!rotchange && !locchange && !celchange && !blochange) { 62 continue; 63 } 64 65 int32_t oldrotation = (*i)->getOldRotation(); 66 int32_t newrotation = (*i)->getRotation(); 67 if (!rotchange) { 68 oldrotation = newrotation; 69 } 70 71 if (rotchange || locchange || celchange) { 72 // update visual positions 73 (*i)->updateMultiInstances(); 74 } 75 if (rotchange || celchange) { 76 // update cache positions 77 ModelCoordinate oldmc; 78 ModelCoordinate newmc; 79 if (m_layer == layer) { 80 oldmc = (*i)->getOldLocationRef().getLayerCoordinates(); 81 newmc = (*i)->getLocationRef().getLayerCoordinates(); 82 } else { 83 oldmc = m_layer->getCellGrid()->toLayerCoordinates( 84 layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef())); 85 newmc = m_layer->getCellGrid()->toLayerCoordinates( 86 layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef())); 87 } 88 89 if (!celchange) { 90 oldmc = newmc; 91 } 92 93 CellGrid* cg = m_layer->getCellGrid(); 94 const std::vector<Instance*>& multiinstances = (*i)->getMultiInstances(); 95 std::vector<Instance*>::const_iterator it = multiinstances.begin(); 96 for (; it != multiinstances.end(); ++it) { 97 // remove 98 std::vector<ModelCoordinate> coordinates = 99 cg->toMultiCoordinates(oldmc, (*it)->getObject()->getMultiPartCoordinates(oldrotation)); 100 std::vector<ModelCoordinate>::iterator mcit = coordinates.begin(); 101 for (; mcit != coordinates.end(); ++mcit) { 102 Cell* cell = m_layer->getCellCache()->getCell(*mcit); 103 if (cell) { 104 cell->removeInstance(*it); 105 } 106 } 107 // add 108 coordinates = cg->toMultiCoordinates(newmc, (*it)->getObject()->getMultiPartCoordinates(newrotation)); 109 mcit = coordinates.begin(); 110 for (; mcit != coordinates.end(); ++mcit) { 111 Cell* cell = m_layer->getCellCache()->getCell(*mcit); 112 if (cell) { 113 cell->addInstance(*it); 114 } 115 } 116 } 117 118 if (celchange) { 119 // leader instance 120 Cell* oldcell = m_layer->getCellCache()->getCell(oldmc); 121 Cell* newcell = m_layer->getCellCache()->getCell(newmc); 122 if (oldcell == newcell) { 123 continue; 124 } 125 if (oldcell) { 126 oldcell->removeInstance(*i); 127 } 128 if (newcell) { 129 newcell->addInstance(*i); 130 } 131 } 132 } 133 continue; 134 } 135 if ((*i)->getObject()->isMultiPart()) { 136 continue; 137 } 138 if (((*i)->getChangeInfo() & ICHANGE_BLOCK) == ICHANGE_BLOCK) { 139 ModelCoordinate mc; 140 if (m_layer == layer) { 141 mc = (*i)->getLocationRef().getLayerCoordinates(); 142 } else { 143 mc = m_layer->getCellGrid()->toLayerCoordinates( 144 layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef())); 145 } 146 Cell* cell = m_layer->getCellCache()->getCell(mc); 147 if (cell) { 148 cell->changeInstance(*i); 149 } 150 } 151 if (((*i)->getChangeInfo() & ICHANGE_CELL) == ICHANGE_CELL) { 152 ModelCoordinate oldmc; 153 ModelCoordinate newmc; 154 if (m_layer == layer) { 155 oldmc = (*i)->getOldLocationRef().getLayerCoordinates(); 156 newmc = (*i)->getLocationRef().getLayerCoordinates(); 157 } else { 158 oldmc = m_layer->getCellGrid()->toLayerCoordinates( 159 layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef())); 160 newmc = m_layer->getCellGrid()->toLayerCoordinates( 161 layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef())); 162 } 163 164 Cell* oldcell = m_layer->getCellCache()->getCell(oldmc); 165 Cell* newcell = m_layer->getCellCache()->getCell(newmc); 166 if (oldcell == newcell) { 167 continue; 168 } 169 if (oldcell) { 170 oldcell->removeInstance(*i); 171 } 172 if (newcell) { 173 newcell->addInstance(*i); 174 } 175 } 176 } 177 } 178 onInstanceCreate(Layer * layer,Instance * instance)179 virtual void onInstanceCreate(Layer* layer, Instance* instance) { 180 ModelCoordinate mc; 181 if (m_layer == layer) { 182 mc = instance->getLocationRef().getLayerCoordinates(); 183 } else { 184 mc = m_layer->getCellGrid()->toLayerCoordinates( 185 layer->getCellGrid()->toMapCoordinates(instance->getLocationRef().getExactLayerCoordinatesRef())); 186 } 187 188 CellCache* cache = m_layer->getCellCache(); 189 Location loc(m_layer); 190 loc.setLayerCoordinates(mc); 191 if (!cache->isInCellCache(loc)) { 192 cache->resize(); 193 } 194 if (instance->isMultiCell()) { 195 instance->updateMultiInstances(); 196 CellGrid* cg = m_layer->getCellGrid(); 197 const std::vector<Instance*>& multiinstances = instance->getMultiInstances(); 198 std::vector<Instance*>::const_iterator it = multiinstances.begin(); 199 for (; it != multiinstances.end(); ++it) { 200 std::vector<ModelCoordinate> coordinates = 201 cg->toMultiCoordinates(mc, (*it)->getObject()->getMultiPartCoordinates(instance->getRotation())); 202 std::vector<ModelCoordinate>::iterator mcit = coordinates.begin(); 203 for (; mcit != coordinates.end(); ++mcit) { 204 loc.setLayerCoordinates(*mcit); 205 if (!cache->isInCellCache(loc)) { 206 cache->resize(); 207 } 208 Cell* cell = cache->getCell(*mcit); 209 if (cell) { 210 cell->addInstance(*it); 211 } 212 } 213 } 214 } 215 Cell* cell = cache->getCell(mc); 216 if (cell) { 217 cell->addInstance(instance); 218 } 219 } 220 onInstanceDelete(Layer * layer,Instance * instance)221 virtual void onInstanceDelete(Layer* layer, Instance* instance) { 222 ModelCoordinate mc; 223 if (m_layer == layer) { 224 mc = instance->getLocationRef().getLayerCoordinates(); 225 } else { 226 mc = m_layer->getCellGrid()->toLayerCoordinates( 227 layer->getCellGrid()->toMapCoordinates(instance->getLocationRef().getExactLayerCoordinatesRef())); 228 } 229 230 CellCache* cache = m_layer->getCellCache(); 231 if (instance->isMultiCell()) { 232 instance->updateMultiInstances(); 233 CellGrid* cg = m_layer->getCellGrid(); 234 const std::vector<Instance*>& multiinstances = instance->getMultiInstances(); 235 std::vector<Instance*>::const_iterator it = multiinstances.begin(); 236 for (; it != multiinstances.end(); ++it) { 237 std::vector<ModelCoordinate> coordinates = 238 cg->toMultiCoordinates(mc, (*it)->getObject()->getMultiPartCoordinates(instance->getRotation())); 239 std::vector<ModelCoordinate>::iterator mcit = coordinates.begin(); 240 for (; mcit != coordinates.end(); ++mcit) { 241 Cell* cell = cache->getCell(*mcit); 242 if (cell) { 243 cell->removeInstance(*it); 244 } 245 } 246 } 247 } 248 Cell* cell = cache->getCell(mc); 249 if (cell) { 250 cell->removeInstance(instance); 251 } 252 // updates size on the next cache update (happens on same pump) 253 cache->setSizeUpdate(true); 254 } 255 256 private: 257 Layer* m_layer; 258 }; 259 Zone(uint32_t id)260 Zone::Zone(uint32_t id): 261 m_id(id) { 262 } 263 ~Zone()264 Zone::~Zone() { 265 for (std::set<Cell*>::iterator i = m_cells.begin(); i != m_cells.end(); ++i) { 266 (*i)->resetZone(); 267 } 268 } 269 addCell(Cell * cell)270 void Zone::addCell(Cell* cell) { 271 if (!cell->getZone()) { 272 cell->setZone(this); 273 m_cells.insert(cell); 274 } 275 } 276 removeCell(Cell * cell)277 void Zone::removeCell(Cell* cell) { 278 std::set<Cell*>::iterator i = m_cells.find(cell); 279 if (i != m_cells.end()) { 280 (*i)->resetZone(); 281 m_cells.erase(i); 282 } 283 } 284 mergeZone(Zone * zone)285 void Zone::mergeZone(Zone* zone) { 286 const std::set<Cell*>& cells = zone->getCells(); 287 m_cells.insert(cells.begin(), cells.end()); 288 for (std::set<Cell*>::const_iterator it = cells.begin(); it != cells.end(); ++it) { 289 (*it)->setZone(this); 290 } 291 zone->resetCells(); 292 } 293 getCells() const294 const std::set<Cell*>& Zone::getCells() const { 295 return m_cells; 296 } 297 resetCells()298 void Zone::resetCells() { 299 m_cells.clear(); 300 } 301 getId() const302 uint32_t Zone::getId() const { 303 return m_id; 304 } 305 getCellCount() const306 uint32_t Zone::getCellCount() const { 307 return static_cast<uint32_t>(m_cells.size()); 308 } 309 getTransitionCells(Layer * layer)310 std::vector<Cell*> Zone::getTransitionCells(Layer* layer) { 311 std::vector<Cell*> transitions; 312 std::set<Cell*>::iterator it = m_cells.begin(); 313 for (; it != m_cells.end(); ++it) { 314 TransitionInfo* trans = (*it)->getTransition(); 315 if (!trans) { 316 continue; 317 } 318 if (layer) { 319 if (layer == (*it)->getLayer()) { 320 transitions.push_back(*it); 321 } 322 } else { 323 transitions.push_back(*it); 324 } 325 } 326 return transitions; 327 } 328 329 class ZoneCellChangeListener : public CellChangeListener { 330 public: ZoneCellChangeListener(CellCache * cache)331 ZoneCellChangeListener(CellCache* cache) { 332 m_cache = cache; 333 } ~ZoneCellChangeListener()334 virtual ~ZoneCellChangeListener() { 335 } 336 onInstanceEnteredCell(Cell * cell,Instance * instance)337 virtual void onInstanceEnteredCell(Cell* cell, Instance* instance) { 338 339 } 340 onInstanceExitedCell(Cell * cell,Instance * instance)341 virtual void onInstanceExitedCell(Cell* cell, Instance* instance) { 342 343 } 344 onBlockingChangedCell(Cell * cell,CellTypeInfo type,bool blocks)345 virtual void onBlockingChangedCell(Cell* cell, CellTypeInfo type, bool blocks) { 346 if (blocks) { 347 cell->setZoneProtected(true); 348 m_cache->splitZone(cell); 349 } else { 350 Zone* z1 = cell->getZone(); 351 Zone* z2 = NULL; 352 const std::vector<Cell*>& neighbors = cell->getNeighbors(); 353 std::vector<Cell*>::const_iterator it = neighbors.begin(); 354 for (; it != neighbors.end(); ++it) { 355 Zone* z = (*it)->getZone(); 356 if (z && z != z1) { 357 z2 = z; 358 } 359 } 360 if (z1 && z2) { 361 cell->setZoneProtected(false); 362 m_cache->mergeZones(z1, z2); 363 } 364 } 365 } 366 367 private: 368 CellCache* m_cache; 369 }; 370 CellCache(Layer * layer)371 CellCache::CellCache(Layer* layer): 372 m_layer(layer), 373 m_defaultCostMulti(1.0), 374 m_defaultSpeedMulti(1.0), 375 m_neighborZ(-1), 376 m_blockingUpdate(false), 377 m_sizeUpdate(false), 378 m_searchNarrow(true), 379 m_staticSize(false) { 380 // create cell change listener 381 m_cellZoneListener = new ZoneCellChangeListener(this); 382 // set base size 383 ModelCoordinate min, max; 384 m_layer->getMinMaxCoordinates(min, max); 385 m_size.w = max.x; 386 m_size.h = max.y; 387 m_size.x = min.x; 388 m_size.y = min.y; 389 390 // create and add layer listener 391 m_cellListener = new CellCacheChangeListener(m_layer); 392 m_layer->addChangeListener(m_cellListener); 393 const std::vector<Layer*>& interacts = m_layer->getInteractLayers(); 394 if (!interacts.empty()) { 395 std::vector<Layer*>::const_iterator layit = interacts.begin(); 396 for(; layit != interacts.end(); ++layit) { 397 // set size 398 (*layit)->getMinMaxCoordinates(min, max, m_layer); 399 m_size.w = std::max(max.x, m_size.w); 400 m_size.h = std::max(max.y, m_size.h); 401 m_size.x = std::min(min.x, m_size.x); 402 m_size.y = std::min(min.y, m_size.y); 403 // add listener 404 (*layit)->addChangeListener(m_cellListener); 405 } 406 } 407 408 m_width = ABS(m_size.w - m_size.x) + 1; 409 m_height = ABS(m_size.h - m_size.y) + 1; 410 411 m_cells.resize(m_width); 412 for (uint32_t i = 0; i < m_width; ++i) { 413 m_cells[i].resize(m_height, NULL); 414 } 415 } 416 ~CellCache()417 CellCache::~CellCache() { 418 // reset cache 419 reset(); 420 // remove listener from layers 421 m_layer->removeChangeListener(m_cellListener); 422 const std::vector<Layer*>& interacts = m_layer->getInteractLayers(); 423 if (!interacts.empty()) { 424 std::vector<Layer*>::const_iterator layit = interacts.begin(); 425 for(; layit != interacts.end(); ++layit) { 426 (*layit)->removeChangeListener(m_cellListener); 427 } 428 } 429 // delete listener 430 delete m_cellListener; 431 delete m_cellZoneListener; 432 } 433 reset()434 void CellCache::reset() { 435 // delete zones 436 if (!m_zones.empty()) { 437 std::vector<Zone*>::iterator it = m_zones.begin(); 438 for (; it != m_zones.end(); ++it) { 439 delete *it; 440 } 441 m_zones.clear(); 442 } 443 // clear all containers 444 m_costsToCells.clear(); 445 m_costsTable.clear(); 446 m_costMultipliers.clear(); 447 m_speedMultipliers.clear(); 448 m_narrowCells.clear(); 449 m_cellAreas.clear(); 450 // delete cells 451 if (!m_cells.empty()) { 452 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin(); 453 for (; it != m_cells.end(); ++it) { 454 std::vector<Cell*>::iterator cit = (*it).begin(); 455 for (; cit != (*it).end(); ++cit) { 456 delete *cit; 457 } 458 } 459 m_cells.clear(); 460 } 461 // reset default cost and speed 462 m_defaultCostMulti = 1.0; 463 m_defaultSpeedMulti = 1.0; 464 // reset size 465 m_size.x = 0; 466 m_size.y = 0; 467 m_size.w = 0; 468 m_size.h = 0; 469 m_width = 0; 470 m_height = 0; 471 } 472 resize()473 void CellCache::resize() { 474 if (m_staticSize) { 475 return; 476 } 477 // get new size and check if it has changed 478 Rect newsize = calculateCurrentSize(); 479 resize(newsize); 480 } 481 resize(const Rect & rec)482 void CellCache::resize(const Rect& rec) { 483 // check if size has changed 484 Rect newsize = rec; 485 if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) { 486 uint32_t w = ABS(newsize.w - newsize.x) + 1; 487 uint32_t h = ABS(newsize.h - newsize.y) + 1; 488 489 std::vector<std::vector<Cell*> > cells; 490 cells.resize(w); 491 for (uint32_t i = 0; i < w; ++i) { 492 cells[i].resize(h, NULL); 493 } 494 const std::vector<Layer*>& interacts = m_layer->getInteractLayers(); 495 for(uint32_t y = 0; y < h; ++y) { 496 for(uint32_t x = 0; x < w; ++x) { 497 // transfer cells 498 ModelCoordinate mc(newsize.x+x, newsize.y+y); 499 Cell* cell = NULL; 500 int32_t old_x = mc.x - m_size.x; 501 int32_t old_y = mc.y - m_size.y; 502 // out of range in the old size, so we create a new cell 503 if (old_x < 0 || old_x >= static_cast<int32_t>(m_width) || old_y < 0 || old_y >= static_cast<int32_t>(m_height)) { 504 int32_t coordId = x + y * w; 505 cell = new Cell(coordId, mc, m_layer); 506 cells[x][y] = cell; 507 508 std::list<Instance*> cell_instances; 509 m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances); 510 if (!interacts.empty()) { 511 // fill interact Instances into Cell 512 std::vector<Layer*>::const_iterator it = interacts.begin(); 513 std::list<Instance*> interact_instances; 514 for(; it != interacts.end(); ++it) { 515 // convert coordinates 516 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); 517 ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); 518 // check interact layer for instances 519 (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); 520 if (!interact_instances.empty()) { 521 cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end()); 522 interact_instances.clear(); 523 } 524 } 525 } 526 if (!cell_instances.empty()) { 527 // add instances to cell 528 cell->addInstances(cell_instances); 529 } 530 // transfer ownership 531 } else { 532 cell = m_cells[static_cast<uint32_t>(old_x)][static_cast<uint32_t>(old_y)]; 533 m_cells[static_cast<uint32_t>(old_x)][static_cast<uint32_t>(old_y)] = NULL; 534 cells[x][y] = cell; 535 int32_t coordId = x + y * w; 536 cell->setCellId(coordId); 537 cell->resetNeighbors(); 538 } 539 } 540 } 541 // delete old unused cells 542 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin(); 543 for (; it != m_cells.end(); ++it) { 544 std::vector<Cell*>::iterator cit = (*it).begin(); 545 for (; cit != (*it).end(); ++cit) { 546 if (*cit) { 547 delete *cit; 548 *cit = NULL; 549 } 550 } 551 } 552 // use new values 553 m_cells = cells; 554 m_size = newsize; 555 m_width = w; 556 m_height = h; 557 558 bool zCheck = m_neighborZ != -1; 559 // fill neighbors into cells 560 it = m_cells.begin(); 561 for (; it != m_cells.end(); ++it) { 562 std::vector<Cell*>::iterator cit = (*it).begin(); 563 for (; cit != (*it).end(); ++cit) { 564 int32_t cellZ = (*cit)->getLayerCoordinates().z; 565 std::vector<ModelCoordinate> coordinates; 566 m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates); 567 for (std::vector<ModelCoordinate>::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) { 568 Cell* c = getCell(*mi); 569 if (*cit == c || !c) { 570 continue; 571 } 572 if (zCheck) { 573 if (ABS(c->getLayerCoordinates().z - cellZ) > m_neighborZ) { 574 continue; 575 } 576 } 577 (*cit)->addNeighbor(c); 578 } 579 } 580 } 581 } 582 } 583 createCells()584 void CellCache::createCells() { 585 const std::vector<Layer*>& interacts = m_layer->getInteractLayers(); 586 for(uint32_t y = 0; y < m_height; ++y) { 587 for(uint32_t x = 0; x < m_width; ++x) { 588 ModelCoordinate mc(m_size.x+x, m_size.y+y); 589 Cell* cell = getCell(mc); 590 if (!cell) { 591 cell = new Cell(convertCoordToInt(mc), mc, m_layer); 592 m_cells[x][y] = cell; 593 } 594 // fill Instances into Cell 595 std::list<Instance*> cell_instances; 596 m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances); 597 if (!interacts.empty()) { 598 // fill interact Instances into Cell 599 std::vector<Layer*>::const_iterator it = interacts.begin(); 600 std::list<Instance*> interact_instances; 601 for(; it != interacts.end(); ++it) { 602 // convert coordinates 603 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); 604 ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); 605 // check interact layer for instances 606 (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); 607 if (!interact_instances.empty()) { 608 cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end()); 609 interact_instances.clear(); 610 } 611 } 612 } 613 if (!cell_instances.empty()) { 614 // add instances to cell 615 cell->addInstances(cell_instances); 616 } 617 } 618 } 619 // fill neighbors into cells 620 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin(); 621 for (; it != m_cells.end(); ++it) { 622 std::vector<Cell*>::iterator cit = (*it).begin(); 623 for (; cit != (*it).end(); ++cit) { 624 uint8_t accessible = 0; 625 bool selfblocker = (*cit)->getCellType() == CTYPE_STATIC_BLOCKER || (*cit)->getCellType() == CTYPE_CELL_BLOCKER; 626 std::vector<ModelCoordinate> coordinates; 627 m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates); 628 for (std::vector<ModelCoordinate>::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) { 629 Cell* c = getCell(*mi); 630 if (*cit == c || !c) { 631 continue; 632 } 633 if (!selfblocker && c->getCellType() != CTYPE_STATIC_BLOCKER && 634 c->getCellType() != CTYPE_CELL_BLOCKER) { 635 ++accessible; 636 } 637 (*cit)->addNeighbor(c); 638 } 639 // add cell to narrow cells and add listener for zone change 640 if (m_searchNarrow && !selfblocker && accessible < 3) { 641 addNarrowCell(*cit); 642 } 643 } 644 } 645 // create Zones 646 it = m_cells.begin(); 647 for (; it != m_cells.end(); ++it) { 648 std::vector<Cell*>::iterator cit = (*it).begin(); 649 for (; cit != (*it).end(); ++cit) { 650 Cell* cell = *cit; 651 if (cell->getZone() || cell->isInserted()) { 652 continue; 653 } 654 if (cell->getCellType() == CTYPE_STATIC_BLOCKER || cell->getCellType() == CTYPE_CELL_BLOCKER) { 655 continue; 656 } 657 Zone* zone = createZone(); 658 cell->setInserted(true); 659 std::stack<Cell*> cellstack; 660 cellstack.push(cell); 661 while(!cellstack.empty()) { 662 Cell* c = cellstack.top(); 663 cellstack.pop(); 664 zone->addCell(c); 665 666 const std::vector<Cell*>& neighbors = c->getNeighbors(); 667 for (std::vector<Cell*>::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) { 668 Cell* nc = *nit; 669 if (!nc->isInserted() && 670 nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) { 671 nc->setInserted(true); 672 cellstack.push(nc); 673 } 674 } 675 } 676 } 677 } 678 } 679 forceUpdate()680 void CellCache::forceUpdate() { 681 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin(); 682 for (; it != m_cells.end(); ++it) { 683 std::vector<Cell*>::iterator cit = (*it).begin(); 684 for (; cit != (*it).end(); ++cit) { 685 (*cit)->updateCellInfo(); 686 } 687 } 688 } 689 addCell(Cell * cell)690 void CellCache::addCell(Cell* cell) { 691 ModelCoordinate mc = cell->getLayerCoordinates(); 692 m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell; 693 } 694 createCell(const ModelCoordinate & mc)695 Cell* CellCache::createCell(const ModelCoordinate& mc) { 696 Cell* cell = getCell(mc); 697 if (!cell) { 698 cell = new Cell(convertCoordToInt(mc), mc, m_layer); 699 m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell; 700 } 701 return cell; 702 } 703 getCell(const ModelCoordinate & mc)704 Cell* CellCache::getCell(const ModelCoordinate& mc) { 705 int32_t x = mc.x - m_size.x; 706 int32_t y = mc.y - m_size.y; 707 708 if (x < 0 || x >= static_cast<int32_t>(m_width) || y < 0 || y >= static_cast<int32_t>(m_height)) { 709 return NULL; 710 } 711 712 return m_cells[static_cast<uint32_t>(x)][static_cast<uint32_t>(y)]; 713 } 714 getCells()715 const std::vector<std::vector<Cell*> >& CellCache::getCells() { 716 return m_cells; 717 } 718 removeCell(Cell * cell)719 void CellCache::removeCell(Cell* cell) { 720 if (!m_costsToCells.empty()) { 721 removeCellFromCost(cell); 722 } 723 if (!m_costMultipliers.empty()) { 724 resetCostMultiplier(cell); 725 } 726 if (!m_speedMultipliers.empty()) { 727 resetSpeedMultiplier(cell); 728 } 729 if (!m_narrowCells.empty()) { 730 removeNarrowCell(cell); 731 } 732 if (!m_cellAreas.empty()) { 733 removeCellFromArea(cell); 734 } 735 } 736 addInteractOnRuntime(Layer * interact)737 void CellCache::addInteractOnRuntime(Layer* interact) { 738 interact->setInteract(true, m_layer->getId()); 739 m_layer->addInteractLayer(interact); 740 interact->addChangeListener(m_cellListener); 741 Rect newsize = calculateCurrentSize(); 742 if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) { 743 resize(); 744 } 745 // not optimal but needed if the grids have different geometry 746 for(uint32_t y = 0; y < m_height; ++y) { 747 for(uint32_t x = 0; x < m_width; ++x) { 748 ModelCoordinate mc(m_size.x+x, m_size.y+y); 749 Cell* cell = getCell(mc); 750 if (cell) { 751 // convert coordinates 752 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); 753 ModelCoordinate inter_mc = interact->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); 754 // check interact layer for instances 755 std::list<Instance*> interact_instances; 756 interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); 757 if (!interact_instances.empty()) { 758 // fill interact Instances into Cell 759 cell->addInstances(interact_instances); 760 } 761 } 762 } 763 } 764 } 765 removeInteractOnRuntime(Layer * interact)766 void CellCache::removeInteractOnRuntime(Layer* interact) { 767 interact->setInteract(false, ""); 768 m_layer->removeInteractLayer(interact); 769 Rect newsize = calculateCurrentSize(); 770 if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) { 771 resize(); 772 } 773 // not optimal but needed if the grids have different geometry 774 for(uint32_t y = 0; y < m_height; ++y) { 775 for(uint32_t x = 0; x < m_width; ++x) { 776 ModelCoordinate mc(m_size.x+x, m_size.y+y); 777 Cell* cell = getCell(mc); 778 if (cell) { 779 // convert coordinates 780 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc)); 781 ModelCoordinate inter_mc = interact->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc)); 782 // check interact layer for instances 783 std::list<Instance*> interact_instances; 784 interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances); 785 if (!interact_instances.empty()) { 786 // remove interact Instances from Cell 787 for (std::list<Instance*>::iterator it = interact_instances.begin(); it != interact_instances.end(); ++it) { 788 cell->removeInstance(*it); 789 } 790 } 791 } 792 } 793 } 794 } 795 getCellCacheChangeListener()796 LayerChangeListener* CellCache::getCellCacheChangeListener() { 797 return m_cellListener; 798 } 799 getLayer()800 Layer* CellCache::getLayer() { 801 return m_layer; 802 } 803 getSize()804 const Rect& CellCache::getSize() { 805 return m_size; 806 } 807 setSize(const Rect & rec)808 void CellCache::setSize(const Rect& rec) { 809 resize(rec); 810 } 811 getWidth()812 uint32_t CellCache::getWidth() { 813 return m_width; 814 } 815 getHeight()816 uint32_t CellCache::getHeight() { 817 return m_height; 818 } 819 isInCellCache(const Location & location) const820 bool CellCache::isInCellCache(const Location& location) const { 821 if (m_layer != location.getLayer()) { 822 return false; 823 } 824 int32_t x = location.getLayerCoordinates().x - m_size.x; 825 int32_t y = location.getLayerCoordinates().y - m_size.y; 826 827 if (x < 0 || x >= static_cast<int32_t>(m_width) || y < 0 || y >= static_cast<int32_t>(m_height)) { 828 return false; 829 } 830 return true; 831 } 832 convertCoordToInt(const ModelCoordinate & coord) const833 int32_t CellCache::convertCoordToInt(const ModelCoordinate& coord) const { 834 ModelCoordinate newcoords(coord.x - m_size.x, coord.y - m_size.y); 835 return newcoords.x + newcoords.y*m_width; 836 } 837 convertIntToCoord(const int32_t cell) const838 ModelCoordinate CellCache::convertIntToCoord(const int32_t cell) const { 839 ModelCoordinate coord((cell % m_width) + m_size.x, (cell / m_width) + m_size.y); 840 return coord; 841 } 842 getMaxIndex() const843 int32_t CellCache::getMaxIndex() const { 844 int32_t max_index = m_width*m_height; 845 return max_index; 846 } 847 setMaxNeighborZ(int32_t z)848 void CellCache::setMaxNeighborZ(int32_t z) { 849 m_neighborZ = z; 850 } 851 getMaxNeighborZ()852 int32_t CellCache::getMaxNeighborZ() { 853 return m_neighborZ; 854 } 855 getCellsInLine(const ModelCoordinate & pt1,const ModelCoordinate & pt2,bool blocker)856 std::vector<Cell*> CellCache::getCellsInLine(const ModelCoordinate& pt1, const ModelCoordinate& pt2, bool blocker) { 857 std::vector<Cell*> cells; 858 std::vector<ModelCoordinate> coords = m_layer->getCellGrid()->getCoordinatesInLine(pt1, pt2); 859 for (std::vector<ModelCoordinate>::iterator it = coords.begin(); it != coords.end(); ++it) { 860 Cell* c = getCell(*it); 861 if (c) { 862 if (blocker && c->getCellType() != CTYPE_NO_BLOCKER) { 863 return cells; 864 } 865 cells.push_back(c); 866 } else { 867 return cells; 868 } 869 } 870 return cells; 871 } 872 getCellsInRect(const Rect & rec)873 std::vector<Cell*> CellCache::getCellsInRect(const Rect& rec) { 874 std::vector<Cell*> cells; 875 cells.reserve(rec.w * rec.h); 876 877 ModelCoordinate current(rec.x, rec.y); 878 ModelCoordinate target(rec.x+rec.w, rec.y+rec.h); 879 for (; current.y < target.y; ++current.y) { 880 current.x = rec.x; 881 for (; current.x < target.x; ++current.x) { 882 Cell* c = getCell(current); 883 if (c) { 884 cells.push_back(c); 885 } 886 } 887 } 888 return cells; 889 } 890 getBlockingCellsInRect(const Rect & rec)891 std::vector<Cell*> CellCache::getBlockingCellsInRect(const Rect& rec) { 892 std::vector<Cell*> cells; 893 cells.reserve(rec.w * rec.h); 894 895 ModelCoordinate current(rec.x, rec.y); 896 ModelCoordinate target(rec.x + rec.w, rec.y + rec.h); 897 for (; current.y < target.y; ++current.y) { 898 current.x = rec.x; 899 for (; current.x < target.x; ++current.x) { 900 Cell* c = getCell(current); 901 if (c && c->getCellType() != CTYPE_NO_BLOCKER) { 902 cells.push_back(c); 903 } 904 } 905 } 906 return cells; 907 } 908 getCellsInCircle(const ModelCoordinate & center,uint16_t radius)909 std::vector<Cell*> CellCache::getCellsInCircle(const ModelCoordinate& center, uint16_t radius) { 910 std::vector<Cell*> cells; 911 //radius power 2 912 uint16_t radiusp2 = (radius+1) * radius; 913 914 ModelCoordinate current(center.x-radius, center.y-radius); 915 ModelCoordinate target(center.x+radius, center.y+radius); 916 for (; current.y < center.y; current.y++) { 917 current.x = center.x-radius; 918 for (; current.x < center.x; current.x++) { 919 Cell* c = getCell(current); 920 if (c) { 921 uint16_t dx = center.x - current.x; 922 uint16_t dy = center.y - current.y; 923 uint16_t distance = dx*dx + dy*dy; 924 if (distance <= radiusp2) { 925 cells.push_back(c); 926 927 current.x = center.x + dx; 928 c = getCell(current); 929 if (c) cells.push_back(c); 930 931 current.y = center.y + dy; 932 c = getCell(current); 933 if (c) cells.push_back(c); 934 935 current.x = center.x-dx; 936 c = getCell(current); 937 if (c) cells.push_back(c); 938 939 current.y = center.y-dy; 940 941 } 942 } 943 } 944 } 945 current.x = center.x; 946 current.y = center.y-radius; 947 for (; current.y <= target.y; current.y++) { 948 Cell* c = getCell(current); 949 if (c) cells.push_back(c); 950 } 951 952 current.y = center.y; 953 current.x = center.x-radius; 954 for (; current.x <= target.x; current.x++) { 955 Cell* c = getCell(current); 956 if (c) cells.push_back(c); 957 } 958 return cells; 959 } 960 getCellsInCircleSegment(const ModelCoordinate & center,uint16_t radius,int32_t sangle,int32_t eangle)961 std::vector<Cell*> CellCache::getCellsInCircleSegment(const ModelCoordinate& center, uint16_t radius, int32_t sangle, int32_t eangle) { 962 std::vector<Cell*> cells; 963 ExactModelCoordinate exactCenter(center.x, center.y); 964 std::vector<Cell*> tmpCells = getCellsInCircle(center, radius); 965 int32_t s = (sangle + 360) % 360; 966 int32_t e = (eangle + 360) % 360; 967 bool greater = (s > e) ? true : false; 968 for (std::vector<Cell*>::iterator it = tmpCells.begin(); it != tmpCells.end(); ++it) { 969 int32_t angle = getAngleBetween(exactCenter, intPt2doublePt((*it)->getLayerCoordinates())); 970 if (greater) { 971 if (angle >= s || angle <= e) { 972 cells.push_back(*it); 973 } 974 } else { 975 if (angle >= s && angle <= e) { 976 cells.push_back(*it); 977 } 978 } 979 } 980 return cells; 981 } 982 registerCost(const std::string & costId,double cost)983 void CellCache::registerCost(const std::string& costId, double cost) { 984 std::pair<std::map<std::string, double>::iterator, bool> insertiter; 985 insertiter = m_costsTable.insert(std::pair<std::string, double>(costId, cost)); 986 if (insertiter.second == false) { 987 double& old_cost = insertiter.first->second; 988 old_cost = cost; 989 } 990 } 991 unregisterCost(const std::string & costId)992 void CellCache::unregisterCost(const std::string& costId) { 993 std::map<std::string, double>::iterator it = m_costsTable.find(costId); 994 if (it != m_costsTable.end()) { 995 m_costsTable.erase(it); 996 m_costsToCells.erase(costId); 997 } 998 } 999 getCost(const std::string & costId)1000 double CellCache::getCost(const std::string& costId) { 1001 std::map<std::string, double>::iterator it = m_costsTable.find(costId); 1002 if (it != m_costsTable.end()) { 1003 return it->second; 1004 } 1005 return 0.0; 1006 } 1007 existsCost(const std::string & costId)1008 bool CellCache::existsCost(const std::string& costId) { 1009 std::map<std::string, double>::iterator it = m_costsTable.find(costId); 1010 if (it != m_costsTable.end()) { 1011 return true; 1012 } 1013 return false; 1014 } 1015 getCosts()1016 std::list<std::string> CellCache::getCosts() { 1017 std::list<std::string> costs; 1018 std::map<std::string, double>::iterator it = m_costsTable.begin(); 1019 for (; it != m_costsTable.end(); ++it) { 1020 costs.push_back((*it).first); 1021 } 1022 return costs; 1023 } 1024 unregisterAllCosts()1025 void CellCache::unregisterAllCosts() { 1026 m_costsTable.clear(); 1027 m_costsToCells.clear(); 1028 } 1029 addCellToCost(const std::string & costId,Cell * cell)1030 void CellCache::addCellToCost(const std::string& costId, Cell* cell) { 1031 if (existsCost(costId)) { 1032 StringCellPair result = m_costsToCells.equal_range(costId); 1033 StringCellIterator it = result.first; 1034 for (; it != result.second; ++it) { 1035 if ((*it).second == cell) { 1036 return; 1037 } 1038 } 1039 m_costsToCells.insert(std::pair<std::string, Cell*>(costId, cell)); 1040 } 1041 } 1042 addCellsToCost(const std::string & costId,const std::vector<Cell * > & cells)1043 void CellCache::addCellsToCost(const std::string& costId, const std::vector<Cell*>& cells) { 1044 std::vector<Cell*>::const_iterator it = cells.begin(); 1045 for (; it != cells.end(); ++it) { 1046 addCellToCost(costId, *it); 1047 } 1048 } 1049 removeCellFromCost(Cell * cell)1050 void CellCache::removeCellFromCost(Cell* cell) { 1051 StringCellIterator it = m_costsToCells.begin(); 1052 for (; it != m_costsToCells.end();) { 1053 if ((*it).second == cell) { 1054 m_costsToCells.erase(it++); 1055 } else { 1056 ++it; 1057 } 1058 } 1059 } 1060 removeCellFromCost(const std::string & costId,Cell * cell)1061 void CellCache::removeCellFromCost(const std::string& costId, Cell* cell) { 1062 StringCellPair result = m_costsToCells.equal_range(costId); 1063 StringCellIterator it = result.first; 1064 for (; it != result.second; ++it) { 1065 if ((*it).second == cell) { 1066 m_costsToCells.erase(it); 1067 break; 1068 } 1069 } 1070 } 1071 removeCellsFromCost(const std::string & costId,const std::vector<Cell * > & cells)1072 void CellCache::removeCellsFromCost(const std::string& costId, const std::vector<Cell*>& cells) { 1073 std::vector<Cell*>::const_iterator it = cells.begin(); 1074 for (; it != cells.end(); ++it) { 1075 removeCellFromCost(costId, *it); 1076 } 1077 } 1078 getCostCells(const std::string & costId)1079 std::vector<Cell*> CellCache::getCostCells(const std::string& costId) { 1080 std::vector<Cell*> cells; 1081 StringCellPair result = m_costsToCells.equal_range(costId); 1082 StringCellIterator it = result.first; 1083 for (; it != result.second; ++it) { 1084 cells.push_back((*it).second); 1085 } 1086 return cells; 1087 } 1088 getCellCosts(Cell * cell)1089 std::vector<std::string> CellCache::getCellCosts(Cell* cell) { 1090 std::vector<std::string> costs; 1091 StringCellIterator it = m_costsToCells.begin(); 1092 for (; it != m_costsToCells.end(); ++it) { 1093 if ((*it).second == cell) { 1094 costs.push_back((*it).first); 1095 } 1096 } 1097 return costs; 1098 } 1099 existsCostForCell(const std::string & costId,Cell * cell)1100 bool CellCache::existsCostForCell(const std::string& costId, Cell* cell) { 1101 StringCellPair result = m_costsToCells.equal_range(costId); 1102 StringCellIterator it = result.first; 1103 for (; it != result.second; ++it) { 1104 if ((*it).second == cell) { 1105 return true; 1106 } 1107 } 1108 return false; 1109 } 1110 getAdjacentCost(const ModelCoordinate & adjacent,const ModelCoordinate & next)1111 double CellCache::getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next) { 1112 double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next); 1113 Cell* nextcell = getCell(next); 1114 if (nextcell) { 1115 if (!nextcell->defaultCost()) { 1116 cost *= nextcell->getCostMultiplier(); 1117 } else { 1118 cost *= m_defaultCostMulti; 1119 } 1120 } 1121 return cost; 1122 } 1123 getAdjacentCost(const ModelCoordinate & adjacent,const ModelCoordinate & next,const std::string & costId)1124 double CellCache::getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next, const std::string& costId) { 1125 double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next); 1126 Cell* nextcell = getCell(next); 1127 if (nextcell) { 1128 if (existsCostForCell(costId, nextcell)) { 1129 cost *= getCost(costId); 1130 } else { 1131 if (!nextcell->defaultCost()) { 1132 cost *= nextcell->getCostMultiplier(); 1133 } else { 1134 cost *= m_defaultCostMulti; 1135 } 1136 } 1137 } 1138 return cost; 1139 } 1140 getCellSpeedMultiplier(const ModelCoordinate & cell,double & multiplier)1141 bool CellCache::getCellSpeedMultiplier(const ModelCoordinate& cell, double& multiplier) { 1142 Cell* nextcell = getCell(cell); 1143 if (nextcell) { 1144 if (!nextcell->defaultSpeed()) { 1145 multiplier = nextcell->getSpeedMultiplier(); 1146 return true; 1147 } 1148 } 1149 multiplier = m_defaultSpeedMulti; 1150 return false; 1151 } 1152 setDefaultCostMultiplier(double multi)1153 void CellCache::setDefaultCostMultiplier(double multi) { 1154 m_defaultCostMulti = multi; 1155 } 1156 getDefaultCostMultiplier()1157 double CellCache::getDefaultCostMultiplier() { 1158 return m_defaultCostMulti; 1159 } 1160 setDefaultSpeedMultiplier(double multi)1161 void CellCache::setDefaultSpeedMultiplier(double multi) { 1162 m_defaultSpeedMulti = multi; 1163 } 1164 getDefaultSpeedMultiplier()1165 double CellCache::getDefaultSpeedMultiplier() { 1166 return m_defaultSpeedMulti; 1167 } 1168 isDefaultCost(Cell * cell)1169 bool CellCache::isDefaultCost(Cell* cell) { 1170 std::map<Cell*, double>::iterator it = m_costMultipliers.find(cell); 1171 if (it != m_costMultipliers.end()) { 1172 return false; 1173 } 1174 return true; 1175 } 1176 setCostMultiplier(Cell * cell,double multi)1177 void CellCache::setCostMultiplier(Cell* cell, double multi) { 1178 std::pair<std::map<Cell*, double>::iterator, bool> insertiter = 1179 m_costMultipliers.insert(std::pair<Cell*, double>(cell, multi)); 1180 if (insertiter.second == false) { 1181 double& old = insertiter.first->second; 1182 old = multi; 1183 } 1184 } 1185 getCostMultiplier(Cell * cell)1186 double CellCache::getCostMultiplier(Cell* cell) { 1187 double cost = 1.0; 1188 std::map<Cell*, double>::iterator it = m_costMultipliers.find(cell); 1189 if (it != m_costMultipliers.end()) { 1190 cost = it->second; 1191 } 1192 return cost; 1193 } 1194 resetCostMultiplier(Cell * cell)1195 void CellCache::resetCostMultiplier(Cell* cell) { 1196 m_costMultipliers.erase(cell); 1197 } 1198 isDefaultSpeed(Cell * cell)1199 bool CellCache::isDefaultSpeed(Cell* cell) { 1200 std::map<Cell*, double>::iterator it = m_speedMultipliers.find(cell); 1201 if (it != m_speedMultipliers.end()) { 1202 return false; 1203 } 1204 return true; 1205 } 1206 setSpeedMultiplier(Cell * cell,double multi)1207 void CellCache::setSpeedMultiplier(Cell* cell, double multi) { 1208 std::pair<std::map<Cell*, double>::iterator, bool> insertiter = 1209 m_speedMultipliers.insert(std::pair<Cell*, double>(cell, multi)); 1210 if (insertiter.second == false) { 1211 double& old = insertiter.first->second; 1212 old = multi; 1213 } 1214 } 1215 getSpeedMultiplier(Cell * cell)1216 double CellCache::getSpeedMultiplier(Cell* cell) { 1217 double speed = 1.0; 1218 std::map<Cell*, double>::iterator it = m_speedMultipliers.find(cell); 1219 if (it != m_speedMultipliers.end()) { 1220 speed = it->second; 1221 } 1222 return speed; 1223 } 1224 resetSpeedMultiplier(Cell * cell)1225 void CellCache::resetSpeedMultiplier(Cell* cell) { 1226 m_speedMultipliers.erase(cell); 1227 } 1228 addTransition(Cell * cell)1229 void CellCache::addTransition(Cell* cell) { 1230 m_transitions.push_back(cell); 1231 } 1232 removeTransition(Cell * cell)1233 void CellCache::removeTransition(Cell* cell) { 1234 std::vector<Cell*>::iterator it = m_transitions.begin(); 1235 for (; it != m_transitions.end(); ++it) { 1236 if (cell == *it) { 1237 m_transitions.erase(it); 1238 break; 1239 } 1240 } 1241 } 1242 getTransitionCells(Layer * layer)1243 std::vector<Cell*> CellCache::getTransitionCells(Layer* layer) { 1244 if (!layer) { 1245 return m_transitions; 1246 } 1247 std::vector<Cell*> cells; 1248 std::vector<Cell*>::iterator it = m_transitions.begin(); 1249 for (; it != m_transitions.end(); ++it) { 1250 TransitionInfo* trans = (*it)->getTransition(); 1251 if (trans) { 1252 if (trans->m_layer == layer) { 1253 cells.push_back(*it); 1254 } 1255 } 1256 } 1257 return cells; 1258 } 1259 createZone()1260 Zone* CellCache::createZone() { 1261 uint32_t id = 0; 1262 bool search = true; 1263 while (search) { 1264 bool found = false; 1265 if (!m_zones.empty()) { 1266 for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) { 1267 if ((*i)->getId() == id) { 1268 found = true; 1269 ++id; 1270 break; 1271 } 1272 } 1273 } 1274 search = found; 1275 } 1276 Zone* zi = new Zone(id); 1277 m_zones.push_back(zi); 1278 1279 return zi; 1280 } 1281 getZones()1282 const std::vector<Zone*>& CellCache::getZones() { 1283 return m_zones; 1284 } 1285 getZone(uint32_t id)1286 Zone* CellCache::getZone(uint32_t id) { 1287 Zone* zi = 0; 1288 for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) { 1289 if ((*i)->getId() == id) { 1290 zi = (*i); 1291 break; 1292 } 1293 } 1294 1295 if (!zi) { 1296 zi = new Zone(id); 1297 m_zones.push_back(zi); 1298 } 1299 1300 return zi; 1301 } 1302 removeZone(Zone * zone)1303 void CellCache::removeZone(Zone* zone) { 1304 for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) { 1305 if (*i == zone) { 1306 delete *i; 1307 m_zones.erase(i); 1308 break; 1309 } 1310 } 1311 } 1312 splitZone(Cell * cell)1313 void CellCache::splitZone(Cell* cell) { 1314 Zone* currentZone = cell->getZone(); 1315 if (!currentZone) { 1316 return; 1317 } 1318 1319 Zone* newZone = createZone(); 1320 std::stack<Cell*> cellstack; 1321 const std::vector<Cell*>& neighbors = cell->getNeighbors(); 1322 for (std::vector<Cell*>::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) { 1323 Cell* nc = *nit; 1324 if (nc->isInserted() && !nc->isZoneProtected() && 1325 nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) { 1326 cellstack.push(nc); 1327 break; 1328 } 1329 } 1330 1331 while(!cellstack.empty()) { 1332 Cell* c = cellstack.top(); 1333 cellstack.pop(); 1334 1335 currentZone->removeCell(c); 1336 newZone->addCell(c); 1337 c->setInserted(true); 1338 if (c->isZoneProtected()) { 1339 continue; 1340 } 1341 const std::vector<Cell*>& neigh = c->getNeighbors(); 1342 for (std::vector<Cell*>::const_iterator nit = neigh.begin(); nit != neigh.end(); ++nit) { 1343 Cell* nc = *nit; 1344 if (nc->getZone() == currentZone && nc->isInserted() && 1345 nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) { 1346 cellstack.push(nc); 1347 nc->setInserted(false); 1348 } 1349 } 1350 } 1351 if (currentZone->getCellCount() == 0) { 1352 removeZone(currentZone); 1353 } 1354 } 1355 mergeZones(Zone * zone1,Zone * zone2)1356 void CellCache::mergeZones(Zone* zone1, Zone* zone2) { 1357 if (!zone1 || !zone2) { 1358 return; 1359 } 1360 Zone* addZone = zone2; 1361 Zone* oldZone = zone1; 1362 if (zone1->getCellCount() > zone2->getCellCount()) { 1363 addZone = zone1; 1364 oldZone = zone2; 1365 } 1366 addZone->mergeZone(oldZone); 1367 removeZone(oldZone); 1368 } 1369 addNarrowCell(Cell * cell)1370 void CellCache::addNarrowCell(Cell* cell) { 1371 std::pair<std::set<Cell*>::iterator, bool> insertiter = m_narrowCells.insert(cell); 1372 if (insertiter.second) { 1373 cell->addChangeListener(m_cellZoneListener); 1374 } 1375 } 1376 getNarrowCells()1377 const std::set<Cell*>& CellCache::getNarrowCells() { 1378 return m_narrowCells; 1379 } 1380 removeNarrowCell(Cell * cell)1381 void CellCache::removeNarrowCell(Cell* cell) { 1382 std::set<Cell*>::iterator it = m_narrowCells.find(cell); 1383 if (it != m_narrowCells.end()) { 1384 (*it)->removeChangeListener(m_cellZoneListener); 1385 m_narrowCells.erase(it); 1386 } 1387 } 1388 resetNarrowCells()1389 void CellCache::resetNarrowCells() { 1390 std::set<Cell*>::const_iterator it = m_narrowCells.begin(); 1391 for (; it != m_narrowCells.end(); ++it) { 1392 (*it)->removeChangeListener(m_cellZoneListener); 1393 } 1394 m_narrowCells.clear(); 1395 } 1396 isSearchNarrowCells()1397 bool CellCache::isSearchNarrowCells() { 1398 return m_searchNarrow; 1399 } 1400 setSearchNarrowCells(bool search)1401 void CellCache::setSearchNarrowCells(bool search) { 1402 m_searchNarrow = search; 1403 } 1404 addCellToArea(const std::string & id,Cell * cell)1405 void CellCache::addCellToArea(const std::string& id, Cell* cell) { 1406 m_cellAreas.insert(std::pair<std::string, Cell*>(id, cell)); 1407 } 1408 addCellsToArea(const std::string & id,const std::vector<Cell * > & cells)1409 void CellCache::addCellsToArea(const std::string& id, const std::vector<Cell*>& cells) { 1410 std::vector<Cell*>::const_iterator it = cells.begin(); 1411 for (; it != cells.end(); ++it) { 1412 addCellToArea(id, *it); 1413 } 1414 } 1415 removeCellFromArea(Cell * cell)1416 void CellCache::removeCellFromArea(Cell* cell) { 1417 StringCellIterator it = m_cellAreas.begin(); 1418 while (it != m_cellAreas.end()) { 1419 if ((*it).second == cell) { 1420 m_cellAreas.erase(it++); 1421 } else { 1422 ++it; 1423 } 1424 } 1425 } 1426 removeCellFromArea(const std::string & id,Cell * cell)1427 void CellCache::removeCellFromArea(const std::string& id, Cell* cell) { 1428 StringCellPair result = m_cellAreas.equal_range(id); 1429 StringCellIterator it = result.first; 1430 for (; it != result.second; ++it) { 1431 if ((*it).second == cell) { 1432 m_cellAreas.erase(it); 1433 break; 1434 } 1435 } 1436 } 1437 removeCellsFromArea(const std::string & id,const std::vector<Cell * > & cells)1438 void CellCache::removeCellsFromArea(const std::string& id, const std::vector<Cell*>& cells) { 1439 std::vector<Cell*>::const_iterator it = cells.begin(); 1440 for (; it != cells.end(); ++it) { 1441 removeCellFromArea(id, *it); 1442 } 1443 } 1444 removeArea(const std::string & id)1445 void CellCache::removeArea(const std::string& id) { 1446 m_cellAreas.erase(id); 1447 } 1448 existsArea(const std::string & id)1449 bool CellCache::existsArea(const std::string& id) { 1450 StringCellIterator it = m_cellAreas.find(id); 1451 if (it == m_cellAreas.end()) { 1452 return false; 1453 } 1454 return true; 1455 } 1456 getAreas()1457 std::vector<std::string> CellCache::getAreas() { 1458 std::vector<std::string> areas; 1459 std::string last(""); 1460 StringCellIterator it = m_cellAreas.begin(); 1461 for (; it != m_cellAreas.end(); ++it) { 1462 if (last != (*it).first) { 1463 last = (*it).first; 1464 areas.push_back(last); 1465 } 1466 } 1467 return areas; 1468 } 1469 getCellAreas(Cell * cell)1470 std::vector<std::string> CellCache::getCellAreas(Cell* cell) { 1471 std::vector<std::string> areas; 1472 StringCellIterator it = m_cellAreas.begin(); 1473 for (; it != m_cellAreas.end(); ++it) { 1474 if ((*it).second == cell) { 1475 areas.push_back((*it).first); 1476 } 1477 } 1478 return areas; 1479 } 1480 getAreaCells(const std::string & id)1481 std::vector<Cell*> CellCache::getAreaCells(const std::string& id) { 1482 std::vector<Cell*> cells; 1483 StringCellPair result = m_cellAreas.equal_range(id); 1484 StringCellIterator it = result.first; 1485 for (; it != result.second; ++it) { 1486 cells.push_back((*it).second); 1487 } 1488 return cells; 1489 } 1490 isCellInArea(const std::string & id,Cell * cell)1491 bool CellCache::isCellInArea(const std::string& id, Cell* cell) { 1492 StringCellPair result = m_cellAreas.equal_range(id); 1493 StringCellIterator it = result.first; 1494 for (; it != result.second; ++it) { 1495 if ((*it).second == cell) { 1496 return true; 1497 } 1498 } 1499 return false; 1500 } 1501 calculateCurrentSize()1502 Rect CellCache::calculateCurrentSize() { 1503 // set base size 1504 ModelCoordinate min, max; 1505 m_layer->getMinMaxCoordinates(min, max); 1506 Rect newsize(min.x, min.y, max.x, max.y); 1507 1508 const std::vector<Layer*>& interacts = m_layer->getInteractLayers(); 1509 if (!interacts.empty()) { 1510 std::vector<Layer*>::const_iterator layit = interacts.begin(); 1511 for(; layit != interacts.end(); ++layit) { 1512 // set size 1513 (*layit)->getMinMaxCoordinates(min, max, m_layer); 1514 newsize.w = std::max(max.x, newsize.w); 1515 newsize.h = std::max(max.y, newsize.h); 1516 newsize.x = std::min(min.x, newsize.x); 1517 newsize.y = std::min(min.y, newsize.y); 1518 } 1519 } 1520 return newsize; 1521 } 1522 setStaticSize(bool staticSize)1523 void CellCache::setStaticSize(bool staticSize) { 1524 m_staticSize = staticSize; 1525 } 1526 isStaticSize()1527 bool CellCache::isStaticSize() { 1528 return m_staticSize; 1529 } 1530 setBlockingUpdate(bool update)1531 void CellCache::setBlockingUpdate(bool update) { 1532 m_blockingUpdate = update; 1533 } 1534 setSizeUpdate(bool update)1535 void CellCache::setSizeUpdate(bool update) { 1536 m_sizeUpdate = update; 1537 } 1538 update()1539 void CellCache::update() { 1540 if (m_sizeUpdate) { 1541 resize(); 1542 m_sizeUpdate = false; 1543 } 1544 m_blockingUpdate = false; 1545 } 1546 } // FIFE 1547