Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Wed Mar 20, 2019 6:50 pm

All times are UTC




Post new topic  Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Movement algorithm
PostPosted: Sat Dec 08, 2012 4:31 pm 
Offline
Engineer
Engineer

Joined: Sat Dec 08, 2012 4:18 pm
Posts: 6
Hi all;

I've played TT (and Locomotion) from the earliest days. I'm also the creator of the game Enemy Nations if any of you ever played that.

I have a question related to the TTD code. I am creating a simple vehicle movement game and I'm struggling with how to handle stop signs, traffic lights, not hitting other cars, and acceleration/deceleration. All the stuff you handle oh so well in TTD.

I took a look at the source but I think it would take me days to understand it well enough to pull out how it handles this. So I'm hoping someone here can give me some pointers about how to approach this problem. The items in this I see (please also let me know if I missed anything):
1. When to start decelerating due to issues ahead (stop, signal, slower vehicle).
2. Best way to track position (I'm presently doing a coordinate system for vehicles and another for map tiles with a 1:24 relationship).
3. Curve to take through turns.
4. Rate at which to accelerate/decelerate.
5. Is it best to hold all map squares for the path with the vehicle, or just ones where it has to make a choice?

I know this isn't a TTD dev question but I figure the developers here know this better than anyone. So I'm hoping one of you can point me in the best direction.

I'm not trying to write an awesome game, just one that works ok. But instant acceleration/deceleration (which eliminates most of these problems) looks so wrong. Adding that then I'm comfortable with how it works. It's not close to TTD, but it's ok.

thanks - dave


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sat Dec 08, 2012 9:28 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Wed Dec 20, 2006 1:31 pm
Posts: 978
Location: Aschaffenburg
DavidThi wrote:
1. When to start decelerating due to issues ahead (stop, signal, slower vehicle).
2. Best way to track position (I'm presently doing a coordinate system for vehicles and another for map tiles with a 1:24 relationship).
3. Curve to take through turns.
4. Rate at which to accelerate/decelerate.
5. Is it best to hold all map squares for the path with the vehicle, or just ones where it has to make a choice?


1. Vehicles only look a single tile ahead. They stop very quickly when encountering a signal or the end of the line. The only exception are stations: When a vehicle is on a station tile and it wants to stop at that station, it looks ahead the complete platform for the end. If the platform is very short, the train will again stop very quickly.

2. OpenTTD does the same. A tile is divided into 16 subunits.

3. Road vehicles just have table of positions (and directions) on a tile. The vehicle knows in what state it is, and at what state it enters the next tile. Deviating from the table is only possible at the border of tiles. There road vehicle can decide to turn around, or to pick one of the routes on the next tile.

4. Today vehicles have weight, power, a maximum tractive effort and a maximum speed. This controls acceleration according to usual (simplified) physics.

5. There are two different methods for this in OpenTTD.
- Generally vehicles don't store any path. They decide upon entering a tile which direction to take.
- If there is only one direction they continue along that.

Method 1:
- If there is a junction they ask the pathfinder what direction to take, which computes the complete path from the current point to the destination using A*, and a cost function.
- The input of the A* is the complete track network, but with stretches of track contracted, if there is no junction on the track. The static track cost is cached per stretch.
- This type of pathfinding works fine, if there are not many junctions. For ships where every water tile on an ocean is a junction, it works quite bad :p

Method 2:
- For trains there is a different method. The pathfinder is not asked at junctions, but at signals. It then stores the path up to the next signal on the map, i.e. at every junction it marks which choice to take.
- This generally works only if there is only one vehicle between signals.



So, to summarize:
- Vehicles only make choices between tiles.
- While traveling over a tile, the vehicle has time to decide what to do at the end of the tile, whether to stop, reverse or enter the next tile. This decision usually only makes use of the current and the next tile.

_________________
⢇⡸⢸⠢⡇⡇⢎⡁⢎⡱⢸⡱⢸⣭⠀⢸⢜⢸⢸⣀⢸⣀⢸⣭⢸⡱⠀⢰⠭⡆⣫⠰⣉⢸⢸⠀⢰⠭⡆⡯⡆⢹⠁⠀⢐⠰⡁


Last edited by frosch on Sun Dec 09, 2012 11:53 am, edited 1 time in total.

Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sat Dec 08, 2012 9:36 pm 
Offline
Engineer
Engineer

Joined: Sat Dec 08, 2012 4:18 pm
Posts: 6
Thank you very much!!!

Instant stopping make this all a lot easier. And I never noticed that in TTD so I guess that looks ok.

The angle for each sub location in the tile square is great - makes that part simple too.

Thank you and have a wonderful day.


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sun Dec 09, 2012 4:43 pm 
Offline
Engineer
Engineer

Joined: Sat Dec 08, 2012 4:18 pm
Posts: 6
frosch wrote:
1. Vehicles only look a single tile ahead. They stop very quickly when encountering a signal or the end of the line. The only exception are stations: When a vehicle is on a station tile and it wants to stop at that station, it looks ahead the complete platform for the end. If the platform is very short, the train will again stop very quickly.

2. OpenTTD does the same. A tile is divided into 16 subunits.

3. Road vehicles just have table of positions (and directions) on a tile. The vehicle knows in what state it is, and at what state it enters the next tile. Deviating from the table is only possible at the border of tiles. There road vehicle can decide to turn around, or to pick one of the routes on the next tile.


How do you track the vehicle sprite location? Do you use the center of the sprite bitmap or the front? The center works great for rendering and setting the angle while the front works best for determining when reaching the exit of a tile.

??? - thanks - dave


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sun Dec 09, 2012 4:50 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Sun Sep 09, 2007 5:03 am
Posts: 4694
Location: home
I don't know the answer to your question, but why would you need the center position for rendering?

A vehicle has 8 possible directions, and each direction has a separate sprite with its own offsets. Thus, you can give each sprite the right offset from the front (or any point of the vehicle, for that matter) such that it is rendered correctly.


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sun Dec 09, 2012 4:59 pm 
Offline
Engineer
Engineer

Joined: Sat Dec 08, 2012 4:18 pm
Posts: 6
Alberth wrote:
I don't know the answer to your question, but why would you need the center position for rendering?

A vehicle has 8 possible directions, and each direction has a separate sprite with its own offsets. Thus, you can give each sprite the right offset from the front (or any point of the vehicle, for that matter) such that it is rendered correctly.


I have 16 because I do 3 angles through a turn (22.5, 45, 67.5). But I'm rendering by doing the rotation as part of the draw so I only have to have 1 bitmap for each vehicle. And the center position also makes it trivial to know where to render the sprite on the board. If I have the front, then I need to figure the center (or upper left) based on that front position and the angle.

Each has its advantages. I was wondering which TTD uses, and why.

thanks - dave


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sun Dec 09, 2012 6:16 pm 
Offline
Tycoon
Tycoon

Joined: Wed Jan 17, 2007 12:14 am
Posts: 7300
Each sprite has an "anchor point", and each vehicle on the map has a "bounding box". the vehicle travels and turns along the center of the bounding box, but the "anchor point" of the sprite is placed at the back corner of the bounding box (the one that is not visible)

see also: Image

the calculation of the ancor points for the above template is a bit complicated... see here the view_normal, view_left_1 etc. functions. but it's difficult to explain in short. you can reuse the drawing code if you make your rendering match the boxes in the above picture.

_________________
You might not exactly be interested in Ferion, but if you are, have fun :)


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sun Dec 09, 2012 8:01 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Wed Dec 20, 2006 1:31 pm
Posts: 978
Location: Aschaffenburg
The movement point is the center of the vehicle. The movement code also knows the length of the vehicle.
This is not only needed to know when to stop, but also where the next vehicle behind it has to follow.

_________________
⢇⡸⢸⠢⡇⡇⢎⡁⢎⡱⢸⡱⢸⣭⠀⢸⢜⢸⢸⣀⢸⣀⢸⣭⢸⡱⠀⢰⠭⡆⣫⠰⣉⢸⢸⠀⢰⠭⡆⡯⡆⢹⠁⠀⢐⠰⡁


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sat Jan 05, 2013 6:59 pm 
Offline
Engineer
Engineer

Joined: Tue Apr 03, 2012 12:34 pm
Posts: 37
Location: Russia, Moscow
Hi all!

To not produce not very important topics post here.

About a month ago I founded this page:
http://qiao.github.com/PathFinding.js/visual/
there's comparison of various path finding algorithms. There in visual form showed how selected algorithm "think". I liked that.
But.
The most important is that exist algorithm MUCH better that A* on almost any labyrinth - "Jump Point Search". Where A* takes 1300-1800 iterations JPS takes... 300-500 iterations!!! It's amazing!
Dev's - maybe you may be interested in... It is possible that this can improve game performance with huge amount of vehicles. I think so...
Sources where I read about it:
Russian habrahabr
And links from there to source for habrahabr :)
first
second


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Sat Jan 05, 2013 11:23 pm 
Offline
Engineer
Engineer

Joined: Tue Feb 23, 2010 3:44 pm
Posts: 103
This looks easy, but it can't be as easy as it looks.
There is much more hidden calculation needed. How should the algorithm know where the next point to jump to is?
I did a test with some challenging obstacles and A-algorithm was faster, although it needs more iterations.


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Thu Jan 17, 2013 2:20 am 
Offline
Engineer
Engineer

Joined: Fri Oct 12, 2007 10:14 pm
Posts: 1
Location: Szczecin, Poland
Jump Point Search is improvement for A* which only works for uniform-cost grids, and it's purpose is to optimise cost of processing big, empty areas. So it could be possibly used in pathfinding for ships (however inefficiently), but for other vehicles it has no use at all - there is no grid, and costs are not uniform.


Top
   
 Post subject: Re: Movement algorithm
PostPosted: Mon Jan 28, 2013 1:15 am 
Offline
Engineer
Engineer

Joined: Sat Dec 08, 2012 4:18 pm
Posts: 6
If any of you were wondering what game I asked this about - it was for a Code War competition Windwardopolis that ran yesterday.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 12 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-2019 phpBB Limited

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