API tools faq
paste
Guest User

Untitled

a guest
May 20th, 2020
33
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 26.60 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. * Copyright (c) 2010-2014 OTClient <https://github.com/edubart/otclient>
  3. *
  4. * Permission is hereby granted, free of charge, to any person obtaining a copy
  5. * of this software and associated documentation files (the "Software"), to deal
  6. * in the Software without restriction, including without limitation the rights
  7. * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  8. * copies of the Software, and to permit persons to whom the Software is
  9. * furnished to do so, subject to the following conditions:
  10. *
  11. * The above copyright notice and this permission notice shall be included in
  12. * all copies or substantial portions of the Software.
  13. *
  14. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16. * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17. * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18. * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19. * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20. * THE SOFTWARE.
  21. */
  22.  
  23. #include "map.h"
  24. #include "game.h"
  25. #include "localplayer.h"
  26. #include "tile.h"
  27. #include "item.h"
  28. #include "missile.h"
  29. #include "statictext.h"
  30. #include "mapview.h"
  31. #include "minimap.h"
  32.  
  33. #include <framework/core/eventdispatcher.h>
  34. #include <framework/core/application.h>
  35.  
  36. Map g_map;
  37. TilePtr Map::m_nulltile;
  38.  
  39. void Map::init()
  40. {
  41. resetAwareRange();
  42. m_animationFlags |= Animation_Show;
  43. }
  44.  
  45. void Map::terminate()
  46. {
  47. clean();
  48. }
  49.  
  50. void Map::addMapView(const MapViewPtr& mapView)
  51. {
  52. m_mapViews.push_back(mapView);
  53. }
  54.  
  55. void Map::removeMapView(const MapViewPtr& mapView)
  56. {
  57. auto it = std::find(m_mapViews.begin(), m_mapViews.end(), mapView);
  58. if(it != m_mapViews.end())
  59. m_mapViews.erase(it);
  60. }
  61.  
  62. void Map::notificateTileUpdate(const Position& pos)
  63. {
  64. if(!pos.isMapPosition())
  65. return;
  66.  
  67. for(const MapViewPtr& mapView : m_mapViews)
  68. mapView->onTileUpdate(pos);
  69. g_minimap.updateTile(pos, getTile(pos));
  70. }
  71.  
  72. void Map::clean()
  73. {
  74. cleanDynamicThings();
  75.  
  76. for(int i=0;i<=Otc::MAX_Z;++i)
  77. m_tileBlocks[i].clear();
  78.  
  79. m_waypoints.clear();
  80.  
  81. g_towns.clear();
  82. g_houses.clear();
  83. g_creatures.clearSpawns();
  84. m_tilesRect = Rect(65534, 65534, 0, 0);
  85. }
  86.  
  87. void Map::cleanDynamicThings()
  88. {
  89. for(const auto& pair : m_knownCreatures) {
  90. const CreaturePtr& creature = pair.second;
  91. removeThing(creature);
  92. }
  93. m_knownCreatures.clear();
  94.  
  95. for(int i=0;i<=Otc::MAX_Z;++i)
  96. m_floorMissiles[i].clear();
  97.  
  98. cleanTexts();
  99. }
  100.  
  101. void Map::cleanTexts()
  102. {
  103. m_animatedTexts.clear();
  104. m_staticTexts.clear();
  105. }
  106.  
  107. void Map::addThing(const ThingPtr& thing, const Position& pos, int stackPos)
  108. {
  109. if(!thing)
  110. return;
  111.  
  112. if(thing->isItem() || thing->isCreature() || thing->isEffect()) {
  113. const TilePtr& tile = getOrCreateTile(pos);
  114. if(tile)
  115. tile->addThing(thing, stackPos);
  116. } else {
  117. if(thing->isMissile()) {
  118. m_floorMissiles[pos.z].push_back(thing->static_self_cast<Missile>());
  119. thing->onAppear();
  120. } else if(thing->isAnimatedText()) {
  121. // this code will stack animated texts of the same color
  122. AnimatedTextPtr animatedText = thing->static_self_cast<AnimatedText>();
  123. AnimatedTextPtr prevAnimatedText;
  124. bool merged = false;
  125. for(auto other : m_animatedTexts) {
  126. if(other->getPosition() == pos) {
  127. prevAnimatedText = other;
  128. if(other->merge(animatedText)) {
  129. merged = true;
  130. break;
  131. }
  132. }
  133. }
  134. if(!merged) {
  135. if(prevAnimatedText) {
  136. Point offset = prevAnimatedText->getOffset();
  137. float t = prevAnimatedText->getTimer().ticksElapsed();
  138. if(t < Otc::ANIMATED_TEXT_DURATION / 4.0) { // didnt move 12 pixels
  139. int y = 12 - 48 * t / (float)Otc::ANIMATED_TEXT_DURATION;
  140. offset += Point(0, y);
  141. }
  142. offset.y = std::min<int>(offset.y, 12);
  143. animatedText->setOffset(offset);
  144. }
  145. m_animatedTexts.push_back(animatedText);
  146. }
  147. } else if(thing->isStaticText()) {
  148. StaticTextPtr staticText = thing->static_self_cast<StaticText>();
  149. bool mustAdd = true;
  150. for(auto other : m_staticTexts) {
  151. // try to combine messages
  152. if(other->getPosition() == pos && other->addMessage(staticText->getName(), staticText->getMessageMode(), staticText->getFirstMessage())) {
  153. mustAdd = false;
  154. break;
  155. }
  156. }
  157.  
  158. if(mustAdd)
  159. m_staticTexts.push_back(staticText);
  160. else
  161. return;
  162. }
  163.  
  164. thing->setPosition(pos);
  165. thing->onAppear();
  166. }
  167.  
  168. notificateTileUpdate(pos);
  169. }
  170.  
  171. ThingPtr Map::getThing(const Position& pos, int stackPos)
  172. {
  173. if(TilePtr tile = getTile(pos))
  174. return tile->getThing(stackPos);
  175. return nullptr;
  176. }
  177.  
  178. bool Map::removeThing(const ThingPtr& thing)
  179. {
  180. if(!thing)
  181. return false;
  182.  
  183. bool ret = false;
  184. if(thing->isMissile()) {
  185. MissilePtr missile = thing->static_self_cast<Missile>();
  186. int z = missile->getPosition().z;
  187. auto it = std::find(m_floorMissiles[z].begin(), m_floorMissiles[z].end(), missile);
  188. if(it != m_floorMissiles[z].end()) {
  189. m_floorMissiles[z].erase(it);
  190. ret = true;
  191. }
  192. } else if(thing->isAnimatedText()) {
  193. AnimatedTextPtr animatedText = thing->static_self_cast<AnimatedText>();
  194. auto it = std::find(m_animatedTexts.begin(), m_animatedTexts.end(), animatedText);
  195. if(it != m_animatedTexts.end()) {
  196. m_animatedTexts.erase(it);
  197. ret = true;
  198. }
  199. } else if(thing->isStaticText()) {
  200. StaticTextPtr staticText = thing->static_self_cast<StaticText>();
  201. auto it = std::find(m_staticTexts.begin(), m_staticTexts.end(), staticText);
  202. if(it != m_staticTexts.end()) {
  203. m_staticTexts.erase(it);
  204. ret = true;
  205. }
  206. } else if(const TilePtr& tile = thing->getTile())
  207. ret = tile->removeThing(thing);
  208.  
  209. notificateTileUpdate(thing->getPosition());
  210. return ret;
  211. }
  212.  
  213. bool Map::removeThingByPos(const Position& pos, int stackPos)
  214. {
  215. if(TilePtr tile = getTile(pos))
  216. return removeThing(tile->getThing(stackPos));
  217. return false;
  218. }
  219.  
  220. void Map::colorizeThing(const ThingPtr& thing, const Color& color)
  221. {
  222. if(!thing)
  223. return;
  224.  
  225. if(thing->isItem())
  226. thing->static_self_cast<Item>()->setColor(color);
  227. else if(thing->isCreature()) {
  228. const TilePtr& tile = thing->getTile();
  229. assert(tile);
  230.  
  231. const ThingPtr& topThing = tile->getTopThing();
  232. assert(topThing);
  233.  
  234. topThing->static_self_cast<Item>()->setColor(color);
  235. }
  236. }
  237.  
  238. void Map::removeThingColor(const ThingPtr& thing)
  239. {
  240. if(!thing)
  241. return;
  242.  
  243. if(thing->isItem())
  244. thing->static_self_cast<Item>()->setColor(Color::alpha);
  245. else if(thing->isCreature()) {
  246. const TilePtr& tile = thing->getTile();
  247. assert(tile);
  248.  
  249. const ThingPtr& topThing = tile->getTopThing();
  250. assert(topThing);
  251.  
  252. topThing->static_self_cast<Item>()->setColor(Color::alpha);
  253. }
  254. }
  255.  
  256. StaticTextPtr Map::getStaticText(const Position& pos)
  257. {
  258. for(auto staticText : m_staticTexts) {
  259. // try to combine messages
  260. if(staticText->getPosition() == pos)
  261. return staticText;
  262. }
  263. return nullptr;
  264. }
  265.  
  266. const TilePtr& Map::createTile(const Position& pos)
  267. {
  268. if(!pos.isMapPosition())
  269. return m_nulltile;
  270. if(pos.x < m_tilesRect.left())
  271. m_tilesRect.setLeft(pos.x);
  272. if(pos.y < m_tilesRect.top())
  273. m_tilesRect.setTop(pos.y);
  274. if(pos.x > m_tilesRect.right())
  275. m_tilesRect.setRight(pos.x);
  276. if(pos.y > m_tilesRect.bottom())
  277. m_tilesRect.setBottom(pos.y);
  278. TileBlock& block = m_tileBlocks[pos.z][getBlockIndex(pos)];
  279. return block.create(pos);
  280. }
  281.  
  282. template <typename... Items>
  283. const TilePtr& Map::createTileEx(const Position& pos, const Items&... items)
  284. {
  285. if(!pos.isValid())
  286. return m_nulltile;
  287. const TilePtr& tile = getOrCreateTile(pos);
  288. auto vec = {items...};
  289. for(auto it : vec)
  290. addThing(it, pos);
  291.  
  292. return tile;
  293. }
  294.  
  295. const TilePtr& Map::getOrCreateTile(const Position& pos)
  296. {
  297. if(!pos.isMapPosition())
  298. return m_nulltile;
  299. if(pos.x < m_tilesRect.left())
  300. m_tilesRect.setLeft(pos.x);
  301. if(pos.y < m_tilesRect.top())
  302. m_tilesRect.setTop(pos.y);
  303. if(pos.x > m_tilesRect.right())
  304. m_tilesRect.setRight(pos.x);
  305. if(pos.y > m_tilesRect.bottom())
  306. m_tilesRect.setBottom(pos.y);
  307. TileBlock& block = m_tileBlocks[pos.z][getBlockIndex(pos)];
  308. return block.getOrCreate(pos);
  309. }
  310.  
  311. const TilePtr& Map::getTile(const Position& pos)
  312. {
  313. if(!pos.isMapPosition())
  314. return m_nulltile;
  315. auto it = m_tileBlocks[pos.z].find(getBlockIndex(pos));
  316. if(it != m_tileBlocks[pos.z].end())
  317. return it->second.get(pos);
  318. return m_nulltile;
  319. }
  320.  
  321. const TileList Map::getTiles(int floor/* = -1*/)
  322. {
  323. TileList tiles;
  324. if(floor > Otc::MAX_Z) {
  325. return tiles;
  326. }
  327. else if(floor < 0) {
  328. // Search all floors
  329. for(uint8_t z = 0; z <= Otc::MAX_Z; ++z) {
  330. for(const auto& pair : m_tileBlocks[z]) {
  331. const TileBlock& block = pair.second;
  332. for(const TilePtr& tile : block.getTiles()) {
  333. if(tile != nullptr)
  334. tiles.push_back(tile);
  335. }
  336. }
  337. }
  338. }
  339. else {
  340. for(const auto& pair : m_tileBlocks[floor]) {
  341. const TileBlock& block = pair.second;
  342. for(const TilePtr& tile : block.getTiles()) {
  343. if(tile != nullptr)
  344. tiles.push_back(tile);
  345. }
  346. }
  347. }
  348. return tiles;
  349. }
  350.  
  351. void Map::cleanTile(const Position& pos)
  352. {
  353. if(!pos.isMapPosition())
  354. return;
  355. auto it = m_tileBlocks[pos.z].find(getBlockIndex(pos));
  356. if(it != m_tileBlocks[pos.z].end()) {
  357. TileBlock& block = it->second;
  358. if(const TilePtr& tile = block.get(pos)) {
  359. tile->clean();
  360. if(tile->canErase())
  361. block.remove(pos);
  362.  
  363. notificateTileUpdate(pos);
  364. }
  365. }
  366. for(auto it = m_staticTexts.begin();it != m_staticTexts.end();) {
  367. const StaticTextPtr& staticText = *it;
  368. if(staticText->getPosition() == pos && staticText->getMessageMode() == Otc::MessageNone)
  369. it = m_staticTexts.erase(it);
  370. else
  371. ++it;
  372. }
  373. }
  374.  
  375. void Map::setShowZone(tileflags_t zone, bool show)
  376. {
  377. if(show)
  378. m_zoneFlags |= (uint32)zone;
  379. else
  380. m_zoneFlags &= ~(uint32)zone;
  381. }
  382.  
  383. void Map::setShowZones(bool show)
  384. {
  385. if(!show)
  386. m_zoneFlags = 0;
  387. else if(m_zoneFlags == 0)
  388. m_zoneFlags = TILESTATE_HOUSE | TILESTATE_PROTECTIONZONE;
  389. }
  390.  
  391. void Map::setZoneColor(tileflags_t zone, const Color& color)
  392. {
  393. if((m_zoneFlags & zone) == zone)
  394. m_zoneColors[zone] = color;
  395. }
  396.  
  397. void Map::setForceShowAnimations(bool force)
  398. {
  399. if(force) {
  400. if(!(m_animationFlags & Animation_Force))
  401. m_animationFlags |= Animation_Force;
  402. } else
  403. m_animationFlags &= ~Animation_Force;
  404. }
  405.  
  406. bool Map::isForcingAnimations()
  407. {
  408. return (m_animationFlags & Animation_Force) == Animation_Force;
  409. }
  410.  
  411. bool Map::isShowingAnimations()
  412. {
  413. return (m_animationFlags & Animation_Show) == Animation_Show;
  414. }
  415.  
  416. void Map::setShowAnimations(bool show)
  417. {
  418. if(show) {
  419. if(!(m_animationFlags & Animation_Show))
  420. m_animationFlags |= Animation_Show;
  421. } else
  422. m_animationFlags &= ~Animation_Show;
  423. }
  424.  
  425. void Map::beginGhostMode(float opacity)
  426. {
  427. g_painter->setOpacity(opacity);
  428. }
  429.  
  430. void Map::endGhostMode()
  431. {
  432. g_painter->resetOpacity();
  433. }
  434.  
  435. std::map<Position, ItemPtr> Map::findItemsById(uint16 clientId, uint32 max)
  436. {
  437. std::map<Position, ItemPtr> ret;
  438. uint32 count = 0;
  439. for(uint8_t z = 0; z <= Otc::MAX_Z; ++z) {
  440. for(const auto& pair : m_tileBlocks[z]) {
  441. const TileBlock& block = pair.second;
  442. for(const TilePtr& tile : block.getTiles()) {
  443. if(unlikely(!tile || tile->isEmpty()))
  444. continue;
  445. for(const ItemPtr& item : tile->getItems()) {
  446. if(item->getId() == clientId) {
  447. ret.insert(std::make_pair(tile->getPosition(), item));
  448. if(++count >= max)
  449. break;
  450. }
  451. }
  452. }
  453. }
  454. }
  455.  
  456. return ret;
  457. }
  458.  
  459. void Map::addCreature(const CreaturePtr& creature)
  460. {
  461. m_knownCreatures[creature->getId()] = creature;
  462. }
  463.  
  464. CreaturePtr Map::getCreatureById(uint32 id)
  465. {
  466. auto it = m_knownCreatures.find(id);
  467. if(it == m_knownCreatures.end())
  468. return nullptr;
  469. return it->second;
  470. }
  471.  
  472. void Map::removeCreatureById(uint32 id)
  473. {
  474. if(id == 0)
  475. return;
  476.  
  477. auto it = m_knownCreatures.find(id);
  478. if(it != m_knownCreatures.end())
  479. m_knownCreatures.erase(it);
  480. }
  481.  
  482. void Map::removeUnawareThings()
  483. {
  484. // remove creatures from tiles that we are not aware of anymore
  485. for(const auto& pair : m_knownCreatures) {
  486. const CreaturePtr& creature = pair.second;
  487. if(!isAwareOfPosition(creature->getPosition()))
  488. removeThing(creature);
  489. }
  490.  
  491. // remove static texts from tiles that we are not aware anymore
  492. for(auto it = m_staticTexts.begin(); it != m_staticTexts.end();) {
  493. const StaticTextPtr& staticText = *it;
  494. if(staticText->getMessageMode() == Otc::MessageNone && !isAwareOfPosition(staticText->getPosition()))
  495. it = m_staticTexts.erase(it);
  496. else
  497. ++it;
  498. }
  499. }
  500.  
  501. void Map::setCentralPosition(const Position& centralPosition)
  502. {
  503. if(m_centralPosition == centralPosition)
  504. return;
  505.  
  506. m_centralPosition = centralPosition;
  507.  
  508. removeUnawareThings();
  509.  
  510. // this fixes local player position when the local player is removed from the map,
  511. // the local player is removed from the map when there are too many creatures on his tile,
  512. // so there is no enough stackpos to the server send him
  513. g_dispatcher.addEvent([this] {
  514. LocalPlayerPtr localPlayer = g_game.getLocalPlayer();
  515. if(!localPlayer || localPlayer->getPosition() == m_centralPosition)
  516. return;
  517. TilePtr tile = localPlayer->getTile();
  518. if(tile && tile->hasThing(localPlayer))
  519. return;
  520.  
  521. Position oldPos = localPlayer->getPosition();
  522. Position pos = m_centralPosition;
  523. if(oldPos != pos) {
  524. if(!localPlayer->isRemoved())
  525. localPlayer->onDisappear();
  526. localPlayer->setPosition(pos);
  527. localPlayer->onAppear();
  528. g_logger.debug("forced player position update");
  529. }
  530. });
  531.  
  532. for(const MapViewPtr& mapView : m_mapViews)
  533. mapView->onMapCenterChange(centralPosition);
  534. }
  535.  
  536. std::vector<CreaturePtr> Map::getSightSpectators(const Position& centerPos, bool multiFloor)
  537. {
  538. return getSpectatorsInRangeEx(centerPos, multiFloor, m_awareRange.left - 1, m_awareRange.right - 2, m_awareRange.top - 1, m_awareRange.bottom - 2);
  539. }
  540.  
  541. std::vector<CreaturePtr> Map::getSpectators(const Position& centerPos, bool multiFloor)
  542. {
  543. return getSpectatorsInRangeEx(centerPos, multiFloor, m_awareRange.left, m_awareRange.right, m_awareRange.top, m_awareRange.bottom);
  544. }
  545.  
  546. std::vector<CreaturePtr> Map::getSpectatorsInRange(const Position& centerPos, bool multiFloor, int xRange, int yRange)
  547. {
  548. return getSpectatorsInRangeEx(centerPos, multiFloor, xRange, xRange, yRange, yRange);
  549. }
  550.  
  551. std::vector<CreaturePtr> Map::getSpectatorsInRangeEx(const Position& centerPos, bool multiFloor, int minXRange, int maxXRange, int minYRange, int maxYRange)
  552. {
  553. int minZRange = 0;
  554. int maxZRange = 0;
  555. std::vector<CreaturePtr> creatures;
  556.  
  557. if(multiFloor) {
  558. minZRange = 0;
  559. maxZRange = Otc::MAX_Z;
  560. }
  561.  
  562. //TODO: optimize
  563. //TODO: get creatures from other floors corretly
  564. //TODO: delivery creatures in distance order
  565.  
  566. for(int iz=-minZRange; iz<=maxZRange; ++iz) {
  567. for(int iy=-minYRange; iy<=maxYRange; ++iy) {
  568. for(int ix=-minXRange; ix<=maxXRange; ++ix) {
  569. TilePtr tile = getTile(centerPos.translated(ix,iy,iz));
  570. if(!tile)
  571. continue;
  572.  
  573. auto tileCreatures = tile->getCreatures();
  574. creatures.insert(creatures.end(), tileCreatures.rbegin(), tileCreatures.rend());
  575. }
  576. }
  577. }
  578.  
  579. return creatures;
  580. }
  581.  
  582. bool Map::isLookPossible(const Position& pos)
  583. {
  584. TilePtr tile = getTile(pos);
  585. return tile && tile->isLookPossible();
  586. }
  587.  
  588. bool Map::isCovered(const Position& pos, int firstFloor)
  589. {
  590. // check for tiles on top of the postion
  591. Position tilePos = pos;
  592. while(tilePos.coveredUp() && tilePos.z >= firstFloor) {
  593. TilePtr tile = getTile(tilePos);
  594. // the below tile is covered when the above tile has a full ground
  595. if(tile && tile->isFullGround())
  596. return true;
  597. }
  598. return false;
  599. }
  600.  
  601. bool Map::isCompletelyCovered(const Position& pos, int firstFloor)
  602. {
  603. const TilePtr& checkTile = getTile(pos);
  604. Position tilePos = pos;
  605. while(tilePos.coveredUp() && tilePos.z >= firstFloor) {
  606. bool covered = true;
  607. bool done = false;
  608. // check in 2x2 range tiles that has no transparent pixels
  609. for(int x=0;x<2 && !done;++x) {
  610. for(int y=0;y<2 && !done;++y) {
  611. const TilePtr& tile = getTile(tilePos.translated(-x, -y));
  612. if(!tile || !tile->isFullyOpaque()) {
  613. covered = false;
  614. done = true;
  615. } else if(x==0 && y==0 && (!checkTile || checkTile->isSingleDimension())) {
  616. done = true;
  617. }
  618. }
  619. }
  620. if(covered)
  621. return true;
  622. }
  623. return false;
  624. }
  625.  
  626. bool Map::isAwareOfPosition(const Position& pos)
  627. {
  628. if(pos.z < getFirstAwareFloor() || pos.z > getLastAwareFloor())
  629. return false;
  630.  
  631. Position groundedPos = pos;
  632. while(groundedPos.z != m_centralPosition.z) {
  633. if(groundedPos.z > m_centralPosition.z) {
  634. if(groundedPos.x == 65535 || groundedPos.y == 65535) // When pos == 65535,65535,15 we cant go up to 65536,65536,14
  635. break;
  636. groundedPos.coveredUp();
  637. }
  638. else {
  639. if(groundedPos.x == 0 || groundedPos.y == 0) // When pos == 0,0,0 we cant go down to -1,-1,1
  640. break;
  641. groundedPos.coveredDown();
  642. }
  643. }
  644. return m_centralPosition.isInRange(groundedPos, m_awareRange.left,
  645. m_awareRange.right,
  646. m_awareRange.top,
  647. m_awareRange.bottom);
  648. }
  649.  
  650. void Map::setAwareRange(const AwareRange& range)
  651. {
  652. m_awareRange = range;
  653. removeUnawareThings();
  654. }
  655.  
  656. void Map::resetAwareRange()
  657. {
  658. AwareRange range;
  659. range.left = 14; //Change this to = maxClientViewportX
  660. range.top = 8; //Change this to = maxClientViewportY
  661. range.bottom = range.top+1;
  662. range.right = range.left+1;
  663. setAwareRange(range);
  664. }
  665.  
  666. int Map::getFirstAwareFloor()
  667. {
  668. if(m_centralPosition.z > Otc::SEA_FLOOR)
  669. return m_centralPosition.z-Otc::AWARE_UNDEGROUND_FLOOR_RANGE;
  670. else
  671. return 0;
  672. }
  673.  
  674. int Map::getLastAwareFloor()
  675. {
  676. if(m_centralPosition.z > Otc::SEA_FLOOR)
  677. return std::min<int>(m_centralPosition.z+Otc::AWARE_UNDEGROUND_FLOOR_RANGE, (int)Otc::MAX_Z);
  678. else
  679. return Otc::SEA_FLOOR;
  680. }
  681.  
  682. std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult> Map::findPath(const Position& startPos, const Position& goalPos, int maxComplexity, int flags)
  683. {
  684. // pathfinding using A* search algorithm
  685. // as described in http://en.wikipedia.org/wiki/A*_search_algorithm
  686.  
  687. struct Node {
  688. Node(const Position& pos) : cost(0), totalCost(0), pos(pos), prev(nullptr), dir(Otc::InvalidDirection) { }
  689. float cost;
  690. float totalCost;
  691. Position pos;
  692. Node *prev;
  693. Otc::Direction dir;
  694. };
  695.  
  696. struct LessNode : std::binary_function<std::pair<Node*, float>, std::pair<Node*, float>, bool> {
  697. bool operator()(std::pair<Node*, float> a, std::pair<Node*, float> b) const {
  698. return b.second < a.second;
  699. }
  700. };
  701.  
  702. std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult> ret;
  703. std::vector<Otc::Direction>& dirs = std::get<0>(ret);
  704. Otc::PathFindResult& result = std::get<1>(ret);
  705.  
  706. result = Otc::PathFindResultNoWay;
  707.  
  708. if(startPos == goalPos) {
  709. result = Otc::PathFindResultSamePosition;
  710. return ret;
  711. }
  712.  
  713. if(startPos.z != goalPos.z) {
  714. result = Otc::PathFindResultImpossible;
  715. return ret;
  716. }
  717.  
  718. // check the goal pos is walkable
  719. if(g_map.isAwareOfPosition(goalPos)) {
  720. const TilePtr goalTile = getTile(goalPos);
  721. if(!goalTile || !goalTile->isWalkable()) {
  722. return ret;
  723. }
  724. }
  725. else {
  726. const MinimapTile& goalTile = g_minimap.getTile(goalPos);
  727. if(goalTile.hasFlag(MinimapTileNotWalkable)) {
  728. return ret;
  729. }
  730. }
  731.  
  732. std::unordered_map<Position, Node*, PositionHasher> nodes;
  733. std::priority_queue<std::pair<Node*, float>, std::vector<std::pair<Node*, float>>, LessNode> searchList;
  734.  
  735. Node *currentNode = new Node(startPos);
  736. currentNode->pos = startPos;
  737. nodes[startPos] = currentNode;
  738. Node *foundNode = nullptr;
  739. while(currentNode) {
  740. if((int)nodes.size() > maxComplexity) {
  741. result = Otc::PathFindResultTooFar;
  742. break;
  743. }
  744.  
  745. // path found
  746. if(currentNode->pos == goalPos && (!foundNode || currentNode->cost < foundNode->cost))
  747. foundNode = currentNode;
  748.  
  749. // cost too high
  750. if(foundNode && currentNode->totalCost >= foundNode->cost)
  751. break;
  752.  
  753. for(int i=-1;i<=1;++i) {
  754. for(int j=-1;j<=1;++j) {
  755. if(i == 0 && j == 0)
  756. continue;
  757.  
  758. bool wasSeen = false;
  759. bool hasCreature = false;
  760. bool isNotWalkable = true;
  761. bool isNotPathable = true;
  762. int speed = 100;
  763.  
  764. Position neighborPos = currentNode->pos.translated(i, j);
  765. if(g_map.isAwareOfPosition(neighborPos)) {
  766. wasSeen = true;
  767. if(const TilePtr& tile = getTile(neighborPos)) {
  768. hasCreature = tile->hasCreature();
  769. isNotWalkable = !tile->isWalkable();
  770. isNotPathable = !tile->isPathable();
  771. speed = tile->getGroundSpeed();
  772. }
  773. } else {
  774. const MinimapTile& mtile = g_minimap.getTile(neighborPos);
  775. wasSeen = mtile.hasFlag(MinimapTileWasSeen);
  776. isNotWalkable = mtile.hasFlag(MinimapTileNotWalkable);
  777. isNotPathable = mtile.hasFlag(MinimapTileNotPathable);
  778. if(isNotWalkable || isNotPathable)
  779. wasSeen = true;
  780. speed = mtile.getSpeed();
  781. }
  782.  
  783. float walkFactor = 0;
  784. if(neighborPos != goalPos) {
  785. if(!(flags & Otc::PathFindAllowNotSeenTiles) && !wasSeen)
  786. continue;
  787. if(wasSeen) {
  788. if(!(flags & Otc::PathFindAllowCreatures) && hasCreature)
  789. continue;
  790. if(!(flags & Otc::PathFindAllowNonPathable) && isNotPathable)
  791. continue;
  792. if(!(flags & Otc::PathFindAllowNonWalkable) && isNotWalkable)
  793. continue;
  794. }
  795. } else {
  796. if(!(flags & Otc::PathFindAllowNotSeenTiles) && !wasSeen)
  797. continue;
  798. if(wasSeen) {
  799. if(!(flags & Otc::PathFindAllowNonWalkable) && isNotWalkable)
  800. continue;
  801. }
  802. }
  803.  
  804. Otc::Direction walkDir = currentNode->pos.getDirectionFromPosition(neighborPos);
  805. if(walkDir >= Otc::NorthEast)
  806. walkFactor += 3.0f;
  807. else
  808. walkFactor += 1.0f;
  809.  
  810. float cost = currentNode->cost + (speed * walkFactor) / 100.0f;
  811.  
  812. Node *neighborNode;
  813. if(nodes.find(neighborPos) == nodes.end()) {
  814. neighborNode = new Node(neighborPos);
  815. nodes[neighborPos] = neighborNode;
  816. } else {
  817. neighborNode = nodes[neighborPos];
  818. if(neighborNode->cost <= cost)
  819. continue;
  820. }
  821.  
  822. neighborNode->prev = currentNode;
  823. neighborNode->cost = cost;
  824. neighborNode->totalCost = neighborNode->cost + neighborPos.distance(goalPos);
  825. neighborNode->dir = walkDir;
  826. searchList.push(std::make_pair(neighborNode, neighborNode->totalCost));
  827. }
  828. }
  829.  
  830. if(!searchList.empty()) {
  831. currentNode = searchList.top().first;
  832. searchList.pop();
  833. } else
  834. currentNode = nullptr;
  835. }
  836.  
  837. if(foundNode) {
  838. currentNode = foundNode;
  839. while(currentNode) {
  840. dirs.push_back(currentNode->dir);
  841. currentNode = currentNode->prev;
  842. }
  843. dirs.pop_back();
  844. std::reverse(dirs.begin(), dirs.end());
  845. result = Otc::PathFindResultOk;
  846. }
  847.  
  848. for(auto it : nodes)
  849. delete it.second;
  850.  
  851. return ret;
  852. }
Add Comment
Please, Sign In to add comment
Public Pastes
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!