Open Tibia Server List

Grow your Open Tibia server.

Reach new players • Build your community • Climb the rankings

Add Server Explore Servers

map.cpp

main 1428 lines · 43.7 KB Raw

Alex Commit Client Upload Part 2 19/10/2026 00:06

1/*

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 */

23#include "map.h"

24#include "game.h"

25#include "item.h"

26#include "localplayer.h"

27#include "mapview.h"

28#include "minimap.h"

29#include "missile.h"

30#include "statictext.h"

31#include "tile.h"

33#include <framework/core/application.h>

34#include <framework/core/asyncdispatcher.h>

35#include <framework/core/eventdispatcher.h>

36#include <framework/util/extras.h>

37#include <set>

39Map g_map;

40TilePtr Map::m_nulltile = nullptr;

42void Map::init() {

43 resetAwareRange();

44 m_animationFlags |= Animation_Show;

45}

47void Map::terminate() { clean(); }

49void Map::addMapView(const MapViewPtr &mapView) {

50 m_mapViews.push_back(mapView);

51}

53void Map::removeMapView(const MapViewPtr &mapView) {

54 auto it = std::find(m_mapViews.begin(), m_mapViews.end(), mapView);

55 if (it != m_mapViews.end())

56 m_mapViews.erase(it);

57}

59void Map::notificateTileUpdate(const Position &pos, bool updateMinimap) {

60 if (!pos.isMapPosition())

61 return;

63 for (const MapViewPtr &mapView : m_mapViews)

64 mapView->onTileUpdate(pos);

66 if (!updateMinimap)

67 return;

69 if (!g_game.getFeature(Otc::GameMinimapLimitedToSingleFloor) ||

70 (m_centralPosition.z == pos.z)) {

71 g_minimap.updateTile(pos, getTile(pos));

72 }

73}

75void Map::requestVisibleTilesCacheUpdate() {

76 for (const MapViewPtr &mapView : m_mapViews)

77 mapView->requestVisibleTilesCacheUpdate();

78}

80void Map::clean() {

81 cleanDynamicThings();

83 for (int i = 0; i <= Otc::MAX_Z; ++i)

84 m_tileBlocks[i].clear();

86 m_waypoints.clear();

88 g_towns.clear();

89 g_houses.clear();

90 g_creatures.clearSpawns();

91 m_tilesRect = Rect(65534, 65534, 0, 0);

92}

94void Map::cleanDynamicThings() {

95 for (const auto &pair : m_knownCreatures) {

96 const CreaturePtr &creature = pair.second;

97 removeThing(creature);

98 }

99 m_knownCreatures.clear();

100

101 for (int i = 0; i <= Otc::MAX_Z; ++i)

102 m_floorMissiles[i].clear();

103

104 cleanTexts();

105}

106

107void Map::cleanTexts() {

108 m_animatedTexts.clear();

109 m_staticTexts.clear();

110}

111

112void Map::addThing(const ThingPtr &thing, const Position &pos, int stackPos) {

113 if (!thing)

114 return;

115

116 if (thing->isItem() || thing->isCreature() || thing->isEffect()) {

117 const TilePtr &tile = getOrCreateTile(pos);

118 if (tile)

119 tile->addThing(thing, stackPos);

120 } else {

121 if (thing->isMissile()) {

122 m_floorMissiles[pos.z].push_back(thing->static_self_cast<Missile>());

123 } else if (thing->isAnimatedText()) {

124 // this code will stack animated texts of the same color

125 AnimatedTextPtr animatedText = thing->static_self_cast<AnimatedText>();

126

127 AnimatedTextPtr prevAnimatedText;

128 bool merged = false;

129 for (auto other : m_animatedTexts) {

130 if (other->getPosition() == pos) {

131 prevAnimatedText = other;

132 if (!g_game.getFeature(Otc::GameDontMergeAnimatedText)) {

133 if (other->merge(animatedText)) {

134 merged = true;

135 break;

136 }

137 }

138 }

139 }

140

141 if (!merged) {

142 if (prevAnimatedText) {

143 Point offset = prevAnimatedText->getOffset();

144 float t = prevAnimatedText->getTimer().ticksElapsed();

145 int y = 48 * t / (float)Otc::ANIMATED_TEXT_DURATION;

146 offset -= Point(0, y);

147 offset.y = std::min<int>(std::max<int>(0, offset.y + 12), 24);

148 animatedText->setOffset(offset);

149 }

150 m_animatedTexts.push_back(animatedText);

151 }

152 } else if (thing->isStaticText()) {

153 StaticTextPtr staticText = thing->static_self_cast<StaticText>();

154

155 bool mustAdd = true;

156 for (auto other : m_staticTexts) {

157 // try to combine messages

158 if (other->getPosition() == pos &&

159 other->addColoredMessage(staticText->getName(),

160 staticText->getMessageMode(),

161 staticText->getFirstMessage())) {

162 mustAdd = false;

163 break;

164 }

165 }

166

167 if (mustAdd)

168 m_staticTexts.push_back(staticText);

169 else

170 return;

171 }

172

173 thing->setPosition(pos);

174 thing->onAppear();

175

176 if (thing->isMissile()) {

177 g_lua.callGlobalField("g_map", "onMissle", thing);

178 } else if (thing->isAnimatedText()) {

179 AnimatedTextPtr animatedText = thing->static_self_cast<AnimatedText>();

180 g_lua.callGlobalField("g_map", "onAnimatedText", thing,

181 animatedText->getText());

182 } else if (thing->isStaticText()) {

183 StaticTextPtr staticText = thing->static_self_cast<StaticText>();

184 g_lua.callGlobalField("g_map", "onStaticText", thing,

185 staticText->getText());

186 }

187 }

188

189 notificateTileUpdate(pos, thing->isItem());

190}

191

192void Map::setTileSpeed(const Position &pos, uint16_t speed, uint8_t blocking) {

193 const TilePtr &tile = getOrCreateTile(pos);

194 if (tile)

195 tile->setSpeed(speed, blocking);

196}

197

198ThingPtr Map::getThing(const Position &pos, int stackPos) {

199 if (TilePtr tile = getTile(pos))

200 return tile->getThing(stackPos);

201 return nullptr;

202}

203

