More aggressive path splicing

[leijurv]

Right now, if playerFeet intersects with any position of next, it jumps immediately onto that path. This is fine and good if, for example, next begins with a bit of a backtrack of current, you'll never end up executing those redundant parts at all and can skip to what happens next on next.

However, it doesn't always backtrack the same way. A few times I've seen it make a big loop where it goes ~10 blocks diagonal into a corner, then next moves one block to the side and goes all the way back. It never intersects with next but it's really really close and should totally just jump on it.

A duct tape patch solution would be to calculate all movement costs from playerFeet and if any of them intersect with next, take it... but that only applies to a gap of 1 block.

A more interesting solution would be to have more than one start node in the A* pathfinding. Normally, you start off by setting one node (your start node) to be 0 cost and adding it to your open set, then starting the graph search loop from there. I wonder if it would be possible to set the blockpos of every node in current to be 0 cost while calculating next. That way it would get the current full path, but be able to jump off it anywhere it wants instead of just at the very end. And with the goal heuristic combined cost in the openset selection process, it would (most of the time) end up just popping off the end node first (because it has the lowest goal heuristic, because current and next were calculated with the same goal), and running from there. So it wouldn't have any negative impact on normal splicing with no backtracking, but would allow more efficient backtracking.

So the TODO is figure out if this would have any negative impacts or gotchas that I'm not thinking of, and to try it out.

[leijurv]

Here's a gotcha, 30-minutes-ago-self. If the next path is allowed to start anywhere along the current path it wants, it might start from a position that it's already passed.

So there's a tradeoff here. The earlier you calculate the path, the more breathing room you have to calculate the next one. But also, the earlier you calculate it, the fewer chunks are loaded in the direction you're going in. (this is why old MineBot next planning was so dumb: it starting calculating the next segment immediately after current finished calculating and started executing). So, right now path calculation takes a max of 4 seconds, and to account for fluctuations between cost calculation and actual tick time, we start calculating the next path 150 ticks out (7.5 seconds). So, theoretically, we could start calculating at 150 ticks out, then allow the last 3 seconds of path to be valid starting points for the next path? This is tricky. What if there's an overestimate in cost? Does the current path just stop N blocks from the end because it's still waiting for the next one to be done calculating and we told it that it could start from any of these last N blocks?

This is starting to just sound like we should cutoff the last N blocks from every path we calculate and let the next one start from there, which is bad.

[leijurv]

Ok here's a better way to do it! Force the next path to start from exactly the end of the current one, but decrease the cost of backtracking below what the actual costs of those movements are. Like, if a movement ends on a position that's a part of the current path, decrease its cost by 10%. This will tiebreak between all the possible traverse/diagonal combinations to backtrack and make the "best" one an exact backtrack of the current path. This way we can use the existing path splicer and get the benefit. Yay!

[leijurv]

Done! e0f2159

[leijurv]

Explanatory video: https://www.youtube.com/watch?v=CGiMcb8-99Y