Method findBestPath

source/gamemap/GameMap.cpp:1337–1382

}

std::list<Tile*> GameMap::findBestPath(const Creature* creature, Tile* tileStart, const std::vector<Tile*> possibleDests,
    Tile*& chosenTile)
{
    chosenTile = nullptr;
    std::list<Tile*> returnList;
    if(possibleDests.empty())
        return returnList;

    // We start by sorting the vector
    std::vector<Tile*> possibleDestsTmp = possibleDests;
    std::sort(possibleDestsTmp.begin(), possibleDestsTmp.end(), [this, &tileStart](Tile* tile1, Tile* tile2){
              int d1 = Pathfinding::squaredDistanceTile(*tile1, *tileStart);
              int d2 = Pathfinding::squaredDistanceTile(*tile2, *tileStart);
              return d1 < d2;
        });

    double magic = 2.0;
    for(Tile* tile : possibleDestsTmp)
    {
        if(!pathExists(creature, tileStart, tile))
            continue;

        // The first reachable tile is the best by default
        Ogre::Real dist = std::hypotf(tile->getX() - tileStart->getX(), tile->getY() - tileStart->getY());
        if(chosenTile == nullptr)
        {
            chosenTile = tile;
            returnList = path(tileStart, tile, creature, creature->getSeat(), false);
            continue;
        }

        // We compute the path only if walkableDist < (dist * magic).
        double walkableDist = static_cast<double>(returnList.size());
        if(walkableDist < (dist * magic))
            continue;

        std::list<Tile*> pathTmp = path(tileStart, tile, creature, creature->getSeat(), false);
        if(pathTmp.size() < returnList.size())
        {
            // The path is shorter
            chosenTile = tile;
            returnList = pathTmp;
        }
    }
    return returnList;
}

bool GameMap::pathExists(const Creature* creature, Tile* tileStart, Tile* tileEnd)
{