1 /*****************************************************************************
2 * Copyright (c) 2014-2020 OpenRCT2 developers
3 *
4 * For a complete list of all authors, please refer to contributors.md
5 * Interested in contributing? Visit https://github.com/OpenRCT2/OpenRCT2
6 *
7 * OpenRCT2 is licensed under the GNU General Public License version 3.
8 *****************************************************************************/
9
10 #include "Sprite.h"
11
12 #include "../Game.h"
13 #include "../core/ChecksumStream.h"
14 #include "../core/Crypt.h"
15 #include "../core/DataSerialiser.h"
16 #include "../core/Guard.hpp"
17 #include "../core/MemoryStream.h"
18 #include "../interface/Viewport.h"
19 #include "../peep/Peep.h"
20 #include "../peep/RideUseSystem.h"
21 #include "../peep/Staff.h"
22 #include "../ride/Vehicle.h"
23 #include "../scenario/Scenario.h"
24 #include "Balloon.h"
25 #include "Duck.h"
26 #include "EntityTweener.h"
27 #include "Fountain.h"
28 #include "MoneyEffect.h"
29 #include "Particle.h"
30
31 #include <algorithm>
32 #include <cmath>
33 #include <iterator>
34 #include <numeric>
35 #include <vector>
36
37 static rct_sprite _spriteList[MAX_ENTITIES];
38 static std::array<std::list<uint16_t>, EnumValue(EntityType::Count)> gEntityLists;
39 static std::vector<uint16_t> _freeIdList;
40
41 static bool _spriteFlashingList[MAX_ENTITIES];
42
43 constexpr const uint32_t SPATIAL_INDEX_SIZE = (MAXIMUM_MAP_SIZE_TECHNICAL * MAXIMUM_MAP_SIZE_TECHNICAL) + 1;
44 constexpr const uint32_t SPATIAL_INDEX_LOCATION_NULL = SPATIAL_INDEX_SIZE - 1;
45
46 static std::array<std::vector<uint16_t>, SPATIAL_INDEX_SIZE> gSpriteSpatialIndex;
47
48 static void FreeEntity(EntityBase& entity);
49
GetSpatialIndexOffset(const CoordsXY & loc)50 static constexpr size_t GetSpatialIndexOffset(const CoordsXY& loc)
51 {
52 if (loc.IsNull())
53 return SPATIAL_INDEX_LOCATION_NULL;
54
55 // NOTE: The input coordinate is rotated and can have negative components.
56 const auto tileX = std::abs(loc.x) / COORDS_XY_STEP;
57 const auto tileY = std::abs(loc.y) / COORDS_XY_STEP;
58
59 if (tileX >= MAXIMUM_MAP_SIZE_TECHNICAL || tileY >= MAXIMUM_MAP_SIZE_TECHNICAL)
60 return SPATIAL_INDEX_LOCATION_NULL;
61
62 return tileX * MAXIMUM_MAP_SIZE_TECHNICAL + tileY;
63 }
64
65 // Required for GetEntity to return a default
Is() const66 template<> bool EntityBase::Is<EntityBase>() const
67 {
68 return true;
69 }
70
Is() const71 template<> bool EntityBase::Is<Litter>() const
72 {
73 return Type == EntityType::Litter;
74 }
75
EntityTypeIsMiscEntity(const EntityType type)76 constexpr bool EntityTypeIsMiscEntity(const EntityType type)
77 {
78 switch (type)
79 {
80 case EntityType::SteamParticle:
81 case EntityType::MoneyEffect:
82 case EntityType::CrashedVehicleParticle:
83 case EntityType::ExplosionCloud:
84 case EntityType::CrashSplash:
85 case EntityType::ExplosionFlare:
86 case EntityType::JumpingFountain:
87 case EntityType::Balloon:
88 case EntityType::Duck:
89 return true;
90 default:
91 return false;
92 }
93 }
94
Is() const95 template<> bool EntityBase::Is<MiscEntity>() const
96 {
97 return EntityTypeIsMiscEntity(Type);
98 }
99
Is() const100 template<> bool EntityBase::Is<SteamParticle>() const
101 {
102 return Type == EntityType::SteamParticle;
103 }
104
Is() const105 template<> bool EntityBase::Is<ExplosionFlare>() const
106 {
107 return Type == EntityType::ExplosionFlare;
108 }
109
Is() const110 template<> bool EntityBase::Is<ExplosionCloud>() const
111 {
112 return Type == EntityType::ExplosionCloud;
113 }
114
GetEntityListCount(EntityType type)115 uint16_t GetEntityListCount(EntityType type)
116 {
117 return static_cast<uint16_t>(gEntityLists[EnumValue(type)].size());
118 }
119
GetNumFreeEntities()120 uint16_t GetNumFreeEntities()
121 {
122 return static_cast<uint16_t>(_freeIdList.size());
123 }
124
ToString() const125 std::string rct_sprite_checksum::ToString() const
126 {
127 std::string result;
128
129 result.reserve(raw.size() * 2);
130 for (auto b : raw)
131 {
132 char buf[3];
133 snprintf(buf, 3, "%02x", static_cast<int32_t>(b));
134 result.append(buf);
135 }
136
137 return result;
138 }
139
try_get_sprite(size_t spriteIndex)140 EntityBase* try_get_sprite(size_t spriteIndex)
141 {
142 return spriteIndex >= MAX_ENTITIES ? nullptr : &_spriteList[spriteIndex].base;
143 }
144
get_sprite(size_t spriteIndex)145 EntityBase* get_sprite(size_t spriteIndex)
146 {
147 if (spriteIndex == SPRITE_INDEX_NULL)
148 {
149 return nullptr;
150 }
151 openrct2_assert(spriteIndex < MAX_ENTITIES, "Tried getting sprite %u", spriteIndex);
152 return try_get_sprite(spriteIndex);
153 }
154
GetEntityTileList(const CoordsXY & spritePos)155 const std::vector<uint16_t>& GetEntityTileList(const CoordsXY& spritePos)
156 {
157 return gSpriteSpatialIndex[GetSpatialIndexOffset(spritePos)];
158 }
159
Invalidate()160 void EntityBase::Invalidate()
161 {
162 if (x == LOCATION_NULL)
163 return;
164
165 int32_t maxZoom = 0;
166 switch (Type)
167 {
168 case EntityType::Vehicle:
169 case EntityType::Guest:
170 case EntityType::Staff:
171 maxZoom = 2;
172 break;
173 case EntityType::CrashedVehicleParticle:
174 case EntityType::JumpingFountain:
175 maxZoom = 0;
176 break;
177 case EntityType::Duck:
178 maxZoom = 1;
179 break;
180 case EntityType::SteamParticle:
181 case EntityType::MoneyEffect:
182 case EntityType::ExplosionCloud:
183 case EntityType::CrashSplash:
184 case EntityType::ExplosionFlare:
185 case EntityType::Balloon:
186 maxZoom = 2;
187 break;
188 case EntityType::Litter:
189 maxZoom = 0;
190 break;
191 default:
192 break;
193 }
194
195 viewports_invalidate(SpriteRect, maxZoom);
196 }
197
ResetEntityLists()198 static void ResetEntityLists()
199 {
200 for (auto& list : gEntityLists)
201 {
202 list.clear();
203 }
204 }
205
ResetFreeIds()206 static void ResetFreeIds()
207 {
208 _freeIdList.clear();
209
210 _freeIdList.resize(MAX_ENTITIES);
211 // List needs to be back to front to simplify removing
212 std::iota(std::rbegin(_freeIdList), std::rend(_freeIdList), 0);
213 }
214
GetEntityList(const EntityType id)215 const std::list<uint16_t>& GetEntityList(const EntityType id)
216 {
217 return gEntityLists[EnumValue(id)];
218 }
219
220 /**
221 *
222 * rct2: 0x0069EB13
223 */
reset_sprite_list()224 void reset_sprite_list()
225 {
226 gSavedAge = 0;
227
228 // Free all associated Entity pointers prior to zeroing memory
229 for (int32_t i = 0; i < MAX_ENTITIES; ++i)
230 {
231 auto* spr = GetEntity(i);
232 if (spr == nullptr)
233 {
234 continue;
235 }
236 FreeEntity(*spr);
237 }
238
239 std::fill(std::begin(_spriteList), std::end(_spriteList), rct_sprite());
240 OpenRCT2::RideUse::GetHistory().Clear();
241 OpenRCT2::RideUse::GetTypeHistory().Clear();
242 for (int32_t i = 0; i < MAX_ENTITIES; ++i)
243 {
244 auto* spr = GetEntity(i);
245 if (spr == nullptr)
246 {
247 continue;
248 }
249 spr->Type = EntityType::Null;
250 spr->sprite_index = i;
251
252 _spriteFlashingList[i] = false;
253 }
254 ResetEntityLists();
255 ResetFreeIds();
256 reset_sprite_spatial_index();
257 }
258
259 static void SpriteSpatialInsert(EntityBase* sprite, const CoordsXY& newLoc);
260
261 /**
262 *
263 * rct2: 0x0069EBE4
264 * This function looks as though it sets some sort of order for sprites.
265 * Sprites can share their position if this is the case.
266 */
reset_sprite_spatial_index()267 void reset_sprite_spatial_index()
268 {
269 for (auto& vec : gSpriteSpatialIndex)
270 {
271 vec.clear();
272 }
273 for (size_t i = 0; i < MAX_ENTITIES; i++)
274 {
275 auto* spr = GetEntity(i);
276 if (spr != nullptr && spr->Type != EntityType::Null)
277 {
278 SpriteSpatialInsert(spr, { spr->x, spr->y });
279 }
280 }
281 }
282
283 #ifndef DISABLE_NETWORK
284
NetworkSerialseEntityType(DataSerialiser & ds)285 template<typename T> void NetworkSerialseEntityType(DataSerialiser& ds)
286 {
287 for (auto* ent : EntityList<T>())
288 {
289 ent->Serialise(ds);
290 }
291 }
292
NetworkSerialiseEntityTypes(DataSerialiser & ds)293 template<typename... T> void NetworkSerialiseEntityTypes(DataSerialiser& ds)
294 {
295 (NetworkSerialseEntityType<T>(ds), ...);
296 }
297
sprite_checksum()298 rct_sprite_checksum sprite_checksum()
299 {
300 rct_sprite_checksum checksum{};
301
302 OpenRCT2::ChecksumStream ms(checksum.raw);
303 DataSerialiser ds(true, ms);
304 NetworkSerialiseEntityTypes<Guest, Staff, Vehicle, Litter>(ds);
305
306 return checksum;
307 }
308 #else
309
sprite_checksum()310 rct_sprite_checksum sprite_checksum()
311 {
312 return rct_sprite_checksum{};
313 }
314
315 #endif // DISABLE_NETWORK
316
sprite_reset(EntityBase * sprite)317 static void sprite_reset(EntityBase* sprite)
318 {
319 // Need to retain how the sprite is linked in lists
320 uint16_t sprite_index = sprite->sprite_index;
321 _spriteFlashingList[sprite_index] = false;
322
323 rct_sprite* spr = reinterpret_cast<rct_sprite*>(sprite);
324 *spr = rct_sprite();
325
326 sprite->sprite_index = sprite_index;
327 sprite->Type = EntityType::Null;
328 }
329
330 static constexpr uint16_t MAX_MISC_SPRITES = 300;
AddToEntityList(EntityBase * entity)331 static void AddToEntityList(EntityBase* entity)
332 {
333 auto& list = gEntityLists[EnumValue(entity->Type)];
334 // Entity list must be in sprite_index order to prevent desync issues
335 list.insert(std::lower_bound(std::begin(list), std::end(list), entity->sprite_index), entity->sprite_index);
336 }
337
AddToFreeList(uint16_t index)338 static void AddToFreeList(uint16_t index)
339 {
340 // Free list must be in reverse sprite_index order to prevent desync issues
341 _freeIdList.insert(std::upper_bound(std::rbegin(_freeIdList), std::rend(_freeIdList), index).base(), index);
342 }
343
RemoveFromEntityList(EntityBase * entity)344 static void RemoveFromEntityList(EntityBase* entity)
345 {
346 auto& list = gEntityLists[EnumValue(entity->Type)];
347 auto ptr = std::lower_bound(std::begin(list), std::end(list), entity->sprite_index);
348 if (ptr != std::end(list) && *ptr == entity->sprite_index)
349 {
350 list.erase(ptr);
351 }
352 }
353
GetMiscEntityCount()354 uint16_t GetMiscEntityCount()
355 {
356 uint16_t count = 0;
357 for (auto id : { EntityType::SteamParticle, EntityType::MoneyEffect, EntityType::CrashedVehicleParticle,
358 EntityType::ExplosionCloud, EntityType::CrashSplash, EntityType::ExplosionFlare,
359 EntityType::JumpingFountain, EntityType::Balloon, EntityType::Duck })
360 {
361 count += GetEntityListCount(id);
362 }
363 return count;
364 }
365
PrepareNewEntity(EntityBase * base,const EntityType type)366 static void PrepareNewEntity(EntityBase* base, const EntityType type)
367 {
368 // Need to reset all sprite data, as the uninitialised values
369 // may contain garbage and cause a desync later on.
370 sprite_reset(base);
371
372 base->Type = type;
373 AddToEntityList(base);
374
375 base->x = LOCATION_NULL;
376 base->y = LOCATION_NULL;
377 base->z = 0;
378 base->sprite_width = 0x10;
379 base->sprite_height_negative = 0x14;
380 base->sprite_height_positive = 0x8;
381 base->SpriteRect = {};
382
383 SpriteSpatialInsert(base, { LOCATION_NULL, 0 });
384 }
385
CreateEntity(EntityType type)386 EntityBase* CreateEntity(EntityType type)
387 {
388 if (_freeIdList.size() == 0)
389 {
390 // No free sprites.
391 return nullptr;
392 }
393
394 if (EntityTypeIsMiscEntity(type))
395 {
396 // Misc sprites are commonly used for effects, if there are less than MAX_MISC_SPRITES
397 // free it will fail to keep slots for more relevant sprites.
398 // Also there can't be more than MAX_MISC_SPRITES sprites in this list.
399 uint16_t miscSlotsRemaining = MAX_MISC_SPRITES - GetMiscEntityCount();
400 if (miscSlotsRemaining >= _freeIdList.size())
401 {
402 return nullptr;
403 }
404 }
405
406 auto* entity = GetEntity(_freeIdList.back());
407 if (entity == nullptr)
408 {
409 return nullptr;
410 }
411 _freeIdList.pop_back();
412
413 PrepareNewEntity(entity, type);
414
415 return entity;
416 }
417
CreateEntityAt(const uint16_t index,const EntityType type)418 EntityBase* CreateEntityAt(const uint16_t index, const EntityType type)
419 {
420 auto id = std::lower_bound(std::rbegin(_freeIdList), std::rend(_freeIdList), index);
421 if (id == std::rend(_freeIdList) || *id != index)
422 {
423 return nullptr;
424 }
425
426 auto* entity = GetEntity(index);
427 if (entity == nullptr)
428 {
429 return nullptr;
430 }
431
432 _freeIdList.erase(std::next(id).base());
433
434 PrepareNewEntity(entity, type);
435 return entity;
436 }
437
MiscUpdateAllType()438 template<typename T> void MiscUpdateAllType()
439 {
440 for (auto misc : EntityList<T>())
441 {
442 misc->Update();
443 }
444 }
445
MiscUpdateAllTypes()446 template<typename... T> void MiscUpdateAllTypes()
447 {
448 (MiscUpdateAllType<T>(), ...);
449 }
450
451 /**
452 *
453 * rct2: 0x00672AA4
454 */
sprite_misc_update_all()455 void sprite_misc_update_all()
456 {
457 MiscUpdateAllTypes<
458 SteamParticle, MoneyEffect, VehicleCrashParticle, ExplosionCloud, CrashSplashParticle, ExplosionFlare, JumpingFountain,
459 Balloon, Duck>();
460 }
461
462 // Performs a search to ensure that insert keeps next_in_quadrant in sprite_index order
SpriteSpatialInsert(EntityBase * sprite,const CoordsXY & newLoc)463 static void SpriteSpatialInsert(EntityBase* sprite, const CoordsXY& newLoc)
464 {
465 size_t newIndex = GetSpatialIndexOffset(newLoc);
466 auto& spatialVector = gSpriteSpatialIndex[newIndex];
467 auto index = std::lower_bound(std::begin(spatialVector), std::end(spatialVector), sprite->sprite_index);
468 spatialVector.insert(index, sprite->sprite_index);
469 }
470
SpriteSpatialRemove(EntityBase * sprite)471 static void SpriteSpatialRemove(EntityBase* sprite)
472 {
473 size_t currentIndex = GetSpatialIndexOffset({ sprite->x, sprite->y });
474 auto& spatialVector = gSpriteSpatialIndex[currentIndex];
475 auto index = std::lower_bound(std::begin(spatialVector), std::end(spatialVector), sprite->sprite_index);
476 if (index != std::end(spatialVector) && *index == sprite->sprite_index)
477 {
478 spatialVector.erase(index, index + 1);
479 }
480 else
481 {
482 log_warning("Bad sprite spatial index. Rebuilding the spatial index...");
483 reset_sprite_spatial_index();
484 }
485 }
486
SpriteSpatialMove(EntityBase * sprite,const CoordsXY & newLoc)487 static void SpriteSpatialMove(EntityBase* sprite, const CoordsXY& newLoc)
488 {
489 size_t newIndex = GetSpatialIndexOffset(newLoc);
490 size_t currentIndex = GetSpatialIndexOffset({ sprite->x, sprite->y });
491 if (newIndex == currentIndex)
492 return;
493
494 SpriteSpatialRemove(sprite);
495 SpriteSpatialInsert(sprite, newLoc);
496 }
497
MoveTo(const CoordsXYZ & newLocation)498 void EntityBase::MoveTo(const CoordsXYZ& newLocation)
499 {
500 if (x != LOCATION_NULL)
501 {
502 // Invalidate old position.
503 Invalidate();
504 }
505
506 auto loc = newLocation;
507 if (!map_is_location_valid(loc))
508 {
509 loc.x = LOCATION_NULL;
510 }
511
512 SpriteSpatialMove(this, loc);
513
514 if (loc.x == LOCATION_NULL)
515 {
516 x = loc.x;
517 y = loc.y;
518 z = loc.z;
519 }
520 else
521 {
522 sprite_set_coordinates(loc, this);
523 Invalidate(); // Invalidate new position.
524 }
525 }
526
GetLocation() const527 CoordsXYZ EntityBase::GetLocation() const
528 {
529 return { x, y, z };
530 }
531
SetLocation(const CoordsXYZ & newLocation)532 void EntityBase::SetLocation(const CoordsXYZ& newLocation)
533 {
534 x = static_cast<int16_t>(newLocation.x);
535 y = static_cast<int16_t>(newLocation.y);
536 z = static_cast<int16_t>(newLocation.z);
537 }
538
sprite_set_coordinates(const CoordsXYZ & spritePos,EntityBase * sprite)539 void sprite_set_coordinates(const CoordsXYZ& spritePos, EntityBase* sprite)
540 {
541 auto screenCoords = translate_3d_to_2d_with_z(get_current_rotation(), spritePos);
542
543 sprite->SpriteRect = ScreenRect(
544 screenCoords - ScreenCoordsXY{ sprite->sprite_width, sprite->sprite_height_negative },
545 screenCoords + ScreenCoordsXY{ sprite->sprite_width, sprite->sprite_height_positive });
546 sprite->SetLocation(spritePos);
547 }
548
549 /**
550 * Frees any dynamically attached memory to the entity, such as peep name.
551 */
FreeEntity(EntityBase & entity)552 static void FreeEntity(EntityBase& entity)
553 {
554 auto* guest = entity.As<Guest>();
555 auto* staff = entity.As<Staff>();
556 if (staff != nullptr)
557 {
558 staff->SetName({});
559 staff->ClearPatrolArea();
560 }
561 else if (guest != nullptr)
562 {
563 guest->SetName({});
564 OpenRCT2::RideUse::GetHistory().RemoveHandle(guest->sprite_index);
565 OpenRCT2::RideUse::GetTypeHistory().RemoveHandle(guest->sprite_index);
566 }
567 }
568
569 /**
570 *
571 * rct2: 0x0069EDB6
572 */
sprite_remove(EntityBase * sprite)573 void sprite_remove(EntityBase* sprite)
574 {
575 FreeEntity(*sprite);
576
577 EntityTweener::Get().RemoveEntity(sprite);
578 RemoveFromEntityList(sprite); // remove from existing list
579 AddToFreeList(sprite->sprite_index);
580
581 SpriteSpatialRemove(sprite);
582 sprite_reset(sprite);
583 }
584
585 /**
586 * Loops through all sprites, finds floating objects and removes them.
587 * Returns the amount of removed objects as feedback.
588 */
remove_floating_sprites()589 uint16_t remove_floating_sprites()
590 {
591 uint16_t removed = 0;
592 for (auto* balloon : EntityList<Balloon>())
593 {
594 sprite_remove(balloon);
595 removed++;
596 }
597 for (auto* duck : EntityList<Duck>())
598 {
599 if (duck->IsFlying())
600 {
601 sprite_remove(duck);
602 removed++;
603 }
604 }
605 for (auto* money : EntityList<MoneyEffect>())
606 {
607 sprite_remove(money);
608 removed++;
609 }
610 return removed;
611 }
612
sprite_set_flashing(EntityBase * sprite,bool flashing)613 void sprite_set_flashing(EntityBase* sprite, bool flashing)
614 {
615 assert(sprite->sprite_index < MAX_ENTITIES);
616 _spriteFlashingList[sprite->sprite_index] = flashing;
617 }
618
sprite_get_flashing(EntityBase * sprite)619 bool sprite_get_flashing(EntityBase* sprite)
620 {
621 assert(sprite->sprite_index < MAX_ENTITIES);
622 return _spriteFlashingList[sprite->sprite_index];
623 }
624