Skip to content
Snippets Groups Projects
  1. May 12, 2016
  2. May 11, 2016
  3. May 10, 2016
  4. May 09, 2016
  5. May 08, 2016
  6. May 07, 2016
  7. May 06, 2016
  8. May 05, 2016
  9. May 04, 2016
  10. May 03, 2016
  11. May 02, 2016
    • Zeno-'s avatar
      Fix Windows build · c92cff5d
      Zeno- authored
      Fixes the issue introduced by c1a0ebb7 (Fix use of uninitialised variable
      in class Event) causing Windows builds to fail
      c92cff5d
  12. May 01, 2016
    • Kahrl's avatar
    • Auke Kok's avatar
      find_path: consider walkable instead of CONTENT_AIR · aa8c88cf
      Auke Kok authored
      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.
      aa8c88cf
    • est31's avatar
      Pathfinder: improve GridNode storage · 9aec701a
      est31 authored
      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.
      9aec701a
    • est31's avatar
      Pathfinder: use core::aabbox3d instead of own type · f0de237d
      est31 authored
      There is no need to reinvent the wheel here, we have
      great classes from irrlicht.
      f0de237d
Loading