Patch: New passenger destinations

[Rubidium]

[off-topic]

And please Dev's, don't let this one die like the last patch!

In what way did we let the other patch die? We, as devs, game comments on the patch about all kinds of things and I got the feeling they did not listen. What am I supposed to do in that case?
"Your patch is buggy and not according to coding style, but because people like it and you do not care about the bugginess and code style we have to add it to trunk?" I really think such patches must not be added to trunk. As far as I am aware all the Integrated Nightlies have had lots of trouble with multiplayer stability due to just adding patches without proper reviews and such. And because people do not seem to care about multiplayer compatability of patches in INs, they will proclaim that they patch is tested very well, when they were desyncing all the time due to that patch.

Furthermore we are not "not fixing" stuff just to keep a patch compatible with trunk. That way trunk will never get any structural fixes, such as:
- unlimited widgets
- proper fifo loading
- proper transfer accounting
Or any of the major changes that were needed to reduce code duplications using C++ techniques, or fixing the configure/build system.
[/off-topic]

I personally think that both passengers and mail should use the same system. Furthermore I am certainly not against this patch, but one should be able to enable/disable the patch whenever he/she wants to.

I think that the "best" way to determine the "fastest" route is the following (using A*):
- each station the vehicle stops at enroute (in orders) add extra cost
- each transfer adds some extra cost
- the distance between hops divided by some constant per vehicle type adds extra cost, but... there is an initial cost: planes have a high initial cost, which makes travelling short distances by plane unlikely, but after a certain distances planes will be cheaper than a direct train.

So, a short distance means busses or trams. A long journey where the bus goes from A-B directly might take the train *if* the transfer to the train is "worth" it; a short hop with the train will not be taken, but if there are 100 tiles between the train/bus transfer stations it will take the train.


The destination of the passengers should be determined by the size of the town/city first, then some station within that town where stations in higher town "zones" get more passengers. Furthermore most people will stay within the city and do not go very far, for towns people will usually get to the cities.

[MagicBuzz]

The destination choice is quite "easy" to simulate.

What can we see IRL ?
- A lot of passengers are moving in the suburbs area of cities
- A lot of passengers are moving between big cities
- A few passengers are moving between far small cities

So the destination choice can be computed according distance and town size quite easily according reality with something like that :
chance = min(townsize / distancetotown, 100)


Another system is the Transport Giant (Jowood) method : each city is associated to 8 random cities, and announce how much passengers wants to go to each of these 8 cities. By this way, you can see if a route will be profitable or not before creating it. Another good think is that the passengers using one service won't overflow it if it's the only one : not everyone wants to move anywhere... Passengers have a destination, then they choose if they move or not according the transportation availability. People won't come to the station, then choose where they will go at this time.

But I far prefer the Trafic Giant (Jowoo too) method. It's far more memory consummer, but it's really realistic (Trafic Giant allows you to manage intra-city transports). Each house have destinations (according the number of people in the building).
Then you have to check where people wants to go when creating a station.

As OTTD unlikely Trafic Giant have dynamic cities, there is a formidable challenge : buldings are demolished and reconstructed in time, so you transportation network can fit the passengers need in the 1950th but not in the 2000th, because many house were rebuilt and people now prefer to go somewhere else.

As the Trafic G system is really hard to play (you have to cover a big amount of destination in order to fill a simple bus) it needs to be coupled with an advanced correspondance system : passengers must be able to take a bus, then a train, then a plane and a bus again in the same course, because on big maps it's simply impossible to have a station that deserve all the catchment area destinations.

It should need a total rework of the transportation system, and I don't have any idea of the memory consumption (should be huge)

[finesse]

I really like your patch, fantastic work.

My test game crashes however, Im not sure if it's me or not so I've got a save file here for you. I used BOTTD and am not using any other patches/grfs etc. It crashes every time the hovercraft gets to the dock.

Also an idea for industry destinations is to only allow goods to be transported from an industry when a subsidy has been offered for it and then only to the destination. I would really like to play a game set like this. Would make for more cut throat competition etc.

Narnfield Transport, 21st Jun 1983.sav

Crash savegame

(323.65 KiB) Downloaded 110 times

[Tekky]

