Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Tue Mar 19, 2019 10:07 pm

All times are UTC




Post new topic  This topic is locked, you cannot edit posts or make further replies.  [ 25 posts ]  Go to page 1 2 Next
Author Message
PostPosted: Thu Sep 29, 2005 8:22 pm 
Offline
Transport Empire Moderator
Transport Empire Moderator
User avatar

Joined: Fri Jan 10, 2003 12:21 pm
Posts: 2134
Location: Wroclaw, Poland / Katowice, Poland
Got ya didn't I.

But think about it:

Pathfinding is NP-complete - requires tons of speed to work.

Pathfinding fails without notice.

Pathfinding leads to lost vehicles.

Pathfinding causes a mess when you want to upgrade tracks.

Now imagine this:

Static path creation.

First create a service (name it something - Like "Coal Through Pluddypup Valley"). Then create a path(s)

Path be manual method (altho automation may be provided :) of showing the trains (or other vehicles, but I'll use trains as a base) on which tracks to run on. Then the path is saved and viola - trains will always use it.

This static path may have several cool attributes:
- when modifying a track with a path a pop-up will jump telling the player that Services X,y and z are using this track

- the path may be very complicated, including optional stops, optional depots and platform precise station stops (eg - stop at platform 1,3 or 7 at Planingbury Central). The path may also contain optional routes (eg - if Firfingway route is blocked use Derningbury route) and other nice things :)

- freeing the game from dynamic pathfinding will increase the speed (meaning - smoother game or more trains or lower requirements - make your pick)

- freeing the game from dynamic pathfinding will lower the potential lag

_________________
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.


Top
   
 
 Post subject:
PostPosted: Thu Sep 29, 2005 10:43 pm 
Offline
Route Supervisor
Route Supervisor
User avatar

Joined: Tue Mar 09, 2004 8:30 pm
Posts: 429
good point.

We can ofcourse provide a recommended path to the user when he starts a service. Maybe even include a lot more advanced path options and variables to give a default to the player (ie: fastest / shortest / not-too-crowded / flattest / ...)

This sounds cool :-) It works OK for removing tracks on a path, but what about adding track? If you add a shortcut somewhere, the trains won't automaticly use it. So we should provide a button like "find services that could benefit from this new track" and then let the players update the pathfinding.


Ofcourse, we can also have an option that does this automaticly by using some default values for those who don't want this micro-management or for multiplayer where everything needs to happen fast.

_________________
On holiday from 16/07 till 31/07


Top
   
 
 Post subject:
PostPosted: Thu Sep 29, 2005 10:49 pm 
Offline
Transport Empire Moderator
Transport Empire Moderator
User avatar

Joined: Fri Jan 10, 2003 12:21 pm
Posts: 2134
Location: Wroclaw, Poland / Katowice, Poland
Well - considering that you will set up a path once - and then simply add trains to it - I don't see a reason to provide 'live' pathfinding at all.

But true - when setting up a path - a wizard that will find possible connections might be beneficial :)

_________________
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.


Top
   
 
 Post subject:
PostPosted: Fri Sep 30, 2005 8:38 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Tue Dec 03, 2002 10:36 am
Posts: 13185
Location: The Netherlands
But what if you change the layout of your track? For aircraft this will never be a problem and for ships it will be a lesser problem I guess. RV's and trains however are fully affected.

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


Top
   
 
 Post subject:
PostPosted: Fri Sep 30, 2005 10:03 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Tue Mar 30, 2004 12:30 pm
Posts: 16663
Location: Almere, The Netherlands
I'm not really understanding your suggestion, but does this mean we have to build our 'line' and then have to select vehicles which are using this line, like in, for example, Traffic Giant?

_________________
Contributor to the The 2cc Set and Dutch Trainset. Inventor of the Metro concept. Retired Graphics Artist.
Image Image
Download TT | Latest TTDPatch | OpenTTD | OpenTTDCoop | BaNaNaS: OpenTTD content system | 2048² OTTD scenario of the Netherlands
GRF Codec | GRF Crawler | GRF Maker | Usefull graphics & tools sites | NML Documentation Wiki | NFO Documentation Wiki
All my graphics are licensed under GPL. "Always remember you're unique, just like everyone else."


Top
   
 
 Post subject:
