Pathfinding - do we really need it?

[uzurpator]

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

[PJayTycy]

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.

[uzurpator]

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

[Hyronymus]

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.

[Purno]

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?

[Steve]

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.

[Patchman]

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.

[fujitsu]

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.

[uzurpator]

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:

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.

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.

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.

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.

[spaceman-spiff]

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

[Arathorn]

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.

[Steve]

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.

[Hyronymus]

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.

[Hellfire]

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:

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)

[Patchman]

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]

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.

[Patchman]

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?

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.

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?

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.

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.

[Steve]

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.

[uzurpator]

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?

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.

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?

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.

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.

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.

[Hellfire]

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?