I spent some time working on the pathfinding for mech_rl. The game is turn-based, but the pathfinding code is threaded and caches path request results so that the display of potential movement paths as the player moves the mouse cursor around the map remains responsive.

Pathfinding performance was pretty good until entities larger than one tile were added. When the player was piloting a large mech, there was a noticeable delay in the UI drawing of potential movement paths as the cursor was moved. Threading kept the game responsive but the UI still had the appearance that it was lagging.

A combination of multiple clearance maps and an occupancy map were used to speed up pathfinding. Clearance maps are maintained for different cell sizes and determine which tiles are accessible by entities of the same size. Occupancy maps determine if a map tile is open, blocked by a map feature such as a wall, or occupied by multiple entities. The changes reduced the pathfinding time for larger entities significantly and improved the appearance of paths within the UI.