PostPosted: Fri Sep 30, 2005 11:22 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Jan 10, 2004 8:19 pm
Posts: 2085
Location: London
It's too complicated. The great thing about pathfinding is that it can deal with complex situations, that you didn't forsee when you built the track.
It also makes multi-track systems much easier for the player and train to handle, rather than some complex user interface things for selecting all possible routes.


Top
   
 
 Post subject:
PostPosted: Fri Sep 30, 2005 1:58 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Wed Oct 02, 2002 6:57 pm
Posts: 5552
Location: Ithaca, New York
Purely as a player, I'd say that some sort of automatic pathfinding is necessary.

If I notice that one line is becoming overloaded and add a bypass line so that some trains will take it, I don't want to have to go to every single train and tell it that there's now a better route. That would become irritating very quickly.

Still, that doesn't mean you can't cache pathfinding information, which can be just as fast as static routes if you do it right. The difficult part will be deciding when to update the cache, but even if you clear all cached pathfinding whenever the player makes a new connection or removes some existing route, you'll have most of the benefit.

You can also have the pathfinding decisions called less frequently but for a longer route ahead. That way you'd still use less CPU, unlike for example TTD that does the pathfinding every single time a train is about to enter a junction.

But to go entirely without automatic pathfinding is not a good idea. If you want to be able to tell trains to go to platforms 1, 3 or 7, that'd still be possible with automatic pathfinding. But while creating static routes may be a nice feature in some cases, it should be an option, and not a requirement for every single route.

_________________
Josef Drexler

TTDPatch main | alpha/beta | nightly | manual | FAQ | tracker
No private messages please, you'll only get the answering machine there. Send email instead.


Top
   
 
 Post subject:
PostPosted: Fri Sep 30, 2005 9:57 pm 
Offline
Engineer
Engineer

Joined: Tue Jul 12, 2005 8:14 am
Posts: 32
Location: Melbourne suburbs, Victoria, Australia (GMT+10)
Patchman wrote:
Purely as a player, I'd say that some sort of automatic pathfinding is necessary.

If I notice that one line is becoming overloaded and add a bypass line so that some trains will take it, I don't want to have to go to every single train and tell it that there's now a better route. That would become irritating very quickly.

Still, that doesn't mean you can't cache pathfinding information, which can be just as fast as static routes if you do it right. The difficult part will be deciding when to update the cache, but even if you clear all cached pathfinding whenever the player makes a new connection or removes some existing route, you'll have most of the benefit.

You can also have the pathfinding decisions called less frequently but for a longer route ahead. That way you'd still use less CPU, unlike for example TTD that does the pathfinding every single time a train is about to enter a junction.

But to go entirely without automatic pathfinding is not a good idea. If you want to be able to tell trains to go to platforms 1, 3 or 7, that'd still be possible with automatic pathfinding. But while creating static routes may be a nice feature in some cases, it should be an option, and not a requirement for every single route.


That basically sums up what I think about it. Pathfinding, with static as an option.

William.


Top
   
 
 Post subject:
PostPosted: Sat Oct 01, 2005 6:08 am 
Offline
Transport Empire Moderator
Transport Empire Moderator
User avatar

Joined: Fri Jan 10, 2003 12:21 pm
Posts: 2134
Location: Wroclaw, Poland / Katowice, Poland
Hyro:

If you change the layout of your track you will be notified that schedules x,y,z and t need to be updated. (maybe with a an option do you want to update them automatically y/n)

Steve:

Can deal with complicated situations like TTD pathfinder? Or like, say, RT3 - where the pathfinder lags the game?

And its not complicated:

1. Set up a route
2. Assign x trains to it
3. Let it go

Dynamic pathfinding cannot deal with situations you didn't forsee when you created your algorithm - which is worse because you cannot change the algorithm within the game.

And you don't need a 'complex' interface. A simple one will suffice. Besides I want a choice of what routes to choose.

Patchman:

Quote:
Purely as a player, I'd say that some sort of automatic pathfinding is necessary.


When building a path an automation can be provided. EG. the player shows the stations like in TTD. Pathfinder looks for possible routes - player accepts,builds his own or edits the result. Path is then saved, trains assigned to it and viola - everything works.

Quote:
If I notice that one line is becoming overloaded and add a bypass line so that some trains will take it, I don't want to have to go to every single train and tell it that there's now a better route. That would become irritating very quickly.