204bool Map::removeThing(const ThingPtr &thing) {

205 if (!thing)

206 return false;

207

208 bool ret = false;

209 if (thing->isMissile()) {

210 MissilePtr missile = thing->static_self_cast<Missile>();

211 int z = missile->getPosition().z;

212 auto it = std::find(m_floorMissiles[z].begin(), m_floorMissiles[z].end(),

213 missile);

214 if (it != m_floorMissiles[z].end()) {

215 m_floorMissiles[z].erase(it);

216 ret = true;

217 }

218 } else if (thing->isAnimatedText()) {

219 AnimatedTextPtr animatedText = thing->static_self_cast<AnimatedText>();

220 auto it =

221 std::find(m_animatedTexts.begin(), m_animatedTexts.end(), animatedText);

222 if (it != m_animatedTexts.end()) {

223 m_animatedTexts.erase(it);

224 ret = true;

225 }

226 } else if (thing->isStaticText()) {

227 StaticTextPtr staticText = thing->static_self_cast<StaticText>();

228 auto it = std::find(m_staticTexts.begin(), m_staticTexts.end(), staticText);

229 if (it != m_staticTexts.end()) {

230 m_staticTexts.erase(it);

231 ret = true;

232 }

233 } else if (const TilePtr &tile = thing->getTile())

234 ret = tile->removeThing(thing);

235

236 notificateTileUpdate(thing->getPosition(), thing->isItem());

237 return ret;

238}

239

240bool Map::removeThingByPos(const Position &pos, int stackPos) {

241 if (TilePtr tile = getTile(pos))

242 return removeThing(tile->getThing(stackPos));

243 return false;

244}

245

246void Map::colorizeThing(const ThingPtr &thing, const Color &color) {

247 if (!thing)

248 return;

249

250 if (thing->isItem())

251 thing->static_self_cast<Item>()->setColor(color);

252 else if (thing->isCreature()) {

253 const TilePtr &tile = thing->getTile();

254 VALIDATE(tile);

255

256 const ThingPtr &topThing = tile->getTopThing();

257 VALIDATE(topThing);

258

259 topThing->static_self_cast<Item>()->setColor(color);

260 }

261}

262

263void Map::removeThingColor(const ThingPtr &thing) {

264 if (!thing)

265 return;

266

267 if (thing->isItem())

268 thing->static_self_cast<Item>()->setColor(Color::alpha);

269 else if (thing->isCreature()) {

270 const TilePtr &tile = thing->getTile();

271 VALIDATE(tile);

272

273 const ThingPtr &topThing = tile->getTopThing();

274 VALIDATE(topThing);

275

276 topThing->static_self_cast<Item>()->setColor(Color::alpha);

277 }

278}

279

280StaticTextPtr Map::getStaticText(const Position &pos) {

281 for (auto staticText : m_staticTexts) {

282 // try to combine messages

283 if (staticText->getPosition() == pos)

284 return staticText;

285 }

286 return nullptr;

287}

288

289const TilePtr &Map::createTile(const Position &pos) {

290 if (!pos.isMapPosition())

291 return m_nulltile;

292 if (pos.x < m_tilesRect.left())

293 m_tilesRect.setLeft(pos.x);

294 if (pos.y < m_tilesRect.top())

295 m_tilesRect.setTop(pos.y);

296 if (pos.x > m_tilesRect.right())

297 m_tilesRect.setRight(pos.x);

298 if (pos.y > m_tilesRect.bottom())

299 m_tilesRect.setBottom(pos.y);

300 TileBlock &block = m_tileBlocks[pos.z][getBlockIndex(pos)];

301 return block.create(pos);

302}

303

304template <typename... Items>

305const TilePtr &Map::createTileEx(const Position &pos, const Items &...items) {

306 if (!pos.isValid())

307 return m_nulltile;

308 const TilePtr &tile = getOrCreateTile(pos);

309 auto vec = {items...};

310 for (auto it : vec)

311 addThing(it, pos);

312

313 return tile;

314}

315

316const TilePtr &Map::getOrCreateTile(const Position &pos) {

317 if (!pos.isMapPosition())

318 return m_nulltile;

319 if (pos.x < m_tilesRect.left())

320 m_tilesRect.setLeft(pos.x);

321 if (pos.y < m_tilesRect.top())

322 m_tilesRect.setTop(pos.y);

323 if (pos.x > m_tilesRect.right())

324 m_tilesRect.setRight(pos.x);

325 if (pos.y > m_tilesRect.bottom())

326 m_tilesRect.setBottom(pos.y);

327 TileBlock &block = m_tileBlocks[pos.z][getBlockIndex(pos)];

328 return block.getOrCreate(pos);

329}

330

331const TilePtr &Map::getTile(const Position &pos) {

332 if (!pos.isMapPosition())

333 return m_nulltile;

334 auto it = m_tileBlocks[pos.z].find(getBlockIndex(pos));

335 if (it != m_tileBlocks[pos.z].end())

336 return it->second.get(pos);

337 return m_nulltile;

338}

339

340const TileList Map::getTiles(int floor /* = -1*/) {

341 TileList tiles;

342 if (floor > Otc::MAX_Z) {

343 return tiles;

344 } else if (floor < 0) {

345 // Search all floors

346 for (uint8_t z = 0; z <= Otc::MAX_Z; ++z) {

347 for (const auto &pair : m_tileBlocks[z]) {

348 const TileBlock &block = pair.second;

349 for (const TilePtr &tile : block.getTiles()) {

350 if (tile != nullptr)

351 tiles.push_back(tile);

352 }

353 }

354 }

355 } else {

356 for (const auto &pair : m_tileBlocks[floor]) {

357 const TileBlock &block = pair.second;

358 for (const TilePtr &tile : block.getTiles()) {

359 if (tile != nullptr)

360 tiles.push_back(tile);

361 }

362 }

363 }

364 return tiles;

365}

366

367void Map::cleanTile(const Position &pos) {

368 if (!pos.isMapPosition())

369 return;

370 auto it = m_tileBlocks[pos.z].find(getBlockIndex(pos));

371 if (it != m_tileBlocks[pos.z].end()) {

372 TileBlock &block = it->second;

373 if (const TilePtr &tile = block.get(pos)) {

374 tile->clean();

375 if (tile->canErase())

376 block.remove(pos);

377

378 notificateTileUpdate(pos, false);

379 }

380 }

381 for (auto it = m_staticTexts.begin(); it != m_staticTexts.end();) {

382 const StaticTextPtr &staticText = *it;

383 if (staticText->getPosition() == pos &&

384 staticText->getMessageMode() == Otc::MessageNone)

385 it = m_staticTexts.erase(it);

386 else

387 ++it;

388 }

389

390 if (!g_game.getFeature(Otc::GameMinimapLimitedToSingleFloor) ||

391 (m_centralPosition.z == pos.z)) {

392 g_minimap.updateTile(pos, getTile(pos));

393 }

394}

