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 #ifndef FIFE_CELLCACHE_H 23 #define FIFE_CELLCACHE_H 24 25 // Standard C++ library includes 26 #include <algorithm> 27 #include <string> 28 #include <vector> 29 #include <set> 30 #include <stack> 31 32 // 3rd party library includes 33 34 // FIFE includes 35 // These includes are split up in two parts, separated by one empty line 36 // First block: files included from the FIFE root src directory 37 // Second block: files included from the same folder 38 #include "util/base/fifeclass.h" 39 #include "util/structures/rect.h" 40 #include "model/metamodel/modelcoords.h" 41 #include "model/metamodel/object.h" 42 43 #include "layer.h" 44 #include "cell.h" 45 46 namespace FIFE { 47 48 /** A Zone is an abstract depiction of a CellCache or of a part of it. 49 */ 50 class Zone { 51 public: 52 /** Constructor 53 * @param id A integer value used as identifier. Simple counter values are used. 54 */ 55 Zone(uint32_t id); 56 57 /** Destructor 58 */ 59 ~Zone(); 60 61 /** Adds a cell to this zone. 62 * @param cell A pointer to cell which should be added. 63 */ 64 void addCell(Cell* cell); 65 66 /** Removes a cell from this zone. 67 * @param cell A pointer to cell which should be removed. 68 */ 69 void removeCell(Cell* cell); 70 71 /** Merge two zones to one. 72 * @param zone A pointer to the old zone. 73 */ 74 void mergeZone(Zone* zone); 75 76 /** Returns all cells of this zone. 77 * @return A const reference to a set that contains all cells of this zone. 78 */ 79 const std::set<Cell*>& getCells() const; 80 81 /** Remove all cells from zone but does not alter the cells. 82 */ 83 void resetCells(); 84 85 /** Returns the zone identifier. 86 * @return A unsigned integer with the identifier. 87 */ 88 uint32_t getId() const; 89 90 /** Returns the number of cells. 91 * @return A unsigned integer with the number of cells. 92 */ 93 uint32_t getCellCount() const; 94 95 /** Returns transistion cells of this zone. 96 * @param layer A pointer to the layer which should be the target of the transition. If NULL all transistions be returned. 97 * @return A vector which contains the transition cells. 98 */ 99 std::vector<Cell*> getTransitionCells(Layer* layer = NULL); 100 101 private: 102 //! identifier 103 uint32_t m_id; 104 //! cells in the zone 105 std::set<Cell*> m_cells; 106 }; 107 108 /** A CellCache is an abstract depiction of one or a few layers 109 * and contains additional information, such as different cost and speed and so on. 110 */ 111 class CellCache : public FifeClass { 112 public: 113 /** Constructor 114 * @param layer A pointer to the associated layer. 115 */ 116 CellCache(Layer* layer); 117 118 /** Destructor 119 */ 120 ~CellCache(); 121 122 /** Resets the CellCache 123 */ 124 void reset(); 125 126 /** Checks the layer size and if the size is different with current size then 127 the cache size is adjusted. 128 */ 129 void resize(); 130 131 /** Checks the given size and if the size is different with current size then 132 the cache is adjusted. 133 * @param rec A rect that contains the new size in layer coordinates. 134 */ 135 void resize(const Rect& rec); 136 137 /** Creates cells for this CellCache based on the size of the assigned layer. 138 */ 139 void createCells(); 140 141 /** Updates all cells. 142 */ 143 void forceUpdate(); 144 145 /** Adds cell to this CellCache. 146 * @param cell A pointer to cell which should be added. 147 */ 148 void addCell(Cell* cell); 149 150 /** Creates cell on this CellCache. 151 * @param mc A const reference to ModelCoordinate where the cell should be created. 152 * @return A pointer to the new cell. 153 */ 154 Cell* createCell(const ModelCoordinate& mc); 155 156 /** Returns cell on this coordinate. 157 * @param mc A const reference to ModelCoordinate where the cell should be. 158 * @return A pointer to the cell or NULL if there is no. 159 */ 160 Cell* getCell(const ModelCoordinate& mc); 161 162 /** Returns all cells of this CellCache. 163 * @return A const reference to a two dimensional vector which contain all cells. 164 */ 165 const std::vector<std::vector<Cell*> >& getCells(); 166 167 /** Removes cell from CellCache. 168 * Removes cell from cost table, special cost and speed, 169 * futhermore from areas and narrows. 170 * @param cell A pointer to the cell. 171 */ 172 void removeCell(Cell* cell); 173 174 /** Adds a interact layer to the CellCache on runtime and sets all needed layer properties. 175 * @param interact A pointer to the interact layer. 176 */ 177 void addInteractOnRuntime(Layer* interact); 178 179 /** Removes a interact layer from the CellCache on runtime and sets all needed layer properties. 180 * @param interact A pointer to the interact layer. 181 */ 182 void removeInteractOnRuntime(Layer* interact); 183 184 /** Returns change listener. 185 * @return A pointer to the change listener. 186 */ 187 LayerChangeListener* getCellCacheChangeListener(); 188 189 /** Returns layer. 190 * @return A pointer to the layer this CellCache is based on. 191 */ 192 Layer* getLayer(); 193 194 /** Returns CellCache size. 195 * @return A const reference to rect that contain the min and max coordinates. 196 */ 197 const Rect& getSize(); 198 199 /** Sets CellCache size. 200 * @param rec A const reference to a rect that contain new min, max coordinates. 201 rec.x = min.x, rec.w = max.x, rec.y = min.y, rec.h = max.y 202 */ 203 void setSize(const Rect& rec); 204 205 /** Returns width of the CellCache. 206 * @return A unsigned integer that is the width. 207 */ 208 uint32_t getWidth(); 209 210 /** Returns height of the CellCache. 211 * @return A unsigned integer that is the height. 212 */ 213 uint32_t getHeight(); 214 215 /** Checks whether the location is in CellCache range. 216 * @param location A const reference to location which should be checked. 217 * @return A boolean, true if the location is in range, otherwise false. 218 */ 219 bool isInCellCache(const Location& location) const; 220 221 /** Convertes coordinate to unique identifier. 222 * @param coord A const reference to ModelCoordinate which should be converted. 223 * @return A integer, the cell identifier. 224 */ 225 int32_t convertCoordToInt(const ModelCoordinate& coord) const; 226 227 /** Convertes unique identifier to coordinate. 228 * @param cell A const reference to the integer id which should be converted. 229 * @return A ModelCoordinate, contain the cell coordinate. 230 */ 231 ModelCoordinate convertIntToCoord(const int32_t cell) const; 232 233 /** Returns the number of cells on this CellCache. 234 * @return A integer value, the number of cells. 235 */ 236 int32_t getMaxIndex() const; 237 238 /** Sets maximal z range for neighbors. 239 * @param z The maximal z range as int. 240 */ 241 void setMaxNeighborZ(int32_t z); 242 243 /** Gets maximal z range for neighbors. By default disabled with the value -1. 244 * @return The maximal z range as int. 245 */ 246 int32_t getMaxNeighborZ(); 247 248 /** Returns all cells in the line. 249 * @param pt1 A const reference to the ModelCoordinate where the line begin. 250 * @param pt2 A const reference to the ModelCoordinate where the line end. 251 * @param blocker A boolean, true stops when a blocker is found, false ignored blocker. 252 * @return A vector that contain the cells. 253 */ 254 std::vector<Cell*> getCellsInLine(const ModelCoordinate& pt1, const ModelCoordinate& pt2, bool blocker = false); 255 256 /** Returns all cells in the rect. 257 * @param rec A const reference to the Rect which specifies the size. 258 * @return A vector that contain the cells. 259 */ 260 std::vector<Cell*> getCellsInRect(const Rect& rec); 261 262 /** Returns all blocking cells in the rect. 263 * @param rec A const reference to the Rect which specifies the size. 264 * @return A vector that contain the cells. 265 */ 266 std::vector<Cell*> getBlockingCellsInRect(const Rect& rec); 267 268 /** Returns all cells in the circle. 269 * @param center A const reference to the ModelCoordinate where the center of the circle is. 270 * @param radius A unsigned integer, radius of the circle. 271 * @return A vector that contain the cells. 272 */ 273 std::vector<Cell*> getCellsInCircle(const ModelCoordinate& center, uint16_t radius); 274 275 /** Returns all cells in the circle segment. 276 * @param center A const reference to the ModelCoordinate where the center of the circle is. 277 * @param radius A unsigned integer, radius of the circle. 278 * @param sangle A interger, start angle of the segment. 279 * @param eangle A interger, end angle of the segment. 280 * @return A vector that contain the cells. 281 */ 282 std::vector<Cell*> getCellsInCircleSegment(const ModelCoordinate& center, uint16_t radius, int32_t sangle, int32_t eangle); 283 284 /** Adds a cost with the given id and value. 285 * @param costId A const reference to a string that refs to the cost id. 286 * @param cost A double that contains the cost value. Used as multiplier for default cost. 287 */ 288 void registerCost(const std::string& costId, double cost); 289 290 /** Removes a cost with the given id. 291 * @param costId A const reference to a string that refs to the cost id. 292 */ 293 void unregisterCost(const std::string& costId); 294 295 /** Returns the cost value for the given id. 296 * @param costId A const reference to a string that refs to the cost id. 297 * @return cost value as a double, if cost id can not be found 1.0 is returned. 298 */ 299 double getCost(const std::string& costId); 300 301 /** Returns if the cost for the given id exists. 302 * @return True if cost id could be found otherwise false. 303 */ 304 bool existsCost(const std::string& costId); 305 306 /** Returns all registered cost ids. 307 * @return A list that contains the cost ids. 308 */ 309 std::list<std::string> getCosts(); 310 311 /** Removes all costs. 312 */ 313 void unregisterAllCosts(); 314 315 /** Assigns a cell to a cost identifier. 316 * @param costId A const reference to the cost identifier. 317 * @param cell A pointer to the cell. 318 */ 319 void addCellToCost(const std::string& costId, Cell* cell); 320 321 /** Assigns cells to a cost identifier. 322 * @param costId A const reference to the cost identifier. 323 * @param cells A const reference to a vector which contains the cells. 324 */ 325 void addCellsToCost(const std::string& costId, const std::vector<Cell*>& cells); 326 327 /** Removes a cell from costs. 328 * @param cell A pointer to the cell. 329 */ 330 void removeCellFromCost(Cell* cell); 331 332 /** Removes a cell from a cost identifier. 333 * @param costId A const reference to the cost identifier. 334 * @param cell A pointer to the cell. 335 */ 336 void removeCellFromCost(const std::string& costId, Cell* cell); 337 338 /** Removes cells from a cost identifier. 339 * @param costId A const reference to the cost identifier. 340 * @param cells A const reference to a vector which contains the cells. 341 */ 342 void removeCellsFromCost(const std::string& costId, const std::vector<Cell*>& cells); 343 344 /** Returns cells for a cost identifier. 345 * @param costId A const reference to the cost identifier. 346 * @return A vector which contains the cells. 347 */ 348 std::vector<Cell*> getCostCells(const std::string& costId); 349 350 /** Returns cost identifiers for cell. 351 * @param cell A pointer to the cell. 352 * @return A vector which contains the cost ids. 353 */ 354 std::vector<std::string> getCellCosts(Cell* cell); 355 356 /** Gets if cell is assigned to cost identifier. 357 * @param costId A const reference to the cost identifier. 358 * @param cell A pointer to the cell. 359 * @return A boolean, true if the cell is assigned to the cost identifier, otherwise false. 360 */ 361 bool existsCostForCell(const std::string& costId, Cell* cell); 362 363 /** Returns cost for movement between these two adjacent coordinates. 364 * @param adjacent A const reference to the start ModelCoordinate. 365 * @param next A const reference to the end ModelCoordinate. 366 * @return A double which represents the cost. 367 */ 368 double getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next); 369 370 /** Returns cost for movement between these two adjacent coordinates. 371 * @param adjacent A const reference to the start ModelCoordinate. 372 * @param next A const reference to the end ModelCoordinate. 373 * @param costId A const reference to the string that contain a cost identifier. 374 * @return A double which represents the cost. 375 */ 376 double getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next, const std::string& costId); 377 378 /** Returns speed value from cell. 379 * @param cell A const reference to the cell ModelCoordinate. 380 * @param multiplier A reference to a double which receives the speed value. 381 * @return A boolean, true if on next cell use special speed, otherwise false. 382 */ 383 bool getCellSpeedMultiplier(const ModelCoordinate& cell, double& multiplier); 384 385 /** Sets default cost for this CellCache. 386 * @param multi A double, the cost. 387 */ 388 void setDefaultCostMultiplier(double multi); 389 390 /** Gets default cost for this CellCache. 391 * @return A double, the cost. 392 */ 393 double getDefaultCostMultiplier(); 394 395 /** Sets default speed for this CellCache. 396 * @param multi A double, the speed. 397 */ 398 void setDefaultSpeedMultiplier(double multi); 399 400 /** Gets default speed for this CellCache. 401 * @return A double, the speed. 402 */ 403 double getDefaultSpeedMultiplier(); 404 405 /** Gets if cell uses default cost multiplier. 406 * @param cell A pointer to the cell. 407 * @return A boolean, true if the cell uses default cost multiplier, otherwise false. 408 */ 409 bool isDefaultCost(Cell* cell); 410 411 /** Sets cost multiplier for the cell. 412 * @param cell A pointer to the cell. 413 * @param multi A double, the cost multiplier. 414 */ 415 void setCostMultiplier(Cell* cell, double multi); 416 417 /** Returns cost multiplier for the cell. 418 * @param cell A pointer to the cell. 419 * @return A double, the cost multiplier. 1.0 is default. 420 */ 421 double getCostMultiplier(Cell* cell); 422 423 /** Resets the cost multiplier for the cell. 424 * @param cell A pointer to the cell. 425 */ 426 void resetCostMultiplier(Cell* cell); 427 428 /** Gets if cell uses default speed multiplier. 429 * @param cell A pointer to the cell. 430 * @return A boolean, true if the cell uses default speed multiplier, otherwise false. 431 */ 432 bool isDefaultSpeed(Cell* cell); 433 434 /** Sets speed multiplier for the cell. 435 * @param cell A pointer to the cell. 436 * @param multi A double, the speed multiplier. 437 */ 438 void setSpeedMultiplier(Cell* cell, double multi); 439 440 /** Returns speed multiplier for the cell. 441 * @param cell A pointer to the cell. 442 * @return A double, the speed multiplier. 1.0 is default. 443 */ 444 double getSpeedMultiplier(Cell* cell); 445 446 /** Resets the speed multiplier for the cell. 447 * @param cell A pointer to the cell. 448 */ 449 void resetSpeedMultiplier(Cell* cell); 450 451 /** Adds a cell as transition. 452 * @param cell A pointer to transition cell. 453 */ 454 void addTransition(Cell* cell); 455 456 /** Removes a cell as transition. 457 * @param cell A pointer to transition cell. 458 */ 459 void removeTransition(Cell* cell); 460 461 /** Returns transistion cells of this CellCache. 462 * @param layer A pointer to the layer which should be the target of the transition. If NULL all transistions be returned. 463 * @return A vector which contains the transition cells. 464 */ 465 std::vector<Cell*> getTransitionCells(Layer* layer = NULL); 466 467 /** Returns zones of this CellCache. 468 * @return A vector which contains the zones. 469 */ 470 const std::vector<Zone*>& getZones(); 471 472 /** Gets zone by identifier. 473 * @param id A unsigned integer which is used as zone identifier, 474 * @return A pointer to the zone. 475 */ 476 Zone* getZone(uint32_t id); 477 478 /** Creates zone. 479 * @return A pointer to the new zone. 480 */ 481 Zone* createZone(); 482 483 /** Removes zone. 484 * @param zone A pointer to the zone which should be removed. 485 */ 486 void removeZone(Zone* zone); 487 488 /** Splits zone on the cell. 489 * @param cell A pointer to the cell where the zone should be splited. 490 */ 491 void splitZone(Cell* cell); 492 493 /** Merges two zones to one. 494 * @param zone1 A pointer to the first zone. 495 * @param zone2 A pointer to the second zone. 496 */ 497 void mergeZones(Zone* zone1, Zone* zone2); 498 499 /** Adds cell to narrow cells. 500 * Narrow cells are observed. On blocking change, the underlying zones are merged or splitted. 501 * @param cell A pointer to the cell. 502 */ 503 void addNarrowCell(Cell* cell); 504 505 /** Returns narrow cells. 506 * @return A const reference to a set which contains the cells. 507 */ 508 const std::set<Cell*>& getNarrowCells(); 509 510 /** Removes cell from narrow cells. 511 * @param cell A pointer to the cell. 512 */ 513 void removeNarrowCell(Cell* cell); 514 515 /** Resets narrow cells. 516 */ 517 void resetNarrowCells(); 518 519 /** Gets if narrow cells should be searched automatic. 520 * Note that narrow cells will only saved if this is disabled. 521 * @return A boolean, if true the automatic search is enabled, otherwise false. 522 */ 523 bool isSearchNarrowCells(); 524 525 /** Sets if narrow cells should be searched automatic. 526 * @param search A boolean, if true the automatic search is enabled, otherwise false. 527 */ 528 void setSearchNarrowCells(bool search); 529 530 /** Adds a cell to a specific area group. With an area you can group cells without the need 531 * of checking the underlying instances or similar. 532 * @param id A const reference to string that contains the area id. 533 * @param cell A pointer to the cell which should be added. 534 */ 535 void addCellToArea(const std::string& id, Cell* cell); 536 537 /** Adds few cell to a specific area group. With an area you can group cells without the need 538 * of checking the underlying instances or similar. 539 * @param id A const reference to string that contains the area id. 540 * @param cells A const reference to vector which contains the cells. 541 */ 542 void addCellsToArea(const std::string& id, const std::vector<Cell*>& cells); 543 544 /** Removes the cell from all areas. 545 * @param cell A pointer to the cell which should be removed. 546 */ 547 void removeCellFromArea(Cell* cell); 548 549 /** Removes the cell from a area. 550 * @param id A const reference to string that contains the area id. 551 * @param cell A pointer to the cell which should be removed. 552 */ 553 void removeCellFromArea(const std::string& id, Cell* cell); 554 555 /** Removes few cells from a area. 556 * @param id A const reference to string that contains the area id. 557 * @param cells A const reference to vector which contains the cells. 558 */ 559 void removeCellsFromArea(const std::string& id, const std::vector<Cell*>& cells); 560 561 /** Removes a area. 562 * @param id A const reference to string that contains the area id. 563 */ 564 void removeArea(const std::string& id); 565 566 /** Checks whether the area exists. 567 * @param id A const reference to string that contains the area id. 568 * @return A boolean, true if the area id exists, otherwise false. 569 */ 570 bool existsArea(const std::string& id); 571 572 /** Returns all area ids. 573 * @return A vector that contains the area ids. 574 */ 575 std::vector<std::string> getAreas(); 576 577 /** Returns all areas of a cell. 578 * @param cell A pointer to the cell. 579 * @return A vector that contains the area ids. 580 */ 581 std::vector<std::string> getCellAreas(Cell* cell); 582 583 /** Returns all cells of an area. 584 * @param id A const reference to string that contains the area id. 585 * @return A vector that contains the cells from the area. 586 */ 587 std::vector<Cell*> getAreaCells(const std::string& id); 588 589 /** Returns true if cell is part of the area, otherwise false. 590 * @param id A const reference to string that contains the area id. 591 * @param cell A pointer to the cell which is used for the check. 592 * @return A boolean, true if the cell is part of the area, otherwise false. 593 */ 594 bool isCellInArea(const std::string& id, Cell* cell); 595 596 /** Sets the cache size to static so that automatic resize is disabled. 597 * @param staticSize A boolean, true if the cache size is static, otherwise false. 598 */ 599 void setStaticSize(bool staticSize); 600 601 /** Returns if the cache size is static. 602 * @return A boolean, true if the cache size is static, otherwise false. 603 */ 604 bool isStaticSize(); 605 606 void setBlockingUpdate(bool update); 607 void setSizeUpdate(bool update); 608 void update(); 609 private: 610 typedef std::multimap<std::string, Cell*> StringCellMultimap; 611 typedef StringCellMultimap::iterator StringCellIterator; 612 typedef std::pair<StringCellIterator, StringCellIterator> StringCellPair; 613 614 /** Returns the current size. 615 * @return A rect that contains the min, max coordinates. 616 */ 617 Rect calculateCurrentSize(); 618 619 //! walkable layer 620 Layer* m_layer; 621 622 //! default cost 623 double m_defaultCostMulti; 624 625 //! default speed 626 double m_defaultSpeedMulti; 627 628 //! change listener 629 LayerChangeListener* m_cellListener; 630 631 // cells on this cache 632 std::vector<std::vector<Cell*> > m_cells; 633 634 //! Rect holds the min and max size 635 //! x = min.x, w = max.x, y = min.y, h = max.y 636 Rect m_size; 637 638 //! cache width 639 uint32_t m_width; 640 641 //! cache height 642 uint32_t m_height; 643 644 //! max z value for neighbors 645 int32_t m_neighborZ; 646 647 //! indicates blocking update 648 bool m_blockingUpdate; 649 650 //! indicates size update 651 bool m_sizeUpdate; 652 653 //! is automatic seach enabled 654 bool m_searchNarrow; 655 656 //! is automatic size update enabled/disabled 657 bool m_staticSize; 658 659 //! cells with transitions 660 std::vector<Cell*> m_transitions; 661 662 //! zones 663 std::vector<Zone*> m_zones; 664 665 //! special cells which are monitored (zone split and merge) 666 std::set<Cell*> m_narrowCells; 667 668 //! areas with assigned cells 669 StringCellMultimap m_cellAreas; 670 671 //! listener for zones 672 CellChangeListener* m_cellZoneListener; 673 674 //! holds cost table 675 std::map<std::string, double> m_costsTable; 676 677 //! holds cells for each cost 678 StringCellMultimap m_costsToCells; 679 680 //! holds default cost multiplier, only if it is not default(1.0) 681 std::map<Cell*, double> m_costMultipliers; 682 683 //! holds default speed multiplier, only if it is not default(1.0) 684 std::map<Cell*, double> m_speedMultipliers; 685 }; 686 687 } // FIFE 688 689 #endif 690