Debian Codegraph @

engine/core/model/structures/cellcache.h

raw
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