395

396void Map::setShowZone(tileflags_t zone, bool show) {

397 if (show)

398 m_zoneFlags |= (uint32)zone;

399 else

400 m_zoneFlags &= ~(uint32)zone;

401}

402

403void Map::setShowZones(bool show) {

404 if (!show)

405 m_zoneFlags = 0;

406 else if (m_zoneFlags == 0)

407 m_zoneFlags = TILESTATE_HOUSE | TILESTATE_PROTECTIONZONE;

408}

409

410void Map::setZoneColor(tileflags_t zone, const Color &color) {

411 if ((m_zoneFlags & zone) == zone)

412 m_zoneColors[zone] = color;

413}

414

415Color Map::getZoneColor(tileflags_t flag) {

416 auto it = m_zoneColors.find(flag);

417 if (it == m_zoneColors.end())

418 return Color::alpha;

419 return it->second;

420}

421

422void Map::setForceShowAnimations(bool force) {

423 if (force) {

424 if (!(m_animationFlags & Animation_Force))

425 m_animationFlags |= Animation_Force;

426 } else

427 m_animationFlags &= ~Animation_Force;

428}

429

430bool Map::isForcingAnimations() {

431 return (m_animationFlags & Animation_Force) == Animation_Force;

432}

433

434bool Map::isShowingAnimations() {

435 return (m_animationFlags & Animation_Show) == Animation_Show;

436}

437

438void Map::setShowAnimations(bool show) {

439 if (show) {

440 if (!(m_animationFlags & Animation_Show))

441 m_animationFlags |= Animation_Show;

442 } else

443 m_animationFlags &= ~Animation_Show;

444}

445

446std::map<Position, ItemPtr> Map::findItemsById(uint16 clientId, uint32 max) {

447 std::map<Position, ItemPtr> ret;

448 uint32 count = 0;

449 for (uint8_t z = 0; z <= Otc::MAX_Z; ++z) {

450 for (const auto &pair : m_tileBlocks[z]) {

451 const TileBlock &block = pair.second;

452 for (const TilePtr &tile : block.getTiles()) {

453 if (unlikely(!tile || tile->isEmpty()))

454 continue;

455 for (const ItemPtr &item : tile->getItems()) {

456 if (item->getId() == clientId) {

457 ret.insert(std::make_pair(tile->getPosition(), item));

458 if (++count >= max)

459 break;

460 }

461 }

462 }

463 }

464 }

465

466 return ret;

467}

468

469void Map::addCreature(const CreaturePtr &creature) {

470 m_knownCreatures[creature->getId()] = creature;

471}

472

473CreaturePtr Map::getCreatureById(uint32 id) {

474 auto it = m_knownCreatures.find(id);

475 if (it == m_knownCreatures.end())

476 return nullptr;

477 return it->second;

478}

479

480void Map::removeCreatureById(uint32 id) {

481 if (id == 0)

482 return;

483

484 auto it = m_knownCreatures.find(id);

485 if (it != m_knownCreatures.end())

486 m_knownCreatures.erase(it);

487}

488

489void Map::removeUnawareThings() {

490 // remove creatures from tiles that we are not aware of anymore

491 for (const auto &pair : m_knownCreatures) {

492 const CreaturePtr &creature = pair.second;

493 if (!isAwareOfPosition(creature->getPosition()))

494 removeThing(creature);

495 }

496

497 // remove static texts from tiles that we are not aware anymore

498 for (auto it = m_staticTexts.begin(); it != m_staticTexts.end();) {

499 const StaticTextPtr &staticText = *it;

500 if (staticText->getMessageMode() == Otc::MessageNone &&

501 !isAwareOfPosition(staticText->getPosition()))

502 it = m_staticTexts.erase(it);

503 else

504 ++it;

505 }

506

507 bool extended = g_game.getFeature(Otc::GameBiggerMapCache);

508 if (!g_game.getFeature(Otc::GameKeepUnawareTiles)) {

509 // remove tiles that we are not aware anymore

510 for (int z = 0; z <= Otc::MAX_Z; ++z) {

511 auto &tileBlocks = m_tileBlocks[z];

512 for (auto it = tileBlocks.begin(); it != tileBlocks.end();) {

513 TileBlock &block = (*it).second;

514 bool blockEmpty = true;

515 for (const TilePtr &tile : block.getTiles()) {

516 if (!tile)

517 continue;

518

519 const Position &pos = tile->getPosition();

520

521 if (!isAwareOfPositionForClean(pos, extended))

522 block.remove(pos);

523 else

524 blockEmpty = false;

525 }

526

527 if (blockEmpty)

528 it = tileBlocks.erase(it);

529 else

530 ++it;

531 }

532 }

533 }

534}

535

536void Map::setCentralPosition(const Position &centralPosition) {

537 if (m_centralPosition == centralPosition)

538 return;

539

540 m_centralPosition = centralPosition;

541

542 removeUnawareThings();

543

544 // this fixes local player position when the local player is removed from the

545 // map, the local player is removed from the map when there are too many

546 // creatures on his tile, so there is no enough stackpos to the server send

547 // him

548 g_dispatcher.addEvent([this] {

549 LocalPlayerPtr localPlayer = g_game.getLocalPlayer();

550 if (!localPlayer || localPlayer->getPosition() == m_centralPosition)

551 return;

552 TilePtr tile = localPlayer->getTile();

553 if (tile && tile->hasThing(localPlayer))

554 return;

555

556 Position oldPos = localPlayer->getPosition();

557 Position pos = m_centralPosition;

558 if (oldPos != pos) {

559 if (!localPlayer->isRemoved())

560 localPlayer->onDisappear();

561 localPlayer->setPosition(pos);

562 localPlayer->onAppear();

563 g_logger.debug("forced player position update");

564 }

565 });

566

567 for (const MapViewPtr &mapView : m_mapViews)

568 mapView->onMapCenterChange(centralPosition);

569}

570

571std::vector<CreaturePtr> Map::getSightSpectators(const Position &centerPos,

572 bool multiFloor) {

573 return getSpectatorsInRangeEx(centerPos, multiFloor, m_awareRange.left - 1,

574 m_awareRange.right - 2, m_awareRange.top - 1,

575 m_awareRange.bottom - 2);

576}

577