That is why there are services:

A service contains a path (or optional paths) and trains. IF you change a path in the service then all trains assigned to the service will use the new updated path. This is actually better then in the case of dynamic pathfinding because when you create a new stretch track it is you who decides which traffic to move there.

Quote:
Still, that doesn't mean you can't cache pathfinding information, which can be just as fast as static routes if you do it right. The difficult part will be deciding when to update the cache, but even if you clear all cached pathfinding whenever the player makes a new connection or removes some existing route, you'll have most of the benefit.


The speed benefits are not all - the possibility to control the path of a vehicle is the cool part. Ferinstance I'd like to have a control over which tracks the trains go through PBS junctions.

[quote]You can also have the pathfinding decisions called less frequently but for a longer route ahead. That way you'd still use less CPU, unlike for example TTD that does the pathfinding every single time a train is about to enter a junction.[quote]

Pathfinding is rather On^2 - so calling it more then less often might actually be faster...

But with 8 players and 500 vehicles on each dynamic pathfinder will bog the game down.

_________________
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.


Top
   
 
 Post subject:
PostPosted: Sat Oct 01, 2005 10:54 am 
Offline
Retired Moderator
Retired Moderator
User avatar

Joined: Sun Jul 28, 2002 7:08 am
Posts: 20670
Location: Belgium
Just my two cents, how about adding a button 'preferred routes' in which you tell the game what are preferred routes if pathfinding comes in
It would speed up things and I think it wouldn't be that hard to program

The items/fields of a route could be for instance:

- Type of transport
- start point
- connecting point 1
- ....
- finish point

Now every train or truck could check this list of points whether a station in its schedule is somewhere on this list and use it
You could even put in a priority when certain points are very busy, a pointer simple that counts every train that used the route

You wouldn't need to change anything in the train's schedule because you don't add these points in there

Just my thoughts, don't read this because I know how people think of my programming knowledge

_________________
Well, back to work, lot's of it in the near future


Top
   
 
 Post subject:
PostPosted: Sat Oct 01, 2005 11:27 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Nov 30, 2002 5:10 pm
Posts: 6939
It's not only about programming, this is a very important aspect of the game for end-users.
For me, I would prefer having real pathfinding. How much CPU does that really take? A train for example doesn't have much choice, and an aircraft or ship just chooces the direct line, with for the ship only the need to detect corners.


Top
   
 
 Post subject:
PostPosted: Sat Oct 01, 2005 12:24 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Jan 10, 2004 8:19 pm
Posts: 2085
Location: London
If you could somehow segment the network, you could decrease the processing required. Basically, when the trains first run, they find the best route and remember it. And then, when you edit track, all the trains that use that segment are updated.

Perhaps have an extra view showing the routes on the track and letting the player drag them to a new spot (creating new waypoints automatically). But by default, it has to be automatic.


Top
   
 
 Post subject:
PostPosted: Sun Oct 02, 2005 10:49 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Tue Dec 03, 2002 10:36 am
Posts: 13185
Location: The Netherlands
uzurpator wrote:
Hyro:

If you change the layout of your track you will be notified that schedules x,y,z and t need to be updated. (maybe with a an option do you want to update them automatically y/n)

That is soooo player-unfriendly especially if I think of people like RobC who create massive mainlines on their maps. It's not changing schedule x,y,z then but more changing schedule a-z, 1-99 and so on.

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


Top
   
 
 Post subject:
PostPosted: Mon Oct 03, 2005 6:01 pm 
Offline
Transport Empire Developer
Transport Empire Developer
User avatar

Joined: Mon Feb 03, 2003 9:30 am
Posts: 699
Location: Back at the office
uzurpator wrote:
Pathfinding is NP-complete - requires tons of speed to work.

Pathfinding fails without notice.

Pathfinding leads to lost vehicles.

Pathfinding causes a mess when you want to upgrade tracks.

Huh?? :?: Why is that? Because TT/Loco have worthless algorithms?

You contradict yourself:
uzurpator wrote:
Pathfinding is rather On^2 - so calling it more then less often might actually be faster...

NP-complete means exponential time complexity. In fact, pathfinding can be done in less than O(n^2) if you have the right datastructures supporting your algorithm.

