diff options
author | whiterandrek | 2018-04-05 08:15:14 +0300 |
---|---|---|
committer | Eugene Sandulenko | 2018-06-28 23:51:32 +0200 |
commit | cad72b1532faa96c68848392766f25a4a58398ab (patch) | |
tree | 04d5e0cbda2aadb79fce35a1ddd45f0f0798f60f /engines/pink/objects/walk/walk_shortest_path.cpp | |
parent | 4b7c75607a5d54d95c383fabf381d82d4ac77b94 (diff) | |
download | scummvm-rg350-cad72b1532faa96c68848392766f25a4a58398ab.tar.gz scummvm-rg350-cad72b1532faa96c68848392766f25a4a58398ab.tar.bz2 scummvm-rg350-cad72b1532faa96c68848392766f25a4a58398ab.zip |
PINK: basic walk, left click and seqTimer implementation
Diffstat (limited to 'engines/pink/objects/walk/walk_shortest_path.cpp')
-rw-r--r-- | engines/pink/objects/walk/walk_shortest_path.cpp | 159 |
1 files changed, 159 insertions, 0 deletions
diff --git a/engines/pink/objects/walk/walk_shortest_path.cpp b/engines/pink/objects/walk/walk_shortest_path.cpp new file mode 100644 index 0000000000..77562e81cb --- /dev/null +++ b/engines/pink/objects/walk/walk_shortest_path.cpp @@ -0,0 +1,159 @@ +/* ScummVM - Graphic Adventure Engine + * + * ScummVM is the legal property of its developers, whose names + * are too numerous to list here. Please refer to the COPYRIGHT + * file distributed with this source distribution. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + */ + +#include "walk_shortest_path.h" +#include "walk_mgr.h" +#include "walk_location.h" + +namespace Pink { + +WalkShortestPath::WalkShortestPath(WalkMgr *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); +} + +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); +} + +WalkLocation *WalkShortestPath::build() { + WalkLocation *nearest = nullptr; + WalkLocation *location = nullptr; + double len = -1.0; + addLocationsToVisit(); + for (int 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(int i = 0; i < _visited.size(); ++i){ + if (_visited[i] == location) + return _nearestNeigbor[i]; + } + + return nullptr; +} + +void WalkShortestPath::addLocationsToVisit() { + _toVisit.resize(_locations.size()); + for (int i = 0; i < _locations.size(); ++i) { + _toVisit[i] = _locations[i]; + } +} + +double WalkShortestPath::getLengthToNearestNeigbor(WalkLocation *location) { + double minLength = -1.0; + auto &neighbors = location->getNeigbors(); + for (int 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; + auto neighbors = location->getNeigbors(); + for (int 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 (int i = 0; i < _locations.size(); ++i) { + if (_locations[i] == location) + return _weight[i]; + } + return 0.0; +} + +bool WalkShortestPath::isLocationVisited(WalkLocation *location) { + for (int i = 0; i < _visited.size(); ++i) { + if (_visited[i] == location) + return 1; + } + return 0; +} + +void WalkShortestPath::remove(WalkLocation *location) { + for (int i = 0; i < _locations.size(); ++i) { + if (_locations[i] == location){ + _locations.remove_at(i); + _weight.remove_at(i); + } + } +} + +} // End of namespace Pink
\ No newline at end of file |