578std::vector<CreaturePtr> Map::getSpectators(const Position &centerPos,

579 bool multiFloor) {

580 return getSpectatorsInRangeEx(centerPos, multiFloor, m_awareRange.left,

581 m_awareRange.right, m_awareRange.top,

582 m_awareRange.bottom);

583}

584

585std::vector<CreaturePtr> Map::getSpectatorsInRange(const Position &centerPos,

586 bool multiFloor, int xRange,

587 int yRange) {

588 return getSpectatorsInRangeEx(centerPos, multiFloor, xRange, xRange, yRange,

589 yRange);

590}

591

592std::vector<CreaturePtr>

593Map::getSpectatorsInRangeEx(const Position &centerPos, bool multiFloor,

594 int minXRange, int maxXRange, int minYRange,

595 int maxYRange) {

596 int minZRange = 0;

597 int maxZRange = 0;

598 std::vector<CreaturePtr> creatures;

599

600 if (multiFloor) {

601 minZRange = centerPos.z - getFirstAwareFloor();

602 maxZRange = getLastAwareFloor() - centerPos.z;

603 }

604

605 // TODO: optimize

606 // TODO: delivery creatures in distance order

607

608 for (int iz = -minZRange; iz <= maxZRange; ++iz) {

609 for (int iy = -minYRange; iy <= maxYRange; ++iy) {

610 for (int ix = -minXRange; ix <= maxXRange; ++ix) {

611 TilePtr tile = getTile(centerPos.translated(ix, iy, iz));

612 if (!tile)

613 continue;

614

615 auto tileCreatures = tile->getCreatures();

616 creatures.insert(creatures.end(), tileCreatures.rbegin(),

617 tileCreatures.rend());

618 }

619 }

620 }

621

622 return creatures;

623}

624

625std::vector<CreaturePtr> Map::getSpectatorsByPattern(const Position &centerPos,

626 const std::string &pattern,

627 Otc::Direction direction) {

628 std::vector<bool> finalPattern(pattern.size(), false);

629 std::vector<CreaturePtr> creatures;

630 int width = 0, height = 0, lineLength = 0, p = 0;

631 for (auto &c : pattern) {

632 lineLength += 1;

633 if (c == '0' || c == '-') {

634 p += 1;

635 } else if (c == '1' || c == '+') {

636 finalPattern[p++] = true;

637 } else if (c == 'N' || c == 'n') {

638 finalPattern[p++] = direction == Otc::North;

639 } else if (c == 'E' || c == 'e') {

640 finalPattern[p++] = direction == Otc::East;

641 } else if (c == 'W' || c == 'w') {

642 finalPattern[p++] = direction == Otc::West;

643 } else if (c == 'S' || c == 's') {

644 finalPattern[p++] = direction == Otc::South;

645 } else {

646 lineLength -= 1;

647 if (lineLength > 1) {

648 if (width == 0)

649 width = lineLength;

650 if (width != lineLength) {

651 g_logger.error(stdext::format(

652 "Invalid pattern for getSpectatorsByPattern: %s", pattern));

653 return creatures;

654 }

655 height += 1;

656 lineLength = 0;

657 }

658 }

659 }

660 if (lineLength > 0) {

661 if (width == 0)

662 width = lineLength;

663 if (width != lineLength) {

664 g_logger.error(stdext::format(

665 "Invalid pattern for getSpectatorsByPattern: %s", pattern));

666 return creatures;

667 }

668 height += 1;

669 }

670 if (width % 2 != 1 || height % 2 != 1) {

671 g_logger.error(

672 stdext::format("Invalid pattern for getSpectatorsByPattern, width and "

673 "height should be odd (height: %i width: %i)",

674 height, width));

675 return creatures;

676 }

677

678 p = 0;

679 for (int y = centerPos.y - height / 2, endy = centerPos.y + height / 2;

680 y <= endy; ++y) {

681 for (int x = centerPos.x - width / 2, endx = centerPos.x + width / 2;

682 x <= endx; ++x) {

683 if (!finalPattern[p++])

684 continue;

685 TilePtr tile = getTile(Position(x, y, centerPos.z));

686 if (!tile)

687 continue;

688 auto tileCreatures = tile->getCreatures();

689 creatures.insert(creatures.end(), tileCreatures.rbegin(),

690 tileCreatures.rend());

691 }

692 }

693 return creatures;

694}

695

696bool Map::isLookPossible(const Position &pos) {

697 TilePtr tile = getTile(pos);

698 return tile && tile->isLookPossible();

699}

700

701bool Map::isCovered(const Position &pos, int firstFloor) {

702 // check for tiles on top of the postion

703 Position tilePos = pos;

704 while (tilePos.coveredUp() && tilePos.z >= firstFloor) {

705 TilePtr tile = getTile(tilePos);

706 // the below tile is covered when the above tile has a full ground

707 if (tile && tile->isFullGround())

708 return true;

709 }

710 return false;

711}

712

713bool Map::isCompletelyCovered(const Position &pos, int firstFloor) {

714 const TilePtr &checkTile = getTile(pos);

715 Position tilePos = pos;

716 while (tilePos.coveredUp() && tilePos.z >= firstFloor) {

717 bool covered = true;

718 bool done = false;

719 // check in 2x2 range tiles that has no transparent pixels

720 for (int x = 0; x < 2 && !done; ++x) {

721 for (int y = 0; y < 2 && !done; ++y) {

722 const TilePtr &tile = getTile(tilePos.translated(-x, -y));

723 if (!tile || !tile->isFullyOpaque()) {

724 covered = false;

725 done = true;

726 } else if (x == 0 && y == 0 &&

727 (!checkTile || checkTile->isSingleDimension())) {

728 done = true;

729 }

730 }

731 }

732 if (covered)

733 return true;

734 }

735 return false;

736}

737

738bool Map::isAwareOfPosition(const Position &pos, bool extended) {

739 if ((pos.z < getFirstAwareFloor() || pos.z > getLastAwareFloor()) &&

740 !extended)

741 return false;

742

743 Position groundedPos = pos;

744 while (groundedPos.z != m_centralPosition.z) {

745 if (groundedPos.z > m_centralPosition.z) {

746 if (groundedPos.x == 65535 ||

747 groundedPos.y == 65535) // When pos == 65535,65535,15 we cant go up to

748 // 65536,65536,14

749 break;

750 groundedPos.coveredUp();

751 } else {

752 if (groundedPos.x == 0 ||

753 groundedPos.y == 0) // When pos == 0,0,0 we cant go down to -1,-1,1

754 break;

755 groundedPos.coveredDown();

756 }

757 }

758

759 if (extended) {

760 return m_centralPosition.isInRange(

761 groundedPos, m_awareRange.left * 2, m_awareRange.right * 2,

762 m_awareRange.top * 2, m_awareRange.bottom * 2);

763 }

764 return m_centralPosition.isInRange(groundedPos, m_awareRange.left,

765 m_awareRange.right, m_awareRange.top,

766 m_awareRange.bottom);

767}

