Mercurial > fife-parpg
changeset 300:1465536aec94
* Reverting revisions 2937 - 2947; these have been pathfinding related changes that partially broke some FIFE-based 3rd party games
* trunk has been copied to branches/active/pathfinding before the revert, so you can continue to work on the pathfinding changes without the risk of breaking trunk by accident
| author | mvbarracuda@33b003aa-7bff-0310-803a-e67f0ece8222 |
|---|---|
| date | Mon, 06 Jul 2009 19:51:22 +0000 |
| parents | ff8bc835260c |
| children | a0856bef4786 |
| 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 engine/core/pathfinder/search.h tests/swig_tests/action_tests.py |
| diffstat | 10 files changed, 365 insertions(+), 79 deletions(-) [+] |
line wrap: on
line diff
--- a/engine/core/controller/engine.cpp Mon Jul 06 01:35:34 2009 +0000 +++ b/engine/core/controller/engine.cpp Mon Jul 06 19:51:22 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());
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/engine/core/pathfinder/linearpather/linearpather.cpp Mon Jul 06 19:51:22 2009 +0000 @@ -0,0 +1,109 @@ +/*************************************************************************** + * 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; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/engine/core/pathfinder/linearpather/linearpather.h Mon Jul 06 19:51:22 2009 +0000 @@ -0,0 +1,70 @@ +/*************************************************************************** + * 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 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/engine/core/pathfinder/linearpather/linearpather.i Mon Jul 06 19:51:22 2009 +0000 @@ -0,0 +1,35 @@ +/*************************************************************************** + * 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 Mon Jul 06 01:35:34 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepather.cpp Mon Jul 06 19:51:22 2009 +0000 @@ -129,14 +129,14 @@ if(m_sessions.empty()) { break; } - RoutePatherSearch* priority_session = m_sessions.getPriorityElement().first; + Search* 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() == RoutePatherSearch::search_status_complete) { + if(priority_session->getSearchStatus() == Search::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() == RoutePatherSearch::search_status_failed) { + } else if(priority_session->getSearchStatus() == Search::search_status_failed) { const int session_id = priority_session->getSessionId(); invalidateSessionId(session_id); delete priority_session;
--- a/engine/core/pathfinder/routepather/routepather.h Mon Jul 06 01:35:34 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepather.h Mon Jul 06 19:51:22 2009 +0000 @@ -92,7 +92,7 @@ std::string getName() const { return "RoutePather"; }; private: typedef std::list<Location> Path; - typedef PriorityQueue<RoutePatherSearch*, int> SessionQueue; + typedef PriorityQueue<Search*, int> SessionQueue; typedef std::list<int> SessionList; typedef std::map<int, Path> PathMap; typedef std::map<Layer*, SearchSpace*> SearchSpaceMap;
--- a/engine/core/pathfinder/routepather/routepathersearch.cpp Mon Jul 06 01:35:34 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepathersearch.cpp Mon Jul 06 19:51:22 2009 +0000 @@ -40,7 +40,7 @@ namespace FIFE { RoutePatherSearch::RoutePatherSearch(const int session_id, const Location& from, const Location& to, SearchSpace* searchSpace) - : m_destCoordInt(0), m_startCoordInt(0), m_next(0), m_to(to), m_from(from), m_sessionId(session_id), m_searchspace(searchSpace) { + : Search(session_id, from, to, searchSpace), m_destCoordInt(0), m_startCoordInt(0), m_next(0) { m_startCoordInt = m_searchspace->convertCoordToInt(from.getLayerCoordinates()); int max_index = m_searchspace->getMaxIndex(); m_destCoordInt = m_searchspace->convertCoordToInt(to.getLayerCoordinates()); @@ -48,12 +48,9 @@ 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()); } - RoutePatherSearch::~RoutePatherSearch(){ - - } - void RoutePatherSearch::updateSearch() { if(m_sortedfrontier.empty()) { setSearchStatus(search_status_failed); @@ -85,7 +82,7 @@ continue; } - float hCost = Heuristic::getHeuristic(m_searchspace->getLayer()->getCellGrid()->getType())->calculate((*i), destCoord); + float hCost = m_heuristic->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));
--- a/engine/core/pathfinder/routepather/routepathersearch.h Mon Jul 06 01:35:34 2009 +0000 +++ b/engine/core/pathfinder/routepather/routepathersearch.h Mon Jul 06 19:51:22 2009 +0000 @@ -30,7 +30,7 @@ // 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 "pathfinder/search.h" #include "util/structures/priorityqueue.h" namespace FIFE { @@ -43,76 +43,16 @@ * * For now this class uses offline A*, however eventually this will be switched over to RTA*. */ - class RoutePatherSearch { + class RoutePatherSearch : public Search { public: RoutePatherSearch(const int session_id, const Location& from, const Location& to, SearchSpace* searchSpace); - ~RoutePatherSearch(); - - 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(); - - /** 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; - + private: + //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.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/engine/core/pathfinder/search.h Mon Jul 06 19:51:22 2009 +0000 @@ -0,0 +1,136 @@ +/*************************************************************************** + * 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_SEARCH +#define FIFE_PATHFINDER_SEARCH + +// Standard C++ library includes +#include <vector> + +// 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" + +namespace FIFE { + + class SearchSpace; + + /** A base class that all searches must derive from. + * + */ + class Search { + public: + 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 + }; + /** Constructor. + * + * @param session_id The id in the pather that references this session. + * @param from The location where the search should be started from. + * @param to The location where the search should finish. + * @param pather A pointer to the pather controlling this session. + */ + Search(const int session_id, const Location& from, const Location& to, SearchSpace* searchspace) + : m_to(to), m_from(from), m_sessionId(session_id), m_searchspace(searchspace), + m_status(search_status_incomplete) { + } + + /** Destructor. + * + */ + virtual ~Search() {} + + /** 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; + } + + + /** Updates the search and returns the next part of the path or the entire path if the + * algorithm is offline. + * + * @return A vector of Location objects representing the path. + */ + virtual void updateSearch() = 0; + + /** Calculates a path generated by a search. + * + * Creates a path and returns it. + */ + virtual Path calcPath() = 0; + protected: + + /** Sets the current status of the search. + * + * @param status The status to set. + */ + void setSearchStatus(const SearchStatus status) { + m_status = status; + } + + //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; + }; + +} + +#endif
--- a/tests/swig_tests/action_tests.py Mon Jul 06 01:35:34 2009 +0000 +++ b/tests/swig_tests/action_tests.py Mon Jul 06 19:51:22 2009 +0000 @@ -23,8 +23,7 @@ self.obj = fife.Object("object001", 'plaa') fife.ObjectVisual.create(self.obj) -# self.pather = fife.LinearPather() - self.pather = fife.RoutePather() + self.pather = fife.LinearPather() self.obj.setPather(self.pather) self.action = self.obj.createAction('walk') fife.ActionVisual.create(self.action)