Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Fri Jan 19, 2018 7:56 am

All times are UTC




Post new topic  Reply to topic  [ 5 posts ] 
Author Message
 Post subject: [DD] Pathfinding
PostPosted: Thu Nov 23, 2006 1:57 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Tue Dec 03, 2002 10:36 am
Posts: 13161
Location: The Netherlands
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

_________________
Image
Dutch Trainset for OpenTTD | Dutch Trainset Topic | Combined Roadset v0.10


Top
   
 Post subject:
PostPosted: Thu Nov 23, 2006 2:36 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Fri May 26, 2006 3:54 pm
Posts: 221
Location: Perth, Australia
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.


Top
   
 Post subject:
PostPosted: Mon Nov 27, 2006 5:22 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Wed Jan 11, 2006 9:36 pm
Posts: 219
Location: Czech Republic
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.


Top
   
 Post subject:
PostPosted: Wed Nov 29, 2006 1:08 pm 
Offline
Chief Executive
Chief Executive
User avatar

Joined: Mon Nov 15, 2004 7:46 pm
Posts: 643
Location: Berlin, Germany
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.


Top
   
 Post subject:
PostPosted: Wed Nov 29, 2006 1:28 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Wed Jan 11, 2006 9:36 pm
Posts: 219
Location: Czech Republic
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.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 5 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000-2018 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2018.
Hosted by Zernebok Hosting.