| 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 |
