Improve pathfinding performance for multi-tile characters

[Annoraaq]

No description provided.

[Annoraaq]

While working on this I realized that the JPS pathfinding algorithm might be broken for multi-tile characters in general and also for diagonal movements (8 direction movement) on maps that have unidirectional collision (tiles that don't block from all sides).

I will investigate and fix this if possible. Worst case will be that one has to use BFS or A* for pathfinding in these situations.

[JCtapuk]

While working on this I realized that the JPS pathfinding algorithm might be broken for multi-tile characters in general and also for diagonal movements (8 direction movement) on maps that have unidirectional collision (tiles that don't block from all sides).

I will investigate and fix this if possible. Worst case will be that one has to use BFS or A* for pathfinding in these situations.

Ok.

[Annoraaq]

I could increase the pathfinding for multi tile characters. The exact speedup depends on many factors, such as the actual tileWidth and tileHeight of the multi-tile chars. For characters with tile sizes like 2 or 3, don't expect orders of magnitudes faster pathfinding.

With the current algorithms, pathfinding for multi-tile characters is always more expensive than for single-tile characters. That is because more positions have to be checked to see if a neighboring position is blocked. Moreover, you can't use the efficient JPS algorithm.

There probably exist better algorithms for multi-tile pathfinding that I am not aware of. So feel free to reopen this (or a feature request for a different algorithm).

Also if performance for multi-tile characters is really slow in comparison to single tile characters, there might be something else causing the problem. In this case also just reopen this bug or open a new one.