ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

shortestpath.cpp

Go to the documentation of this file.
00001 /* ResidualVM - A 3D game interpreter
00002  *
00003  * ResidualVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the AUTHORS
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #include "engines/stark/movement/shortestpath.h"
00024 
00025 #include "common/hash-ptr.h"
00026 
00027 #include "engines/stark/resources/floor.h"
00028 
00029 namespace Stark {
00030 
00031 ShortestPath::NodeList ShortestPath::search(const Resources::FloorEdge *start, const Resources::FloorEdge *goal) {
00032     NodeList frontier;
00033     NodePrecedenceMap cameFrom;
00034     NodeCostMap costSoFar;
00035 
00036     frontier.push_back(start);
00037     cameFrom[start] = nullptr;
00038     costSoFar[start] = 0;
00039 
00040     while (!frontier.empty()) {
00041         const Resources::FloorEdge *current = popEdgeWithLowestCost(frontier, costSoFar);
00042 
00043         if (current == goal)
00044             break;
00045 
00046         Common::Array<Resources::FloorEdge *> neighbours = current->getNeighbours();
00047         for (uint i = 0; i < neighbours.size(); i++) {
00048             const Resources::FloorEdge *next = neighbours[i];
00049             if (!next->isEnabled())
00050                 continue;
00051 
00052             float newCost = costSoFar[current] + current->costTo(next);
00053             if (!costSoFar.contains(next) || newCost < costSoFar[next]) {
00054                 frontier.push_back(next);
00055                 cameFrom[next] = current;
00056                 costSoFar[next] = newCost;
00057             }
00058         }
00059     }
00060 
00061     return rebuildPath(start, goal, cameFrom);
00062 }
00063 
00064 ShortestPath::NodeList ShortestPath::rebuildPath(const Resources::FloorEdge *start, const Resources::FloorEdge *goal,
00065                                                  const NodePrecedenceMap &cameFrom) const {
00066     NodeList path;
00067 
00068     const Resources::FloorEdge *current = goal;
00069     path.push_front(goal);
00070 
00071     while (current && current != start) {
00072         current = cameFrom[current];
00073         path.push_front(current);
00074     }
00075 
00076     if (current != start) {
00077         // No path has been found from start to goal
00078         return NodeList();
00079     }
00080 
00081     path.push_front(start);
00082     return path;
00083 }
00084 
00085 const Resources::FloorEdge *ShortestPath::popEdgeWithLowestCost(NodeList &frontier, const NodeCostMap &costSoFar) const {
00086     // Poor man's priority queue using a list ...
00087     NodeList::iterator lowestCostItem = frontier.begin();
00088     for (NodeList::iterator it = frontier.begin(); it != frontier.end(); it++) {
00089         if (costSoFar[*it] < costSoFar[*lowestCostItem]) {
00090             lowestCostItem = it;
00091         }
00092     }
00093 
00094     const Resources::FloorEdge *result = *lowestCostItem;
00095 
00096     frontier.erase(lowestCostItem);
00097 
00098     return result;
00099 }
00100 
00101 } // End of namespace Stark


Generated on Sat Mar 23 2019 05:02:11 for ResidualVM by doxygen 1.7.1
curved edge   curved edge