map.cpp

main 989 lines · 25.3 KB Raw
Alex Alex Commit Server upload 18/10/2026 23:38
1/**
2 * The Forgotten Server - a free and open-source MMORPG server emulator
3 * Copyright (C) 2019 Mark Samman <mark.samman@gmail.com>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20#include "otpch.h"
21
22#include "iomap.h"
23#include "iomapserialize.h"
24#include "combat.h"
25#include "creature.h"
26#include "game.h"
27#include "monster.h"
28
29extern Game g_game;
30
31bool Map::loadMap(const std::string& identifier, bool loadHouses)
32{
33 IOMap loader;
34 if (!loader.loadMap(this, identifier)) {
35 std::cout << "[Fatal - Map::loadMap] " << loader.getLastErrorString() << std::endl;
36 return false;
37 }
38
39 if (!IOMap::loadSpawns(this)) {
40 std::cout << "[Warning - Map::loadMap] Failed to load spawn data." << std::endl;
41 }
42
43 if (loadHouses) {
44 if (!IOMap::loadHouses(this)) {
45 std::cout << "[Warning - Map::loadMap] Failed to load house data." << std::endl;
46 }
47
48 IOMapSerialize::loadHouseInfo();
49 IOMapSerialize::loadHouseItems(this);
50 }
51 return true;
52}
53
54bool Map::save()
55{
56 bool saved = false;
57 for (uint32_t tries = 0; tries < 3; tries++) {
58 if (IOMapSerialize::saveHouseInfo()) {
59 saved = true;
60 break;
61 }
62 }
63
64 if (!saved) {
65 return false;
66 }
67
68 saved = false;
69 for (uint32_t tries = 0; tries < 3; tries++) {
70 if (IOMapSerialize::saveHouseItems()) {
71 saved = true;
72 break;
73 }
74 }
75 return saved;
76}
77
78Tile* Map::getTile(uint16_t x, uint16_t y, uint8_t z) const
79{
80 if (z >= MAP_MAX_LAYERS) {
81 return nullptr;
82 }
83
84 const QTreeLeafNode* leaf = QTreeNode::getLeafStatic<const QTreeLeafNode*, const QTreeNode*>(&root, x, y);
85 if (!leaf) {
86 return nullptr;
87 }
88
89 const Floor* floor = leaf->getFloor(z);
90 if (!floor) {
91 return nullptr;
92 }
93 return floor->tiles[x & FLOOR_MASK][y & FLOOR_MASK];
94}
95
96void Map::setTile(uint16_t x, uint16_t y, uint8_t z, Tile* newTile)
97{
98 if (z >= MAP_MAX_LAYERS) {
99 std::cout << "ERROR: Attempt to set tile on invalid coordinate " << Position(x, y, z) << "!" << std::endl;
100 return;
101 }
102
103 QTreeLeafNode::newLeaf = false;
104 QTreeLeafNode* leaf = root.createLeaf(x, y, 15);
105
106 if (QTreeLeafNode::newLeaf) {
107 //update north
108 QTreeLeafNode* northLeaf = root.getLeaf(x, y - FLOOR_SIZE);
109 if (northLeaf) {
110 northLeaf->leafS = leaf;
111 }
112
113 //update west leaf
114 QTreeLeafNode* westLeaf = root.getLeaf(x - FLOOR_SIZE, y);
115 if (westLeaf) {
116 westLeaf->leafE = leaf;
117 }
118
119 //update south
120 QTreeLeafNode* southLeaf = root.getLeaf(x, y + FLOOR_SIZE);
121 if (southLeaf) {
122 leaf->leafS = southLeaf;
123 }
124
125 //update east
126 QTreeLeafNode* eastLeaf = root.getLeaf(x + FLOOR_SIZE, y);
127 if (eastLeaf) {
128 leaf->leafE = eastLeaf;
129 }
130 }
131
132 Floor* floor = leaf->createFloor(z);
133 uint32_t offsetX = x & FLOOR_MASK;
134 uint32_t offsetY = y & FLOOR_MASK;
135
136 Tile*& tile = floor->tiles[offsetX][offsetY];
137 if (tile) {
138 TileItemVector* items = newTile->getItemList();
139 if (items) {
140 for (auto it = items->rbegin(), end = items->rend(); it != end; ++it) {
141 tile->addThing(*it);
142 }
143 items->clear();
144 }
145
146 Item* ground = newTile->getGround();
147 if (ground) {
148 tile->addThing(ground);
149 newTile->setGround(nullptr);
150 }
151 delete newTile;
152 } else {
153 tile = newTile;
154 }
155}
156
157bool Map::placeCreature(const Position& centerPos, Creature* creature, bool extendedPos/* = false*/, bool forceLogin/* = false*/)
158{
159 bool foundTile;
160 bool placeInPZ;
161
162 Tile* tile = getTile(centerPos.x, centerPos.y, centerPos.z);
163 if (tile) {
164 placeInPZ = tile->hasFlag(TILESTATE_PROTECTIONZONE);
165 ReturnValue ret = tile->queryAdd(0, *creature, 1, FLAG_IGNOREBLOCKITEM);
166 foundTile = forceLogin || ret == RETURNVALUE_NOERROR || ret == RETURNVALUE_PLAYERISNOTINVITED;
167 } else {
168 placeInPZ = false;
169 foundTile = false;
170 }
171
172 if (!foundTile) {
173 static std::vector<std::pair<int32_t, int32_t>> extendedRelList {
174 {0, -2},
175 {-1, -1}, {0, -1}, {1, -1},
176 {-2, 0}, {-1, 0}, {1, 0}, {2, 0},
177 {-1, 1}, {0, 1}, {1, 1},
178 {0, 2}
179 };
180
181 static std::vector<std::pair<int32_t, int32_t>> normalRelList {
182 {-1, -1}, {0, -1}, {1, -1},
183 {-1, 0}, {1, 0},
184 {-1, 1}, {0, 1}, {1, 1}
185 };
186
187 std::vector<std::pair<int32_t, int32_t>>& relList = (extendedPos ? extendedRelList : normalRelList);
188
189 if (extendedPos) {
190 std::shuffle(relList.begin(), relList.begin() + 4, getRandomGenerator());
191 std::shuffle(relList.begin() + 4, relList.end(), getRandomGenerator());
192 } else {
193 std::shuffle(relList.begin(), relList.end(), getRandomGenerator());
194 }
195
196 for (const auto& it : relList) {
197 Position tryPos(centerPos.x + it.first, centerPos.y + it.second, centerPos.z);
198
199 tile = getTile(tryPos.x, tryPos.y, tryPos.z);
200 if (!tile || (placeInPZ && !tile->hasFlag(TILESTATE_PROTECTIONZONE))) {
201 continue;
202 }
203
204 if (tile->queryAdd(0, *creature, 1, 0) == RETURNVALUE_NOERROR) {
205 if (!extendedPos || isSightClear(centerPos, tryPos, false)) {
206 foundTile = true;
207 break;
208 }
209 }
210 }
211
212 if (!foundTile) {
213 return false;
214 }
215 }
216
217 int32_t index = 0;
218 uint32_t flags = 0;
219 Item* toItem = nullptr;
220
221 Cylinder* toCylinder = tile->queryDestination(index, *creature, &toItem, flags);
222 toCylinder->internalAddThing(creature);
223
224 const Position& dest = toCylinder->getPosition();
225 getQTNode(dest.x, dest.y)->addCreature(creature);
226 return true;
227}
228
229void Map::moveCreature(Creature& creature, Tile& newTile, bool forceTeleport/* = false*/)
230{
231 Tile& oldTile = *creature.getTile();
232
233 Position oldPos = oldTile.getPosition();
234 Position newPos = newTile.getPosition();
235
236 bool teleport = forceTeleport || !newTile.getGround() || !Position::areInRange<1, 1, 0>(oldPos, newPos);
237
238 SpectatorVec spectators, newPosSpectators;
239 getSpectators(spectators, oldPos, true);
240 getSpectators(newPosSpectators, newPos, true);
241 spectators.addSpectators(newPosSpectators);
242
243 std::vector<int32_t> oldStackPosVector;
244 for (Creature* spectator : spectators) {
245 if (Player* tmpPlayer = spectator->getPlayer()) {
246 if (tmpPlayer->canSeeCreature(&creature)) {
247 oldStackPosVector.push_back(oldTile.getClientIndexOfCreature(tmpPlayer, &creature));
248 } else {
249 oldStackPosVector.push_back(-1);
250 }
251 }
252 }
253
254 //remove the creature
255 oldTile.removeThing(&creature, 0);
256
257 QTreeLeafNode* leaf = getQTNode(oldPos.x, oldPos.y);
258 QTreeLeafNode* new_leaf = getQTNode(newPos.x, newPos.y);
259
260 // Switch the node ownership
261 if (leaf != new_leaf) {
262 leaf->removeCreature(&creature);
263 new_leaf->addCreature(&creature);
264 }
265
266 //add the creature
267 newTile.addThing(&creature);
268
269 if (!teleport) {
270 if (oldPos.y > newPos.y) {
271 creature.setDirection(DIRECTION_NORTH);
272 } else if (oldPos.y < newPos.y) {
273 creature.setDirection(DIRECTION_SOUTH);
274 }
275
276 if (oldPos.x < newPos.x) {
277 creature.setDirection(DIRECTION_EAST);
278 } else if (oldPos.x > newPos.x) {
279 creature.setDirection(DIRECTION_WEST);
280 }
281 }
282
283 //send to client
284 size_t i = 0;
285 for (Creature* spectator : spectators) {
286 if (Player* tmpPlayer = spectator->getPlayer()) {
287 //Use the correct stackpos
288 int32_t stackpos = oldStackPosVector[i++];
289 if (stackpos != -1) {
290 tmpPlayer->sendCreatureMove(&creature, newPos, newTile.getStackposOfCreature(tmpPlayer, &creature), oldPos, stackpos, teleport);
291 }
292 }
293 }
294
295 //event method
296 for (Creature* spectator : spectators) {
297 spectator->onCreatureMove(&creature, &newTile, newPos, &oldTile, oldPos, teleport);
298 }
299
300 oldTile.postRemoveNotification(&creature, &newTile, 0);
301 newTile.postAddNotification(&creature, &oldTile, 0);
302}
303
304void Map::getSpectatorsInternal(SpectatorVec& spectators, const Position& centerPos, int32_t minRangeX, int32_t maxRangeX, int32_t minRangeY, int32_t maxRangeY, int32_t minRangeZ, int32_t maxRangeZ, bool onlyPlayers) const
305{
306 int_fast16_t min_y = centerPos.y + minRangeY;
307 int_fast16_t min_x = centerPos.x + minRangeX;
308 int_fast16_t max_y = centerPos.y + maxRangeY;
309 int_fast16_t max_x = centerPos.x + maxRangeX;
310
311 int32_t minoffset = centerPos.getZ() - maxRangeZ;
312 uint16_t x1 = std::min<uint32_t>(0xFFFF, std::max<int32_t>(0, (min_x + minoffset)));
313 uint16_t y1 = std::min<uint32_t>(0xFFFF, std::max<int32_t>(0, (min_y + minoffset)));
314
315 int32_t maxoffset = centerPos.getZ() - minRangeZ;
316 uint16_t x2 = std::min<uint32_t>(0xFFFF, std::max<int32_t>(0, (max_x + maxoffset)));
317 uint16_t y2 = std::min<uint32_t>(0xFFFF, std::max<int32_t>(0, (max_y + maxoffset)));
318
319 int32_t startx1 = x1 - (x1 % FLOOR_SIZE);
320 int32_t starty1 = y1 - (y1 % FLOOR_SIZE);
321 int32_t endx2 = x2 - (x2 % FLOOR_SIZE);
322 int32_t endy2 = y2 - (y2 % FLOOR_SIZE);
323
324 const QTreeLeafNode* startLeaf = QTreeNode::getLeafStatic<const QTreeLeafNode*, const QTreeNode*>(&root, startx1, starty1);
325 const QTreeLeafNode* leafS = startLeaf;
326 const QTreeLeafNode* leafE;
327
328 for (int_fast32_t ny = starty1; ny <= endy2; ny += FLOOR_SIZE) {
329 leafE = leafS;
330 for (int_fast32_t nx = startx1; nx <= endx2; nx += FLOOR_SIZE) {
331 if (leafE) {
332 const CreatureVector& node_list = (onlyPlayers ? leafE->player_list : leafE->creature_list);
333 for (Creature* creature : node_list) {
334 const Position& cpos = creature->getPosition();
335 if (minRangeZ > cpos.z || maxRangeZ < cpos.z) {
336 continue;
337 }
338
339 int_fast16_t offsetZ = Position::getOffsetZ(centerPos, cpos);
340 if ((min_y + offsetZ) > cpos.y || (max_y + offsetZ) < cpos.y || (min_x + offsetZ) > cpos.x || (max_x + offsetZ) < cpos.x) {
341 continue;
342 }
343
344 spectators.emplace_back(creature);
345 }
346 leafE = leafE->leafE;
347 } else {
348 leafE = QTreeNode::getLeafStatic<const QTreeLeafNode*, const QTreeNode*>(&root, nx + FLOOR_SIZE, ny);
349 }
350 }
351
352 if (leafS) {
353 leafS = leafS->leafS;
354 } else {
355 leafS = QTreeNode::getLeafStatic<const QTreeLeafNode*, const QTreeNode*>(&root, startx1, ny + FLOOR_SIZE);
356 }
357 }
358}
359
360void Map::getSpectators(SpectatorVec& spectators, const Position& centerPos, bool multifloor /*= false*/, bool onlyPlayers /*= false*/, int32_t minRangeX /*= 0*/, int32_t maxRangeX /*= 0*/, int32_t minRangeY /*= 0*/, int32_t maxRangeY /*= 0*/)
361{
362 if (centerPos.z >= MAP_MAX_LAYERS) {
363 return;
364 }
365
366 bool foundCache = false;
367 bool cacheResult = false;
368
369 minRangeX = (minRangeX == 0 ? -maxViewportX : -minRangeX);
370 maxRangeX = (maxRangeX == 0 ? maxViewportX : maxRangeX);
371 minRangeY = (minRangeY == 0 ? -maxViewportY : -minRangeY);
372 maxRangeY = (maxRangeY == 0 ? maxViewportY : maxRangeY);
373
374 if (minRangeX == -maxViewportX && maxRangeX == maxViewportX && minRangeY == -maxViewportY && maxRangeY == maxViewportY && multifloor) {
375 if (onlyPlayers) {
376 auto it = playersSpectatorCache.find(centerPos);
377 if (it != playersSpectatorCache.end()) {
378 if (!spectators.empty()) {
379 const SpectatorVec& cachedSpectators = it->second;
380 spectators.insert(spectators.end(), cachedSpectators.begin(), cachedSpectators.end());
381 } else {
382 spectators = it->second;
383 }
384
385 foundCache = true;
386 }
387 }
388
389 if (!foundCache) {
390 auto it = spectatorCache.find(centerPos);
391 if (it != spectatorCache.end()) {
392 if (!onlyPlayers) {
393 if (!spectators.empty()) {
394 const SpectatorVec& cachedSpectators = it->second;
395 spectators.insert(spectators.end(), cachedSpectators.begin(), cachedSpectators.end());
396 } else {
397 spectators = it->second;
398 }
399 } else {
400 const SpectatorVec& cachedSpectators = it->second;
401 for (Creature* spectator : cachedSpectators) {
402 if (spectator->getPlayer()) {
403 spectators.emplace_back(spectator);
404 }
405 }
406 }
407
408 foundCache = true;
409 } else {
410 cacheResult = true;
411 }
412 }
413 }
414
415 if (!foundCache) {
416 int32_t minRangeZ;
417 int32_t maxRangeZ;
418
419 if (multifloor) {
420 if (centerPos.z > 7) {
421 //underground
422
423 //8->15
424 minRangeZ = std::max<int32_t>(centerPos.getZ() - 2, 0);
425 maxRangeZ = std::min<int32_t>(centerPos.getZ() + 2, MAP_MAX_LAYERS - 1);
426 } else if (centerPos.z == 6) {
427 minRangeZ = 0;
428 maxRangeZ = 8;
429 } else if (centerPos.z == 7) {
430 minRangeZ = 0;
431 maxRangeZ = 9;
432 } else {
433 minRangeZ = 0;
434 maxRangeZ = 7;
435 }
436 } else {
437 minRangeZ = centerPos.z;
438 maxRangeZ = centerPos.z;
439 }
440
441 getSpectatorsInternal(spectators, centerPos, minRangeX, maxRangeX, minRangeY, maxRangeY, minRangeZ, maxRangeZ, onlyPlayers);
442
443 if (cacheResult) {
444 if (onlyPlayers) {
445 playersSpectatorCache[centerPos] = spectators;
446 } else {
447 spectatorCache[centerPos] = spectators;
448 }
449 }
450 }
451}
452
453void Map::clearSpectatorCache()
454{
455 spectatorCache.clear();
456}
457
458void Map::clearPlayersSpectatorCache()
459{
460 playersSpectatorCache.clear();
461}
462
463bool Map::canThrowObjectTo(const Position& fromPos, const Position& toPos, bool checkLineOfSight /*= true*/,
464 int32_t rangex /*= Map::maxClientViewportX*/, int32_t rangey /*= Map::maxClientViewportY*/) const
465{
466 //z checks
467 //underground 8->15
468 //ground level and above 7->0
469 if ((fromPos.z >= 8 && toPos.z < 8) || (toPos.z >= 8 && fromPos.z < 8)) {
470 return false;
471 }
472
473 int32_t deltaz = Position::getDistanceZ(fromPos, toPos);
474 if (deltaz > 2) {
475 return false;
476 }
477
478 if ((Position::getDistanceX(fromPos, toPos) - deltaz) > rangex) {
479 return false;
480 }
481
482 //distance checks
483 if ((Position::getDistanceY(fromPos, toPos) - deltaz) > rangey) {
484 return false;
485 }
486
487 if (!checkLineOfSight) {
488 return true;
489 }
490 return isSightClear(fromPos, toPos, false);
491}
492
493bool Map::checkSightLine(const Position& fromPos, const Position& toPos) const
494{
495 if (fromPos == toPos) {
496 return true;
497 }
498
499 Position start(fromPos.z > toPos.z ? toPos : fromPos);
500 Position destination(fromPos.z > toPos.z ? fromPos : toPos);
501
502 const int8_t mx = start.x < destination.x ? 1 : start.x == destination.x ? 0 : -1;
503 const int8_t my = start.y < destination.y ? 1 : start.y == destination.y ? 0 : -1;
504
505 int32_t A = Position::getOffsetY(destination, start);
506 int32_t B = Position::getOffsetX(start, destination);
507 int32_t C = -(A * destination.x + B * destination.y);
508
509 while (start.x != destination.x || start.y != destination.y) {
510 int32_t move_hor = std::abs(A * (start.x + mx) + B * (start.y) + C);
511 int32_t move_ver = std::abs(A * (start.x) + B * (start.y + my) + C);
512 int32_t move_cross = std::abs(A * (start.x + mx) + B * (start.y + my) + C);
513
514 if (start.y != destination.y && (start.x == destination.x || move_hor > move_ver || move_hor > move_cross)) {
515 start.y += my;
516 }
517
518 if (start.x != destination.x && (start.y == destination.y || move_ver > move_hor || move_ver > move_cross)) {
519 start.x += mx;
520 }
521
522 const Tile* tile = getTile(start.x, start.y, start.z);
523 if (tile && tile->hasProperty(CONST_PROP_BLOCKPROJECTILE)) {
524 return false;
525 }
526 }
527
528 // now we need to perform a jump between floors to see if everything is clear (literally)
529 while (start.z != destination.z) {
530 const Tile* tile = getTile(start.x, start.y, start.z);
531 if (tile && tile->getThingCount() > 0) {
532 return false;
533 }
534
535 start.z++;
536 }
537
538 return true;
539}
540
541bool Map::isSightClear(const Position& fromPos, const Position& toPos, bool floorCheck) const
542{
543 if (floorCheck && fromPos.z != toPos.z) {
544 return false;
545 }
546
547 // Cast two converging rays and see if either yields a result.
548 return checkSightLine(fromPos, toPos) || checkSightLine(toPos, fromPos);
549}
550
551const Tile* Map::canWalkTo(const Creature& creature, const Position& pos) const
552{
553 int32_t walkCache = creature.getWalkCache(pos);
554 if (walkCache == 0) {
555 return nullptr;
556 } else if (walkCache == 1) {
557 return getTile(pos.x, pos.y, pos.z);
558 }
559
560 //used for non-cached tiles
561 Tile* tile = getTile(pos.x, pos.y, pos.z);
562 if (creature.getTile() != tile) {
563 if (!tile || tile->queryAdd(0, creature, 1, FLAG_PATHFINDING | FLAG_IGNOREFIELDDAMAGE) != RETURNVALUE_NOERROR) {
564 return nullptr;
565 }
566 }
567 return tile;
568}
569
570bool Map::getPathMatching(const Creature& creature, std::list<Direction>& dirList, const FrozenPathingConditionCall& pathCondition, const FindPathParams& fpp) const
571{
572 Position pos = creature.getPosition();
573 Position endPos;
574
575 AStarNodes nodes(pos.x, pos.y);
576
577 int32_t bestMatch = 0;
578
579 static int_fast32_t dirNeighbors[8][5][2] = {
580 {{-1, 0}, {0, 1}, {1, 0}, {1, 1}, {-1, 1}},
581 {{-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}},
582 {{-1, 0}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}},
583 {{0, 1}, {1, 0}, {0, -1}, {1, -1}, {1, 1}},
584 {{1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}},
585 {{-1, 0}, {0, -1}, {-1, -1}, {1, -1}, {-1, 1}},
586 {{0, 1}, {1, 0}, {1, -1}, {1, 1}, {-1, 1}},
587 {{-1, 0}, {0, 1}, {-1, -1}, {1, 1}, {-1, 1}}
588 };
589 static int_fast32_t allNeighbors[8][2] = {
590 {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}
591 };
592
593 const Position startPos = pos;
594
595 AStarNode* found = nullptr;
596 while (fpp.maxSearchDist != 0 || nodes.getClosedNodes() < 100) {
597 AStarNode* n = nodes.getBestNode();
598 if (!n) {
599 if (found) {
600 break;
601 }
602 return false;
603 }
604
605 const int_fast32_t x = n->x;
606 const int_fast32_t y = n->y;
607 pos.x = x;
608 pos.y = y;
609 if (pathCondition(startPos, pos, fpp, bestMatch)) {
610 found = n;
611 endPos = pos;
612 if (bestMatch == 0) {
613 break;
614 }
615 }
616
617 uint_fast32_t dirCount;
618 int_fast32_t* neighbors;
619 if (n->parent) {
620 const int_fast32_t offset_x = n->parent->x - x;
621 const int_fast32_t offset_y = n->parent->y - y;
622 if (offset_y == 0) {
623 if (offset_x == -1) {
624 neighbors = *dirNeighbors[DIRECTION_WEST];
625 } else {
626 neighbors = *dirNeighbors[DIRECTION_EAST];
627 }
628 } else if (!fpp.allowDiagonal || offset_x == 0) {
629 if (offset_y == -1) {
630 neighbors = *dirNeighbors[DIRECTION_NORTH];
631 } else {
632 neighbors = *dirNeighbors[DIRECTION_SOUTH];
633 }
634 } else if (offset_y == -1) {
635 if (offset_x == -1) {
636 neighbors = *dirNeighbors[DIRECTION_NORTHWEST];
637 } else {
638 neighbors = *dirNeighbors[DIRECTION_NORTHEAST];
639 }
640 } else if (offset_x == -1) {
641 neighbors = *dirNeighbors[DIRECTION_SOUTHWEST];
642 } else {
643 neighbors = *dirNeighbors[DIRECTION_SOUTHEAST];
644 }
645 dirCount = fpp.allowDiagonal ? 5 : 3;
646 } else {
647 dirCount = 8;
648 neighbors = *allNeighbors;
649 }
650
651 const int_fast32_t f = n->f;
652 for (uint_fast32_t i = 0; i < dirCount; ++i) {
653 pos.x = x + *neighbors++;
654 pos.y = y + *neighbors++;
655
656 if (fpp.maxSearchDist != 0 && (Position::getDistanceX(startPos, pos) > fpp.maxSearchDist || Position::getDistanceY(startPos, pos) > fpp.maxSearchDist)) {
657 continue;
658 }
659
660 if (fpp.keepDistance && !pathCondition.isInRange(startPos, pos, fpp)) {
661 continue;
662 }
663
664 const Tile* tile;
665 AStarNode* neighborNode = nodes.getNodeByPosition(pos.x, pos.y);
666 if (neighborNode) {
667 tile = getTile(pos.x, pos.y, pos.z);
668 } else {
669 tile = canWalkTo(creature, pos);
670 if (!tile) {
671 continue;
672 }
673 }
674
675 //The cost (g) for this neighbor
676 const int_fast32_t cost = AStarNodes::getMapWalkCost(n, pos);
677 const int_fast32_t extraCost = AStarNodes::getTileWalkCost(creature, tile);
678 const int_fast32_t newf = f + cost + extraCost;
679
680 if (neighborNode) {
681 if (neighborNode->f <= newf) {
682 //The node on the closed/open list is cheaper than this one
683 continue;
684 }
685
686 neighborNode->f = newf;
687 neighborNode->parent = n;
688 nodes.openNode(neighborNode);
689 } else {
690 //Does not exist in the open/closed list, create a new node
691 neighborNode = nodes.createOpenNode(n, pos.x, pos.y, newf);
692 if (!neighborNode) {
693 if (found) {
694 break;
695 }
696 return false;
697 }
698 }
699 }
700
701 nodes.closeNode(n);
702 }
703
704 if (!found) {
705 return false;
706 }
707
708 int_fast32_t prevx = endPos.x;
709 int_fast32_t prevy = endPos.y;
710
711 found = found->parent;
712 while (found) {
713 pos.x = found->x;
714 pos.y = found->y;
715
716 int_fast32_t dx = pos.getX() - prevx;
717 int_fast32_t dy = pos.getY() - prevy;
718
719 prevx = pos.x;
720 prevy = pos.y;
721
722 if (dx == 1 && dy == 1) {
723 dirList.push_front(DIRECTION_NORTHWEST);
724 } else if (dx == -1 && dy == 1) {
725 dirList.push_front(DIRECTION_NORTHEAST);
726 } else if (dx == 1 && dy == -1) {
727 dirList.push_front(DIRECTION_SOUTHWEST);
728 } else if (dx == -1 && dy == -1) {
729 dirList.push_front(DIRECTION_SOUTHEAST);
730 } else if (dx == 1) {
731 dirList.push_front(DIRECTION_WEST);
732 } else if (dx == -1) {
733 dirList.push_front(DIRECTION_EAST);
734 } else if (dy == 1) {
735 dirList.push_front(DIRECTION_NORTH);
736 } else if (dy == -1) {
737 dirList.push_front(DIRECTION_SOUTH);
738 }
739
740 found = found->parent;
741 }
742 return true;
743}
744
745// AStarNodes
746
747AStarNodes::AStarNodes(uint32_t x, uint32_t y)
748 : nodes(), openNodes()
749{
750 curNode = 1;
751 closedNodes = 0;
752 openNodes[0] = true;
753
754 AStarNode& startNode = nodes[0];
755 startNode.parent = nullptr;
756 startNode.x = x;
757 startNode.y = y;
758 startNode.f = 0;
759 nodeTable[(x << 16) | y] = nodes;
760}
761
762AStarNode* AStarNodes::createOpenNode(AStarNode* parent, uint32_t x, uint32_t y, int_fast32_t f)
763{
764 if (curNode >= MAX_NODES) {
765 return nullptr;
766 }
767
768 size_t retNode = curNode++;
769 openNodes[retNode] = true;
770
771 AStarNode* node = nodes + retNode;
772 nodeTable[(x << 16) | y] = node;
773 node->parent = parent;
774 node->x = x;
775 node->y = y;
776 node->f = f;
777 return node;
778}
779
780AStarNode* AStarNodes::getBestNode()
781{
782 if (curNode == 0) {
783 return nullptr;
784 }
785
786 int32_t best_node_f = std::numeric_limits<int32_t>::max();
787 int32_t best_node = -1;
788 for (size_t i = 0; i < curNode; i++) {
789 if (openNodes[i] && nodes[i].f < best_node_f) {
790 best_node_f = nodes[i].f;
791 best_node = i;
792 }
793 }
794
795 if (best_node >= 0) {
796 return nodes + best_node;
797 }
798 return nullptr;
799}
800
801void AStarNodes::closeNode(AStarNode* node)
802{
803 size_t index = node - nodes;
804 assert(index < MAX_NODES);
805 openNodes[index] = false;
806 ++closedNodes;
807}
808
809void AStarNodes::openNode(AStarNode* node)
810{
811 size_t index = node - nodes;
812 assert(index < MAX_NODES);
813 if (!openNodes[index]) {
814 openNodes[index] = true;
815 --closedNodes;
816 }
817}
818
819int_fast32_t AStarNodes::getClosedNodes() const
820{
821 return closedNodes;
822}
823
824AStarNode* AStarNodes::getNodeByPosition(uint32_t x, uint32_t y)
825{
826 auto it = nodeTable.find((x << 16) | y);
827 if (it == nodeTable.end()) {
828 return nullptr;
829 }
830 return it->second;
831}
832
833int_fast32_t AStarNodes::getMapWalkCost(AStarNode* node, const Position& neighborPos)
834{
835 if (std::abs(node->x - neighborPos.x) == std::abs(node->y - neighborPos.y)) {
836 //diagonal movement extra cost
837 return MAP_DIAGONALWALKCOST;
838 }
839 return MAP_NORMALWALKCOST;
840}
841
842int_fast32_t AStarNodes::getTileWalkCost(const Creature& creature, const Tile* tile)
843{
844 int_fast32_t cost = 0;
845 if (tile->getTopVisibleCreature(&creature) != nullptr) {
846 //destroy creature cost
847 cost += MAP_NORMALWALKCOST * 3;
848 }
849
850 if (const MagicField* field = tile->getFieldItem()) {
851 CombatType_t combatType = field->getCombatType();
852 const Monster* monster = creature.getMonster();
853 if (!creature.isImmune(combatType) && !creature.hasCondition(Combat::DamageToConditionType(combatType)) && (monster && !monster->canWalkOnFieldType(combatType))) {
854 cost += MAP_NORMALWALKCOST * 18;
855 }
856 }
857 return cost;
858}
859
860// Floor
861Floor::~Floor()
862{
863 for (auto& row : tiles) {
864 for (auto tile : row) {
865 delete tile;
866 }
867 }
868}
869
870// QTreeNode
871QTreeNode::~QTreeNode()
872{
873 for (auto* ptr : child) {
874 delete ptr;
875 }
876}
877
878QTreeLeafNode* QTreeNode::getLeaf(uint32_t x, uint32_t y)
879{
880 if (leaf) {
881 return static_cast<QTreeLeafNode*>(this);
882 }
883
884 QTreeNode* node = child[((x & 0x8000) >> 15) | ((y & 0x8000) >> 14)];
885 if (!node) {
886 return nullptr;
887 }
888 return node->getLeaf(x << 1, y << 1);
889}
890
891QTreeLeafNode* QTreeNode::createLeaf(uint32_t x, uint32_t y, uint32_t level)
892{
893 if (!isLeaf()) {
894 uint32_t index = ((x & 0x8000) >> 15) | ((y & 0x8000) >> 14);
895 if (!child[index]) {
896 if (level != FLOOR_BITS) {
897 child[index] = new QTreeNode();
898 } else {
899 child[index] = new QTreeLeafNode();
900 QTreeLeafNode::newLeaf = true;
901 }
902 }
903 return child[index]->createLeaf(x * 2, y * 2, level - 1);
904 }
905 return static_cast<QTreeLeafNode*>(this);
906}
907
908// QTreeLeafNode
909bool QTreeLeafNode::newLeaf = false;
910
911QTreeLeafNode::~QTreeLeafNode()
912{
913 for (auto* ptr : array) {
914 delete ptr;
915 }
916}
917
918Floor* QTreeLeafNode::createFloor(uint32_t z)
919{
920 if (!array[z]) {
921 array[z] = new Floor();
922 }
923 return array[z];
924}
925
926void QTreeLeafNode::addCreature(Creature* c)
927{
928 creature_list.push_back(c);
929
930 if (c->getPlayer()) {
931 player_list.push_back(c);
932 }
933}
934
935void QTreeLeafNode::removeCreature(Creature* c)
936{
937 auto iter = std::find(creature_list.begin(), creature_list.end(), c);
938 assert(iter != creature_list.end());
939 *iter = creature_list.back();
940 creature_list.pop_back();
941
942 if (c->getPlayer()) {
943 iter = std::find(player_list.begin(), player_list.end(), c);
944 assert(iter != player_list.end());
945 *iter = player_list.back();
946 player_list.pop_back();
947 }
948}
949
950uint32_t Map::clean() const
951{
952 uint64_t start = OTSYS_TIME();
953 size_t tiles = 0;
954
955 if (g_game.getGameState() == GAME_STATE_NORMAL) {
956 g_game.setGameState(GAME_STATE_MAINTAIN);
957 }
958
959 std::vector<Item*> toRemove;
960
961 for (auto tileList : g_game.getTilesToClean()) {
962 if (!tileList) {
963 continue;
964 }
965 ++tiles;
966 for (auto* item : *tileList->getItemList()) {
967 if (item->isCleanable()) {
968 toRemove.emplace_back(item);
969 }
970 }
971 }
972
973 for (auto item : toRemove) {
974 g_game.internalRemoveItem(item, -1);
975 }
976
977 size_t count = toRemove.size();
978 g_game.clearTilesToClean();
979
980 if (g_game.getGameState() == GAME_STATE_MAINTAIN) {
981 g_game.setGameState(GAME_STATE_NORMAL);
982 }
983
984 std::cout << "> CLEAN: Removed " << count << " item" << (count != 1 ? "s" : "")
985 << " from " << tiles << " tile" << (tiles != 1 ? "s" : "") << " in "
986 << (OTSYS_TIME() - start) / (1000.) << " seconds." << std::endl;
987 return count;
988}
989
Top