summaryrefslogtreecommitdiff
path: root/cmake/Modules/FindOpenGLES2.cmake
diff options
context:
space:
mode:
authorest31 <MTest31@outlook.com>2016-04-01 03:13:24 +0200
committerest31 <MTest31@outlook.com>2016-05-01 15:32:03 +0200
commit9aec701a4cb999b3d1eb097d4b01df0480b4ebd0 (patch)
treea34b397e126507df981aa1776604fcc7fbe75fa0 /cmake/Modules/FindOpenGLES2.cmake
parentf0de237de729b7b68091210570f10545134b7cf2 (diff)
downloadminetest-9aec701a4cb999b3d1eb097d4b01df0480b4ebd0.tar.gz
minetest-9aec701a4cb999b3d1eb097d4b01df0480b4ebd0.tar.bz2
minetest-9aec701a4cb999b3d1eb097d4b01df0480b4ebd0.zip
Pathfinder: improve GridNode storage
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.
Diffstat (limited to 'cmake/Modules/FindOpenGLES2.cmake')
0 files changed, 0 insertions, 0 deletions