Let's go : I build 50 trains on a very long line between the coal mines and the power plant, then all trains will gain millions dollars for each course. After less than 5 years I have billions in bank so I just have to start a new game coz it's anoying to continue building while there is no challenge anymore.

In this thread I have proposed a solution which would solve this problem of it being most profitable for the player to deliver all cargo to one single far-away destination. Please note that the first post in the linked thread is not mine, I am talking about my counter-proposal to the proposal of the person who started the thread. My proposal does not use specific destinations for cargo, because a power plant doesn't care which coal mine the coal originates form. Instead, my proposal encourages coal to be supplied among all industries about equally because oversupplied industries pay less than undersupplied ones. Actually, my proposal encourages about 70% of the goods to be delivered to closer industries and about 30% to be transported to further-away industries. This behavior seems the most realistic, I think.

For the mathematical details of my proposal, please refer to the above link to my forum thread.

But I far prefer the Trafic Giant (Jowoo too) method. It's far more memory consummer, but it's really realistic (Trafic Giant allows you to manage intra-city transports). Each house have destinations (according the number of people in the building).
Then you have to check where people wants to go when creating a station.

As OTTD unlikely Trafic Giant have dynamic cities, there is a formidable challenge : buldings are demolished and reconstructed in time, so you transportation network can fit the passengers need in the 1950th but not in the 2000th, because many house were rebuilt and people now prefer to go somewhere else.

As the Trafic G system is really hard to play (you have to cover a big amount of destination in order to fill a simple bus) it needs to be coupled with an advanced correspondance system : passengers must be able to take a bus, then a train, then a plane and a bus again in the same course, because on big maps it's simply impossible to have a station that deserve all the catchment area destinations.

It should need a total rework of the transportation system, and I don't have any idea of the memory consumption (should be huge)

I have also proposed something similar to this Traffic Giant system in this thread. In my proposal, all passenger trains are required to have train timetables. Using these timetables, OpenTTD can build a graph of all possible routes. With this graph, the passenger route pathfinder can find the best path for the passengers to take, using the A* algorithm and taking the planned travel and waiting times (timetables) into account. Of course, players will be punished for the delays caused by their trains not keeping to their timetable.

For example, the train pathfinder may find the following route to be best:

1. Walk to the nearest bus stop.
2. Take the bus to the local train station.
3. Take the next passenger train to the next larger city (which has better and faster train connections)
4. Take the next fast passenger express train (InterCity train) to a major city near the destination town.
5. Take the next passenger train from this city station to the destination town.
6. Take the bus from the station to the closest bus stop next to the destination tile.
7. Walk from the bus stop to the destination tile.

For further details, please refer to the above link to my forum thread.

As the Trafic G system is really hard to play (you have to cover a big amount of destination in order to fill a simple bus)

In my proposal, passengers will do whatever they need to in order to reach their destination, even if they must walk (or swim) the entire distance. So if you offer any transport service along the way which would help them, they will use it, even if you cannot offer a route to their final destination. That way, you will not have the problem you mentioned.

[MagicBuzz]

sadly, the problem with your proprosal is that any citizen in the map must compute a route to reach his destination.
because of this, map generation time will be very long, and the game should incredibely suffer of route recomputation each time a player update his network.
i can't even imagine the memory usage on a big map with hunded thousands of citizens :/

[PouncingAnt]

Thanks for putting so much time and effort into recreating this feature! I'm very glad to see it back!

also, well done in making bi-directional circular routes more workable. Very good to hear that one.

Anyway, I've not compiled the patch yet, but look forward to doing so tomorrow.

Keep up the good work. And if possible, please be aware of what the devs require of you to increase the chances of this reaching the trunk (Afterall, if that's what you want, it's pretty much your responsibility). A lot of people are probably hoping for that.

[MagicBuzz]

I can't compile the destination patch.

I get these compilation error with VS 2005 Express :

Code: Select all

Erreur	1	error C2668: 'sqrt' : ambiguous call to overloaded function	e:\ottd_src\src\destinations.cpp	24	
Erreur	2	error C2679: binary '=' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)	e:\ottd_src\src\destinations.cpp	554	
Erreur	3	error C2679: binary '==' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)	e:\ottd_src\src\destinations.cpp	563	
Erreur	4	error C2679: binary '=' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)	e:\ottd_src\src\destinations.cpp	563	

