cooperative pathfinding

[Expresso]

Basically, a pathfinder searches for a route from A to B, various methods are availaboe in openttd, the most advanced being YAPF.

Now, this suggestion only concerns trains, as those stand to benefit most from this. It's a lot of work and I don't expect this to be implemented tomorrow, but it's worth mentioning.

Currently, when a vehicle needs to go to the next order it requests a path from the pathfinder and starts to follow it. The pathfinder finds the cheapest path, with nearly complete disregard of all the movements and performance capabilities of other vehicles. It just tries to find the cheapest route.

If the pathfinder is aware of where each vehicle is expected at what time at what speed, the pathfinder can better inform the vehicle looking for a path what path to take, but also informing the vehicle when to start moving and at what speed. Basically the pathfinder would schedule trains in addition to simply finding a path for them.

Something like this would be extremely helpful with busy junctions and backbones, as a feature like this will help reduce congestion due to the planned nature of the train movements.

Yes, I know. It would basically require a complete rewrite of the pathfinder and vehicle management code and increase memory consumption and (probably) processing power requirements.

By the way: would it be possible to cache pathfinder results between 2 possible destinations? If vehicles happen to (partially) have the same orders, there's no need search for a route over and over again, just checking whether the route is still valid should be enough. This spares valueble cpu cycles on the busier maps.

[planetmaker]

By the way: would it be possible to cache pathfinder results between 2 possible destinations? If vehicles happen to (partially) have the same orders, there's no need search for a route over and over again, just checking whether the route is still valid should be enough. This spares valueble cpu cycles on the busier maps.

With the result that the new, big shiny new track enhancement where you added a 2nd line to a busy route will never be used by trains oder than this new track. The same goes for the shortcut which reduces the needed travel distance from 500 tiles to 50...

[Eddi]

caching and load balancing are contradictory design goals.

with caching, you assign several vehicles the same route
with load balancing, you assign several vehicles different routes.

[Alberth]

Currently, when a vehicle needs to go to the next order it requests a path from the pathfinder and starts to follow it. The pathfinder finds the cheapest path, with nearly complete disregard of all the movements and performance capabilities of other vehicles. It just tries to find the cheapest route.

But it does take position and plans of other vehicles into account. When you go from one track to two, trains will nicely balance between both alternatives. Trains do not collide in blocks with path signals.

If the pathfinder is aware of where each vehicle is expected at what time at what speed, the pathfinder can better inform the vehicle looking for a path what path to take, but also informing the vehicle when to start moving and at what speed. Basically the pathfinder would schedule trains in addition to simply finding a path for them.

Now think one step further, what would be needed to realize it. Say you need to make a decision 5 game-days from now, how would you do it?
I think, you need a picture of how the game world looks in 5 days from now. In other words, you need to simulate the whole world along with your planning of each train. So to plan a 1000 trains, you need to run the game world 1000 times just to make a plan.

Also, what happens when the 30th train gets stuck, say 15 days from now? Obviously, you have made an error somewhere in the 29 previous plans. How do you find it?


Even if you could do it in some way, I don't think it would be good.
You'd see trains take an illogical decision, because some train ahead of them will do some weird, for example, break down.

increase memory consumption and (probably) processing power requirements.

Only slightly beyond the most powerful computer you can create, I think. I hope your block of houses is big enough. How close do you live to the nearest power plant?

[Expresso]

As for the processing power, it should not need to go astronomical. You can always provide an calculated value when a vehicle is expected at which point of interest. When it's not there in a given timeframe, there's something wrong.

In addition to that you could cache the computed values at those points of interest. If two values happen to overlap, some measures need to be taken in order to elimenate the overlap (make the one least vulneravle to congestion go somewhat slower, for example).

Problem is: that this would increase memory consumption quite a bit in addition to processing power... but I'm not convinced a supercomputer is needed for a feature like this.

[syntax_error]

Basically the pathfinder would schedule trains in addition to simply finding a path for them.

I think I would hate this feature. If the computer does all the job, where is the fun? I remember I stopped playing at Railroad Tycoon when in the number 3 they put an option to automate the choices for cargo pickup types. Don't do that kind of thing to openttd please!

[Dimme]

Just throwing in something...

What if the pathfinder would know how often a block is occupied, say the past year or so. Today it can see ten blocks ahead, and only the current picture, not long time statistics.

Then there could be some function mapping saturation to pathfinder penalty.

To avoid oscillations (saturated routes get too high penalty --> they get no trains --> they get too many trains again...) one could use this information to create a PI controller.

That approach will make trains not only choose the (more or less) optimal route for itself, but also takes into account which route will make less trouble for other trains.

As a bonus, we get the sttatistics for each sign

regards
Dimme

[Eddi]

great, and where do you store all that data? keep in mind that the pathfinder is one of the most often called functions in the game, and is very sensitive to execution speed.

[Dimme]

great, and where do you store all that data? keep in mind that the pathfinder is one of the most often called functions in the game, and is very sensitive to execution speed.

Yes, I know it has flaws... but it is not easy to create a pathfinder that is optimal for the whole system. A friend of mine did some work on a similar traffic model in his masters thesis, where he showed that the model was chaotic. It's like predicting weather, it cannot be done for long times ahead without taking everything into account.

At the moment each signal stores its state somewhere, it would then need to store an integer there as well, to keep the statistics. A major increase in storage, but not necessarily impossible. It could perhaps be improved by merging all blocks on a line into one number. For the speed issue, the pathfinder would then need to consider the integer along with the state, in some function that will need to be worked on to ensure speed. Again, it will impact the execution speed, but only as a percentage compared to today (not increasing a lot with complexity or something, the pathfinder already looks ten signs ahead.)

Signal states also need to be updated, but that should not be as demanding.

edit: use some sort of running average to not store more than one number per sign, not then entire history.

[Dimme]

Simple improvement:

- use 3 bit more storage per sign. Stores value I between 0 and 7.

- every month, check all signs, if they are red, increase I by one, if green, decrease by one.

- when pathfinder looks ten signs ahead, also check I.

- tune sampling interval and pathfinder weight.