Minetest logo

IRC log for #minetest-dev, 2020-01-20

| Channels | #minetest-dev index | Today | | Google Search | Plaintext

All times shown according to UTC.

Time Nick Message
00:21 calcul0n joined #minetest-dev
01:25 T4im joined #minetest-dev
02:28 fluxflux_ joined #minetest-dev
04:01 Taoki joined #minetest-dev
06:22 erlehmann joined #minetest-dev
08:38 ShadowNinja joined #minetest-dev
09:56 proller joined #minetest-dev
10:19 proller joined #minetest-dev
10:36 df458 joined #minetest-dev
10:49 proller joined #minetest-dev
11:02 Fixer joined #minetest-dev
11:05 proller joined #minetest-dev
11:22 nepugia joined #minetest-dev
11:57 proller joined #minetest-dev
12:03 Wuzzy joined #minetest-dev
12:05 calcul0n joined #minetest-dev
12:21 proller joined #minetest-dev
12:30 Beton joined #minetest-dev
12:34 AntumDeluge joined #minetest-dev
13:17 proller joined #minetest-dev
13:49 proller joined #minetest-dev
14:15 pmp-p joined #minetest-dev
14:21 proller joined #minetest-dev
15:37 absurb joined #minetest-dev
16:57 bodqhrohro joined #minetest-dev
17:04 pmp-p joined #minetest-dev
17:04 behalebabo joined #minetest-dev
17:33 Krock joined #minetest-dev
18:40 EvergreenTree joined #minetest-dev
19:15 paramat joined #minetest-dev
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:40 Taoki joined #minetest-dev
19:48 proller joined #minetest-dev
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)
19:53 mizux joined #minetest-dev
20:32 ssieb joined #minetest-dev
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:34 fluxflux_ joined #minetest-dev
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:37 df458 joined #minetest-dev
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
22:48 pmp-p joined #minetest-dev
22:53 clavi joined #minetest-dev
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

| Channels | #minetest-dev index | Today | | Google Search | Plaintext