Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Wed Mar 21, 2018 7:08 am

All times are UTC

Post new topic  Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Sat Mar 03, 2018 9:46 am 

Joined: Sat Jan 30, 2016 4:56 pm
Posts: 1
I am led to believe that OpenTTD uses the A* pathfinder algorithm, and that this results in slowdown for ships due to the wide-open ocean having no prelaid tracks to follow.

Has jump point search been considered? It's significantly faster than A*, especially when dealing with open spaces, but results in a speedup in confined spaces as well since it can immediately jump between junctions rather than going one square at a time.

PostPosted: Sun Mar 04, 2018 6:45 am 
OpenTTD Developer
OpenTTD Developer

Joined: Sun Sep 09, 2007 5:03 am
Posts: 4572
Location: home
OpenTTD has several pathfinders, one of them is A*-ish.
It is however heavily modified, and afaik (but I didn't dig down to full understanding), it makes larger steps than a single tile.

JPS still does single tile steps unlike you think, much like the original A* algorithm. The main thing that changes is that it does less internal administration, which leads to the increase in speed. That is, tile access is not the problem for speed, administration of next points to explore is the cause.

Standard JPS does not fit, since it assumes that the center-point of movement is at the center-point of a tile, while in OpenTTD, that is at the center of each tile-edge. The result is that you always have only 6 directions of movement rather than 8. This means the algorithm should be adapted to that situation.

Has it been considered? It depends on what you mean with "consider".
- If you mean "think about it?" I at least have thought about, see above for my conclusions. Other people have pointed to the algorithm before as well, so yes, it has been considered in that meaning.
- If you mean "consider" as "has it been tried by making an implementation?", then I think nobody has done that yet.

Being a OpenTTD developer does not mean I know what I am doing.
Also, other OpenTTD developers may have different opinions.

PostPosted: Fri Mar 09, 2018 11:14 pm 
User avatar

Joined: Wed Dec 10, 2008 4:08 pm
Posts: 534
Location: tile 0x0000

Maybe you should have a look at this approach
from JazzyJaffa.

Chunnel , Distance between ships , Playing with Heightmaps , Signals tunnel , Waypoint air , Everest , Tunnel end

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

All times are UTC

Who is online

Users browsing this forum: No registered users and 3 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.