Bus route finding suggestion

[paullb]

I tried to find a topic to attach this to, but did have any luck so will start a new one.


While working with AI development (though this is not limited to such), sometimes there are an awful lot of busses on the map. As a result sometimes traffic jams can form. I was thinking that it might be a good idea if the number of vehicules along the route was taken into account when choosing a route so that when there is an alternate route to avoid the traffic jam the vehicules would take it.

[Roujin]

Are you talking about NoAI? Then the topic would be better in the NoAI subforum under general.

[paullb]

Are you talking about NoAI? Then the topic would be better in the NoAI subforum under general.

No, I am not talking about the path finding alorigthm in NoAI, but rather the actual route finding alorigthm that road vehicules use when travelling along their route.

[Roujin]

Ah, now I get you.. sorry for misunderstanding you first

So its about adding a penalty value to YAPF (maybe also the older pathfinders) for vehicles on a tile.
The problem is that vehicles don't calculate their path all the time, but only one time when they're starting from their previous stop. And of course if something has changed and they can't take the route they've chosen, then they recalculate.

So in order to make this work well, one would have to make the roadvehs recalculate their path every now and then, which would of course result in more CPU usage. (don't know how much though) If not, they would not be very flexible with choosing their path.

Other problem that might come up with this idea could be finding out if the vehicle in question is going in the same direction as our vehicle, or another one.

[paullb]

Ah, now I get you.. sorry for misunderstanding you first

So its about adding a penalty value to YAPF (maybe also the older pathfinders) for vehicles on a tile.
The problem is that vehicles don't calculate their path all the time, but only one time when they're starting from their previous stop. And of course if something has changed and they can't take the route they've chosen, then they recalculate.

No worries.

But are you sure the above is true. It seems to me that if I add a new road somewhere, already running vehicules use it almost immediately.

[Roujin]

Hmm, I'm not perfectly sure since it's been a while since I've checked that... a while back I played around with YAPP, for my trafficlights patch, and added some debug stuff in the YAPP pathfinding function, and if I recall correctly, it was called rather rarely, only once when the order of the vehicle progressed to the next one, and then of course when it wasn't able to follow the chosen path because I changed something.

But I'll rather go and check again, before I leave you with wrong informations here....

edit:
Okay, turns out I was wrong - they actually calculate their route on every junction they come across.
So strike my remarks about that

[paullb]

Okay, turns out I was wrong - they actually calculate their route on every junction they come across.
So strike my remarks about that

Yeah, that's what I figured, at least that is what it looks like.

So ideally, it would be cool to look a little ahead to see if there is a traffic jam ahead and try and skip it. Like real busses do.

From what you were saying, sounds like a lot of work.

[Roujin]

Well, there is already a function to determine if there's a vehicle on a certain tile. Its EnsureNoVehiclesOnGround in vehicle.cpp.
So it would be quite easy to create a penalty for tiles that have a vehicle on them.

Problem is, you'll probably want a penalty only, if the vehicle is on a specific side of the road, and for this there is no function yet afaik.
Hmm.. actually I have an idea how it could be doable.. fiddling around with it a bit.

[Eddi]

YAPF for rail assigns values for red signals.

these cannot be cached, so it does this only for the first n signals [10, i believe]

you could do similar stuff for the first n road tiles

[Roujin]

I've put together a working version now.. I've not looked into caching until now, but it seems to run fine...
Here's the patch against r13850. It has a new patch setting (not in GUI) for the cost that will be added if at least one vehicle is on the tile.

Eddi: could you elaborate on what has to be done regarding caching?


edit: forgot to actually attach patch, here is it...

[Zutty]

paullb have you considered building traffic detection into your AI? Its surprising how much traffic can be alleviated just buy adding small connecting roads to give YAPF more options on where to send vehicles.