API tools faq
paste
Advertisement
Guest User

Untitled

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