Mercurial > fife-parpg
changeset 310:8afb9b443f66
merged the pathfinding branch to trunk
| author | wenlin_fife@33b003aa-7bff-0310-803a-e67f0ece8222 |
|---|---|
| date | Fri, 14 Aug 2009 00:00:58 +0000 |
| parents | f6b67f424ad2 |
| children | a0e00b4b0fac |
| files | engine/core/controller/engine.cpp engine/core/pathfinder/linearpather/linearpather.cpp engine/core/pathfinder/linearpather/linearpather.h engine/core/pathfinder/linearpather/linearpather.i engine/core/pathfinder/routepather/routepather.cpp engine/core/pathfinder/routepather/routepather.h engine/core/pathfinder/routepather/routepathersearch.cpp engine/core/pathfinder/routepather/routepathersearch.h |
| diffstat | 8 files changed, 89 insertions(+), 235 deletions(-) [+] |
line wrap: on
line diff
--- a/engine/core/controller/engine.cpp Wed Aug 12 22:36:29 2009 +0000 +++ b/engine/core/controller/engine.cpp Fri Aug 14 00:00:58 2009 +0000 @@ -60,7 +60,7 @@ #include "loaders/native/video_loaders/image_loader.h" #include "loaders/native/audio_loaders/ogg_loader.h" #include "model/model.h" -#include "pathfinder/linearpather/linearpather.h" +//#include "pathfinder/linearpather/linearpather.h" #include "pathfinder/routepather/routepather.h" #include "model/metamodel/grids/hexgrid.h" #include "model/metamodel/grids/squaregrid.h" @@ -235,7 +235,7 @@ FL_LOG(_log, "Creating model"); m_model = new Model(); FL_LOG(_log, "Adding pathers to model"); - m_model->adoptPather(new LinearPather()); +// m_model->adoptPather(new LinearPather()); m_model->adoptPather(new RoutePather()); FL_LOG(_log, "Adding grid prototypes to model"); m_model->adoptCellGrid(new SquareGrid());
--- a/engine/core/pathfinder/linearpather/linearpather.cpp Wed Aug 12 22:36:29 2009 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,109 +0,0 @@ -/*************************************************************************** - * Copyright (C) 2005-2008 by the FIFE team * - * http://www.fifengine.de * - * This file is part of FIFE. * - * * - * FIFE is free software; you can redistribute it and/or * - * modify it under the terms of the GNU Lesser General Public * - * License as published by the Free Software Foundation; either * - * version 2.1 of the License, or (at your option) any later version. * - * * - * This library 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 * - * Lesser General Public License for more details. * - * * - * You should have received a copy of the GNU Lesser General Public * - * License along with this library; if not, write to the * - * Free Software Foundation, Inc., * - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * - ***************************************************************************/ - -// Standard C++ library includes - -// 3rd party library includes - -// FIFE includes -// These includes are split up in two parts, separated by one empty line -// First block: files included from the FIFE root src directory -// Second block: files included from the same folder -#include "util/log/logger.h" -#include "model/metamodel/grids/cellgrid.h" -#include "model/structures/instance.h" -#include "model/structures/layer.h" - -#include "linearpather.h" - -namespace FIFE { - static Logger _log(LM_PATHFINDER); - - int LinearPather::getNextLocation(const Instance* instance, const Location& target, - double distance_to_travel, Location& nextLocation, - Location& facingLocation, int session_id, int priority) { - Location curloc = instance->getLocation(); - assert(curloc.getMap() == target.getMap()); - Layer* layer = curloc.getLayer(); - assert(layer == target.getLayer()); - CellGrid* cg = layer->getCellGrid(); - assert(layer == target.getLayer()); - - assert(curloc.getLayer() == target.getLayer()); - m_map = curloc.getMap(); - - int cur_session_id = session_id; - if (cur_session_id < 0) { - cur_session_id = m_session_counter++; - - // extrapolate facing location for this session - ExactModelCoordinate cur_pos = curloc.getMapCoordinates(); - ExactModelCoordinate fac_pos = target.getMapCoordinates(); - fac_pos.x = fac_pos.x + (fac_pos.x - cur_pos.x); - fac_pos.y = fac_pos.y + (fac_pos.y - cur_pos.y); - facingLocation = target; - facingLocation.setMapCoordinates(fac_pos); - m_session2face[cur_session_id] = facingLocation; - FL_DBG(_log, LMsg("storing new facing loc ") << facingLocation); - } else { - FL_DBG(_log, LMsg("getting old facing loc ") << facingLocation); - facingLocation = m_session2face[cur_session_id]; - } - FL_DBG(_log, LMsg("curloc ") << curloc << ", target " << target << ", dist2travel " << distance_to_travel); - ExactModelCoordinate cur_pos = curloc.getMapCoordinates(); - ExactModelCoordinate target_pos = target.getMapCoordinates(); - double dx = (target_pos.x - cur_pos.x) * cg->getXScale(); - double dy = (target_pos.y - cur_pos.y) * cg->getYScale(); - double dist = sqrt(dx*dx + dy*dy); - FL_DBG(_log, LMsg("distance from cur to target = ") << dist); - - // calculate where current position evolves with movement - if (distance_to_travel > dist) { - distance_to_travel = dist; - } - cur_pos.x += dx * (distance_to_travel / dist); - cur_pos.y += dy * (distance_to_travel / dist); - nextLocation.setMapCoordinates(cur_pos); - FL_DBG(_log, LMsg("in case not blocking, could move to ") << nextLocation); - - // check if we have collisions and if we do, keep instance on current location - ModelCoordinate nextCellcoord = nextLocation.getLayerCoordinates(); - const std::vector<Instance*>& instances = target.getLayer()->getInstances(); - std::vector<Instance*>::const_iterator instance_it = instances.begin(); - for (;instance_it != instances.end(); ++instance_it) { - Instance* i = (*instance_it); - if ((i == instance) || (!i->getObject()->isBlocking())) { - continue; - } - ModelCoordinate c = i->getLocationRef().getLayerCoordinates(); - if ((c.x == nextCellcoord.x) && (c.y == nextCellcoord.y)) { - FL_DBG(_log, LMsg("Found blocking instance from planned cell ") << nextLocation); - nextLocation = curloc; - break; - } - } - //We're there - if((ABS(cur_pos.x - target_pos.x) < 0.1) && (ABS(cur_pos.y - target_pos.y) < 0.1)) { - return -1; - } - return cur_session_id; - } -}
--- a/engine/core/pathfinder/linearpather/linearpather.h Wed Aug 12 22:36:29 2009 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,70 +0,0 @@ -/*************************************************************************** - * Copyright (C) 2005-2008 by the FIFE team * - * http://www.fifengine.de * - * This file is part of FIFE. * - * * - * FIFE is free software; you can redistribute it and/or * - * modify it under the terms of the GNU Lesser General Public * - * License as published by the Free Software Foundation; either * - * version 2.1 of the License, or (at your option) any later version. * - * * - * This library 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 * - * Lesser General Public License for more details. * - * * - * You should have received a copy of the GNU Lesser General Public * - * License along with this library; if not, write to the * - * Free Software Foundation, Inc., * - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * - ***************************************************************************/ - -#ifndef FIFE_PATHFINDER_LINEAR_H -#define FIFE_PATHFINDER_LINEAR_H - -// Standard C++ library includes -#include <map> - -// 3rd party library includes - -// FIFE includes -// These includes are split up in two parts, separated by one empty line -// First block: files included from the FIFE root src directory -// Second block: files included from the same folder -#include "model/structures/location.h" -#include "model/structures/map.h" -#include "model/metamodel/abstractpather.h" - -namespace FIFE { - - /** Naive pathfinder implementation - */ - class LinearPather: public AbstractPather { - public: - LinearPather(): m_session_counter(0), m_map(NULL) {} - - virtual ~LinearPather() {} - - int getNextLocation(const Instance* instance, const Location& target, - double speed, Location& nextLocation, - Location& facingLocation, int session_id=-1, - int priority = MEDIUM_PRIORITY); - - void update() { } - - bool cancelSession(const int session_id) { - m_session2face.erase(session_id); - return true; - } - - std::string getName() const { return "LinearPather"; } - - private: - std::map< int, Location > m_session2face; - unsigned int m_session_counter; - Map* m_map; - }; -} - -#endif -
--- a/engine/core/pathfinder/linearpather/linearpather.i Wed Aug 12 22:36:29 2009 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,35 +0,0 @@ -/*************************************************************************** - * Copyright (C) 2005-2008 by the FIFE team * - * http://www.fifengine.de * - * This file is part of FIFE. * - * * - * FIFE is free software; you can redistribute it and/or * - * modify it under the terms of the GNU Lesser General Public * - * License as published by the Free Software Foundation; either * - * version 2.1 of the License, or (at your option) any later version. * - * * - * This library 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 * - * Lesser General Public License for more details. * - * * - * You should have received a copy of the GNU Lesser General Public * - * License along with this library; if not, write to the * - * Free Software Foundation, Inc., * - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * - ***************************************************************************/ -%module fife -%{ -#include "pathfinder/linearpather/linearpather.h" -%} -%include "model/metamodel/abstractpather.i" - -namespace FIFE { - %feature("notabstract") LinearPather; - class LinearPather: public AbstractPather { - public: - LinearPather(); - virtual ~LinearPather(); - std::string getName() const; - }; -}
--- a/engine/core/pathfinder/routepather/routepather.cpp Wed Aug 12 22:36:29 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepather.cpp Fri Aug 14 00:00:58 2009 +0000 @@ -129,14 +129,14 @@ if(m_sessions.empty()) { break; } - Search* priority_session = m_sessions.getPriorityElement().first; + RoutePatherSearch* priority_session = m_sessions.getPriorityElement().first; if(!sessionIdValid(priority_session->getSessionId())) { delete priority_session; m_sessions.popElement(); continue; } priority_session->updateSearch(); - if(priority_session->getSearchStatus() == Search::search_status_complete) { + if(priority_session->getSearchStatus() == RoutePatherSearch::search_status_complete) { const int session_id = priority_session->getSessionId(); Path newPath = priority_session->calcPath(); newPath.erase(newPath.begin()); @@ -144,7 +144,7 @@ invalidateSessionId(session_id); delete priority_session; m_sessions.popElement(); - } else if(priority_session->getSearchStatus() == Search::search_status_failed) { + } else if(priority_session->getSearchStatus() == RoutePatherSearch::search_status_failed) { const int session_id = priority_session->getSessionId(); invalidateSessionId(session_id); delete priority_session;
--- a/engine/core/pathfinder/routepather/routepather.h Wed Aug 12 22:36:29 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepather.h Fri Aug 14 00:00:58 2009 +0000 @@ -92,7 +92,7 @@ std::string getName() const { return "RoutePather"; }; private: typedef std::list<Location> Path; - typedef PriorityQueue<Search*, int> SessionQueue; + typedef PriorityQueue<RoutePatherSearch*, int> SessionQueue; typedef std::list<int> SessionList; typedef std::map<int, Path> PathMap; typedef std::map<Layer*, SearchSpace*> SearchSpaceMap; @@ -183,7 +183,5 @@ //The maximum number of ticks allowed. int m_maxticks; }; - } - #endif
--- a/engine/core/pathfinder/routepather/routepathersearch.cpp Wed Aug 12 22:36:29 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepathersearch.cpp Fri Aug 14 00:00:58 2009 +0000 @@ -40,7 +40,7 @@ namespace FIFE { RoutePatherSearch::RoutePatherSearch(const int session_id, const Location& from, const Location& to, SearchSpace* searchSpace) - : Search(session_id, from, to, searchSpace), m_destCoordInt(0), m_startCoordInt(0), m_next(0) { + : m_destCoordInt(0), m_startCoordInt(0), m_next(0), m_to(to), m_from(from), m_sessionId(session_id), m_searchspace(searchSpace), m_status(search_status_incomplete){ m_startCoordInt = m_searchspace->convertCoordToInt(from.getLayerCoordinates()); int max_index = m_searchspace->getMaxIndex(); m_destCoordInt = m_searchspace->convertCoordToInt(to.getLayerCoordinates()); @@ -48,9 +48,10 @@ m_spt.resize(max_index + 1, -1); m_sf.resize(max_index + 1, -1); m_gCosts.resize(max_index + 1, 0.0f); - m_heuristic = Heuristic::getHeuristic(searchSpace->getLayer()->getCellGrid()->getType()); + m_heuristic = Heuristic::getHeuristic(searchSpace->getLayer()->getCellGrid()->getType()); } + void RoutePatherSearch::updateSearch() { if(m_sortedfrontier.empty()) { setSearchStatus(search_status_failed); @@ -81,8 +82,8 @@ adjacentInt != m_destCoordInt) { continue; } - - float hCost = m_heuristic->calculate((*i), destCoord); + float hCost = m_heuristic->calculate((*i), destCoord); + //float hCost = Heuristic::getHeuristic(m_searchspace->getLayer()->getCellGrid()->getType())->calculate((*i), destCoord); float gCost = m_gCosts[m_next] + loc.getLayer()->getCellGrid()->getAdjacentCost(nextCoord, (*i)); if(m_sf[adjacentInt] == -1) { m_sortedfrontier.pushElement(PriorityQueue<int, float>::value_type(adjacentInt, gCost + hCost)); @@ -106,14 +107,20 @@ Location to(m_to); to.setExactLayerCoordinates(FIFE::intPt2doublePt(to.getLayerCoordinates())); path.push_back(to); + int count = 0; while(current != end) { - current = m_spt[current]; + if(m_spt[current] < 0 ) { + // This is when the size of m_spt can not handle the distance of the location + setSearchStatus(search_status_failed); + break; + } + current = m_spt[current]; Location newnode; newnode.setLayer(m_searchspace->getLayer()); ModelCoordinate currentCoord = m_searchspace->convertIntToCoord(current); newnode.setLayerCoordinates(currentCoord); path.push_front(newnode); - } + } path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinates()); return path; }
--- a/engine/core/pathfinder/routepather/routepathersearch.h Wed Aug 12 22:36:29 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepathersearch.h Fri Aug 14 00:00:58 2009 +0000 @@ -30,7 +30,6 @@ // These includes are split up in two parts, separated by one empty line // First block: files included from the FIFE root src directory // Second block: files included from the same folder -#include "pathfinder/search.h" #include "util/structures/priorityqueue.h" namespace FIFE { @@ -43,32 +42,96 @@ * * For now this class uses offline A*, however eventually this will be switched over to RTA*. */ - class RoutePatherSearch : public Search { + class RoutePatherSearch { public: RoutePatherSearch(const int session_id, const Location& from, const Location& to, SearchSpace* searchSpace); + typedef std::list<Location> Path; + /** An enumeration of the different status the search can be in. + * + */ + enum SearchStatus { + search_status_failed, + search_status_complete, + search_status_incomplete + }; + virtual void updateSearch(); virtual Path calcPath(); - private: - //The class to use to calculate the heuristic value. - Heuristic* m_heuristic; + + /** Retrieves the session id. + * + * @return The searches session id in the pather. + */ + int getSessionId() const { + return m_sessionId; + } + + /** Retrieves the pather. + * + * @return A pointer to the abstract pather which + */ + SearchSpace* getSearchSpace() const { + return m_searchspace; + } + + /** A small function which returns the current status of the search. + * + * @return An integer value representing the status, which is enumerated by this class. + */ + int getSearchStatus() const { + return m_status; + } + + protected: + /** Sets the current status of the search. + * + * @param status The status to set. + */ + void setSearchStatus(const SearchStatus status) { + m_status = status; + } + + private: + //A location object representing where the search started. + Location m_to; + + //A location object representing where the search ended. + Location m_from; + + //An integer containing the session id for this search. + int m_sessionId; + + //A pointer to the pather that owns this search. + SearchSpace* m_searchspace; + + //An enumeration of the searches current status. + SearchStatus m_status; + + //The class to use to calculate the heuristic value. + Heuristic* m_heuristic; + //The destination coordinate as an int. int m_destCoordInt; + //The start coordinate as an int. int m_startCoordInt; + //The next coordinate int to check out. int m_next; + //The shortest path tree. std::vector<int> m_spt; + //The search frontier. std::vector<int> m_sf; + //A table to hold the costs. std::vector<float> m_gCosts; + //priority queue to hold nodes on the sf in order. PriorityQueue<int, float> m_sortedfrontier; }; - } - #endif