Any suggestion ?

[athanasios]

I am happy. So many posts here!

Rubidium:
New industries and passengers destinations are the cream of the game!
I agree with your approach about which vehicles the passengers will prefer according to distance-expences.

About goods destinations: Some argue that current condition is not realistic and goods should go to closer destinations. IMO it is realistic: Most goods are "MADE IN CHINA" fellows!!!

[prissi]

I think with this patch the vehicle dialogue box should be unified. Imho this part can be copied from the old code. Furthermore I always failed to see the use of seperate vehicle info boxes for different classes of vehicles. Especially the different order of buttons does not make sense.

[Tekky]

sadly, the problem with your proprosal is that any citizen in the map must compute a route to reach his destination.
because of this, map generation time will be very long, and the game should incredibely suffer of route recomputation each time a player update his network.

If the passenger route is only updated once a month, and these updates do not all take place at the end of the month but rather are spread over the whole month, it should not be much a performance issue, unless of course you are using a 2048*2048 size map

i can't even imagine the memory usage on a big map with hunded thousands of citizens :/

I don't think every single citizen's path should be simulated, it should be enough for every house tile in a city to calculate a few routes, for example one route for work in the center of town and one for visiting relatives in a different town. These routes of the house tile should be visible when you go over the house with a query tool, as you could do in SimCity 4: Rush Hour (not available in the non-expansion version of SimCity4).

[tydev417]

Thanks for the new patch! I was very much looking forward to the day the patch was released for newer builds!


I keep seeing all this talk about "high memory usage" and "OpenTTD" in the same sentence and it's very bewildering. In this day and age, a simple game like OpenTTD and the small amount of memory it actually uses should certainly not be an issue, and if it is, then I think it's time for a very, very long-needed upgrade.

[Kathius]

Okay, here is an updated version.

The patch settings color is fixed and it should now be possible to (de)activate the patch whenever you want. This means you can also activate it at the start screen without a crash. When the patch is activated during a game, all passengers get assigned a random station, all passengers inside vehicles get assigned INVALID_STATION, meaning that the the next station is treated as their destination.