Transport Tycoon and Locomotion rely too heavily on heuristics to speed up the algorithms, but I think that's more due to bad programming from Chris Sawyer's side than problems with the algorithms. He probably brushed-up his "pathfinding" algorithm from TT for Locomotion.

I believe it's quite safe to let a well-implemented algorithm decide how a vehicle should move on a network. Even speed does not need to be an issue. The graph representing a network in the game should only have nodes for the branches and endpoints of a network. Not for each individual segment (1-tile piece of road/track/etc)

_________________
Feel free to contact me over Email! My current timezone: Europe/Amsterdam (GMT+1 or GMT+2)
Code:
+------------Oo.------+
| Transport Empire -> |
+---------------------+

[ General TE Discussion ] [ TE Development ] [ TE Coding ]
Under construction...


Top
   
 
 Post subject:
PostPosted: Mon Oct 03, 2005 6:18 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Wed Oct 02, 2002 6:57 pm
Posts: 5552
Location: Ithaca, New York
I think if you introduce micromanagement for train routes, it'll be more of a train simulation than a transport simulation. Which of the two do you want to make? Both are fine, as long as you don't force the player into either of the two paradigms. Make automatic pathfinding the default, but let players set specific routes if they want to.

_________________
Josef Drexler



TTDPatch main | alpha/beta | nightly | manual | FAQ | tracker

No private messages please, you'll only get the answering machine there. Send email instead.


Top
   
 
 Post subject:
PostPosted: Sat Oct 08, 2005 6:10 pm 
Offline
Transport Empire Moderator
Transport Empire Moderator
User avatar

Joined: Fri Jan 10, 2003 12:21 pm
Posts: 2134
Location: Wroclaw, Poland / Katowice, Poland
Hyro:

if Rob has 124 routes, then he probably also has 1200+ vehicles running around. I say we just saved Rob A LOT of work.

Hellfire:

Finding a path is easy. Keeping a dynamic pathfinder working for 1000+ vehicles is another. The first is trivial (Dijkstra or A*), the latter may bog the game down. Imagine trucks - not only there are hordes of them, but their enviroment is so dynamic and granular (ROADS!), that dynamic pathfinder will quickly bring the game to its knees.

Also note that we are aiming for a million tile map as a default, that will be a stress to the pathfinder, no matter what.

Even if you include some really aggressive path cacheing pathfinding will eat a substantial amount of processing power.

Besides - try to read what some people expect from the pathfinder - not only the possible path, bat also shortest, fastest and of course load balanced.

BTW - I have yet to see a game with a decent pathfinder.

_________________
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.


Top
   
 
 Post subject:
PostPosted: Sat Oct 08, 2005 6:44 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Wed Oct 02, 2002 6:57 pm
Posts: 5552
Location: Ithaca, New York
uzurpator wrote:
if Rob has 124 routes, then he probably also has 1200+ vehicles running around. I say we just saved Rob A LOT of work.


You saved him work by making him define the routes instead of letting the pathfinder figure them out?

Quote:
Finding a path is easy. Keeping a dynamic pathfinder working for 1000+ vehicles is another. The first is trivial (Dijkstra or A*), the latter may bog the game down. Imagine trucks - not only there are hordes of them, but their enviroment is so dynamic and granular (ROADS!), that dynamic pathfinder will quickly bring the game to its knees.


Have you benchmarked any such game? Have you proven that there is no theoretical possibility of more efficient pathfinding routines? No you haven't, you're making guesses because you seem to hate path finders.

Quote:
Also note that we are aiming for a million tile map as a default, that will be a stress to the pathfinder, no matter what.


And to everything else too. How can you be so sure that it'll be the pathfinder that will be the bottleneck, without it having been neither designed, written, nor benchmarked yet?

Quote:
Even if you include some really aggressive path cacheing pathfinding will eat a substantial amount of processing power.

Besides - try to read what some people expect from the pathfinder - not only the possible path, bat also shortest, fastest and of course load balanced.


And those, of course, couldn't be options you set in the path finding algorithm. Oh no, it all has to be set in stone.

Quote:
BTW - I have yet to see a game with a decent pathfinder.


TTD has a decent pathfinder. Decent, yes. Not perfect, but decent. But then, you don't need a perfect pathfinder, just one that's good enough, and even the one in TTD is good enough. I never have lost trains or trains taking the wrong way.

