FIFE  6e1afdbeda11afe9ac53e6023a4be96ef88f1dc6
cellcache.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2017 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
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 
46  public:
48  m_layer = layer;
49  }
51  }
52 
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 {
84  layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef()));
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 {
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 {
159  layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef()));
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 
179  virtual void onInstanceCreate(Layer* layer, Instance* instance) {
180  ModelCoordinate mc;
181  if (m_layer == layer) {
182  mc = instance->getLocationRef().getLayerCoordinates();
183  } else {
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 
221  virtual void onInstanceDelete(Layer* layer, Instance* instance) {
222  ModelCoordinate mc;
223  if (m_layer == layer) {
224  mc = instance->getLocationRef().getLayerCoordinates();
225  } else {
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:
258  };
259 
261  m_id(id) {
262  }
263 
265  for (std::set<Cell*>::iterator i = m_cells.begin(); i != m_cells.end(); ++i) {
266  (*i)->resetZone();
267  }
268  }
269 
270  void Zone::addCell(Cell* cell) {
271  if (!cell->getZone()) {
272  cell->setZone(this);
273  m_cells.insert(cell);
274  }
275  }
276 
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 
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 
294  const std::set<Cell*>& Zone::getCells() const {
295  return m_cells;
296  }
297 
299  m_cells.clear();
300  }
301 
303  return m_id;
304  }
305 
307  return static_cast<uint32_t>(m_cells.size());
308  }
309 
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 
330  public:
332  m_cache = cache;
333  }
335  }
336 
337  virtual void onInstanceEnteredCell(Cell* cell, Instance* instance) {
338 
339  }
340 
341  virtual void onInstanceExitedCell(Cell* cell, Instance* instance) {
342 
343  }
344 
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:
369  };
370 
372  m_layer(layer),
373  m_defaultCostMulti(1.0),
374  m_defaultSpeedMulti(1.0),
375  m_neighborZ(-1),
376  m_blockingUpdate(false),
377  m_fowUpdate(false),
378  m_sizeUpdate(false),
379  m_updated(false),
380  m_searchNarrow(true),
381  m_staticSize(false) {
382  // create cell change listener
384  // set base size
385  ModelCoordinate min, max;
386  m_layer->getMinMaxCoordinates(min, max);
387  m_size.w = max.x;
388  m_size.h = max.y;
389  m_size.x = min.x;
390  m_size.y = min.y;
391 
392  // create and add layer listener
395  const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
396  if (!interacts.empty()) {
397  std::vector<Layer*>::const_iterator layit = interacts.begin();
398  for(; layit != interacts.end(); ++layit) {
399  // set size
400  (*layit)->getMinMaxCoordinates(min, max, m_layer);
401  m_size.w = std::max(max.x, m_size.w);
402  m_size.h = std::max(max.y, m_size.h);
403  m_size.x = std::min(min.x, m_size.x);
404  m_size.y = std::min(min.y, m_size.y);
405  // add listener
406  (*layit)->addChangeListener(m_cellListener);
407  }
408  }
409 
410  m_width = ABS(m_size.w - m_size.x) + 1;
411  m_height = ABS(m_size.h - m_size.y) + 1;
412 
413  m_cells.resize(m_width);
414  for (uint32_t i = 0; i < m_width; ++i) {
415  m_cells[i].resize(m_height, NULL);
416  }
417  }
418 
420  // reset cache
421  reset();
422  // remove listener from layers
424  const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
425  if (!interacts.empty()) {
426  std::vector<Layer*>::const_iterator layit = interacts.begin();
427  for(; layit != interacts.end(); ++layit) {
428  (*layit)->removeChangeListener(m_cellListener);
429  }
430  }
431  // delete listener
432  delete m_cellListener;
433  delete m_cellZoneListener;
434  }
435 
437  // delete zones
438  if (!m_zones.empty()) {
439  std::vector<Zone*>::iterator it = m_zones.begin();
440  for (; it != m_zones.end(); ++it) {
441  delete *it;
442  }
443  m_zones.clear();
444  }
445  // clear all containers
446  m_costsToCells.clear();
447  m_costsTable.clear();
448  m_costMultipliers.clear();
449  m_speedMultipliers.clear();
450  m_narrowCells.clear();
451  m_cellAreas.clear();
452  // delete cells
453  if (!m_cells.empty()) {
454  std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
455  for (; it != m_cells.end(); ++it) {
456  std::vector<Cell*>::iterator cit = (*it).begin();
457  for (; cit != (*it).end(); ++cit) {
458  delete *cit;
459  }
460  }
461  m_cells.clear();
462  }
463  // reset default cost and speed
464  m_defaultCostMulti = 1.0;
465  m_defaultSpeedMulti = 1.0;
466  // reset size
467  m_size.x = 0;
468  m_size.y = 0;
469  m_size.w = 0;
470  m_size.h = 0;
471  m_width = 0;
472  m_height = 0;
473  }
474 
476  if (m_staticSize) {
477  return;
478  }
479  // get new size and check if it has changed
480  Rect newsize = calculateCurrentSize();
481  resize(newsize);
482  }
483 
484  void CellCache::resize(const Rect& rec) {
485  // check if size has changed
486  Rect newsize = rec;
487  if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) {
488  uint32_t w = ABS(newsize.w - newsize.x) + 1;
489  uint32_t h = ABS(newsize.h - newsize.y) + 1;
490 
491  std::vector<std::vector<Cell*> > cells;
492  cells.resize(w);
493  for (uint32_t i = 0; i < w; ++i) {
494  cells[i].resize(h, NULL);
495  }
496  const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
497  for(uint32_t y = 0; y < h; ++y) {
498  for(uint32_t x = 0; x < w; ++x) {
499  // transfer cells
500  ModelCoordinate mc(newsize.x+x, newsize.y+y);
501  Cell* cell = NULL;
502  int32_t old_x = mc.x - m_size.x;
503  int32_t old_y = mc.y - m_size.y;
504  // out of range in the old size, so we create a new cell
505  if (old_x < 0 || old_x >= static_cast<int32_t>(m_width) || old_y < 0 || old_y >= static_cast<int32_t>(m_height)) {
506  int32_t coordId = x + y * w;
507  cell = new Cell(coordId, mc, m_layer);
508  cells[x][y] = cell;
509 
510  std::list<Instance*> cell_instances;
511  m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances);
512  if (!interacts.empty()) {
513  // fill interact Instances into Cell
514  std::vector<Layer*>::const_iterator it = interacts.begin();
515  std::list<Instance*> interact_instances;
516  for(; it != interacts.end(); ++it) {
517  // convert coordinates
519  ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc));
520  // check interact layer for instances
521  (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
522  if (!interact_instances.empty()) {
523  cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end());
524  interact_instances.clear();
525  }
526  }
527  }
528  if (!cell_instances.empty()) {
529  // add instances to cell
530  cell->addInstances(cell_instances);
531  }
532  // transfer ownership
533  } else {
534  cell = m_cells[static_cast<uint32_t>(old_x)][static_cast<uint32_t>(old_y)];
535  m_cells[static_cast<uint32_t>(old_x)][static_cast<uint32_t>(old_y)] = NULL;
536  cells[x][y] = cell;
537  int32_t coordId = x + y * w;
538  cell->setCellId(coordId);
539  cell->resetNeighbors();
540  }
541  }
542  }
543  // delete old unused cells
544  std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
545  for (; it != m_cells.end(); ++it) {
546  std::vector<Cell*>::iterator cit = (*it).begin();
547  for (; cit != (*it).end(); ++cit) {
548  if (*cit) {
549  delete *cit;
550  *cit = NULL;
551  }
552  }
553  }
554  // use new values
555  m_cells = cells;
556  m_size = newsize;
557  m_width = w;
558  m_height = h;
559 
560  bool zCheck = m_neighborZ != -1;
561  // fill neighbors into cells
562  it = m_cells.begin();
563  for (; it != m_cells.end(); ++it) {
564  std::vector<Cell*>::iterator cit = (*it).begin();
565  for (; cit != (*it).end(); ++cit) {
566  int32_t cellZ = (*cit)->getLayerCoordinates().z;
567  std::vector<ModelCoordinate> coordinates;
568  m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates);
569  for (std::vector<ModelCoordinate>::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) {
570  Cell* c = getCell(*mi);
571  if (*cit == c || !c) {
572  continue;
573  }
574  if (zCheck) {
575  if (ABS(c->getLayerCoordinates().z - cellZ) > m_neighborZ) {
576  continue;
577  }
578  }
579  (*cit)->addNeighbor(c);
580  }
581  }
582  }
583  }
584  }
585 
587  const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
588  for(uint32_t y = 0; y < m_height; ++y) {
589  for(uint32_t x = 0; x < m_width; ++x) {
590  ModelCoordinate mc(m_size.x+x, m_size.y+y);
591  Cell* cell = getCell(mc);
592  if (!cell) {
593  cell = new Cell(convertCoordToInt(mc), mc, m_layer);
594  m_cells[x][y] = cell;
595  }
596  // fill Instances into Cell
597  std::list<Instance*> cell_instances;
598  m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances);
599  if (!interacts.empty()) {
600  // fill interact Instances into Cell
601  std::vector<Layer*>::const_iterator it = interacts.begin();
602  std::list<Instance*> interact_instances;
603  for(; it != interacts.end(); ++it) {
604  // convert coordinates
606  ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc));
607  // check interact layer for instances
608  (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
609  if (!interact_instances.empty()) {
610  cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end());
611  interact_instances.clear();
612  }
613  }
614  }
615  if (!cell_instances.empty()) {
616  // add instances to cell
617  cell->addInstances(cell_instances);
618  }
619  }
620  }
621  // fill neighbors into cells
622  std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
623  for (; it != m_cells.end(); ++it) {
624  std::vector<Cell*>::iterator cit = (*it).begin();
625  for (; cit != (*it).end(); ++cit) {
626  uint8_t accessible = 0;
627  bool selfblocker = (*cit)->getCellType() == CTYPE_STATIC_BLOCKER || (*cit)->getCellType() == CTYPE_CELL_BLOCKER;
628  std::vector<ModelCoordinate> coordinates;
629  m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates);
630  for (std::vector<ModelCoordinate>::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) {
631  Cell* c = getCell(*mi);
632  if (*cit == c || !c) {
633  continue;
634  }
635  if (!selfblocker && c->getCellType() != CTYPE_STATIC_BLOCKER &&
637  ++accessible;
638  }
639  (*cit)->addNeighbor(c);
640  }
641  // add cell to narrow cells and add listener for zone change
642  if (m_searchNarrow && !selfblocker && accessible < 3) {
643  addNarrowCell(*cit);
644  }
645  }
646  }
647  // create Zones
648  it = m_cells.begin();
649  for (; it != m_cells.end(); ++it) {
650  std::vector<Cell*>::iterator cit = (*it).begin();
651  for (; cit != (*it).end(); ++cit) {
652  Cell* cell = *cit;
653  if (cell->getZone() || cell->isInserted()) {
654  continue;
655  }
656  if (cell->getCellType() == CTYPE_STATIC_BLOCKER || cell->getCellType() == CTYPE_CELL_BLOCKER) {
657  continue;
658  }
659  Zone* zone = createZone();
660  cell->setInserted(true);
661  std::stack<Cell*> cellstack;
662  cellstack.push(cell);
663  while(!cellstack.empty()) {
664  Cell* c = cellstack.top();
665  cellstack.pop();
666  zone->addCell(c);
667 
668  const std::vector<Cell*>& neighbors = c->getNeighbors();
669  for (std::vector<Cell*>::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) {
670  Cell* nc = *nit;
671  if (!nc->isInserted() &&
673  nc->setInserted(true);
674  cellstack.push(nc);
675  }
676  }
677  }
678  }
679  }
680  }
681 
683  std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
684  for (; it != m_cells.end(); ++it) {
685  std::vector<Cell*>::iterator cit = (*it).begin();
686  for (; cit != (*it).end(); ++cit) {
687  (*cit)->updateCellInfo();
688  }
689  }
690  }
691 
692  void CellCache::addCell(Cell* cell) {
694  m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell;
695  }
696 
698  Cell* cell = getCell(mc);
699  if (!cell) {
700  cell = new Cell(convertCoordToInt(mc), mc, m_layer);
701  m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell;
702  }
703  return cell;
704  }
705 
707  int32_t x = mc.x - m_size.x;
708  int32_t y = mc.y - m_size.y;
709 
710  if (x < 0 || x >= static_cast<int32_t>(m_width) || y < 0 || y >= static_cast<int32_t>(m_height)) {
711  return NULL;
712  }
713 
714  return m_cells[static_cast<uint32_t>(x)][static_cast<uint32_t>(y)];
715  }
716 
717  const std::vector<std::vector<Cell*> >& CellCache::getCells() {
718  return m_cells;
719  }
720 
722  if (!m_costsToCells.empty()) {
723  removeCellFromCost(cell);
724  }
725  if (!m_costMultipliers.empty()) {
726  resetCostMultiplier(cell);
727  }
728  if (!m_speedMultipliers.empty()) {
729  resetSpeedMultiplier(cell);
730  }
731  if (!m_narrowCells.empty()) {
732  removeNarrowCell(cell);
733  }
734  if (!m_cellAreas.empty()) {
735  removeCellFromArea(cell);
736  }
737  }
738 
740  interact->setInteract(true, m_layer->getId());
741  m_layer->addInteractLayer(interact);
743  Rect newsize = calculateCurrentSize();
744  if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) {
745  resize();
746  }
747  // not optimal but needed if the grids have different geometry
748  for(uint32_t y = 0; y < m_height; ++y) {
749  for(uint32_t x = 0; x < m_width; ++x) {
750  ModelCoordinate mc(m_size.x+x, m_size.y+y);
751  Cell* cell = getCell(mc);
752  if (cell) {
753  // convert coordinates
756  // check interact layer for instances
757  std::list<Instance*> interact_instances;
758  interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
759  if (!interact_instances.empty()) {
760  // fill interact Instances into Cell
761  cell->addInstances(interact_instances);
762  }
763  }
764  }
765  }
766  }
767 
769  interact->setInteract(false, "");
770  m_layer->removeInteractLayer(interact);
771  Rect newsize = calculateCurrentSize();
772  if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) {
773  resize();
774  }
775  // not optimal but needed if the grids have different geometry
776  for(uint32_t y = 0; y < m_height; ++y) {
777  for(uint32_t x = 0; x < m_width; ++x) {
778  ModelCoordinate mc(m_size.x+x, m_size.y+y);
779  Cell* cell = getCell(mc);
780  if (cell) {
781  // convert coordinates
784  // check interact layer for instances
785  std::list<Instance*> interact_instances;
786  interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
787  if (!interact_instances.empty()) {
788  // remove interact Instances from Cell
789  for (std::list<Instance*>::iterator it = interact_instances.begin(); it != interact_instances.end(); ++it) {
790  cell->removeInstance(*it);
791  }
792  }
793  }
794  }
795  }
796  }
797 
799  return m_cellListener;
800  }
801 
803  return m_layer;
804  }
805 
807  return m_size;
808  }
809 
810  void CellCache::setSize(const Rect& rec) {
811  resize(rec);
812  }
813 
815  return m_width;
816  }
817 
819  return m_height;
820  }
821 
822  bool CellCache::isInCellCache(const Location& location) const {
823  if (m_layer != location.getLayer()) {
824  return false;
825  }
826  int32_t x = location.getLayerCoordinates().x - m_size.x;
827  int32_t y = location.getLayerCoordinates().y - m_size.y;
828 
829  if (x < 0 || x >= static_cast<int32_t>(m_width) || y < 0 || y >= static_cast<int32_t>(m_height)) {
830  return false;
831  }
832  return true;
833  }
834 
835  int32_t CellCache::convertCoordToInt(const ModelCoordinate& coord) const {
836  ModelCoordinate newcoords(coord.x - m_size.x, coord.y - m_size.y);
837  return newcoords.x + newcoords.y*m_width;
838  }
839 
840  ModelCoordinate CellCache::convertIntToCoord(const int32_t cell) const {
841  ModelCoordinate coord((cell % m_width) + m_size.x, (cell / m_width) + m_size.y);
842  return coord;
843  }
844 
845  int32_t CellCache::getMaxIndex() const {
846  int32_t max_index = m_width*m_height;
847  return max_index;
848  }
849 
850  void CellCache::setMaxNeighborZ(int32_t z) {
851  m_neighborZ = z;
852  }
853 
855  return m_neighborZ;
856  }
857 
858  void CellCache::setUpdated(bool updated) {
859  m_updated = updated;
860  }
861 
863  return m_updated;
864  }
865 
866  std::vector<Cell*> CellCache::getCellsInLine(const ModelCoordinate& pt1, const ModelCoordinate& pt2, bool blocker) {
867  std::vector<Cell*> cells;
868  std::vector<ModelCoordinate> coords = m_layer->getCellGrid()->getCoordinatesInLine(pt1, pt2);
869  for (std::vector<ModelCoordinate>::iterator it = coords.begin(); it != coords.end(); ++it) {
870  Cell* c = getCell(*it);
871  if (c) {
872  if (blocker && c->getCellType() != CTYPE_NO_BLOCKER) {
873  return cells;
874  }
875  cells.push_back(c);
876  } else {
877  return cells;
878  }
879  }
880  return cells;
881  }
882 
883  std::vector<Cell*> CellCache::getCellsInRect(const Rect& rec) {
884  std::vector<Cell*> cells;
885 
886  ModelCoordinate current(rec.x, rec.y);
887  ModelCoordinate target(rec.x+rec.w, rec.y+rec.h);
888  for (; current.y < target.y; ++current.y) {
889  current.x = rec.x;
890  for (; current.x < target.x; ++current.x) {
891  Cell* c = getCell(current);
892  if (c) {
893  cells.push_back(c);
894  }
895  }
896  }
897  return cells;
898  }
899 
900  std::vector<Cell*> CellCache::getCellsInCircle(const ModelCoordinate& center, uint16_t radius) {
901  std::vector<Cell*> cells;
902  //radius power 2
903  uint16_t radiusp2 = (radius+1) * radius;
904 
905  ModelCoordinate current(center.x-radius, center.y-radius);
906  ModelCoordinate target(center.x+radius, center.y+radius);
907  for (; current.y < center.y; current.y++) {
908  current.x = center.x-radius;
909  for (; current.x < center.x; current.x++) {
910  Cell* c = getCell(current);
911  if (c) {
912  uint16_t dx = center.x - current.x;
913  uint16_t dy = center.y - current.y;
914  uint16_t distance = dx*dx + dy*dy;
915  if (distance <= radiusp2) {
916  cells.push_back(c);
917 
918  current.x = center.x + dx;
919  c = getCell(current);
920  if (c) cells.push_back(c);
921 
922  current.y = center.y + dy;
923  c = getCell(current);
924  if (c) cells.push_back(c);
925 
926  current.x = center.x-dx;
927  c = getCell(current);
928  if (c) cells.push_back(c);
929 
930  current.y = center.y-dy;
931 
932  }
933  }
934  }
935  }
936  current.x = center.x;
937  current.y = center.y-radius;
938  for (; current.y <= target.y; current.y++) {
939  Cell* c = getCell(current);
940  if (c) cells.push_back(c);
941  }
942 
943  current.y = center.y;
944  current.x = center.x-radius;
945  for (; current.x <= target.x; current.x++) {
946  Cell* c = getCell(current);
947  if (c) cells.push_back(c);
948  }
949  return cells;
950  }
951 
952  std::vector<Cell*> CellCache::getCellsInCircleSegment(const ModelCoordinate& center, uint16_t radius, int32_t sangle, int32_t eangle) {
953  std::vector<Cell*> cells;
954  ExactModelCoordinate exactCenter(center.x, center.y);
955  std::vector<Cell*> tmpCells = getCellsInCircle(center, radius);
956  int32_t s = (sangle + 360) % 360;
957  int32_t e = (eangle + 360) % 360;
958  bool greater = (s > e) ? true : false;
959  for (std::vector<Cell*>::iterator it = tmpCells.begin(); it != tmpCells.end(); ++it) {
960  int32_t angle = getAngleBetween(exactCenter, intPt2doublePt((*it)->getLayerCoordinates()));
961  if (greater) {
962  if (angle >= s || angle <= e) {
963  cells.push_back(*it);
964  }
965  } else {
966  if (angle >= s && angle <= e) {
967  cells.push_back(*it);
968  }
969  }
970  }
971  return cells;
972  }
973 
974  void CellCache::registerCost(const std::string& costId, double cost) {
975  std::pair<std::map<std::string, double>::iterator, bool> insertiter;
976  insertiter = m_costsTable.insert(std::pair<std::string, double>(costId, cost));
977  if (insertiter.second == false) {
978  double& old_cost = insertiter.first->second;
979  old_cost = cost;
980  }
981  }
982 
983  void CellCache::unregisterCost(const std::string& costId) {
984  std::map<std::string, double>::iterator it = m_costsTable.find(costId);
985  if (it != m_costsTable.end()) {
986  m_costsTable.erase(it);
987  m_costsToCells.erase(costId);
988  }
989  }
990 
991  double CellCache::getCost(const std::string& costId) {
992  std::map<std::string, double>::iterator it = m_costsTable.find(costId);
993  if (it != m_costsTable.end()) {
994  return it->second;
995  }
996  return 0.0;
997  }
998 
999  bool CellCache::existsCost(const std::string& costId) {
1000  std::map<std::string, double>::iterator it = m_costsTable.find(costId);
1001  if (it != m_costsTable.end()) {
1002  return true;
1003  }
1004  return false;
1005  }
1006 
1007  std::list<std::string> CellCache::getCosts() {
1008  std::list<std::string> costs;
1009  std::map<std::string, double>::iterator it = m_costsTable.begin();
1010  for (; it != m_costsTable.end(); ++it) {
1011  costs.push_back((*it).first);
1012  }
1013  return costs;
1014  }
1015 
1017  m_costsTable.clear();
1018  m_costsToCells.clear();
1019  }
1020 
1021  void CellCache::addCellToCost(const std::string& costId, Cell* cell) {
1022  if (existsCost(costId)) {
1023  StringCellPair result = m_costsToCells.equal_range(costId);
1024  StringCellIterator it = result.first;
1025  for (; it != result.second; ++it) {
1026  if ((*it).second == cell) {
1027  return;
1028  }
1029  }
1030  m_costsToCells.insert(std::pair<std::string, Cell*>(costId, cell));
1031  }
1032  }
1033 
1034  void CellCache::addCellsToCost(const std::string& costId, const std::vector<Cell*>& cells) {
1035  std::vector<Cell*>::const_iterator it = cells.begin();
1036  for (; it != cells.end(); ++it) {
1037  addCellToCost(costId, *it);
1038  }
1039  }
1040 
1042  StringCellIterator it = m_costsToCells.begin();
1043  for (; it != m_costsToCells.end();) {
1044  if ((*it).second == cell) {
1045  m_costsToCells.erase(it++);
1046  } else {
1047  ++it;
1048  }
1049  }
1050  }
1051 
1052  void CellCache::removeCellFromCost(const std::string& costId, Cell* cell) {
1053  StringCellPair result = m_costsToCells.equal_range(costId);
1054  StringCellIterator it = result.first;
1055  for (; it != result.second; ++it) {
1056  if ((*it).second == cell) {
1057  m_costsToCells.erase(it);
1058  break;
1059  }
1060  }
1061  }
1062 
1063  void CellCache::removeCellsFromCost(const std::string& costId, const std::vector<Cell*>& cells) {
1064  std::vector<Cell*>::const_iterator it = cells.begin();
1065  for (; it != cells.end(); ++it) {
1066  removeCellFromCost(costId, *it);
1067  }
1068  }
1069 
1070  std::vector<Cell*> CellCache::getCostCells(const std::string& costId) {
1071  std::vector<Cell*> cells;
1072  StringCellPair result = m_costsToCells.equal_range(costId);
1073  StringCellIterator it = result.first;
1074  for (; it != result.second; ++it) {
1075  cells.push_back((*it).second);
1076  }
1077  return cells;
1078  }
1079 
1080  std::vector<std::string> CellCache::getCellCosts(Cell* cell) {
1081  std::vector<std::string> costs;
1082  StringCellIterator it = m_costsToCells.begin();
1083  for (; it != m_costsToCells.end(); ++it) {
1084  if ((*it).second == cell) {
1085  costs.push_back((*it).first);
1086  }
1087  }
1088  return costs;
1089  }
1090 
1091  bool CellCache::existsCostForCell(const std::string& costId, Cell* cell) {
1092  StringCellPair result = m_costsToCells.equal_range(costId);
1093  StringCellIterator it = result.first;
1094  for (; it != result.second; ++it) {
1095  if ((*it).second == cell) {
1096  return true;
1097  }
1098  }
1099  return false;
1100  }
1101 
1103  double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next);
1104  Cell* nextcell = getCell(next);
1105  if (nextcell) {
1106  if (!nextcell->defaultCost()) {
1107  cost *= nextcell->getCostMultiplier();
1108  } else {
1109  cost *= m_defaultCostMulti;
1110  }
1111  }
1112  return cost;
1113  }
1114 
1115  double CellCache::getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next, const std::string& costId) {
1116  double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next);
1117  Cell* nextcell = getCell(next);
1118  if (nextcell) {
1119  if (existsCostForCell(costId, nextcell)) {
1120  cost *= getCost(costId);
1121  } else {
1122  if (!nextcell->defaultCost()) {
1123  cost *= nextcell->getCostMultiplier();
1124  } else {
1125  cost *= m_defaultCostMulti;
1126  }
1127  }
1128  }
1129  return cost;
1130  }
1131 
1132  bool CellCache::getCellSpeedMultiplier(const ModelCoordinate& cell, double& multiplier) {
1133  Cell* nextcell = getCell(cell);
1134  if (nextcell) {
1135  if (!nextcell->defaultSpeed()) {
1136  multiplier = nextcell->getSpeedMultiplier();
1137  return true;
1138  }
1139  }
1140  multiplier = m_defaultSpeedMulti;
1141  return false;
1142  }
1143 
1145  m_defaultCostMulti = multi;
1146  }
1147 
1149  return m_defaultCostMulti;
1150  }
1151 
1153  m_defaultSpeedMulti = multi;
1154  }
1155 
1157  return m_defaultSpeedMulti;
1158  }
1159 
1161  std::map<Cell*, double>::iterator it = m_costMultipliers.find(cell);
1162  if (it != m_costMultipliers.end()) {
1163  return false;
1164  }
1165  return true;
1166  }
1167 
1168  void CellCache::setCostMultiplier(Cell* cell, double multi) {
1169  std::pair<std::map<Cell*, double>::iterator, bool> insertiter =
1170  m_costMultipliers.insert(std::pair<Cell*, double>(cell, multi));
1171  if (insertiter.second == false) {
1172  double& old = insertiter.first->second;
1173  old = multi;
1174  }
1175  }
1176 
1178  double cost = 1.0;
1179  std::map<Cell*, double>::iterator it = m_costMultipliers.find(cell);
1180  if (it != m_costMultipliers.end()) {
1181  cost = it->second;
1182  }
1183  return cost;
1184  }
1185 
1187  m_costMultipliers.erase(cell);
1188  }
1189 
1191  std::map<Cell*, double>::iterator it = m_speedMultipliers.find(cell);
1192  if (it != m_speedMultipliers.end()) {
1193  return false;
1194  }
1195  return true;
1196  }
1197 
1198  void CellCache::setSpeedMultiplier(Cell* cell, double multi) {
1199  std::pair<std::map<Cell*, double>::iterator, bool> insertiter =
1200  m_speedMultipliers.insert(std::pair<Cell*, double>(cell, multi));
1201  if (insertiter.second == false) {
1202  double& old = insertiter.first->second;
1203  old = multi;
1204  }
1205  }
1206 
1208  double speed = 1.0;
1209  std::map<Cell*, double>::iterator it = m_speedMultipliers.find(cell);
1210  if (it != m_speedMultipliers.end()) {
1211  speed = it->second;
1212  }
1213  return speed;
1214  }
1215 
1217  m_speedMultipliers.erase(cell);
1218  }
1219 
1221  m_transitions.push_back(cell);
1222  }
1223 
1225  std::vector<Cell*>::iterator it = m_transitions.begin();
1226  for (; it != m_transitions.end(); ++it) {
1227  if (cell == *it) {
1228  m_transitions.erase(it);
1229  break;
1230  }
1231  }
1232  }
1233 
1234  std::vector<Cell*> CellCache::getTransitionCells(Layer* layer) {
1235  if (!layer) {
1236  return m_transitions;
1237  }
1238  std::vector<Cell*> cells;
1239  std::vector<Cell*>::iterator it = m_transitions.begin();
1240  for (; it != m_transitions.end(); ++it) {
1241  TransitionInfo* trans = (*it)->getTransition();
1242  if (trans) {
1243  if (trans->m_layer == layer) {
1244  cells.push_back(*it);
1245  }
1246  }
1247  }
1248  return cells;
1249  }
1250 
1252  uint32_t id = 0;
1253  bool search = true;
1254  while (search) {
1255  bool found = false;
1256  if (!m_zones.empty()) {
1257  for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) {
1258  if ((*i)->getId() == id) {
1259  found = true;
1260  ++id;
1261  break;
1262  }
1263  }
1264  }
1265  search = found;
1266  }
1267  Zone* zi = new Zone(id);
1268  m_zones.push_back(zi);
1269 
1270  return zi;
1271  }
1272 
1273  const std::vector<Zone*>& CellCache::getZones() {
1274  return m_zones;
1275  }
1276 
1278  Zone* zi = 0;
1279  for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) {
1280  if ((*i)->getId() == id) {
1281  zi = (*i);
1282  break;
1283  }
1284  }
1285 
1286  if (!zi) {
1287  zi = new Zone(id);
1288  m_zones.push_back(zi);
1289  }
1290 
1291  return zi;
1292  }
1293 
1295  for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) {
1296  if (*i == zone) {
1297  delete *i;
1298  m_zones.erase(i);
1299  break;
1300  }
1301  }
1302  }
1303 
1305  Zone* currentZone = cell->getZone();
1306  if (!currentZone) {
1307  return;
1308  }
1309 
1310  Zone* newZone = createZone();
1311  std::stack<Cell*> cellstack;
1312  const std::vector<Cell*>& neighbors = cell->getNeighbors();
1313  for (std::vector<Cell*>::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) {
1314  Cell* nc = *nit;
1315  if (nc->isInserted() && !nc->isZoneProtected() &&
1317  cellstack.push(nc);
1318  break;
1319  }
1320  }
1321 
1322  while(!cellstack.empty()) {
1323  Cell* c = cellstack.top();
1324  cellstack.pop();
1325 
1326  currentZone->removeCell(c);
1327  newZone->addCell(c);
1328  c->setInserted(true);
1329  if (c->isZoneProtected()) {
1330  continue;
1331  }
1332  const std::vector<Cell*>& neigh = c->getNeighbors();
1333  for (std::vector<Cell*>::const_iterator nit = neigh.begin(); nit != neigh.end(); ++nit) {
1334  Cell* nc = *nit;
1335  if (nc->getZone() == currentZone && nc->isInserted() &&
1337  cellstack.push(nc);
1338  nc->setInserted(false);
1339  }
1340  }
1341  }
1342  if (currentZone->getCellCount() == 0) {
1343  removeZone(currentZone);
1344  }
1345  }
1346 
1347  void CellCache::mergeZones(Zone* zone1, Zone* zone2) {
1348  if (!zone1 || !zone2) {
1349  return;
1350  }
1351  Zone* addZone = zone2;
1352  Zone* oldZone = zone1;
1353  if (zone1->getCellCount() > zone2->getCellCount()) {
1354  addZone = zone1;
1355  oldZone = zone2;
1356  }
1357  addZone->mergeZone(oldZone);
1358  removeZone(oldZone);
1359  }
1360 
1362  std::pair<std::set<Cell*>::iterator, bool> insertiter = m_narrowCells.insert(cell);
1363  if (insertiter.second) {
1365  }
1366  }
1367 
1368  const std::set<Cell*>& CellCache::getNarrowCells() {
1369  return m_narrowCells;
1370  }
1371 
1373  std::set<Cell*>::iterator it = m_narrowCells.find(cell);
1374  if (it != m_narrowCells.end()) {
1375  (*it)->removeChangeListener(m_cellZoneListener);
1376  m_narrowCells.erase(it);
1377  }
1378  }
1379 
1381  std::set<Cell*>::const_iterator it = m_narrowCells.begin();
1382  for (; it != m_narrowCells.end(); ++it) {
1383  (*it)->removeChangeListener(m_cellZoneListener);
1384  }
1385  m_narrowCells.clear();
1386  }
1387 
1389  return m_searchNarrow;
1390  }
1391 
1393  m_searchNarrow = search;
1394  }
1395 
1396  void CellCache::addCellToArea(const std::string& id, Cell* cell) {
1397  m_cellAreas.insert(std::pair<std::string, Cell*>(id, cell));
1398  }
1399 
1400  void CellCache::addCellsToArea(const std::string& id, const std::vector<Cell*>& cells) {
1401  std::vector<Cell*>::const_iterator it = cells.begin();
1402  for (; it != cells.end(); ++it) {
1403  addCellToArea(id, *it);
1404  }
1405  }
1406 
1408  StringCellIterator it = m_cellAreas.begin();
1409  while (it != m_cellAreas.end()) {
1410  if ((*it).second == cell) {
1411  m_cellAreas.erase(it++);
1412  } else {
1413  ++it;
1414  }
1415  }
1416  }
1417 
1418  void CellCache::removeCellFromArea(const std::string& id, Cell* cell) {
1419  StringCellPair result = m_cellAreas.equal_range(id);
1420  StringCellIterator it = result.first;
1421  for (; it != result.second; ++it) {
1422  if ((*it).second == cell) {
1423  m_cellAreas.erase(it);
1424  break;
1425  }
1426  }
1427  }
1428 
1429  void CellCache::removeCellsFromArea(const std::string& id, const std::vector<Cell*>& cells) {
1430  std::vector<Cell*>::const_iterator it = cells.begin();
1431  for (; it != cells.end(); ++it) {
1432  removeCellFromArea(id, *it);
1433  }
1434  }
1435 
1436  void CellCache::removeArea(const std::string& id) {
1437  m_cellAreas.erase(id);
1438  }
1439 
1440  bool CellCache::existsArea(const std::string& id) {
1441  StringCellIterator it = m_cellAreas.find(id);
1442  if (it == m_cellAreas.end()) {
1443  return false;
1444  }
1445  return true;
1446  }
1447 
1448  std::vector<std::string> CellCache::getAreas() {
1449  std::vector<std::string> areas;
1450  std::string last("");
1451  StringCellIterator it = m_cellAreas.begin();
1452  for (; it != m_cellAreas.end(); ++it) {
1453  if (last != (*it).first) {
1454  last = (*it).first;
1455  areas.push_back(last);
1456  }
1457  }
1458  return areas;
1459  }
1460 
1461  std::vector<std::string> CellCache::getCellAreas(Cell* cell) {
1462  std::vector<std::string> areas;
1463  StringCellIterator it = m_cellAreas.begin();
1464  for (; it != m_cellAreas.end(); ++it) {
1465  if ((*it).second == cell) {
1466  areas.push_back((*it).first);
1467  }
1468  }
1469  return areas;
1470  }
1471 
1472  std::vector<Cell*> CellCache::getAreaCells(const std::string& id) {
1473  std::vector<Cell*> cells;
1474  StringCellPair result = m_cellAreas.equal_range(id);
1475  StringCellIterator it = result.first;
1476  for (; it != result.second; ++it) {
1477  cells.push_back((*it).second);
1478  }
1479  return cells;
1480  }
1481 
1482  bool CellCache::isCellInArea(const std::string& id, Cell* cell) {
1483  StringCellPair result = m_cellAreas.equal_range(id);
1484  StringCellIterator it = result.first;
1485  for (; it != result.second; ++it) {
1486  if ((*it).second == cell) {
1487  return true;
1488  }
1489  }
1490  return false;
1491  }
1492 
1494  // set base size
1495  ModelCoordinate min, max;
1496  m_layer->getMinMaxCoordinates(min, max);
1497  Rect newsize(min.x, min.y, max.x, max.y);
1498 
1499  const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
1500  if (!interacts.empty()) {
1501  std::vector<Layer*>::const_iterator layit = interacts.begin();
1502  for(; layit != interacts.end(); ++layit) {
1503  // set size
1504  (*layit)->getMinMaxCoordinates(min, max, m_layer);
1505  newsize.w = std::max(max.x, newsize.w);
1506  newsize.h = std::max(max.y, newsize.h);
1507  newsize.x = std::min(min.x, newsize.x);
1508  newsize.y = std::min(min.y, newsize.y);
1509  }
1510  }
1511  return newsize;
1512  }
1513 
1514  void CellCache::setStaticSize(bool staticSize) {
1515  m_staticSize = staticSize;
1516  }
1517 
1519  return m_staticSize;
1520  }
1521 
1524  }
1525 
1527  m_fowUpdate = update;
1528  }
1529 
1531  m_sizeUpdate = update;
1532  }
1533 
1536  m_fowUpdate = false;
1537  if (m_sizeUpdate) {
1538  resize();
1539  m_sizeUpdate = false;
1540  }
1541  m_blockingUpdate = false;
1542  }
1543 } // FIFE
void setZoneProtected(bool protect)
Mark zone on this cell as protected.
Definition: cell.cpp:491
virtual double getAdjacentCost(const ModelCoordinate &curpos, const ModelCoordinate &target)=0
Returns distance const from curpos to target point only cells adjacent to curpos are considered in th...
void removeCellsFromCost(const std::string &costId, const std::vector< Cell * > &cells)
Removes cells from a cost identifier.
Definition: cellcache.cpp:1063
void removeZone(Zone *zone)
Removes zone.
Definition: cellcache.cpp:1294
uint32_t getHeight()
Returns height of the CellCache.
Definition: cellcache.cpp:818
void setStaticSize(bool staticSize)
Sets the cache size to static so that automatic resize is disabled.
Definition: cellcache.cpp:1514
virtual std::vector< ModelCoordinate > toMultiCoordinates(const ModelCoordinate &position, const std::vector< ModelCoordinate > &orig, bool reverse=false)=0
Returns point vector with coordinates for a multi object.
StringCellMultimap::iterator StringCellIterator
Definition: cellcache.h:616
double getSpeedMultiplier(Cell *cell)
Returns speed multiplier for the cell.
Definition: cellcache.cpp:1207
uint32_t m_width
cache width
Definition: cellcache.h:644
double getCostMultiplier()
Returns the current cell cost.
Definition: cell.cpp:442
void updateMultiInstances()
Updates the visual positions of all instances in case this is a multi object.
Definition: instance.cpp:1074
int32_t getAngleBetween(const Location &loc1, const Location &loc2)
Gets angle of vector defined by given locations.
Definition: angles.cpp:98
void removeInteractOnRuntime(Layer *interact)
Removes a interact layer from the CellCache on runtime and sets all needed layer properties.
Definition: cellcache.cpp:768
bool isUpdated()
Gets whether the CellCache need to be updated.
Definition: cellcache.cpp:862
void unregisterCost(const std::string &costId)
Removes a cost with the given id.
Definition: cellcache.cpp:983
void setLayerCoordinates(const ModelCoordinate &coordinates)
Sets "cell precise" layer coordinates to this location.
Definition: location.cpp:94
Layer * m_layer
target layer
Definition: cell.h:85
Layer * m_layer
walkable layer
Definition: cellcache.h:625
double getCostMultiplier(Cell *cell)
Returns cost multiplier for the cell.
Definition: cellcache.cpp:1177
int32_t convertCoordToInt(const ModelCoordinate &coord) const
Convertes coordinate to unique identifier.
Definition: cellcache.cpp:835
void addCell(Cell *cell)
Adds a cell to this zone.
Definition: cellcache.cpp:270
void setSpeedMultiplier(Cell *cell, double multi)
Sets speed multiplier for the cell.
Definition: cellcache.cpp:1198
void resize()
Checks the layer size and if the size is different with current size then the cache size is adjusted...
Definition: cellcache.cpp:475
#define ABS(x)
Definition: fife_math.h:41
void addInstance(Instance *instance)
Adds a instance to this cell.
Definition: cell.cpp:138
int32_t getMaxNeighborZ()
Gets maximal z range for neighbors.
Definition: cellcache.cpp:854
T h
Height of the rectangle.
Definition: rect.h:93
std::vector< std::string > getCellCosts(Cell *cell)
Returns cost identifiers for cell.
Definition: cellcache.cpp:1080
uint32_t next(octet_iterator &it, octet_iterator end)
Definition: checked.h:137
bool isDefaultSpeed(Cell *cell)
Gets if cell uses default speed multiplier.
Definition: cellcache.cpp:1190
void removeTransition(Cell *cell)
Removes a cell as transition.
Definition: cellcache.cpp:1224
double getSpeedMultiplier()
Returns the current cell speed.
Definition: cell.cpp:458
bool isCellInArea(const std::string &id, Cell *cell)
Returns true if cell is part of the area, otherwise false.
Definition: cellcache.cpp:1482
std::set< Cell * > m_cells
cells in the zone
Definition: cellcache.h:105
Layer * getLayer()
Returns layer.
Definition: cellcache.cpp:802
Listener interface for changes happening on a cell.
Definition: cell.h:110
std::set< Cell * > m_narrowCells
special cells which are monitored (zone split and merge)
Definition: cellcache.h:677
std::vector< Cell * > getCellsInCircleSegment(const ModelCoordinate &center, uint16_t radius, int32_t sangle, int32_t eangle)
Returns all cells in the circle segment.
Definition: cellcache.cpp:952
T x
The X Coordinate.
Definition: rect.h:84
void setSearchNarrowCells(bool search)
Sets if narrow cells should be searched automatic.
Definition: cellcache.cpp:1392
void removeCellFromCost(Cell *cell)
Removes a cell from costs.
Definition: cellcache.cpp:1041
std::vector< Cell * > getCellsInRect(const Rect &rec)
Returns all cells in the rect.
Definition: cellcache.cpp:883
StringCellMultimap m_costsToCells
holds cells for each cost
Definition: cellcache.h:689
StringCellMultimap m_cellAreas
areas with assigned cells
Definition: cellcache.h:680
A CellCache is an abstract depiction of one or a few layers and contains additional information...
Definition: cellcache.h:111
bool m_updated
need update
Definition: cellcache.h:662
bool m_blockingUpdate
indicates blocking update
Definition: cellcache.h:653
void addInstances(const std::list< Instance * > &instances)
Adds instances to this cell.
Definition: cell.cpp:76
void resetNarrowCells()
Resets narrow cells.
Definition: cellcache.cpp:1380
void setDefaultCostMultiplier(double multi)
Sets default cost for this CellCache.
Definition: cellcache.cpp:1144
const std::set< Cell * > & getCells() const
Returns all cells of this zone.
Definition: cellcache.cpp:294
void addCellToCost(const std::string &costId, Cell *cell)
Assigns a cell to a cost identifier.
Definition: cellcache.cpp:1021
bool isDefaultCost(Cell *cell)
Gets if cell uses default cost multiplier.
Definition: cellcache.cpp:1160
void addCellsToArea(const std::string &id, const std::vector< Cell * > &cells)
Adds few cell to a specific area group.
Definition: cellcache.cpp:1400
CellCache * getCellCache()
Returns the CellCache of this layer.
Definition: layer.cpp:573
void setBlockingUpdate(bool update)
Definition: cellcache.cpp:1522
std::vector< std::vector< Cell * > > m_cells
Definition: cellcache.h:637
static Logger _log(LM_AUDIO)
virtual void onInstanceCreate(Layer *layer, Instance *instance)
Called when some instance gets created on layer.
Definition: cellcache.cpp:179
void registerCost(const std::string &costId, double cost)
Adds a cost with the given id and value.
Definition: cellcache.cpp:974
std::vector< Cell * > getCellsInLine(const ModelCoordinate &pt1, const ModelCoordinate &pt2, bool blocker=false)
Returns all cells in the line.
Definition: cellcache.cpp:866
void removeInstance(Instance *instance)
Removes a instance from this cell.
Definition: cell.cpp:202
bool existsCost(const std::string &costId)
Returns if the cost for the given id exists.
Definition: cellcache.cpp:999
void resetSpeedMultiplier(Cell *cell)
Resets the speed multiplier for the cell.
Definition: cellcache.cpp:1216
void addChangeListener(CellChangeListener *listener)
Adds new cell change listener.
Definition: cell.cpp:613
double m_defaultCostMulti
default cost
Definition: cellcache.h:628
bool defaultCost()
Returns if cell use default cost.
Definition: cell.cpp:434
uint32_t getCellCount() const
Returns the number of cells.
Definition: cellcache.cpp:306
std::vector< Cell * > getCostCells(const std::string &costId)
Returns cells for a cost identifier.
Definition: cellcache.cpp:1070
InstanceTree * getInstanceTree(void) const
Get the instance tree.
Definition: layer.cpp:101
void removeCell(Cell *cell)
Removes a cell from this zone.
Definition: cellcache.cpp:277
Layer * getLayer() const
Gets the layer where this location is pointing to.
Definition: location.cpp:83
void setSize(const Rect &rec)
Sets CellCache size.
Definition: cellcache.cpp:810
uint32_t getId() const
Returns the zone identifier.
Definition: cellcache.cpp:302
Location & getLocationRef()
Gets reference of current location of instance.
Definition: instance.cpp:318
std::vector< Zone * > m_zones
zones
Definition: cellcache.h:674
void removeArea(const std::string &id)
Removes a area.
Definition: cellcache.cpp:1436
ModelCoordinate getLayerCoordinates() const
Gets cell precision layer coordinates set to this location.
Definition: location.cpp:113
virtual void onLayerChanged(Layer *layer, std::vector< Instance * > &instances)
Called when some instance is changed on layer.
Definition: cellcache.cpp:53
void removeCellFromArea(Cell *cell)
Removes the cell from all areas.
Definition: cellcache.cpp:1407
void addInteractLayer(Layer *layer)
Adds a interact layer to the walkable layer.
Definition: layer.cpp:544
void setFowUpdate(bool update)
Definition: cellcache.cpp:1526
int32_t m_neighborZ
max z value for neighbors
Definition: cellcache.h:650
const std::vector< Zone * > & getZones()
Returns zones of this CellCache.
Definition: cellcache.cpp:1273
virtual void onInstanceExitedCell(Cell *cell, Instance *instance)
Called when some instance exited the cell.
Definition: cellcache.cpp:341
ModelCoordinate convertIntToCoord(const int32_t cell) const
Convertes unique identifier to coordinate.
Definition: cellcache.cpp:840
std::map< Cell *, double > m_speedMultipliers
holds default speed multiplier, only if it is not default(1.0)
Definition: cellcache.h:695
void resetCells()
Remove all cells from zone but does not alter the cells.
Definition: cellcache.cpp:298
void unregisterAllCosts()
Removes all costs.
Definition: cellcache.cpp:1016
void getMinMaxCoordinates(ModelCoordinate &min, ModelCoordinate &max, const Layer *layer=0) const
Retrieves the minimum/maximum coordinates of instances on the layer.
Definition: layer.cpp:385
double getAdjacentCost(const ModelCoordinate &adjacent, const ModelCoordinate &next)
Returns cost for movement between these two adjacent coordinates.
Definition: cellcache.cpp:1102
std::map< std::string, double > m_costsTable
holds cost table
Definition: cellcache.h:686
const Rect & getSize()
Returns CellCache size.
Definition: cellcache.cpp:806
void findInstances(const ModelCoordinate &point, int32_t w, int32_t h, InstanceList &list)
Find all instances in a given area.
unsigned char uint8_t
Definition: core.h:38
~Zone()
Destructor.
Definition: cellcache.cpp:264
void setZone(Zone *zone)
Sets zone.
Definition: cell.cpp:470
Simple class to hold the data for transistions.
Definition: cell.h:82
void removeChangeListener(LayerChangeListener *listener)
Removes associated change listener.
Definition: layer.cpp:632
const std::vector< Instance * > & getMultiInstances()
Returns a vector that contains all instances of a multi object.
Definition: instance.cpp:580
~CellCache()
Destructor.
Definition: cellcache.cpp:419
bool isInCellCache(const Location &location) const
Checks whether the location is in CellCache range.
Definition: cellcache.cpp:822
double getDefaultSpeedMultiplier()
Gets default speed for this CellCache.
Definition: cellcache.cpp:1156
void removeCellsFromArea(const std::string &id, const std::vector< Cell * > &cells)
Removes few cells from a area.
Definition: cellcache.cpp:1429
Cell * getCell(const ModelCoordinate &mc)
Returns cell on this coordinate.
Definition: cellcache.cpp:706
bool isZoneProtected()
Returns whether the zone on this cell is protected.
Definition: cell.cpp:487
CellCache(Layer *layer)
Constructor.
Definition: cellcache.cpp:371
uint8_t CellTypeInfo
Definition: cell.h:65
std::list< std::string > getCosts()
Returns all registered cost ids.
Definition: cellcache.cpp:1007
Zone * createZone()
Creates zone.
Definition: cellcache.cpp:1251
int32_t getRotation() const
Get the rotation offset of this instance Returns direction where instance is heading.
Definition: instance.cpp:333
CellTypeInfo getCellType()
Returns blocker type.
Definition: cell.cpp:495
std::vector< Cell * > getTransitionCells(Layer *layer=NULL)
Returns transistion cells of this CellCache.
Definition: cellcache.cpp:1234
void addCellsToCost(const std::string &costId, const std::vector< Cell * > &cells)
Assigns cells to a cost identifier.
Definition: cellcache.cpp:1034
void setUpdated(bool updated)
Sets whether the CellCache need to be updated.
Definition: cellcache.cpp:858
A basic layer on a map.
Definition: layer.h:99
bool existsCostForCell(const std::string &costId, Cell *cell)
Gets if cell is assigned to cost identifier.
Definition: cellcache.cpp:1091
uint32_t m_id
identifier
Definition: cellcache.h:103
void splitZone(Cell *cell)
Splits zone on the cell.
Definition: cellcache.cpp:1304
Listener interface for changes happening on a layer.
Definition: layer.h:71
bool m_searchNarrow
is automatic seach enabled
Definition: cellcache.h:665
CellChangeListener * m_cellZoneListener
listener for zones
Definition: cellcache.h:683
void addChangeListener(LayerChangeListener *listener)
Adds new change listener.
Definition: layer.cpp:628
double m_defaultSpeedMulti
default speed
Definition: cellcache.h:631
const std::vector< Cell * > & getNeighbors()
Returns the layer coordinates of this cell.
Definition: cell.cpp:523
ZoneCellChangeListener(CellCache *cache)
Definition: cellcache.cpp:331
ExactModelCoordinate & getExactLayerCoordinatesRef()
Gets reference to exact layer coordinates.
Definition: location.cpp:105
std::vector< std::string > getCellAreas(Cell *cell)
Returns all areas of a cell.
Definition: cellcache.cpp:1461
A basic cell on a CellCache.
Definition: cell.h:136
void forceUpdate()
Updates all cells.
Definition: cellcache.cpp:682
unsigned short uint16_t
Definition: core.h:39
T y
The Y Coordinate.
Definition: rect.h:87
std::iterator_traits< octet_iterator >::difference_type distance(octet_iterator first, octet_iterator last)
Definition: checked.h:198
void createCells()
Creates cells for this CellCache based on the size of the assigned layer.
Definition: cellcache.cpp:586
CellGrid * getCellGrid() const
Get the Cellgrid.
Definition: layer.cpp:93
void addCell(Cell *cell)
Adds cell to this CellCache.
Definition: cellcache.cpp:692
LayerChangeListener * m_cellListener
change listener
Definition: cellcache.h:634
bool getCellSpeedMultiplier(const ModelCoordinate &cell, double &multiplier)
Returns speed value from cell.
Definition: cellcache.cpp:1132
Rect m_size
Rect holds the min and max size x = min.x, w = max.x, y = min.y, h = max.y.
Definition: cellcache.h:641
void setInteract(bool interact, const std::string &id)
Sets interact for the layer.
Definition: layer.cpp:531
Zone * getZone(uint32_t id)
Gets zone by identifier.
Definition: cellcache.cpp:1277
std::vector< Cell * > getAreaCells(const std::string &id)
Returns all cells of an area.
Definition: cellcache.cpp:1472
const std::vector< Layer * > & getInteractLayers()
Returns all assigned interact layer.
Definition: layer.cpp:550
void changeInstance(Instance *instance)
Changes a instance on this cell.
Definition: cell.cpp:198
const ModelCoordinate getLayerCoordinates() const
Returns the layer coordinates of this cell.
Definition: cell.cpp:515
Zone * getZone()
Returns zone.
Definition: cell.cpp:466
CellCacheChangeListener(Layer *layer)
Definition: cellcache.cpp:47
void setDefaultSpeedMultiplier(double multi)
Sets default speed for this CellCache.
Definition: cellcache.cpp:1152
std::map< Cell *, double > m_costMultipliers
holds default cost multiplier, only if it is not default(1.0)
Definition: cellcache.h:692
uint32_t m_height
cache height
Definition: cellcache.h:647
virtual void onInstanceEnteredCell(Cell *cell, Instance *instance)
Called when some instance entered the cell.
Definition: cellcache.cpp:337
void mergeZones(Zone *zone1, Zone *zone2)
Merges two zones to one.
Definition: cellcache.cpp:1347
bool m_fowUpdate
indicates fow update
Definition: cellcache.h:656
bool isStaticSize()
Returns if the cache size is static.
Definition: cellcache.cpp:1518
void removeNarrowCell(Cell *cell)
Removes cell from narrow cells.
Definition: cellcache.cpp:1372
void addCellToArea(const std::string &id, Cell *cell)
Adds a cell to a specific area group.
Definition: cellcache.cpp:1396
Rect calculateCurrentSize()
Returns the current size.
Definition: cellcache.cpp:1493
void setCellId(int32_t id)
Sets the cell identifier.
Definition: cell.cpp:507
std::vector< Cell * > getCellsInCircle(const ModelCoordinate &center, uint16_t radius)
Returns all cells in the circle.
Definition: cellcache.cpp:900
void mergeZone(Zone *zone)
Merge two zones to one.
Definition: cellcache.cpp:285
A 3D Point.
Definition: point.h:205
const std::string & getId() const
Get the id of this layer.
Definition: layer.cpp:81
virtual void onBlockingChangedCell(Cell *cell, CellTypeInfo type, bool blocks)
Called when some instance changed its blocking property.
Definition: cellcache.cpp:345
DoublePoint intPt2doublePt(Point pt)
Convert from 2D int32_t point to 2D double point.
Definition: point.h:349
LayerChangeListener * getCellCacheChangeListener()
Returns change listener.
Definition: cellcache.cpp:798
void setSizeUpdate(bool update)
Definition: cellcache.cpp:1530
void setInserted(bool inserted)
Mark cell as inserted.
Definition: cell.cpp:483
void removeCell(Cell *cell)
Removes cell from CellCache.
Definition: cellcache.cpp:721
const std::vector< std::vector< Cell * > > & getCells()
Returns all cells of this CellCache.
Definition: cellcache.cpp:717
void resetNeighbors()
Removes all neighbors from cell.
Definition: cell.cpp:527
void addTransition(Cell *cell)
Adds a cell as transition.
Definition: cellcache.cpp:1220
virtual std::vector< ModelCoordinate > getCoordinatesInLine(const ModelCoordinate &start, const ModelCoordinate &end)=0
Returns point vector with coordinates for a line from start to end.
Cell * createCell(const ModelCoordinate &mc)
Creates cell on this CellCache.
Definition: cellcache.cpp:697
std::pair< StringCellIterator, StringCellIterator > StringCellPair
Definition: cellcache.h:617
void removeInteractLayer(Layer *layer)
Removes a interact layer from the walkable layer.
Definition: layer.cpp:554
virtual void onInstanceDelete(Layer *layer, Instance *instance)
Called when some instance gets deleted on layer.
Definition: cellcache.cpp:221
bool m_staticSize
is automatic size update enabled/disabled
Definition: cellcache.h:668
Zone(uint32_t id)
Constructor.
Definition: cellcache.cpp:260
void addNarrowCell(Cell *cell)
Adds cell to narrow cells.
Definition: cellcache.cpp:1361
std::vector< std::string > getAreas()
Returns all area ids.
Definition: cellcache.cpp:1448
bool m_sizeUpdate
indicates size update
Definition: cellcache.h:659
double getCost(const std::string &costId)
Returns the cost value for the given id.
Definition: cellcache.cpp:991
void getAccessibleCoordinates(const ModelCoordinate &curpos, std::vector< ModelCoordinate > &coordinates)
Gets the coordinates that are accesible from given point only cells adjacent to given cell are consid...
Definition: cellgrid.cpp:56
bool isInserted()
Returns whether the cell is part of a zone.
Definition: cell.cpp:479
const std::set< Cell * > & getNarrowCells()
Returns narrow cells.
Definition: cellcache.cpp:1368
unsigned int uint32_t
Definition: core.h:40
ExactModelCoordinate toMapCoordinates(const ModelCoordinate &layer_coords)
Transforms given point from layer coordinates to map coordinates.
Definition: cellgrid.cpp:75
double getDefaultCostMultiplier()
Gets default cost for this CellCache.
Definition: cellcache.cpp:1148
void setMaxNeighborZ(int32_t z)
Sets maximal z range for neighbors.
Definition: cellcache.cpp:850
bool isMultiCell()
Returns true if it is multi cell otherwise false.
Definition: instance.cpp:1066
uint32_t getWidth()
Returns width of the CellCache.
Definition: cellcache.cpp:814
bool existsArea(const std::string &id)
Checks whether the area exists.
Definition: cellcache.cpp:1440
bool defaultSpeed()
Returns if cell use default speed.
Definition: cell.cpp:450
T w
Width of the rectangle.
Definition: rect.h:90
std::vector< Cell * > getTransitionCells(Layer *layer=NULL)
Returns transistion cells of this zone.
Definition: cellcache.cpp:310
std::vector< Cell * > m_transitions
cells with transitions
Definition: cellcache.h:671
int32_t getMaxIndex() const
Returns the number of cells on this CellCache.
Definition: cellcache.cpp:845
An Instance is an "instantiation" of an Object at a Location.
Definition: instance.h:101
bool isSearchNarrowCells()
Gets if narrow cells should be searched automatic.
Definition: cellcache.cpp:1388
void resetCostMultiplier(Cell *cell)
Resets the cost multiplier for the cell.
Definition: cellcache.cpp:1186
void addInteractOnRuntime(Layer *interact)
Adds a interact layer to the CellCache on runtime and sets all needed layer properties.
Definition: cellcache.cpp:739
A Zone is an abstract depiction of a CellCache or of a part of it.
Definition: cellcache.h:50
virtual ModelCoordinate toLayerCoordinates(const ExactModelCoordinate &map_coord)=0
Transforms given point from map coordinates to layer coordinates.
void setCostMultiplier(Cell *cell, double multi)
Sets cost multiplier for the cell.
Definition: cellcache.cpp:1168
void reset()
Resets the CellCache.
Definition: cellcache.cpp:436