It should also be possible to build with vc now (but I didn't test, sorry, I always build with cygwin).

The connection system has also been changed. The fastest route is now computed the following way:

• sum up all distances between stations and divide by (relative) vehicle speed - this prefers fast vehicles
• multiply the number of stations (and depots!) by (relative) vehicle speed - this prefers slow vehicles for higher number of stations

This way, for short routes slower vehicles are preferred over faster vehicles. This might need a lot of balancing, I just made up some numbers to test the general behavior. Of course, timetables would be more accurate, but as timetables are not forced to be built and the times are not guaranteed to be realistic, a lot of work would have to be done before they would be reliable.

Keep in mind that if you build a train route with a depot order involved and build the same route with a bus, for slow trains it might end up with the train route being considered longer than the bus route. I don't like trains with passengers entering depots anyway, so I just set my orders to first go to the station, then into the depot and then again to the station. This is a more realistic behavior and also makes the route a bit shorter (for fast trains it makes it a LOT shorter).

By the way, this rather complex way of computing the relative route length is only done for direct connections, i.e. where no transfers are involved. Transfers are built by looking at each directly connected station and just adding their connections (with or without transfers).

To ensure that passengers take the right vehicle, the index of the vehicle's order list is also stored. Every month stations check if the connections are still valid by checking if the order list is still existent and if their station id is still somewhere inside. Once a vehicle enters a station, all connections linked to its order list are dropped and rebuilt, ensuring that connection lengths are up to date.

As promised before, the savegame format has changed and is incompatible with the old format, so you will have to start a new game to test the new behavior.

I did only very basic testing (couldn't load my old game), so I can only hope it also works with large networks.

I didn't improve the destination choosing system yet. It should have changed a bit though, since connection lengths are now computed differently and are one of the factors for deciding the destination. Choosing a reasonable destination is most likely the next thing I will be working on.
I will also try to move the ConnectionList from the Station to the GoodsEntry, that should really be the right place as every cargo type has different connections. This change should not only generalize but also improve the readability code a lot.
Since I hate doing GUI things, copying the general vehicle GUI code from the old patch will be done later. The same applies to the seperate connections window. I think that could be done by copying most parts from the code that displays the window with the vehicles passing the station. But both will still be a lot of work, so it has to wait a bit.

Oh, and before I forget is, here is the update:

newdestinations_10823.diff

(52.5 KiB) Downloaded 164 times

Have fun,
Kathius

[DJ Nekkid]

are you sure this patch works? hehe... i got this bug when my first airplane (or actually first vehicle got to the station)

[Kathius]

Should have tested it a bit better... I'm on it, just wait an hour or so

[Kathius]

Okay, it's fixed (hopefully).
Turned out that planes don't like being asked for their first vehicle...

[PhilSophus]

First of all, great work Kathius. I did not test your patch, yet, but will certainly do so at the weekend.

I started thinking of how to refit passenger destinations at the beginning of the week as I also missed it a lot but the next day your patch arrived, to support my laziness

I just skimmed through your code and noticed that the destination selection (I do not mean route finding) is well isolated in a separate function. As there was a lot of discussion on this issue, I would suggest that anyone interested just provides his alternative algorithm of destination selection (ConnectionList::GetRandomStation() seems to be the right place) so than we can try out the alternatives. I think it is hardly possible to foresee the effect of different approaches in a complex system like a big OpenTTD network, so we should just test multiple options.

I found the system prissi's patch used (just taking the number of passengers generated last month as the weight for random destination selection) quite reasonable (a big source of passengers is also a big destination, people doing mostly round-trips) and working well. It felt right when playing with it

[MagicBuzz]

Okay, here is an updated version.

It should also be possible to build with vc now (but I didn't test, sorry, I always build with cygwin).

Have fun,
Kathius

You're right, it should

Code: Select all

Erreur	1	error C2086: 'uint32 Destinations::MapDistanceFactor' : redefinition	e:\ottd_src\src\destinations.cpp	653	
Erreur	2	error C2086: 'uint16 Destinations::MaxPassengerWeight' : redefinition	e:\ottd_src\src\destinations.cpp	654	
Erreur	3	error C2084: function 'uint32 Destinations::Distance(TileIndex,TileIndex)' already has a body	e:\ottd_src\src\destinations.cpp	657	
Erreur	4	error C2668: 'sqrt' : ambiguous call to overloaded function	e:\ottd_src\src\destinations.cpp	658	
Erreur	5	error C2374: 'Destinations::_Connection_pool' : redefinition; multiple initialization	e:\ottd_src\src\destinations.cpp	662	
Erreur	6	error C2084: function 'void Destinations::InitializeConnections(void)' already has a body	e:\ottd_src\src\destinations.cpp	665	
Erreur	7	error C2296: '/' : illegal, left operand has type 'uint32 (__fastcall *)(TileIndex,TileIndex)'	e:\ottd_src\src\destinations.cpp	668	
Erreur	8	error C3861: 'Distance': identifier not found	e:\ottd_src\src\destinations.cpp	668	
Erreur	9	error C2084: function 'Destinations::Connection::Connection(void)' already has a body	e:\ottd_src\src\destinations.cpp	673	
Erreur	10	error C2084: function 'Destinations::Connection::~Connection(void)' already has a body	e:\ottd_src\src\destinations.cpp	677	
Erreur	11	error C2084: function 'bool Destinations::Connection::IsValid(void)' already has a body	e:\ottd_src\src\destinations.cpp	683	
Erreur	12	error C2370: 'Destinations::_connection_desc' : redefinition; different storage class	e:\ottd_src\src\destinations.cpp	687	
Erreur	13	error C2084: function 'void Destinations::Save_CONN(void)' already has a body	e:\ottd_src\src\destinations.cpp	699	
Erreur	14	error C2264: 'Destinations::Connection::IsValid' : error in function definition or declaration; function not called	e:\ottd_src\src\destinations.cpp	702	
Erreur	15	error C2084: function 'void Destinations::Load_CONN(void)' already has a body	e:\ottd_src\src\destinations.cpp	709	
Erreur	16	error C2264: 'Destinations::Connection::Connection' : error in function definition or declaration; function not called	e:\ottd_src\src\destinations.cpp	713	
Erreur	17	error C2296: '/' : illegal, left operand has type 'uint32 (__fastcall *)(TileIndex,TileIndex)'	e:\ottd_src\src\destinations.cpp	716	
Erreur	18	error C3861: 'Distance': identifier not found	e:\ottd_src\src\destinations.cpp	716	
Erreur	19	error C2084: function 'void Destinations::FindAllConnections(void)' already has a body	e:\ottd_src\src\destinations.cpp	722	
Erreur	20	error C2084: function 'void Destinations::UnsetPassengersDestinations(void)' already has a body	e:\ottd_src\src\destinations.cpp	726	
Erreur	21	error C2084: function 'void Destinations::SetPassengersDestinations(void)' already has a body	e:\ottd_src\src\destinations.cpp	737	
Erreur	22	error C2084: function 'Destinations::ConnectionList::ConnectionList(void)' already has a body	e:\ottd_src\src\destinations.cpp	752	
Erreur	23	error C2084: function 'void Destinations::ConnectionList::CalculatePopularity(Destinations::Connection &)' already has a body	e:\ottd_src\src\destinations.cpp	758	
Erreur	24	error C2084: function 'void Destinations::ConnectionList::RecalculatePopularities(void)' already has a body	e:\ottd_src\src\destinations.cpp	766	
Erreur	25	error C2264: 'Destinations::ConnectionList::CalculatePopularity' : error in function definition or declaration; function not called	e:\ottd_src\src\destinations.cpp	770	
Erreur	26	error C2084: function 'void Destinations::ConnectionList::AdjustPassengerWeight(void)' already has a body	e:\ottd_src\src\destinations.cpp	775	
Erreur	27	error C2039: 'AgeConnections' : is not a member of 'Destinations::ConnectionList'	e:\ottd_src\src\destinations.cpp	785	
Erreur	28	error C2653: 'List' : is not a class or namespace name	e:\ottd_src\src\destinations.cpp	788	
Erreur	29	error C2065: 'const_iterator' : undeclared identifier	e:\ottd_src\src\destinations.cpp	788	
Erreur	30	error C2146: syntax error : missing ';' before identifier 'it'	e:\ottd_src\src\destinations.cpp	788	
Erreur	31	error C2065: 'it' : undeclared identifier	e:\ottd_src\src\destinations.cpp	788	
Erreur	32	error C2065: 'Connections' : undeclared identifier	e:\ottd_src\src\destinations.cpp	790	
Erreur	33	error C2228: left of '.begin' must have class/struct/union	e:\ottd_src\src\destinations.cpp	790	
Erreur	34	error C2228: left of '.end' must have class/struct/union	e:\ottd_src\src\destinations.cpp	791	
Erreur	35	fatal error C1903: unable to recover from previous error(s); stopping compilation	e:\ottd_src\src\destinations.cpp	791	
Erreur	36	error BK1506 : cannot open file '..\objs\Win32\Release\destinations.sbr': No such file or directory	BSCMAKE	

Anyone could help me figuring out why it can't compile on VC++ 2005 ?

[chrissicom]

@MagicBuzz, the errors you get there would be obvious in cygwin as well, I think the problem is another...

The patch .cpp file is only added to the sources file but not to the MSVC project. Simply add the .cpp file(s) of this patch in the MSVC project and all the errors should be gone At least that's how I solved issues like this in the past

[MagicBuzz]

The patch .cpp file is only added to the sources file but not to the MSVC project. Simply add the .cpp file(s) of this patch in the MSVC project and all the errors should be gone At least that's how I solved issues like this in the past

I already did it.
If I don't, I get a few hundreds errors about link problems

Worste of all, the errors sounds like I have 2 times the same file in the projet (take a look at all these "redefinition" errors )

I'll try to download again all the sources and apply the patch properly. But I think I did well the first time.


-- Edit : hmmmm wait... I think I found the problem !

[Kathius]

If I look at the line numbers, it looks like the file has the contents doubled. The file doesn't even have 650 lines.