You're tilting at wind mills.

_________________
Josef Drexler



TTDPatch main | alpha/beta | nightly | manual | FAQ | tracker

No private messages please, you'll only get the answering machine there. Send email instead.


Top
   
 
 Post subject:
PostPosted: Sat Oct 08, 2005 7:16 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Jan 10, 2004 8:19 pm
Posts: 2085
Location: London
Working out a new, perfect, path at each junction is insane. But we wouldn't do that.
When it comes to road vehicles, things do become A LOT more complicated. But road junctions are much more flexible due to the dual-track nature. Would it not be possible to split the map into several road districts, a district would cover the town or an area etc. You then do a fast pathfind on the districts (you know beforehand which has roads leading to which) and then you do individual district pathfindings. Rather than looking at all the roads, you only look at the roads the vehicle might go through.

Heck, it won't be perfect, but that's what waypoints are for. I'd also suggest some lost vehicle checker, which can make a new route when a vehicle has got utterly lost. It can then use the auto-waypoint thing (that makes the static routes) to save the new, fixed route.


Top
   
 
 Post subject:
PostPosted: Sat Oct 08, 2005 7:28 pm 
Offline
Transport Empire Moderator
Transport Empire Moderator
User avatar

Joined: Fri Jan 10, 2003 12:21 pm
Posts: 2134
Location: Wroclaw, Poland / Katowice, Poland
Patchman wrote:
You saved him work by making him define the routes instead of letting the pathfinder figure them out?


I saved him from work when the pathfinder fails for some reason and he finds 600 of his 1200 vehicles looping around or getting bottlenecked.

Also - If you havent noticed. I am against _dynamic_ pathfinding, not pathfinding per se.

In my concept the player may:
Define the route just like in TTD and allow the pathfinder to find it.
Define the route by hand

Then the route is saved and kept static, until the player decides to update it for whatever reason - in which then he also may go for auto search for new path or edit/enter new path.

How many times I have to repeat it?

Quote:
Have you benchmarked any such game? Have you proven that there is no theoretical possibility of more efficient pathfinding routines?


Irrelevant. No load is better then any load.

Quote:
No you haven't, you're making guesses because you seem to hate path finders.


Ad homini. How come you know I havent researched pathfinding algorithms?

Quote:
And to everything else too. How can you be so sure that it'll be the pathfinder that will be the bottleneck, without it having been neither designed, written, nor benchmarked yet?


To save the time of writing an excuisite pathfinder only to find out that it bogs the game to crawl.

Time spent benchmarking and tailoring pathfinder may be spent on other things.

Quote:
And those, of course, couldn't be options you set in the path finding algorithm. Oh no, it all has to be set in stone.


I does not have to be. However - options -> time spent. Look above.

Quote:
TTD has a decent pathfinder. Decent, yes. Not perfect, but decent. But then, you don't need a perfect pathfinder, just one that's good enough, and even the one in TTD is good enough. I never have lost trains or trains taking the wrong way.


I think we should define 'decent' before trying to argue about it. I do get lost trains occasionally - and usually in a rather nasty traffic jam. Granted - waypoints help tremendusly, but once traffic increases and system grows it starts to get difficult to guess where the pathfinder will send the trains/vehicles.

_________________
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.


Top
   
 
 Post subject:
PostPosted: Mon Oct 10, 2005 3:31 pm 
Offline
Transport Empire Developer
Transport Empire Developer
User avatar

Joined: Mon Feb 03, 2003 9:30 am
Posts: 699
Location: Back at the office
uzurpator wrote:
Besides - try to read what some people expect from the pathfinder - not only the possible path, bat also shortest, fastest and of course load balanced.

True. I see your point. So calculating the path when a vehicle leaves a station and only changing it when the path itself changes, would that be a reasonable option?

_________________
Feel free to contact me over Email! My current timezone: Europe/Amsterdam (GMT+1 or GMT+2)

Code:
+------------Oo.------+
| Transport Empire -> |
+---------------------+


[ General TE Discussion ] [ TE Development ] [ TE Coding ]

Under construction...


Top
   
 
Display posts from previous:  Sort by  
Post new topic  This topic is locked, you cannot edit posts or make further replies.  [ 25 posts ]  Go to page 1 2 Next

All times are UTC


Who is online

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