[Pogamut-list] Floyd Warshall

[jacob.schrum]

Floyd Warshall

Author: jacob.schrum

I tried using FloydWarshall to navigate around, but whenever I use it, the bot attempts to follow paths that obviously won't work. This seems to be a problem in UT2004 levels. Some navpoints seem to point almost straight up to ridiculous heights that even a double jump can't reach. I suspect that the reason these are here is so that bots can so Shield Gun jumps (though I've never seen a native bot do one). However, the FloydWarshall planner doesn't know this, so you end up with bots jumping stupidly and failing to get anywhere. In some cases it even seems as though the bots are trying to move upwards along edges that point downwards, but I'm not sure.

Although these edges are actually part of the nav graph in the levels, the bots using the real-time planner don't seem to have this problem? Why is this? I thought they were basically the same, except that FloydWarshall was precomputed. Also, FloydWarshall will recognize changes made via the navBuilder, whereas the real-time planner does not.

I could use the navBuilder to fix the problem myself, except I would have to specialize for each level. Is there a way to iterate over all NavPoints/Edges with the navBuilder? I could just cut all upward pointing edges with too high of a height difference.

Here are some example edges to help you troubleshoot the problem: 
DM-Flux2.PathNode13 -> DM-Flux2.JumpSpot0
DM-Gestalt.PathNode73 -> DM-Gestalt.JumpSpot21

Both of these are huge jumps near UDamage power-ups that can only be traversed using
a Shield Gun jump.

-- 
Reply Link: <http://diana.ms.mff.cuni.cz/main/tiki-view_forum_thread.php?forumId=4&comments_parentId=703#form>