Pathfinding has glitches when travelling between levels...

[Alistair Broomhead]

Currently only tiles within the current level are considered in pathfinding - this keeps the list of collidables small, howevercan result in odd behaviour if the optimal path when recalculated at level exit is to double back on oneself and walk through the obstacles that are no longer collision tested.

An approach that may be fruitful for this is to create a bounding rectangle of the start and end points and add all the lists of collidables for the levels theat intersect/are contained within said rect.

An alternative approach would be to use the doors between levels as nodes, calculating the optimal path between doorways as the edge cost and use an A* search or similar to find the optimal set of doorways to pass through.

The pros and cons shall have to be considered carefully, as the 1st method shall only use the bounded levels, which may not be an optimal or even possible path - however if the world is large compared to the bounding rect then it shall be a lot cheaper computationally. If however I build my search tree itteratively stopping when the cost to not reach the target location exceeds the most optimal search path has been found, I may be able to trim some of the branches that are not relevent, in a method similar to that used to reduce my level-based search from O(4^x) to O(x^2).

[Alistair Broomhead (alistair-broomhead)]

The original behaviour has mostly been fixed - A tree of doors is built on world initialisation, and when moving from one level to another the path to each door in the initial level is calculated, as is the path from each door in the target level, then the set of door-traversals needed to get from the initial doors to the target doors is built. Each of these traversals has a cost - the number of squares that must be crossed to get from the start to the end. This is added to the cost of getting to the first door and from the last to give the cost of that path, and the path of lowest cost is chosen.

This does not however appear to be working correctly - there is doubtlessly some bug-fixing to do, however I think the basic algorithm feels right.