Refactor pathfinding.

[CLIDragon]

Summary

Infrastructure "Refactor the pathfinding code"

Purpose of change

Revive #70274. Though things have changed a bit since that PR,

Describe the solution

Toss out the old monster movement functions will_move_to, can_reach_to, know_danger_at, and replace them with solely can_move_to. Replace the old pathfinding settings with a new bitflag-based class (PathfindingSettings) with a decent amount more functionality. Additionally, the implementation of A* has been moved to a new file a_star.h, and has been sufficiently genericised to use any heuristic, distance function, and transition cost function that we want. It will also make potential future implementations of e.g. Jump Point Search much easier.

RealityBubblePathfindingCache is a direct replacement for the old flat_index, path_data_layer approach. A RBArray is simply an array sized for each element in each map square.

The new logic is generally a superset of the old logic. Things are handled the same way as before, but a few new things are handled more consistently (or at least, compared to Dec 18 2023)).

Code has been updated to include #74322. The current implementation ignores sharp objects when attempting to attack the player instead of adding a heavy cost. I believe that we do try to path around them if possible, but I would have to check .

#74301 and #74373 complicated merging a bit. I believe that we behave appropriately with regards to avoiding objects, but again, it needs to be verified.

There are a decent amount of unnecessary bounds checks e.g. in RealityBubblePathfindingCache::update. I'm not sure how to remove these. Overloading every function with _ib variants doesn't sound appealing.

• [ ] Check whether we attempt to path around dangerous objects when attacking the player. (i.e. mon get_path_avoid)
• [ ] Check if we avoid objects correctly
• [ ] Confirm that current pathing logic is a superset of old logic - i.e. we behave the same in all cases the old logic explicitly handled (except where rendered obsolete or where it is clearly incorrect).
• [ ] Remove horrific type overload to handle raw tripoints.
• [ ] Did I handle the terrain ids correctly?
• [ ] Check other TODOs in code.
• [ ] Check bash_range is implemented correctly (and how does a large max discourage bashing?)
• [ ] Check whether exponential backoff is implemented correctly in monmove.
• [ ] Convert Character::get_pathfinding_settings() to use the new PathfindingSettings.
• [ ] Add @prharvey to co-authors.

Describe alternatives you've considered

Just leave pathfinding code as is. This clearly doesn't work, as evidenced by the long string of PRs making slight changes and many comments expressing confusion at the system. The more I read, the happier I am with @prharvey's approach of just tossing out the old system for monster movement.

All terrain with a cost less than 2 is homogenised. This is the way we've always done things, but I'm not sure if it's appropriate. For example, terrain with a cost of 1 will path the same as terrain with a cost of 1.9. I wonder if we should have more granularity.

Making closest_points_first into an iterator. It turns out making iterators is a nightmare, and the overhead is not really worth the benefit. I might have a go if (when?) cata moves to C++20.

Testing

Not done yet. I at least plan to revive the tests from #70274.

Additional context

I will download astyle at some point soon.

Does anybody know of a diff tool with syntax highlighting that can ignore whitespace changes, brackets, etc? I basically entirely hand-merged this, and at least half of it should have been automatable.

Ping: @nornagon A lot of this touches on code you have directly changed, and I suspect that you probably have a better grasp of the old behaviour than I do.

[kevingranade]

I strongly recommend pushing the astar extraction to a seperate PR for quick merging and putting some thought into what other pieces of this can get a similar treatment. This PR has a very high conflict risk and we need to mitigate that.

[CLIDragon]

Unfortunately the A* algorithm is probably the hardest piece of code to reuse. The current algorithm is deeply integrated with the current cache and pathfinding settings, and the new algorithm, while decently agnostic, is not designed to work with the old system in any way. It would require a new distance metric, heuristic function, cost function, and neighbour function designed to work with the old system.

Instead, I should be able to separate out the new pathfinding settings (which will have the advantage of reducing a decent amount of noise) and the new cache system into separate pull requests.

[kevingranade]

Ok sure my focus is on splitting where possible, not too bothered about which pieces are best for doing that and you're in a better position to decide on that I think.

[CLIDragon]

Including a list of issues here for future reference. #73674. #74200. #74433 (for the grievances with the current travel system). #75009 (what exactly is the intended behaviour? How much punishment are monsters willing to accept to get to the player?). #72465. #52972. #78520

[CLIDragon]

#75401. #73269.

[Brambor]

#75401. #73269.

If ref is in a list, it expands:

• #75401. #73269.

It's much more readable with a phone, where you cannot hover over a link.

[CLIDragon]

If ref is in a list, it expands:

Good to know, though I'll probably leave them unexpanded as I don't want to clutter the comments too much.

[I-am-Erk]

What's the state of this PR? Has it been parted out into some of the linked PRs?

[CLIDragon]

Most of the utility functions have been ported and the main settings changes are in #77693. However, the bulk of the work, that is porting the old code to the generic A* implementation, remains in this PR.