768

769bool Map::isAwareOfPositionForClean(const Position &pos, bool extended) {

770 if ((pos.z < getFirstAwareFloor() || pos.z > getLastAwareFloor()) &&

771 !extended)

772 return false;

773

774 Position groundedPos = pos;

775 while (groundedPos.z != m_centralPosition.z) {

776 if (groundedPos.z > m_centralPosition.z) {

777 if (groundedPos.x == 65535 ||

778 groundedPos.y == 65535) // When pos == 65535,65535,15 we cant go up to

779 // 65536,65536,14

780 break;

781 groundedPos.coveredUp();

782 } else {

783 if (groundedPos.x == 0 ||

784 groundedPos.y == 0) // When pos == 0,0,0 we cant go down to -1,-1,1

785 break;

786 groundedPos.coveredDown();

787 }

788 }

789

790 if (extended) {

791 return m_centralPosition.isInRange(

792 groundedPos, m_awareRange.left * 4, m_awareRange.right * 4,

793 m_awareRange.top * 4, m_awareRange.bottom * 4);

794 }

795 return m_centralPosition.isInRange(

796 groundedPos, m_awareRange.left + 1, m_awareRange.right + 1,

797 m_awareRange.top + 1, m_awareRange.bottom + 1);

798}

799

800void Map::setAwareRange(const AwareRange &range) {

801 m_awareRange = range;

802 removeUnawareThings();

803}

804

805void Map::resetAwareRange() {

806 AwareRange range;

807 range.left = 8;

808 range.top = 6;

809 range.bottom = 7;

810 range.right = 9;

811 setAwareRange(range);

812}

813

814int Map::getFirstAwareFloor() {

815 if (m_centralPosition.z > Otc::SEA_FLOOR)

816 return m_centralPosition.z - Otc::AWARE_UNDEGROUND_FLOOR_RANGE;

817 else

818 return 0;

819}

820

821int Map::getLastAwareFloor() {

822 if (m_centralPosition.z > Otc::SEA_FLOOR)

823 return std::min<int>(m_centralPosition.z +

824 Otc::AWARE_UNDEGROUND_FLOOR_RANGE,

825 (int)Otc::MAX_Z);

826 else

827 // FIX (OTLand/OTCv8): Server sends floors 15->0 for ALL surface players.

828 // Must keep all floors in the aware range so removeUnawareThings()

829 // does NOT delete them on every walk step.

830 return (int)Otc::MAX_Z; // Keep all floors when at surface

831}

832

833std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult>

834Map::findPath(const Position &startPos, const Position &goalPos,

835 int maxComplexity, int flags) {

836 // pathfinding using A* search algorithm (otclientv8 note: it's dijkstra

837 // algorithm) as described in http://en.wikipedia.org/wiki/A*_search_algorithm

838

839 struct SNode {

840 SNode(const Position &pos)

841 : cost(0), totalCost(0), pos(pos), prev(nullptr),

842 dir(Otc::InvalidDirection) {}

843 float cost;

844 float totalCost;

845 Position pos;

846 SNode *prev;

847 Otc::Direction dir;

848 };

849

850 struct LessNode {

851 bool operator()(std::pair<SNode *, float> a,

852 std::pair<SNode *, float> b) const {

853 return b.second < a.second;

854 }

855 };

856

857 std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult> ret;

858 std::vector<Otc::Direction> &dirs = std::get<0>(ret);

859 Otc::PathFindResult &result = std::get<1>(ret);

860

861 result = Otc::PathFindResultNoWay;

862

863 if (startPos == goalPos) {

864 result = Otc::PathFindResultSamePosition;

865 return ret;

866 }

867

868 if (startPos.z != goalPos.z) {

869 result = Otc::PathFindResultImpossible;

870 return ret;

871 }

872

873 // check the goal pos is walkable

874 if (g_map.isAwareOfPosition(goalPos)) {

875 const TilePtr goalTile = getTile(goalPos);

876 if (!goalTile ||

877 (!goalTile->isWalkable(flags & Otc::PathFindIgnoreCreatures))) {

878 return ret;

879 }

880 } else {

881 const MinimapTile &goalTile = g_minimap.getTile(goalPos);

882 if (goalTile.hasFlag(MinimapTileNotWalkable)) {

883 return ret;

884 }

885 }

886

887 std::unordered_map<Position, SNode *, PositionHasher> nodes;

888 std::priority_queue<std::pair<SNode *, float>,

889 std::vector<std::pair<SNode *, float>>, LessNode>

890 searchList;

891

892 SNode *currentNode = new SNode(startPos);

893 currentNode->pos = startPos;

894 nodes[startPos] = currentNode;

895 SNode *foundNode = nullptr;

896 while (currentNode) {

897 if ((int)nodes.size() > maxComplexity) {

898 result = Otc::PathFindResultTooFar;

899 break;

900 }

901

902 // path found

903 if (currentNode->pos == goalPos &&

904 (!foundNode || currentNode->cost < foundNode->cost))

905 foundNode = currentNode;

906

907 // cost too high

908 if (foundNode && currentNode->totalCost >= foundNode->cost)

909 break;

910

911 for (int i = -1; i <= 1; ++i) {

912 for (int j = -1; j <= 1; ++j) {

913 if (i == 0 && j == 0)

914 continue;

915

916 bool wasSeen = false;

917 bool hasCreature = false;

918 bool isNotWalkable = true;

919 bool isNotPathable = true;

920 int speed = 100;

921

922 Position neighborPos = currentNode->pos.translated(i, j);

923 if (neighborPos.x < 0 || neighborPos.y < 0)

924 continue;

925 if (g_map.isAwareOfPosition(neighborPos)) {

926 wasSeen = true;

927 if (const TilePtr &tile = getTile(neighborPos)) {

928 hasCreature = tile->hasCreature() &&

929 (!(flags & Otc::PathFindIgnoreCreatures));

930 isNotWalkable =

931 !tile->isWalkable(flags & Otc::PathFindIgnoreCreatures);

932 isNotPathable = !tile->isPathable();

933 speed = tile->getGroundSpeed();

934 }

935 } else {

936 const MinimapTile &mtile = g_minimap.getTile(neighborPos);

937 wasSeen = mtile.hasFlag(MinimapTileWasSeen);

938 isNotWalkable = mtile.hasFlag(MinimapTileNotWalkable);

939 isNotPathable = mtile.hasFlag(MinimapTileNotPathable);

940 if (isNotWalkable || isNotPathable)

941 wasSeen = true;

942 speed = mtile.getSpeed();

943 }

944

945 float walkFactor = 0;

946 if (neighborPos != goalPos) {

947 if (!(flags & Otc::PathFindAllowNotSeenTiles) && !wasSeen)

948 continue;

949 if (wasSeen) {

950 if (!(flags & Otc::PathFindAllowCreatures) && hasCreature)

951 continue;

952 if (!(flags & Otc::PathFindAllowNonPathable) && isNotPathable)

953 continue;

954 if (!(flags & Otc::PathFindAllowNonWalkable) && isNotWalkable)

955 continue;

956 }

957 } else {

958 if (!(flags & Otc::PathFindAllowNotSeenTiles) && !wasSeen)

959 continue;

960 if (wasSeen) {

961 if (!(flags & Otc::PathFindAllowNonWalkable) && isNotWalkable)

962 continue;

963 }

964 }

965

966 Otc::Direction walkDir =

967 currentNode->pos.getDirectionFromPosition(neighborPos);

968 if (walkDir >= Otc::NorthEast)

969 walkFactor += 3.0f;

970 else

971 walkFactor += 1.0f;

972

973 float cost = currentNode->cost + (speed * walkFactor) / 100.0f;

974

975 SNode *neighborNode;

976 if (nodes.find(neighborPos) == nodes.end()) {

977 neighborNode = new SNode(neighborPos);

978 nodes[neighborPos] = neighborNode;

979 } else {

980 neighborNode = nodes[neighborPos];

981 if (neighborNode->cost <= cost)

982 continue;

983 }

984

985 neighborNode->prev = currentNode;

986 neighborNode->cost = cost;

987 neighborNode->totalCost =

988 neighborNode->cost + neighborPos.distance(goalPos);

989 neighborNode->dir = walkDir;

990 searchList.push(std::make_pair(neighborNode, neighborNode->totalCost));

991 }

992 }

993

994 if (!searchList.empty()) {

995 currentNode = searchList.top().first;

996 searchList.pop();

997 } else

998 currentNode = nullptr;

999 }

1000

1001 if (foundNode) {

1002 currentNode = foundNode;

1003 while (currentNode) {

1004 dirs.push_back(currentNode->dir);

1005 currentNode = currentNode->prev;

1006 }

1007 dirs.pop_back();

1008 std::reverse(dirs.begin(), dirs.end());

1009 result = Otc::PathFindResultOk;

1010 }

1011

1012 for (auto it : nodes)

1013 delete it.second;

1014

1015 return ret;

1016}

