Refactor pathfinding code for easier readability and maintainability

[Skyaero42]

Background

The pathfinding code is one of the most buggiest and non-performant code the game has. A non-exhaustive list of common issues are:

• It was the primary source for late game crashes (the infamous "Crash warnings" from @LegionnaireG
• It is the cause for partial or full freezing of units (multiple causes)
• It can account for more than 80% of CPU usage in the late game - particularly visible in 8 player FFA games and modded maps such as Zombies.
• AI units can get stuck on difficult pathfinding maps such as Twilight Flame
• Blobs of units may try taking the same path (traffic jamming)
• Specialist units not always take the most optimal route (bike, Burton)
• Time to turn is not taken into account when finding the fastest path (particularly an issue with Overlord tank)
• Non-optimal paths taken by dozers (multiple causes).

With over 12,000 lines of codes in aipathfind.cpp and aipathfind.h combined alone, as well as more than 100 includes of the aipathfind.h header by other files, the pathfinding code is all over the place. In addition, its design structure is poor.

All this makes solving bugs, improving performance and create better pathfinding.

Plan

This issue is created to keep track of multiple successive PR's for refactoring and improving the readability and maintainability of the code. The refactor is too large to perform in one PR. This issue is not tracking actual pathfinding bugs - seperate PR's should be opened for those.

This plan is work in progress.

• refactor(pathfinder): Split several individual classes off of AIPathfind.h into separate header files #3334
• Extract pathfinding class implementations into their own files
• Reformat files using clang-format to increase readibility
• Break circular dependency between PathfindCell and PathfindCellList/PathfindCellInfo
• Consolidate PathfindCell and PathfindCellInfo data by using separate list classes.
• Investigate dependancies between pathfinding classes and other classes and reduce where possible
• Replace retail_compat_crc with retail_compat_pathfinding

This is an initiative from @Skyaero42 and @Mauller