summaryrefslogtreecommitdiff
path: root/src/pathfinder.cpp
Commit message (Collapse)AuthorAge
* Node definition manager refactor (#7016)Dániel Juhász2018-02-10
| | | | | | | | | * Rename IWritableNodeDefManager to NodeDefManager * Make INodeDefManager functions const * Use "const *NodeDefManager" instead of "*INodeDefManager" * Remove unused INodeDefManager class * Merge NodeDefManager and CNodeDefManager * Document NodeDefManager
* Code modernization: src/n*, src/o* (#6280)Loïc Blot2017-08-19
| | | | | | | | | | | * Code modernization: src/n*, src/o* * empty function * default constructor/destructor * for range-based loops * use emplace_back instead of push_back * remove unused IWritableNodeDefManager::clone() * C++ STL header style * Pointer constness in some functions
* Fix various copy instead of const ref reported by cppcheck (part 3) (#5616)Loïc Blot2017-04-20
| | | | * Also remove 2 non declared but defined functions * Make some functions around const ref changes const
* Pathfinder: Send errors to `warningstream`.Diego Martínez2017-03-27
| | | | Avoids spamming the chat about several errors.
* Environment & IGameDef code refactoring (#4985)Ner'zhul2017-01-09
| | | | | | | | | | | | | | | | | | | | | * Environment code refactoring * Cleanup includes & class declarations in client & server environment to improve build speed * ServerEnvironment::m_gamedef is now a pointer to Server instead of IGameDef, permitting to cleanup many casts. * Cleanup IGameDef * Move ITextureSource* IGameDef::getTextureSource() to Client only. * Also move ITextureSource *IGameDef::tsrc() helper * drop getShaderSource, getSceneManager, getSoundManager & getCamera abstract call * drop unused emerge() call * cleanup server unused functions (mentionned before) * Drop one unused parameter from ContentFeatures::updateTextures * move checkLocalPrivilege to Client * Remove some unnecessary casts * create_formspec_menu: remove IWritableTextureSource pointer, as client already knows it * Fix some comments * Change required IGameDef to Server/Client pointers * Previous change that game.cpp sometimes calls functions with Client + InventoryManager + IGameDef in same functions but it's the same objects * Remove duplicate Client pointer in GUIFormSpecMenu::GUIFormSpecMenu * drop ClientMap::sectorWasDrawn which is unused
* Move ServerEnvironment to dedicated cpp/header filesLoic Blot2017-01-08
| | | | * also cleanup some unneeded inclusions
* Move PP() and PP2() macros to basic_macros.hRogier2016-12-24
| | | | Instead of redefining them everywhere.
* find_path: consider walkable instead of CONTENT_AIRAuke Kok2016-05-01
| | | | | | | | | | | | | | | | | | | The path finding code works fairly well except that it considers anythin not CONTENT_AIR to be "above the surface". This results in paths that are unwalkable for entities since e.g. plants are not walkable. The path would force them to jump on top of grass plants, etc.. The obvious solution is not to use CONTENT_AIR as a criteria, but instead distinguish between walkable and non-walkable nodes. This results in paths that properly walk through grass nodes. This was extensively tested by a flock of electric sheep. Note that for underwater purposes this changes the behaviour from "the surface is walkable" to "ignore water entirely" making the path go across the water bottom, and pathing fail likely from the water surface. This is intentional.
* Pathfinder: improve GridNode storageest312016-05-01
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Before, the GridNodes were stored in vector<vector<vector<T>>>, and initialized in advance. Putting three vectors inside each other puts lots of unneccessary stress onto the allocator, costs more memory, and has worse cache locality than a flat vector<T>. For larger search distances, an the array getting initialized means essentially O(distance^3) complexity in both time and memory, which makes the current path search a joke. In order to really profit from the dijkstra/A* algorithms, other data structures need to be used for larger distances. For shorter distances, a map based GridNode storage may be slow as it requires lots of levels of indirection, which is bad for things like cache locality, and an array based storage may be faster. This commit does: 1. remove the vector<vector<vector<T>>> based GridNodes storage that is allocated and initialized in advance and for the whole possible area. 2. Add a vector<T> based GridNodes storage that is allocated and initialized in advance for the whole possible area. 3. Add a map<P,T> based GridNodes storage whose elements are allocated and initialized, when the path search code demands it. 4. Add code to decide between approach 2 and 3, based on the length of the path. 5. Remove the unused "surfaces" member of the PathGridnode class. Setting this isn't as easy anymore for the map based GridNodes storage.
* Pathfinder: use core::aabbox3d instead of own typeest312016-05-01
| | | | | There is no need to reinvent the wheel here, we have great classes from irrlicht.
* Pathfinder: Fix styleest312016-05-01
| | | | | | | | | | | * Fix naming style for methods and classes: Use camelCase for methods and PascalCase for classes as code style demands it. And use sneak_case for methods that are not member of a class. * Replace "* " with " *" for Pointers * Same for references * Put function body opening braces on new line * Other misc minor non functional style improvements
* Move pathfinder classes to cpp fileest312016-05-01
| | | | | | | | | | | | | | | There is no need to put them into the header, they are solely used inside the pathfinder. Another advantage of this change is that only the pathfinder.cpp has to be compiled if PATHFINDER_DEBUG gets defined or undefined, not all files including the .h. This commit moves the pathfinder classes to the cpp file without modifications. Also, the PATHFINDER_DEBUG macro gets moved to the cpp file and the PATHFINDER_CALC_TIME macro gets moved to a plce where it actually does work.
* Change i++ to ++iDavid Jones2015-08-25
|
* Fix pathfinder to produce more useful pathsobneq2015-05-03
| | | | | - Fix unintended negation of condition - Remove line_of_sight 'optimization'
* Remove noisy error messages, prepend "pathfinder: " to pathfinder messagessapier2014-02-03
|
* Fix bug in pathfinder causing endless loop in some situationssapier2013-08-31
|
* Use errorstream instead of std::cout in pathfinder.cppPilzAdam2013-08-16
|
* Omnicleanup: header cleanup, add ModApiUtil shared between game and mainmenuKahrl2013-08-14
|
* Math mapgen fix, ip show on connect, pathfinder segfault fixproller2013-06-23
|
* fix bug in scriptapi line_of_sightsapier2013-04-10
| | | | fix warnings for pathfinder debug traces
* Add Dijkstra A* and A* without prefetching pathfind algorithmssapier2013-04-06