1017

1018int Map::getMinimapColor(const Position &pos) {

1019 int color = 0;

1020 if (const TilePtr &tile = getTile(pos)) {

1021 color = tile->getMinimapColorByte();

1022 }

1023 if (color == 0) {

1024 const MinimapTile &mtile = g_minimap.getTile(pos);

1025 color = mtile.color;

1026 }

1027 return color;

1028}

1029

1030bool Map::isPatchable(const Position &pos) {

1031 if (const TilePtr &tile = getTile(pos)) {

1032 return tile->isPathable();

1033 }

1034 const MinimapTile &mtile = g_minimap.getTile(pos);

1035 return !mtile.hasFlag(MinimapTileNotPathable);

1036}

1037

1038bool Map::isWalkable(const Position &pos, bool ignoreCreatures) {

1039 if (const TilePtr &tile = getTile(pos)) {

1040 return tile->isWalkable(ignoreCreatures);

1041 }

1042 const MinimapTile &mtile = g_minimap.getTile(pos);

1043 return !mtile.hasFlag(MinimapTileNotPathable);

1044}

1045

1046bool Map::isSightClear(const Position &fromPos, const Position &toPos) {

1047 if (fromPos == toPos) {

1048 return true;

1049 }

1050

1051 Position start(fromPos.z > toPos.z ? toPos : fromPos);

1052 Position destination(fromPos.z > toPos.z ? fromPos : toPos);

1053

1054 const int8_t mx = start.x < destination.x ? 1

1055 : start.x == destination.x ? 0

1056 : -1;

1057 const int8_t my = start.y < destination.y ? 1

1058 : start.y == destination.y ? 0

1059 : -1;

1060

1061 int32_t A = destination.y - start.y;

1062 int32_t B = start.x - destination.x;

1063 int32_t C = -(A * destination.x + B * destination.y);

1064

1065 while (start.x != destination.x || start.y != destination.y) {

1066 int32_t move_hor = std::abs(A * (start.x + mx) + B * (start.y) + C);

1067 int32_t move_ver = std::abs(A * (start.x) + B * (start.y + my) + C);

1068 int32_t move_cross = std::abs(A * (start.x + mx) + B * (start.y + my) + C);

1069

1070 if (start.y != destination.y &&

1071 (start.x == destination.x || move_hor > move_ver ||

1072 move_hor > move_cross)) {

1073 start.y += my;

1074 }

1075

1076 if (start.x != destination.x &&

1077 (start.y == destination.y || move_ver > move_hor ||

1078 move_ver > move_cross)) {

1079 start.x += mx;

1080 }

1081

1082 auto tile = getTile(Position(start.x, start.y, start.z));

1083 if (tile && tile->isBlockingProjectile()) {

1084 return false;

1085 }

1086 }

1087

1088 while (start.z != destination.z) {

1089 auto tile = getTile(Position(start.x, start.y, start.z));

1090 if (tile && tile->getThingCount() > 0) {

1091 return false;

1092 }

1093 start.z++;

1094 }

1095

1096 return true;

1097}

1098

1099bool Map::checkSightLine(const Position &fromPos, const Position &toPos) {

1100 if (fromPos.z != toPos.z)

1101 return false;

1102 return checkSightLine(fromPos, toPos) || checkSightLine(toPos, fromPos);

1103}

1104

1105PathFindResult_ptr

