diff options
Diffstat (limited to 'engines/pink/objects/walk/walk_shortest_path.cpp')
-rw-r--r-- | engines/pink/objects/walk/walk_shortest_path.cpp | 192 |
1 files changed, 96 insertions, 96 deletions
diff --git a/engines/pink/objects/walk/walk_shortest_path.cpp b/engines/pink/objects/walk/walk_shortest_path.cpp index 26253235bd..376e638d91 100644 --- a/engines/pink/objects/walk/walk_shortest_path.cpp +++ b/engines/pink/objects/walk/walk_shortest_path.cpp @@ -27,134 +27,134 @@ namespace Pink { WalkShortestPath::WalkShortestPath(WalkMgr *manager) - : _manager(manager) + : _manager(manager) {} WalkLocation *WalkShortestPath::next(WalkLocation *start, WalkLocation *destination) { - if (start == destination) - return nullptr; - add(start, 0.0, 0); - while (build() != destination); - return getNearestNeighbor(destination); + if (start == destination) + return nullptr; + add(start, 0.0, 0); + while (build() != destination); + return getNearestNeighbor(destination); } void WalkShortestPath::add(WalkLocation *wl, double val, WalkLocation *nearest) { - _locations.push_back(wl); - _visited.push_back(wl); - _weight.push_back(val); - _nearestNeigbor.push_back(nearest); + _locations.push_back(wl); + _visited.push_back(wl); + _weight.push_back(val); + _nearestNeigbor.push_back(nearest); } WalkLocation *WalkShortestPath::build() { - WalkLocation *nearest = nullptr; - WalkLocation *location = nullptr; - double len = -1.0; - addLocationsToVisit(); - for (uint i = 0; i < _toVisit.size(); ++i) { - double curLen = getLengthToNearestNeigbor(_toVisit[i]); - if (curLen < 0) { - remove(_toVisit[i]); - continue; - } - curLen += getWeight(_toVisit[i]); - if (len < 0.0 || len > curLen) { - len = curLen; - location = _toVisit[i]; - nearest = getNearestNeighbor(_toVisit[i]); - if (!nearest) - nearest = findNearestNeighbor(_toVisit[i]); - } - } - - WalkLocation *neighbor = findNearestNeighbor(location); - if (neighbor) - add(neighbor, len, nearest); - - return neighbor; + WalkLocation *nearest = nullptr; + WalkLocation *location = nullptr; + double len = -1.0; + addLocationsToVisit(); + for (uint i = 0; i < _toVisit.size(); ++i) { + double curLen = getLengthToNearestNeigbor(_toVisit[i]); + if (curLen < 0) { + remove(_toVisit[i]); + continue; + } + curLen += getWeight(_toVisit[i]); + if (len < 0.0 || len > curLen) { + len = curLen; + location = _toVisit[i]; + nearest = getNearestNeighbor(_toVisit[i]); + if (!nearest) + nearest = findNearestNeighbor(_toVisit[i]); + } + } + + WalkLocation *neighbor = findNearestNeighbor(location); + if (neighbor) + add(neighbor, len, nearest); + + return neighbor; } WalkLocation *WalkShortestPath::getNearestNeighbor(WalkLocation *location) { - for(uint i = 0; i < _visited.size(); ++i){ - if (_visited[i] == location) - return _nearestNeigbor[i]; - } + for(uint i = 0; i < _visited.size(); ++i){ + if (_visited[i] == location) + return _nearestNeigbor[i]; + } - return nullptr; + return nullptr; } void WalkShortestPath::addLocationsToVisit() { - _toVisit.resize(_locations.size()); - for (uint i = 0; i < _locations.size(); ++i) { - _toVisit[i] = _locations[i]; - } + _toVisit.resize(_locations.size()); + for (uint i = 0; i < _locations.size(); ++i) { + _toVisit[i] = _locations[i]; + } } double WalkShortestPath::getLengthToNearestNeigbor(WalkLocation *location) { - double minLength = -1.0; + double minLength = -1.0; Common::StringArray &neighbors = location->getNeigbors(); - for (uint i = 0; i < neighbors.size(); ++i) { - WalkLocation *neighbor = _manager->findLocation(neighbors[i]); - if (!isLocationVisited(neighbor)){ - double length = _manager->getLengthBetweenLocations(location, neighbor); - if (minLength >= 0.0) { - if (length < minLength) - minLength = length; - } - else minLength = length; - } - } - - return minLength; + for (uint i = 0; i < neighbors.size(); ++i) { + WalkLocation *neighbor = _manager->findLocation(neighbors[i]); + if (!isLocationVisited(neighbor)){ + double length = _manager->getLengthBetweenLocations(location, neighbor); + if (minLength >= 0.0) { + if (length < minLength) + minLength = length; + } + else minLength = length; + } + } + + return minLength; } WalkLocation *WalkShortestPath::findNearestNeighbor(WalkLocation *location) { - double minLength = -1.0; - WalkLocation *nearest = nullptr; - Common::StringArray &neighbors = location->getNeigbors(); - for (uint i = 0; i < neighbors.size(); ++i) { - WalkLocation *neighbor = _manager->findLocation(neighbors[i]); - if (!isLocationVisited(neighbor)){ - double length = _manager->getLengthBetweenLocations(location, neighbor); - if (minLength >= 0.0) { - if (length < minLength) { - nearest = neighbor; - minLength = length; - } - } - else { - nearest = neighbor; - minLength = length; - } - } - } - - return nearest; + double minLength = -1.0; + WalkLocation *nearest = nullptr; + Common::StringArray &neighbors = location->getNeigbors(); + for (uint i = 0; i < neighbors.size(); ++i) { + WalkLocation *neighbor = _manager->findLocation(neighbors[i]); + if (!isLocationVisited(neighbor)){ + double length = _manager->getLengthBetweenLocations(location, neighbor); + if (minLength >= 0.0) { + if (length < minLength) { + nearest = neighbor; + minLength = length; + } + } + else { + nearest = neighbor; + minLength = length; + } + } + } + + return nearest; } double WalkShortestPath::getWeight(WalkLocation *location) { - for (uint i = 0; i < _locations.size(); ++i) { - if (_locations[i] == location) - return _weight[i]; - } - return 0.0; + for (uint i = 0; i < _locations.size(); ++i) { + if (_locations[i] == location) + return _weight[i]; + } + return 0.0; } bool WalkShortestPath::isLocationVisited(WalkLocation *location) { - for (uint i = 0; i < _visited.size(); ++i) { - if (_visited[i] == location) - return true; - } - return false; + for (uint i = 0; i < _visited.size(); ++i) { + if (_visited[i] == location) + return true; + } + return false; } void WalkShortestPath::remove(WalkLocation *location) { - for (uint i = 0; i < _locations.size(); ++i) { - if (_locations[i] == location){ - _locations.remove_at(i); - _weight.remove_at(i); - break; - } - } + for (uint i = 0; i < _locations.size(); ++i) { + if (_locations[i] == location){ + _locations.remove_at(i); + _weight.remove_at(i); + break; + } + } } } // End of namespace Pink |