Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Wed Dec 19, 2018 2:59 pm

All times are UTC




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

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.


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

Joined: Sun Sep 09, 2007 5:03 am
Posts: 4677
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.


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

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

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


Top
   
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 4 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.