1106Map::newFindPath(const Position &start, const Position &goal,

1107 std::shared_ptr<std::list<Node *>> visibleNodes) {

1108 auto ret = std::make_shared<PathFindResult>();

1109 ret->start = start;

1110 ret->destination = goal;

1111

1112 if (start == goal) {

1113 ret->status = Otc::PathFindResultSamePosition;

1114 return ret;

1115 }

1116 if (goal.z != start.z) {

1117 return ret;

1118 }

1119

1120 struct LessNode {

1121 bool operator()(Node *a, Node *b) const {

1122 return b->totalCost < a->totalCost;

1123 }

1124 };

1125

1126 std::unordered_map<Position, Node *, PositionHasher> nodes;

1127 std::priority_queue<Node *, std::vector<Node *>, LessNode> searchList;

1128

1129 if (visibleNodes) {

1130 for (auto &node : *visibleNodes)

1131 nodes.emplace(node->pos, node);

1132 }

1133

1134 Node *initNode = new Node{1, 0, start, nullptr, 0, 0};

1135 nodes[start] = initNode;

1136 searchList.push(initNode);

1137

1138 int limit = 50000;

1139 float distance = start.distance(goal);

1140

1141 Node *dstNode = nullptr;

1142 while (!searchList.empty() && --limit) {

1143 Node *node = searchList.top();

1144 searchList.pop();

1145 if (node->pos == goal) {

1146 dstNode = node;

1147 break;

1148 }

1149 if (node->pos.distance(goal) > distance + 10000)

1150 continue;

1151 for (int i = -1; i <= 1; ++i) {

1152 for (int j = -1; j <= 1; ++j) {

1153 if (i == 0 && j == 0)

1154 continue;

1155 Position neighbor = node->pos.translated(i, j);

1156 if (neighbor.x < 0 || neighbor.y < 0)

1157 continue;

1158 auto it = nodes.find(neighbor);

1159 if (it == nodes.end()) {

1160 auto blockAndTile = g_minimap.threadGetTile(neighbor);

1161 bool wasSeen = blockAndTile.second.hasFlag(MinimapTileWasSeen);

1162 bool isNotWalkable =

1163 blockAndTile.second.hasFlag(MinimapTileNotWalkable);

1164 bool isNotPathable =

1165 blockAndTile.second.hasFlag(MinimapTileNotPathable);

1166 bool isEmpty = blockAndTile.second.hasFlag(MinimapTileEmpty);

1167 float speed = blockAndTile.second.getSpeed();

1168 if ((isNotWalkable || isNotPathable || isEmpty) && neighbor != goal) {

1169 it = nodes.emplace(neighbor, nullptr).first;

1170 } else {

1171 if (!wasSeen)

1172 speed = 2000;

1173 it = nodes

1174 .emplace(neighbor,

1175 new Node{speed, 10000000.0f, neighbor, node,

1176 node->distance + 1, wasSeen ? 0 : 1})

1177 .first;

1178 }

1179 }

1180 if (!it->second) // no way

1181 continue;

1182 if (it->second->unseen > 50)

1183 continue;

1184

1185 float diagonal = ((i == 0 || j == 0) ? 1.0f : 3.0f);

1186 float cost = it->second->cost * diagonal;

1187 cost +=

1188 diagonal * (50.0f * std::max<float>(5.0f, it->second->pos.distance(

1189 goal))); // heuristic

1190 if (node->totalCost + cost + 50 < it->second->totalCost) {

1191 it->second->totalCost = node->totalCost + cost;

1192 it->second->prev = node;

1193 if (it->second->unseen)

1194 it->second->unseen = node->unseen + 1;

1195 it->second->distance = node->distance + 1;

1196 searchList.push(it->second);

1197 }

1198 }

1199 }

1200 }

1201

1202 if (dstNode) {

1203 while (dstNode && dstNode->prev) {

1204 if (dstNode->unseen) {

1205 ret->path.clear();

1206 } else {

1207 ret->path.push_back(

1208 dstNode->prev->pos.getDirectionFromPosition(dstNode->pos));

1209 }

1210 dstNode = dstNode->prev;

1211 }

1212 std::reverse(ret->path.begin(), ret->path.end());

1213 ret->status = Otc::PathFindResultOk;

1214 }

1215 ret->complexity = 50000 - limit;

1216

1217 for (auto &node : nodes) {

1218 if (node.second)

1219 delete node.second;

1220 }

1221

1222 return ret;

1223}

1224

1225void Map::findPathAsync(const Position &start, const Position &goal,

1226 std::function<void(PathFindResult_ptr)> callback) {

1227 auto visibleNodes = std::make_shared<std::list<Node *>>();

1228 for (auto &tile : getTiles(start.z)) {

1229 if (tile->getPosition() == start)

1230 continue;

1231 bool isNotWalkable = !tile->isWalkable(false);

1232 bool isNotPathable = !tile->isPathable();

1233 float speed = tile->getGroundSpeed();

1234 if ((isNotWalkable || isNotPathable) && tile->getPosition() != goal) {

1235 visibleNodes->push_back(

1236 new Node{speed, 0, tile->getPosition(), nullptr, 0, 0});

1237 } else {

1238 visibleNodes->push_back(

1239 new Node{speed, 10000000.0f, tile->getPosition(), nullptr, 0, 0});

1240 }

1241 }

1242

1243 g_asyncDispatcher.dispatch([=] {

1244 auto ret = g_map.newFindPath(start, goal, visibleNodes);

1245 g_dispatcher.addEvent(std::bind(callback, ret));

1246 });

1247}

1248

1249std::map<std::string, std::tuple<int, int, int, std::string>>

