[DD] Pathfinding

Development discussion about Transport Empire. Other discussion to General forum please.

Moderator: Transport Empire Moderators

Post Reply
User avatar
Hyronymus
Tycoon
Tycoon
Posts: 13190
Joined: 03 Dec 2002 10:36
Location: The Netherlands
Contact:

[DD] Pathfinding

Post by Hyronymus » 23 Nov 2006 13:57

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

User avatar
aarona
Traffic Manager
Traffic Manager
Posts: 221
Joined: 26 May 2006 15:54
Location: Perth, Australia
Contact:

Post by aarona » 23 Nov 2006 14:36

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
OpenTTD Developer
OpenTTD Developer
Posts: 219
Joined: 11 Jan 2006 21:36
Location: Czech Republic

Post by KUDr » 27 Nov 2006 17:22

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.

User avatar
prissi
Chief Executive
Chief Executive
Posts: 645
Joined: 15 Nov 2004 19:46
Location: Berlin, Germany
Contact:

Post by prissi » 29 Nov 2006 13:08

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
OpenTTD Developer
OpenTTD Developer
Posts: 219
Joined: 11 Jan 2006 21:36
Location: Czech Republic

Post by KUDr » 29 Nov 2006 13:28

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.

Post Reply

Return to “Transport Empire Development”

Who is online

Users browsing this forum: No registered users and 8 guests