[DD] Pathfinding

[Hyronymus]

Pathfinding has been the subject of quite some topics (topic 1, topic 2, topic 3, topic 4) but never made it to the Design Document, strangely. There is really one question to ask:

Question 1: which pathfinding algorythm is recommended for Transport Empire?

Please be aware that route building is not the same as pathfinding. Discuss route building here

[aarona]

Question 1: It's going to have to be a modified A* algorithm...I would just say A* for now, but we may have to review it as the time to implementation comes near.

[KUDr]

If I can tell here something:

Question 1: If you really need the algorithm to be decided at this (design) phase, then I would recommend A* for trains and roadvehs (with some sort of caching for trains). And probably something else for ships.

But not at very first version. C++ allows flexible design meaning that you only need to specify pathfinder interface and that's all. Then you can begin with some simple PF, later write some better (i.e. optimized for one transport) or instead of real PF there can be simple lookup into route plan specified manually. The last one would also require some coding to provide GUI for manual route plan. If the interface will be known, anybody can write different PF with different algorithm.

In this phase you should mainly agree if PFs will be pluggable and if yes, then also:
- if they can be changed during gameplay
- if they will be global (per transport type) or player based (each player can configure his own set of PFs) or if the PF type will be property of vehicle(service) or property of one particular order item in the vehicle's order list.
- if there will be unified way how PF can store its private data belonging to vehicle
- and so on, but not what algorithm you will use.

[prissi]

A* works quite well for ships. All other pathfinders that find a complete path are way worse. A* tries to find the line of sight anyway, so there is not much optimisation possible there.

[KUDr]

yes, works well except that if it is tile based then on large maps with no straight path it becomes very slow. TTD solved it by mandatory buoys which i rather would name workaround than solution. Therefore simple tile based A* is not a solution.