1250Map::findEveryPath(const Position &start, int maxDistance,

1251 const std::map<std::string, std::string> &params) {

1252 // using Dijkstra's algorithm

1253 struct LessNode {

1254 bool operator()(Node *a, Node *b) const {

1255 return b->totalCost < a->totalCost;

1256 }

1257 };

1258

1259 if (g_extras.debugPathfinding) {

1260 g_logger.info(stdext::format("findEveryPath: %i %i %i - %i", start.x,

1261 start.y, start.z, maxDistance));

1262 for (auto &param : params) {

1263 g_logger.info(stdext::format("%s - %s", param.first, param.second));

1264 }

1265 }

1266

1267 std::map<std::string, std::string>::const_iterator it;

1268 it = params.find("ignoreLastCreature");

1269 bool ignoreLastCreature =

1270 it != params.end() && it->second != "0" && it->second != "";

1271 it = params.find("ignoreCreatures");

1272 bool ignoreCreatures =

1273 it != params.end() && it->second != "0" && it->second != "";

1274 it = params.find("ignoreNonPathable");

1275 bool ignoreNonPathable =

1276 it != params.end() && it->second != "0" && it->second != "";

1277 it = params.find("ignoreNonWalkable");

1278 bool ignoreNonWalkable =

1279 it != params.end() && it->second != "0" && it->second != "";

1280 it = params.find("ignoreStairs");

1281 bool ignoreStairs =

1282 it != params.end() && it->second != "0" && it->second != "";

1283 it = params.find("ignoreCost");

1284 bool ignoreCost = it != params.end() && it->second != "0" && it->second != "";

1285 it = params.find("allowUnseen");

1286 bool allowUnseen =

1287 it != params.end() && it->second != "0" && it->second != "";

1288 it = params.find("allowOnlyVisibleTiles");

1289 bool allowOnlyVisibleTiles =

1290 it != params.end() && it->second != "0" && it->second != "";

1291 it = params.find("marginMin");

1292 bool hasMargin = it != params.end();

1293 it = params.find("marginMax");

1294 hasMargin = hasMargin || (it != params.end());

1295

1296 Position destPos;

1297 it = params.find("destination");

1298 if (it != params.end()) {

1299 std::vector<int32> pos = stdext::split<int32>(it->second, ",");

1300 if (pos.size() == 3) {

1301 destPos = Position(pos[0], pos[1], pos[2]);

1302 }

1303 }

1304

1305 Position maxDistanceFromPos;

1306 int maxDistanceFrom = 0;

1307 it = params.find("maxDistanceFrom");

1308 if (it != params.end()) {

1309 std::vector<int32> pos = stdext::split<int32>(it->second, ",");

1310 if (pos.size() == 4) {

1311 maxDistanceFromPos = Position(pos[0], pos[1], pos[2]);

1312 maxDistanceFrom = pos[3];

1313 }

1314 }

1315

1316 std::map<std::string, std::tuple<int, int, int, std::string>> ret;

1317 std::unordered_map<Position, Node *, PositionHasher> nodes;

1318 std::priority_queue<Node *, std::vector<Node *>, LessNode> searchList;

1319

1320 Node *initNode = new Node{1, 0, start, nullptr, 0, 0};

1321 nodes[start] = initNode;

1322 searchList.push(initNode);

1323

1324 while (!searchList.empty()) {

1325 Node *node = searchList.top();

1326 searchList.pop();

1327 ret[node->pos.toString()] = std::make_tuple(

1328 node->totalCost, node->distance,

1329 node->prev ? node->prev->pos.getDirectionFromPosition(node->pos) : -1,

1330 node->prev ? node->prev->pos.toString() : "");

1331 if (node->pos == destPos) {

1332 if (hasMargin) {

1333 maxDistance = std::min<int>(node->distance + 4, maxDistance);

1334 } else {

1335 break;

1336 }

1337 }

1338 if (node->distance >= maxDistance)

1339 continue;

1340 for (int i = -1; i <= 1; ++i) {

1341 for (int j = -1; j <= 1; ++j) {

1342 if (i == 0 && j == 0)

1343 continue;

1344 Position neighbor = node->pos.translated(i, j);

1345 if (neighbor.x < 0 || neighbor.y < 0)

1346 continue;

1347 auto it = nodes.find(neighbor);

1348 if (it == nodes.end()) {

1349 bool wasSeen = false;

1350 bool hasCreature = false;

1351 bool isNotWalkable = true;

1352 bool isNotPathable = true;

1353 int mapColor = 0;

1354 int speed = 1000;

1355 if (g_map.isAwareOfPosition(neighbor)) {

1356 if (const TilePtr &tile = getTile(neighbor)) {

1357 wasSeen = true;

1358 hasCreature = tile->hasBlockingCreature();

1359 isNotWalkable = !tile->isWalkable(true);

1360 isNotPathable = !tile->isPathable();

1361 mapColor = tile->getMinimapColorByte();

1362 speed = tile->getGroundSpeed();

1363 }

1364 } else if (!allowOnlyVisibleTiles) {

1365 const MinimapTile &mtile = g_minimap.getTile(neighbor);

1366 wasSeen = mtile.hasFlag(MinimapTileWasSeen);

1367 isNotWalkable = mtile.hasFlag(MinimapTileNotWalkable);

1368 isNotPathable = mtile.hasFlag(MinimapTileNotPathable);

1369 mapColor = mtile.color;

1370 if (isNotWalkable || isNotPathable)

1371 wasSeen = true;

1372 speed = mtile.getSpeed();

1373 }

1374 bool hasStairs = isNotPathable && mapColor >= 210 && mapColor <= 213;

1375 bool hasReachedMaxDistance =

1376 maxDistanceFrom && maxDistanceFromPos.isValid() &&

1377 maxDistanceFromPos.distance(neighbor) > maxDistanceFrom;

1378 if ((!wasSeen && !allowUnseen) ||

1379 (hasStairs && !ignoreStairs && neighbor != destPos) ||

1380 (isNotPathable && !ignoreNonPathable && neighbor != destPos) ||

1381 (isNotWalkable && !ignoreNonWalkable) || hasReachedMaxDistance) {

1382 it = nodes.emplace(neighbor, nullptr).first;

1383 } else if ((hasCreature && !ignoreCreatures)) {

1384 it = nodes.emplace(neighbor, nullptr).first;

1385 if (ignoreLastCreature) {

1386 ret[neighbor.toString()] =

1387 std::make_tuple(node->totalCost + 100, node->distance + 1,

1388 node->pos.getDirectionFromPosition(neighbor),

1389 node->pos.toString());

1390 }

1391 } else {

1392 it =

1393 nodes

1394 .emplace(neighbor,

1395 new Node{(float)speed, 10000000.0f, neighbor, node,

1396 node->distance + 1, wasSeen ? 0 : 1})

1397 .first;

1398 }

1399 }

1400

1401 if (!it->second) {

1402 continue;

1403 }

1404

1405 float diagonal = ((i == 0 || j == 0) ? 1.0f : 3.0f);

1406 float cost = it->second->cost * diagonal;

1407 if (ignoreCost)

1408 cost = 1;

1409 if (node->totalCost + cost < it->second->totalCost) {

1410 it->second->totalCost = node->totalCost + cost;

1411 it->second->prev = node;

1412 if (it->second->unseen)

1413 it->second->unseen = node->unseen + 1;

1414 it->second->distance = node->distance + 1;

1415 searchList.push(it->second);

1416 }

1417 }

1418 }

1419 }

1420

1421 for (auto &node : nodes) {

1422 if (node.second)

1423 delete node.second;

1424 }

1425

1426 return ret;

1427}

1428