Pathfinding Improvements: Change Search Direction

[JDCalvert]

Change pathfinding to start from the token and work its way to the target rather than the other way round. This means spaces near the token will be cached first, which is more useful than the spaces near the target being cached first, if the target changes significantly.

This also lays some groundwork for future improvements to the algorithm.

Note: waiting for #170 to be merged.

[manuelVo]

I agree that it would be a bit neater to start caching where the token is, instead of starting to cache where it wants to go. However, I feel like this change is way too complicated for a result that's simply "a bit neater". I think we would be able to achieve a similar effect with much less code by just switching around the order of the parameters to findPath so it actually searches from start to finish, then building a list of waypoints from finish to start and then just reversing that list (or iterating it backwards).

What are the future improvements you're planning to build upon this change? Maybe those would sum up to be significant enough to justify this change?

[JDCalvert]

I may have made this a little over-complicated, I agree, but what I was trying to achieve was:

• Path from the token to the target (reasons below)
• Return something you can iterate through from the token to the target (to make the actual path)
• Make that thing repeatedly iterable (for debug drawing, and then making the actual path).

This is mostly in preparation for the background caching changes, but may have some impact even without those changes. I'll describe what this gives us with background caching.

With the current way of pathing and caching from the target back to the token, if we get partway through a path and then stop because it's taken too long, we've cached some things near the target location but probably nothing near the token. If we then change our target to a new location (maybe even just the other side of wall) then we have no cache for that location and most of what we have already cached might be useless to the current path.

If we start caching from the token's position then nomatter where we then want to path to we've already got something useful cached we can use.

[manuelVo]

I think the three goals you've identified are all easily achievable with the simpler algorithm I proposed above (since the result is a list of waypoints, that can be iterated as often as desired).

I fully agree that starting caching from the token's position is desirable if it's achievable in a somewhat simple manner. However, I don't think it's extremely important. While it's true, that moving a token through the wall may make previously cached grid cells useless for that specific pathfinding attempt, that only applies to the first few pathfinding attempts on a given map. The cache will quickly reach a state where most nodes are initialized in the cache. At that point the direction of the pathfinding shouldn't make any meaningful difference.

[JDCalvert]

It's worth noting that the cache is invalidated every time a wall changes, for example opening or closing a door, so it might be slightly more significant. However I tend to agree, with the other improvements that have been/are being made, the cache will be fully-built pretty quickly, so this one probably has the lowest impact, especially compared to how much it changes.