Pathfinding - do we really need it?
Moderator: Transport Empire Moderators
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
Pathfinding - do we really need it?
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
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.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
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.
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
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: 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
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.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
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.
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."
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."
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.
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.
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.
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.
-
- Engineer
- Posts: 32
- Joined: 12 Jul 2005 08:14
- Location: Melbourne suburbs, Victoria, Australia (GMT+10)
That basically sums up what I think about it. Pathfinding, with static as an option.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.
William.
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: 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:
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.
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:
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.Purely as a player, I'd say that some sort of automatic pathfinding is necessary.
That is why there are services: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.
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.
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.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.
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.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
- spaceman-spiff
- Retired Moderator
- Posts: 20634
- Joined: 28 Jul 2002 07:08
- Location: Belgium
- Contact:
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
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
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.
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.
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.
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.
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.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)
-
- Transport Empire Developer
- Posts: 699
- Joined: 03 Feb 2003 09:30
- Location: Back at the office
Huh?? Why is that? Because TT/Loco have worthless algorithms?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.
You contradict yourself:
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.uzurpator wrote:Pathfinding is rather On^2 - so calling it more then less often might actually be faster...
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)
[ General TE Discussion ] [ TE Development ] [ TE Coding ]
Under construction...
Code: Select all
+------------Oo.------+
| Transport Empire -> |
+---------------------+
Under construction...
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.
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: 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.
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.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
You saved him work by making him define the routes instead of letting the pathfinder figure them out?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.
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.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.
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?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 those, of course, couldn't be options you set in the path finding algorithm. Oh no, it all has to be set in stone.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.
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.BTW - I have yet to see a game with a decent pathfinder.
You're tilting at wind mills.
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.
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.
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
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.Patchman wrote:You saved him work by making him define the routes instead of letting the pathfinder figure them out?
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?
Irrelevant. No load is better then any load.Have you benchmarked any such game? Have you proven that there is no theoretical possibility of more efficient pathfinding routines?
Ad homini. How come you know I havent researched pathfinding algorithms?No you haven't, you're making guesses because you seem to hate path finders.
To save the time of writing an excuisite pathfinder only to find out that it bogs the game to crawl.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?
Time spent benchmarking and tailoring pathfinder may be spent on other things.
I does not have to be. However - options -> time spent. Look above.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 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.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.
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.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
-
- Transport Empire Developer
- Posts: 699
- Joined: 03 Feb 2003 09:30
- Location: Back at the office
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?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.
Feel free to contact me over Email! My current timezone: Europe/Amsterdam (GMT+1 or GMT+2)
[ General TE Discussion ] [ TE Development ] [ TE Coding ]
Under construction...
Code: Select all
+------------Oo.------+
| Transport Empire -> |
+---------------------+
Under construction...
Who is online
Users browsing this forum: No registered users and 1 guest