Improve pathfinding AI #39

nwinter opened this Issue Jan 2, 2014 · 1 comment


None yet

1 participant

nwinter commented Jan 2, 2014

There is at least one bug sometimes causing Thangs to think they can't get to places that they can get to, leading them to run straight at their target (since they gave up on actually pathfinding).

There's at least one other bug causing Thangs to not take wide enough corners around structural nav mesh vertices that ends up in them bouncing off of corners a few times, especially if their radius isn't an even multiple of one meter. Try looking at Taunt the Guards, where the archer is following Tharin, and setting her width/height down to 1.5m or less instead of 2m. She'll bounce off corners like crazy.

Part of this is because the grid/pathfinding resolution isn't high enough, i.e., 2.5m ogres are treated as 1.25m radius which gets rounded up to 2m which, with a 1m radius grid and 4m hallways, means the grid thinks they cannot pass.

Those are the only two bugs I know about, but probably there are others resulting from how the nav meshes are generated or how the A* vertices are picked.

In addition to fixing the bugs, it would be awesome to improve performance (should be really easy to do if you look at the code and perhaps cache rectangles' vertices) and to clean it up (the way rectangle vertex associations is currently done is just nasty).

If one were extraordinarily ambitious, one could extend the nav mesh and pathfinding to operate an convex polygons, not just rectangles.

To get an idea of where this code is coming from, just look at the ai.Pathfinds Component and the AI System (from within the level editor) and follow any imports to things like app/lib/world/ and app/lib/world/

This touches upon the code that everyone trounced me with in Gridmancer, too, for generating the nav meshes.

Here are some links I found helpful when implementing this:

Fun fact: I was on an epic coding binge implementing all this stuff in the middle of the week:

nwinter commented Jan 21, 2014

@sderickson has fixed many bugs and cleaned up the way that the vertex graph is constructed. The grid resolution problem is the only bug that I still know of.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment