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

shortestpath.h

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 #ifndef STARK_MOVEMENT_SHORTEST_PATH_H
00024 #define STARK_MOVEMENT_SHORTEST_PATH_H
00025 
00026 #include "common/list.h"
00027 #include "common/hashmap.h"
00028 
00029 namespace Stark {
00030 
00031 namespace Resources {
00032 class FloorEdge;
00033 }
00034 
00040 class ShortestPath {
00041 public:
00042     typedef Common::List<const Resources::FloorEdge *> NodeList;
00043 
00045     NodeList search(const Resources::FloorEdge *start, const Resources::FloorEdge *goal);
00046 
00047 private:
00048     typedef Common::HashMap<const Resources::FloorEdge *, const Resources::FloorEdge *> NodePrecedenceMap;
00049     typedef Common::HashMap<const Resources::FloorEdge *, float> NodeCostMap;
00050 
00051     const Resources::FloorEdge *popEdgeWithLowestCost(NodeList &frontier, const NodeCostMap &costSoFar) const;
00052 
00053     NodeList rebuildPath(const Resources::FloorEdge *start, const Resources::FloorEdge *goal,
00054                                         const NodePrecedenceMap &cameFrom) const;
00055 };
00056 
00057 } // End of namespace Stark
00058 
00059 #endif // STARK_MOVEMENT_SHORTEST_PATH_H


Generated on Sat Feb 16 2019 05:01:04 for ResidualVM by doxygen 1.7.1
curved edge   curved edge