Time Nick Message 19:16 paramat merging #9303 19:16 ShadowBot https://github.com/minetest/minetest/issues/9303 -- Make image of resized `torchlike` attach to side by Wuzzy2 19:16 paramat translucency depth sorting is not 'broken', it just never existed ;) 19:36 p_gimeno that's what I imagined, thanks for confirmation :) 19:50 paramat details in old issue #95 19:50 ShadowBot https://github.com/minetest/minetest/issues/95 -- Seeing more lava through see-through lava (no translucency depth-sorting) 21:07 Wuzzy literally lol 21:07 Wuzzy i lol'ed hard about *how* broken the pathfinder is. its actually funny 21:08 Wuzzy the so-called A* algorithm (haha!) returns me a path with easily 200 waypoints for a destination that is just 6 nodes away and easily reachable. all it takes is a drop in a strategic position =) 21:09 Wuzzy A* ... more like Z- 21:11 Wuzzy and the way it walks is really bonkers, too. i have visualized it with a test mod 21:11 Wuzzy no shame btw i am just very amused ? 21:12 Wuzzy check out this screenshot: 21:12 Wuzzy https://satoshiupload.com/images/YVmC855PVA.png 21:13 Wuzzy it starts at START and the target is the red X. it should only walk a few nodes but intead it decides to drop into the cave and walk all around the mountain 21:14 p_gimeno o.o 21:15 p_gimeno there's a clear path of 9 nodes 21:15 Wuzzy yep 21:15 p_gimeno they are all touched by the algorithm 21:15 p_gimeno is that pathfinder in C++ or in Lua? 21:16 Wuzzy its minetest.find_path. the visualization comes from a test mod. 21:16 Wuzzy It's the same for A* and A*_noprefetch 21:16 p_gimeno er, that was not my question :) 21:16 Wuzzy Dijktra algorithm does not fall into the pit 21:16 rubenwardy there's a definite bug there 21:16 Wuzzy minetest.find_path is the C++ pathfinder. 21:16 p_gimeno ah, thanks 21:17 rubenwardy well, I mean - technically it's functioning as a pathfinder 21:17 rubenwardy just not a very good one 21:17 p_gimeno I know of a Lua pathfinder library 21:17 Wuzzy yeah but this is DEFINITELY not the A* algorithm ? 21:17 rubenwardy I accidentally made a pathfinder that found the longest possible route 21:17 Wuzzy and the path inside the mountain is even crazier 21:18 Wuzzy it goes strange pointless zigzag routes 21:18 Wuzzy yeah its almost as if this is optimized for the longest way =) 21:18 Wuzzy I think I'll add this testing tool to my ever-growing devtest game. its very fun to play around with it 21:19 p_gimeno would it make sense to have it reimplemented in Lua? for ease of maintenance, if anything? 21:19 Wuzzy what's the point? 21:20 Wuzzy just implement A* correctly, test it properly and be done with it forever 21:21 Wuzzy My first guess would be that the pathfinder is greedy 21:21 Wuzzy another issue i found is that the pathfinder fails to walk diagonally. on a target that is diagonal, it goes only on the X and Z axis, it fails to walk diagonally 21:22 p_gimeno I vote for a silly bug... like an inverted condition or a wrong assumption or something like that 21:28 p_gimeno oh gosh, it's 2d pure 21:28 Wuzzy there's a third bug I found as well... If the start point is in mid-air (i.e. not directly above a walkable node), the pathfinder always fails 21:28 Wuzzy 3 bugs found in a very short time =) 21:29 p_gimeno what's wrong with that? 21:29 Wuzzy well the pathfinder function has 2 parameters: max_drop and max_jump 21:30 Wuzzy max_drop is the maximum number of nodes the pathfinder is allowed to "fall" 21:30 p_gimeno ah 21:30 Wuzzy but if the startpoint is in mid-air (even if only 2 nodes above ground), it fails 21:30 p_gimeno ok, sounds like that's easily solvable with preprocessing 21:30 Wuzzy in my tests, i used max_jump=1 and max_drop=5 21:31 Wuzzy which is fitting for players 21:31 p_gimeno "if no node immediately below destination, find the first node below. If the distance is > max_drop, fail, otherwise find the route to the projected position" 21:32 Wuzzy yeah 21:33 Wuzzy but this explains why the pathfinder returns nil so often 21:33 Wuzzy when a mob is close to the edge of a node, it looks to minetest as if it is above open air 21:35 Wuzzy p_gimeno: this fix for the 3rd issue sounds indeed trivial, but i think its quite important. too bad I noticed it too late so the fix won't make it into 5.1.1 ? 21:39 p_gimeno searchdistance is not a parameter, right? 21:43 p_gimeno Wuzzy: how are you calling it exactly? 21:44 Wuzzy searchdistance is literally a parameter 21:45 p_gimeno yes, I've just found out, sorry 21:45 Wuzzy how do I call what? 21:45 p_gimeno find_path 21:47 p_gimeno hm, I see more problems 21:49 p_gimeno there are three possible values for algorithm 21:49 p_gimeno https://github.com/minetest/minetest/blob/0877587cce1d96b1c8c009221684ab382e8f1929/src/script/lua_api/l_env.cpp#L1181 21:49 p_gimeno empty, A* and Dijkstra 21:50 p_gimeno also, there's no warning or error if you enter a wrong algorithm, and Dijkstra is a bit complicated to spell right :) 21:53 p_gimeno ok, after looking in more detail, that's actually the only problem in that area, that there's no error or warning if a wrong algorithm is entered 21:55 p_gimeno if I understand correctly, "Dijkstra" is an exhaustive search, while "A*" is a heuristic search, right? if so, the heuristic can be ruled out as the source of the problem by trying Dijkstra 22:01 Wuzzy dijkstra is much slower tho 22:03 Wuzzy anyway a* should return shortest path 22:03 Wuzzy theres definitely something off with the implementation 22:03 Wuzzy maybe the heurisitc function is bad. but need to look at actual code for that =) 22:04 Wuzzy also the fact that so-called A* dont even know how to walk diagonally is definitely a red flag 22:04 Wuzzy i suspect that Minetest's "A*" is not actually A* 22:04 Wuzzy anyway 22:05 Wuzzy rubenwardy: whats the difference between A* and A*_noprefetch? 22:05 rubenwardy presumably the latter one doesn't prefetch 22:06 * xerox123_ slow claps 22:07 Wuzzy lol 22:13 p_gimeno this is the only distinction: https://github.com/minetest/minetest/blob/0877587cce1d96b1c8c009221684ab382e8f1929/src/pathfinder.cpp#L612 22:14 p_gimeno Wuzzy: since you seem to have a setup that allows you to test easily, maybe you can try the same crazy route with Dijkstra and see if it comes up right? 22:15 Wuzzy dijkstra doesnt make those crazy routes 22:17 p_gimeno that makes the heuristic function suspicious 22:18 p_gimeno I imagine using "A*" doesn't make a difference, right? 22:19 p_gimeno I mean, "A*" vs "A*_noprefetch" 22:19 Wuzzy both made the same crazy paths 22:20 p_gimeno ok 22:21 p_gimeno this is the algorithm selector https://github.com/minetest/minetest/blob/0877587cce1d96b1c8c009221684ab382e8f1929/src/pathfinder.cpp#L679 and it's not in a loop 22:22 p_gimeno so, updateCostHeuristic is the recursive one 22:27 Wuzzy I uploaded my testpathfinder mod 22:27 Wuzzy https://forum.minetest.net/viewtopic.php?f=9&t=23802&p=365713 22:27 Wuzzy see README.md to learn how it works 23:27 p_gimeno Wuzzy: is it normal that the repo is called 'mineTET_devtoys? 23:28 Wuzzy ugh. whatever 23:28 Wuzzy i might discontinue it anyway in favor of devtest 23:29 Wuzzy but testtools will be split off