The International Simutrans Forum

 

Author Topic: poor game flow in large maps  (Read 24427 times)

0 Members and 1 Guest are viewing this topic.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
poor game flow in large maps
« on: September 01, 2009, 10:50:53 AM »
I've got a game going on a 1024x1024 map  with several large towns and 8 fast trains, (4 Northbound 4 Southbound) Multiple trams running in all full growth towns (15000 or over). The game has become extremely laggy with no seeming cause. It can happen at the start of a month, two days in or halfway. All not needed processes are shut down and the graphics card is running at 'Turbo'.

The same game played in Experimental suffers no lagginess at all.

Maybe a look should be taken at Knightlys 'New Path Search' to see if it can be incorporated into Standard? Or maybe a new type of search path could be written to suit Standard?

Offline Isaac.Eiland-Hall us

  • Benevolent Dictator
  • Administrator
  • *
  • Posts: 3659
  • PanamaCityPC.com/support/
    • Facebook Profile
  • Languages: EN
Re: poor game flow in large maps
« Reply #1 on: September 01, 2009, 11:08:30 AM »
I suspect this is not a pak64-specific issue...

Meanwhile, have you compared the performance of the GDI executable vs. SDL?

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #2 on: September 01, 2009, 12:10:10 PM »
I suspect this is not a pak64-specific issue...

Meanwhile, have you compared the performance of the GDI executable vs. SDL?

Yes I have, It doesn't make any noticable difference. I haven't tried it with PAK128 as I only have PAK128 Britain which is a EXP game. I would try PAK128 but it takes weeks to get to the stage where I have PAK64.  But you could be right it may be a Simutrans-Standard problem.

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #3 on: September 01, 2009, 12:23:01 PM »
Can you post your savegame?

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #4 on: September 01, 2009, 07:09:11 PM »
Can you post your savegame?
Ok posted to http://simutrans-germany.com/files As Colin's Standard 2611.sve

Offline whoami

  • Devotees (Inactive)
  • *
  • Posts: 693
Re: poor game flow in large maps
« Reply #5 on: September 01, 2009, 08:34:28 PM »
(Moving to Development...)

Direct link to the savegame is http://simutrans-germany.com/files/upload/Colin%27s%20Standard%202611.sve; (EDIT:) it is loadable with plain pak64/r175.
« Last Edit: September 02, 2009, 07:48:59 PM by whoami »

knightly

  • Guest
Re: poor game flow in large maps
« Reply #6 on: September 02, 2009, 08:57:08 AM »
I have just tried Colin's save game.

There was a brief period of reduced responsiveness immediately after loading, but soon afterwards the game ran smoothly. When I tried to add a halt or adjust certain convoy's schedule, responsiveness was reduced again shortly afterwards for quite some time.

So, probably the reduced responsiveness is caused by the re-routing of all existing ware packets in one single world step after set_schedule_counter() is triggered by actions like halt construction/deletion or schedule changes.

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #7 on: September 02, 2009, 09:04:10 AM »
There was a brief period of reduced responsiveness immediately after loading, but soon afterwards the game ran smoothly. When I tried to add a halt or adjust certain convoy's schedule, responsiveness was reduced again shortly afterwards for quite some time.

So, probably the reduced responsiveness is caused by the re-routing of all existing ware packets in one single world step after set_schedule_counter() is triggered by actions like halt construction/deletion or schedule changes.
I've noticed the same, while trying Colin's game. So it's the rerouting of goods, which makes the game laggy...

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #8 on: September 02, 2009, 09:06:30 AM »
I have just tried Colin's save game.

There was a brief period of reduced responsiveness immediately after loading, but soon afterwards the game ran smoothly. When I tried to add a halt or adjust certain convoy's schedule, responsiveness was reduced again shortly afterwards for quite some time.


Reduced by quite a lot and when building a game, because one is continually adding halts or new schedules, it happens with repeated monotony. Every few game days actually, and not counting Auto Save which I've extended to every 3 months. Brave little Aussie fellow that I am. ;D ;D ;D

knightly

  • Guest
Re: poor game flow in large maps
« Reply #9 on: September 02, 2009, 09:13:59 AM »
I've noticed the same, while trying Colin's game. So it's the rerouting of goods, which makes the game laggy...

Gerw, is it possible to spread the load of re-routing ware packets across a few steps?

Reduced by quite a lot and when building a game, because one is continually adding halts or new schedules, it happens with repeated monotony. Every few game days actually, and not counting Auto Save which I've extended to every 3 months. Brave little Aussie fellow that I am. ;D ;D ;D

Colin, I understand how poor the responsiveness would be when you continue to add/remove halts or adjust schedules, because I have a similar PC specifications as yours ;) The game almost freezes during such global re-routing.


Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #10 on: September 02, 2009, 10:47:49 AM »
Gerw, is it possible to spread the load of re-routing ware packets across a few steps?
It's currently spread across 32 steps, see spieler_t::step. But maybe this number should depend on the time, the rerouting needs.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #11 on: September 02, 2009, 11:34:41 AM »
It's currently spread across 32 steps, see spieler_t::step. But maybe this number should depend on the time, the rerouting needs.

Thanks a lot for pointing out. :) It is quite incredible that after spreading re-routing across 32 steps, the game is still so unresponsive.

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #12 on: September 02, 2009, 01:08:44 PM »
Thanks a lot for pointing out. :) It is quite incredible that after spreading re-routing across 32 steps, the game is still so unresponsive.
But one can think of a worst case, where all the 'expensive' stations (with many waiting goods) are rerouted in one step...

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #13 on: September 02, 2009, 02:22:24 PM »
At least, there wasn't this problem in 99.17.1.
But 100.0 and after versions have this problem.

I heard many people saying 100.0 and after versions are too heavy.

Offline whoami

  • Devotees (Inactive)
  • *
  • Posts: 693
Re: poor game flow in large maps
« Reply #14 on: September 02, 2009, 07:40:40 PM »
My observations with Colin's savegame:
1) After loading of the savegame, and also after deployment of a new schedule or a new goods category for an existing schedule, ST becomes unresponsive for some seconds, with down to 2(!) fps and 100% cpu/core utilization. => ST seems to recalculate routing for all goods packets, not just for the goods categories served by the new schedule/convoy. This should be fixable by filtering before re-routing.
2) The previous observation especially applies to the change of routing in an isolated network, which seems to still lead to re-calculation of routing on the whole map. For isolated freight lines/networks, it may be useful to limit the refresh, e.g. by walking through the graph of stations *and* connected convoys, also filtering(!) by goods category (see above), marking the stations (also convoys due to their contents?) for refresh, and refreshing only the marked ones in the next loop (removing the marker here again).
1)+2) could be changed as described (or by other means), but a large, fully interconnected P+M network will still not benefit directly from such changes, only indirectly by optimized routing for certain other cases. Further spreading of re-routing calculation may help.
3) side-note: station coverage setting in the savegame is 3 (=> 49 tiles to check at P+M+G generation), which doesn't matter for re-routing, but the additional calculation effort for newly generated passengers+mail increases overall load.
« Last Edit: September 02, 2009, 10:16:29 PM by whoami »

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #15 on: September 03, 2009, 08:29:17 AM »
I have just read whoami's post and it seems to me that he has hit the nail on the head, as they say. If his suggestions can be implemented we should see a, not vast, but quite substantial in crease in game flow. (Incidentally my FPS went down to 1)

I could set the station coverage back to 2 but surely that would lead to an increase in Trams/Tram lines/Stations, creating even more route finding?

I have question re this particular game.

modnote by whoami: this part is now discussed in http://forum.simutrans.com/index.php?topic=3203.msg31352#msg31352:
 I have a passenger train (Not shown in the uploaded game)  Which travels between two stations only. It leaves one station with over 3000 pasengers and arrives at it's destination where they all disembark. It makes a loss of over 41 thousand (not in travel costs) when the passengers leave. It returns home with over 300 passengers and makes a profit of over 22k when the passengers leave. Have I got a setting in wrong in the config.tab or is this another bug?
« Last Edit: September 09, 2009, 10:51:19 AM by whoami »

Offline whoami

  • Devotees (Inactive)
  • *
  • Posts: 693
Re: poor game flow in large maps
« Reply #16 on: September 03, 2009, 11:22:18 AM »
As I wrote, my suggestions (if they matter at all) will not help (much) in the case of the passenger/mail network.

I could set the station coverage back to 2 but surely that would lead to an increase in Trams/Tram lines/Stations, creating even more route finding?
Directly, it will only increase routing calculation effort to a smaller extent, because of the larger number of stations ("hops"). But usually, you will have more different lines, more interconnection points and more transfers, and that makes a big difference.

Quote
It makes a loss of over 41 thousand (not in travel costs) when the passengers leave. It returns home with over 300 passengers and makes a profit of over 22k when the passengers leave. Have I got a setting in wrong in the config.tab or is this another bug?
(I assume that you don't refer to ST-experimental.)
pay_for_total_distance = 2 can lead to such a result.
Also, cost deduction at switching of the month might be involved.
« Last Edit: September 03, 2009, 11:26:25 AM by whoami »

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #17 on: September 03, 2009, 06:11:00 PM »
As I wrote, my suggestions (if they matter at all) will not help (much) in the case of the passenger/mail network.
Directly, it will only increase routing calculation effort to a smaller extent, because of the larger number of stations ("hops"). But usually, you will have more different lines, more interconnection points and more transfers, and that makes a big difference.

Do you mean that if I make multiple smaller Tram networks in my cities instead of one large network it would improve the flow of the game?

In Experimental the train made $721 profit on the outward journey with 3078 passengers as apposed to a $41k loss in Standard.

Additional info re-train behaviour.

Train travels A-B-A.
From A to B
journey 1. 3078 passengers, loss on arrival at B -$41k plus.
Journey 2. 3078 passengers, loss on arrival at B -$42k plus.
Journey 3. 3078 passengers, loss on arrival at B -$43k plus.
From B to A
journey 1. 325 Passengers, profit on arrival at A $22k plus.
Journey 2. 476 Passengers, profit on arrival at A $16k plus.
Journey 3. 124 passengers, profit on arrival at A $4k plus.

This doesn't make sense and it doesn't matter if I set the pay_for_total_distance to 0, 1, or 2. I realise that these settings may not affect a current SVE game. But it doesn't detract from the nonsensical profit and loss that is being generated.
« Last Edit: September 03, 2009, 08:42:12 PM by Colin »

Offline whoami

  • Devotees (Inactive)
  • *
  • Posts: 693
Re: poor game flow in large maps
« Reply #18 on: September 04, 2009, 07:39:38 PM »
Do you mean that if I make multiple smaller Tram networks in my cities instead of one large network it would improve the flow of the game?
More different lines means more schedules and transfers to check, so goods routing calculation will need more CPU time. From this aspect, a larger station coverage can support in reducing calculation effort.
The performance-wise effect of the station coverage setting depends, however, also on your network layout: The more tiles with houses are covered by several stations, the slower the game may become, because a generated passenger will check more than one station for suitable connections. But the developers can provide a better, substantiated analysis on this complex problem.

As your savegame doesn't contain an extremely large network, there may be a performance bug. Additionally, Z9999 may be right when he said that ST has become "too heavy".

Regarding the obscure revenue: It's unrelated to the program performance problems, so could you please open a new topic for that, also providing the savegame with the train? After that, I will move my own replies and any remaining related text there.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #19 on: September 05, 2009, 11:01:16 AM »
As your savegame doesn't contain an extremely large network, there may be a performance bug. Additionally, Z9999 may be right when he said that ST has become "too heavy".

Oh dear! I thought my SVE contained a fairly massive network. I must be really naive.

Regarding the obscure revenue: It's unrelated to the program performance problems, so could you please open a new topic for that, also providing the savegame with the train? After that, I will move my own replies and any remaining related text there.

Ok I'll upload my SVE with the latest additions and then open a new topic.

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #20 on: September 05, 2009, 11:38:36 AM »
The station coverage is not important.

The problem in your savegame are not the size of the map but the shear amount of waiting persons. You have several stations with more than 300000 people waiting. Updating such a monster will of course take some time.

I will look into the code to make it smoother, although no promises ...

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #21 on: September 06, 2009, 01:08:36 PM »
The station coverage is not important.

The problem in your savegame are not the size of the map but the shear amount of waiting persons. You have several stations with more than 300000 people waiting. Updating such a monster will of course take some time.

I will look into the code to make it smoother, although no promises ...

Thank You Prissi, I will look forward to any improvements you can make.

 In my next game (which may be awhile away due to this one being nowhere near completed) I will reduce the Passenger Level.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #22 on: September 07, 2009, 08:17:52 PM »
@ Prissi,

Does nightly 2640 contain your changes?

knightly

  • Guest
Re: poor game flow in large maps
« Reply #23 on: September 07, 2009, 11:36:01 PM »
Hi Colin :)

According to the source code update history, Prissi's changes for speeding up re-routing have already been incorporated. So, does it improve the responsiveness of your game?

Knightly

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #24 on: September 08, 2009, 04:07:40 AM »
Hi Colin :)

According to the source code update history, Prissi's changes for speeding up re-routing have already been incorporated. So, does it improve the responsiveness of your game?

Knightly


No, if anything it's getting worse. I'm sorry to say.

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #25 on: September 08, 2009, 05:52:54 AM »
No, if anything it's getting worse. I'm sorry to say.

Same here.
What we want is not to solve jumping convoi, but to solve unresponsive.
In recent simutrans, idle time is zero during long time even though convoi keep moving well.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #26 on: September 08, 2009, 06:35:05 AM »
Quote
void spieler_t::step()
{
   if(  halt_list.get_count()>0  ) {
 
      uint32 it = halt_iterator_start;
      slist_iterator_tpl <halthandle_t> iter( halt_list );
      while(  it>0  &&  iter.next()  ) {
         it--;
      }
      if(  it>0  ) {
         halt_iterator_start = 0;
      }
      else {
         uint32 units_handled = 0;
         while(  units_handled<8192  ) {
            if(  !iter.next()  ) {
               halt_iterator_start = 0;
               break;
            }
            halt_iterator_start ++;
            // iterator until 8192 passengers were handled
            units_handled += iter.get_current()->sum_all_waiting_goods();
            iter.get_current()->step();
         }
         INT_CHECK("simplay 156");
      }
   }
}

After looking at Prissi's changes, I think one of the reasons why the unresponsiveness problem has aggravated lies in the fact that >= 8192 ware (not ware packets) are re-routed in each step. For hub stations with large-sized ware packets (i.e. large menge), this will indeed help to prevent too much re-routing work in one step; but with non-hub halts, they usually have only small-sized ware packets (please see the attached image), so it needs to process many non-hub halts before the limit of 8192 can be reached.

IMHO, re-routing workload depends not on packet size (menge), but on packet count. More packets, more re-routing work, and vice versa. So, I would suggest to change from counting ware menge to counting the number of packets processed. Of course, the limit of 8192 also needs to be reduced accordingly.

« Last Edit: September 08, 2009, 06:50:23 AM by Knightly »

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #27 on: September 08, 2009, 08:47:12 PM »
The problem in Colin save are that there are several stations with 300000 passengers. Updating (rerouting) them takes nearly a second on my computer. During this no user interaction is possible, since such can be only done outside a step. The only other way would be that the stations themselves only handle 8192 each step, and indicate the result then. But this would require more complex logik, as changes of the passenger numbers must be also taken into account (i.e. something like a dirty flag for ware in stations.) I will look into this next week.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #28 on: September 08, 2009, 10:04:32 PM »
Edit : Post removed as the provided screenshot was wrong.
« Last Edit: September 09, 2009, 06:44:39 AM by Knightly »

Offline HeinBloed

  • *
  • Posts: 79
  • Languages: DE, EN, FR
Re: poor game flow in large maps
« Reply #29 on: September 09, 2009, 12:23:14 AM »
Knightly,

I really only stumbled accross this thread randomly, but looking at your screenshot, I strongly suspect that you fell victim to a display bug: the sum of passengers of the packages displayed is never 300k, not even close. I guess lots of destinations with letter >B are missing.

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #30 on: September 09, 2009, 06:31:25 AM »
Display works only with integer coordintes with 16bit; therefore I think the scrollbar just messed up. It is very easy to time those stations and they have like 4000-30000 packets and cn take up to 800ms or rerouting (on this computer here).

knightly

  • Guest
Re: poor game flow in large maps
« Reply #31 on: September 09, 2009, 06:42:19 AM »
Prissi,

Really sorry! I didn't realise that the list is incomplete. I loaded Colin's save game again and looked at the same station, and the list kept growing gradually when I tried to scroll down.

Nevertheless, I think it is more logical to count the number of packets instead of the sum of menge. Hope you can consider this suggestion when you look at the code later.

Knightly



Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4601
  • Languages: EN, DE, AT
Re: poor game flow in large maps
« Reply #32 on: September 09, 2009, 07:15:08 AM »
[offtopic]
this:

I strongly suspect that you fell victim to a display bug: the sum of passengers of the packages displayed is never 300k, not even close. I guess lots of destinations with letter >B are missing.

should be fixed in revision 2642.
[/offtopic]

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #33 on: September 18, 2009, 02:19:31 PM »
In the current implementation, if the goods of a station are rerouted, simutrans does a BFS for each packet. Since no heuristic is used, it is possible to do this in only one BFS, until the target for each packet is found.

I will try to implement this, if there is any free time next week...

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #34 on: September 19, 2009, 09:47:48 PM »
Please check again with curretn nightly. Should be much smoother (only lagging on my eeePC).

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #35 on: September 20, 2009, 12:53:31 AM »
Code: [Select]
bool haltestelle_t::step()
 (...)
else if(reroute_counter!=welt->get_schedule_counter()) {
// all new connection updated => recalc routes
if(  !reroute_goods()  ) {
and
Code: [Select]
bool haltestelle_t::reroute_goods()
{
// reroute only on demand
reroute_counter = welt->get_schedule_counter();
 (...)
// break after a certain number of reroute actions
if(  ++packets==255  ) {
return false;
}

Then, after breaking, reroute_goods() will not be called again, isn't it ?

« Last Edit: September 20, 2009, 01:12:32 AM by z9999 »

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #36 on: September 20, 2009, 07:13:07 AM »
Thank you for spotting this out. Indeed, the update needs to be moved to the end ...

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #37 on: September 20, 2009, 09:11:44 AM »
I tested with Colin's savegame.

For 1184 Halts.
rebuild_destinations() used 106 steps and reroute_goods() used 210 steps.
Sum of them is 316 steps.

[EDIT]
Another game: 3 players and public halts

player 1: 36 halts used 12 steps
public halt: 945 halts used 97 steps
player 2: 122 halts used 8 steps
player 3: 90halts used 24 steps
sums: 1193 halts

Numbers of halts per step is.
older version 1193/32steps=37.28 halts/step
this version 36/12+945/97+122/8+90/24=31.74 halts/step

Not so bad.
« Last Edit: September 20, 2009, 02:35:09 PM by z9999 »

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #38 on: September 20, 2009, 08:31:24 PM »
I didn't tested it, but I think, the changes contains a bug: last_ware_index isn't reseted in the loop in simhalt.cc:781.

However, it would be faster, if the BFS is done for all goods in one step instead of distributing it to several steps... And 316 steps are roughly 60 seconds...

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #39 on: September 20, 2009, 08:51:39 PM »
Doing in one step caused the lag that we are trying to get rid of ... and you are of course right about the last step.

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #40 on: September 21, 2009, 07:00:12 AM »
Doing in one step caused the lag that we are trying to get rid of
But if you do all searches within one BFS run, it will take only a little bit more time than the BFS run for the packet with the most transfers. So it won't be more laggy than the current nightly and the rerouting would be done much faster.

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #41 on: September 21, 2009, 09:07:51 AM »
Not sure, what "BSF" is; but rerouting all goods of one of the large stations took more than 100ms, with no user interaction (and thus no mouse movement) is possible. This is recieved as lagginess, which must be avoided. It severance of course depends much on the computer used.

Offline Spike

  • *
  • Posts: 1361
  • First Simutrans Developer and Graphics Artist
Re: poor game flow in large maps
« Reply #42 on: September 21, 2009, 09:30:04 AM »
Not sure, what "BSF"

I'd assume it means "breadth first search", and he wrote BFS which matches quite nicely on that.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #43 on: September 21, 2009, 10:41:16 AM »
Hi Guys,

I've just downloaded r2650 and I'm pleased to inform you that the game has improved at least 90%. There is still a bit of random jerkiness and it's reasonably difficult to drag a menu screen across the map, Apart from that. :award: :award: :award:

Thanks Gwer, and many thanks to Knightly who has tried his hardest to guide this addle brained gamer through my trials and tribulations.
It's a pity James doesn't listen to you a bit harder, mate. EXP might improve for the better. 

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #44 on: September 21, 2009, 11:01:27 AM »
but rerouting all goods of one of the large stations took more than 100ms
It tooks only 100ms if you reroute each good for itself. If you take one "big" run, where you search the graph for all possible ways, you can calculate all new routes at once.

Wiki says to the Dijkstra algorithm (which is a generalization BFS or A* without heuristic):
Quote
For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.

So its better, to calculate all connections at once.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #45 on: September 21, 2009, 11:05:40 AM »
@Colin

Thanks Gwer, and many thanks to Knightly who has tried his hardest to guide this addle brained gamer through my trials and tribulations.

The improvements in responsiveness are made by Prissi so far. Gerw's suggestion to combine search has not been incorporated yet. And you don't need to thank me -- I have done nothing at all to improve the game responsiveness in this case. :P

@Prissi

I have looked at the code and noticed that in spieler_t::step(), total menge (i.e. get_finance_history(0,HALT_WAITING)) is still used as a basis for limiting rerouting (though packet count is also used as a limit in haltestelle_t::reroute_goods()). IMHO, this will cause some steps to do more rerouting or less rerouting depending on the sizes of the packets.

I have created a patch to make spieler_t::step() dependent on packet count. It is based on r2650, relative to the trunk folder. You may notice that I have changed all last_index to last_catg_index -- this is only done to improve readability.
« Last Edit: September 21, 2009, 11:11:31 AM by Knightly »

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #46 on: September 21, 2009, 11:18:16 AM »
The proble is, that the initial connection calculation also takes some time. Since the routine does not know (yet) in which state it is, it has to have some guidance. THe current code is not finished, I plan to move it into haltestlle, which would iterate over all stops and then could also display the current stage of routine (for debug purposes).

knightly

  • Guest
Re: poor game flow in large maps
« Reply #47 on: September 21, 2009, 11:31:26 AM »
Prissi,

I suppose the above reply is in response to my patch?

If you take a look at my patch again, I have decremented units_remaining by 2 for the case of rebuilding destinations (please see haltestelle_t::step()). So, at most 64 / 2 = 32 halts will rebuild destinations in 1 single step. If you think 32 halts in 1 step is too much, you can increase that number from 2 to say, 3 or 4.

Knightly

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #48 on: September 21, 2009, 01:42:41 PM »
Tested again with same savegames.

Colin's savegame
 Player 1: 1184 halts
 Public: 3 halts

prissi's patch
 rebuild_destinations() used 112 steps and reroute_goods() used 212 steps.
 Sum of them is 324 steps.

Knightly's patch
 rebuild_destinations() used 37 steps and reroute_goods() used 945 steps.
 Sum of them is 982 steps.

Another game: 3 players and public halts
 player 1: 36 halts
 public: 945 halts
 player 2: 122 halts
 player 3: 90halts
 sums: 1193 halts

prissi's patch
 rebuild_destinations() used 94 steps and reroute_goods() used 246 steps.
 Sum of them is 340 steps.

Knightly's patch
 rebuild_destinations() used 30 steps and reroute_goods() used 551 steps.
 Sum of them is 581 steps.

I like the idea of Knightly's patch because it reduces number of halts/step on normal state.
« Last Edit: September 21, 2009, 01:49:14 PM by z9999 »

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #49 on: September 21, 2009, 02:22:20 PM »
Although 500 steps mean two minutes. In multiplayer, when a station is placed every two minutes rerouting may never be completed then ... ALso iterating over all lines takes a constant amount of time for most stations, thus the step routine needs to know the state of each station to decide what to do. Furthermore one player are finished before others; the proper way out is most likey a incorporation into haltestelle_t.

@Knightly
I overlooked you attachment. Will have a look soon.

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #50 on: September 21, 2009, 04:10:01 PM »
Although 500 steps mean two minutes.

You can change it by units_remaining.
I think that anyway it isn't possible to play such a big game in network mode even though without this problem.

The question is which counter is reasonable.

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #51 on: September 21, 2009, 04:32:59 PM »
I did some testing with this and yoshis game and I think I reasonable balanced it. Further tries are appreaciated.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #52 on: September 21, 2009, 06:13:47 PM »
@z9999 : Thank you very much for testing my patch :)

@Prissi : Thanks a lot for considering my patch and adopting it after adaptation.

As for Gerw's suggestion to combine multiple searches for each individual packet into a single search, I think he is right that such combined search can reduce search time significantly, by eliminating the need to rebuild search trees from scratch for each individual packet. However, I think search time cannot be reduced to such a short time as entailed by the single longest individual search, because each examined halt needs to be compared against a list of outstanding ware packets' destination halts to see if there is a match. With a large game like Colin's, some halts may have over 900 pax packets, so even a combined search have to take quite some time to finish, still causing unresponsiveness problem.

I think Prissi's current system has successfully distributed search time relatively evenly across a reasonable number of steps. Nevertheless, combined search can still be useful in this system : it is possible to determine the number of packets to perform path search as a batch for the current category, using Gerw's combined search routine. If this can successfully reduce search time by a large percentage, we can consider increasing units_remaining so as to shorten the lifecycle of a global reroute.

To be more concrete, here is a code block from haltestelle_t::reroute_goods() :
Quote
         if(waren[last_catg_index]  &&  waren[last_catg_index]->get_count()>0) {

            vector_tpl<ware_t> * warray = waren[last_catg_index];
            while(  last_ware_index<warray->get_count()  ) {

               if(  suche_route( (*warray)[last_ware_index], NULL, false )==NO_ROUTE  ) {
                  // remove invalid destinations
                  warray->remove_at(last_ware_index);
               }
               else {
                  last_ware_index++;
               }
               // break after a certain number of reroute actions
               if(  --units_remaining==0  ) {
                  return false;
               }
            }
            // now we are finisched with this array
            // => reset last_ware_index for the next categorie
         }
We can reroute as a batch a number of packets, determined by the smaller of (1) units_remaining and (2) (warray->get_count() - last_ware_index).
« Last Edit: September 21, 2009, 06:31:47 PM by Knightly »

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #53 on: September 21, 2009, 07:19:43 PM »
My apologies to Prissi. I did not realise that it was mainly your patch that fixed my game. Thank you mate.

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #54 on: September 21, 2009, 08:37:17 PM »
I did some testing with this and yoshis game and I think I reasonable balanced it.

yoshi's game is only 1 player and amount of waiting people are large.
Assume munti player and small amount of waiting people but poor PC.

I tested another game.

player 1: 9 halts used 1 step
public: 252 halts used 28 steps
player 3: 77 halts used 3 steps
player 4: 114 halts used 3 steps
player 5: 95 halts used 3 steps
player 6: 245 halts used 4 steps
player 7: 25 halts used 1 step
player 8: 104 halts used 2 steps
player 9: 31 halts used 1 step
sum of halts is 952 halts

Halts per steps
older version: 952/32steps=30 halts/step
prissi's patch: 9+252/28+77/3+114/3+95/3+245/4+25+104/2+31=284 halts/step

Every step reculc 284 halts in your patch.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #55 on: September 21, 2009, 09:21:21 PM »
If anyone is interested I've just uploaded my latest SVE using r2650 to the Simutrans File Sharing site. http://simutrans-germany.com/files/upload/Colin's%20Standard%202650.sve

Can anyone tell me why my uploads always have a Red 'File Delete' where the uploaders name usually goes?

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #56 on: September 22, 2009, 07:25:58 AM »
As for Gerw's suggestion to combine multiple searches for each individual packet into a single search, I think he is right that such combined search can reduce search time significantly, by eliminating the need to rebuild search trees from scratch for each individual packet. However, I think search time cannot be reduced to such a short time as entailed by the single longest individual search, because each examined halt needs to be compared against a list of outstanding ware packets' destination halts to see if there is a match. With a large game like Colin's, some halts may have over 900 pax packets, so even a combined search have to take quite some time to finish, still causing unresponsiveness problem.
If you sort the destinations of the 900 packets, you can use binary search and you will need at most log(900) = 10 comparisons each step (Maybe a hash table is even better?). Further, you can kick out the packets, for which the route is already found. Imho, it takes maybe the time of routing 5 packets (with long route).

knightly

  • Guest
Re: poor game flow in large maps
« Reply #57 on: September 22, 2009, 08:17:26 AM »
@ Colin :

Can anyone tell me why my uploads always have a Red 'File Delete' where the uploaders name usually goes?

Once you have logged on to the file sharing service, files that you have previously uploaded will show a Delete link so that you can remove them if you want. That doesn't mean that those files have been deleted.


@ Gerw :

If you sort the destinations of the 900 packets, you can use binary search and you will need at most log(900) = 10 comparisons each step (Maybe a hash table is even better?). Further, you can kick out the packets, for which the route is already found. Imho, it takes maybe the time of routing 5 packets (with long route).

I see. Look forward to your patch then :)

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #58 on: September 22, 2009, 08:43:33 AM »
I see. Look forward to your patch then :)
I don't feel like patching now. I've got not much time this (and the next 2) weeks and I will wait until prissi has finished his work. Otherwise, I have to rewrite my patch thousand times... Moving the rerouting to haltestelle_t is a good idea, but I don't like the idea of splitting, since Imho my suggestion is more elegant.

And it would also be possible to process not a fixed number of stops (or with the splitting: packets), but as many as 100 ms are gone, isn't it?

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #59 on: September 22, 2009, 09:58:28 AM »
Actually colins game is a little atypical, since usually never more than a few tens of packets are waiting in any stop for all the large savegames I ever got. Usually the RESCHEDULING takes more time, since one has to loop over a lot of convois and lines. Therefore building a search tree most likely will take longer than the actual rescheduling; also most stations have also in colins game very few people waiting.

Offline Spike

  • *
  • Posts: 1361
  • First Simutrans Developer and Graphics Artist
Re: poor game flow in large maps
« Reply #60 on: September 22, 2009, 10:02:09 AM »
Maybe, for stations above some limit, newly arriving packets should be discarded from the game.

Offline gerw

  • Coder/patcher
  • *
  • Posts: 618
Re: poor game flow in large maps
« Reply #61 on: September 22, 2009, 10:17:44 AM »
Usually the RESCHEDULING takes more time, since one has to loop over a lot of convois and lines.
Maybe the lineless convoys and lines should also be cached at the stations?

Therefore building a search tree most likely will take longer than the actual rescheduling; also most stations have also in colins game very few people waiting.
You don't need to build a search tree. You could take the code from suche_route, but in every step you test if the halt is the destination of any packet waiting there.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #62 on: September 22, 2009, 01:51:56 PM »
also most stations have also in colins game very few people waiting.

Thats probably because I try to provide enough transport for everyone. Mind you I just picked a station at random and it had 136231 passengers waiting. Isn't that quite a lot?

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #63 on: September 22, 2009, 07:05:45 PM »
Result of r2658. It seems to be good.
First 3 games are same savegame which were tested before, last 2 are new.

Colin's savegame (551 convois, 1187 halts)
 r2650 rebuild_destinations()=112, reroute_goods()=212, sum=324
 r2658 rebuild_destinations()=20, reroute_goods()=488, sum=508

2nd savegame (3 players, 6671 convois, 1193 halts)
 r2650 rebuild_destinations()=94, reroute_goods()=246, sum=340
 r2658 rebuild_destinations()=20, reroute_goods()=373, sum=393

3rd savegame (9 player, 870 convois, 952 halts)
 r2650 rebuild_destinations()=27, reroute_goods()=28, sum=55
 r2658 rebuild_destinations()=14, reroute_goods()=42, sum=56

regbombay1's London_C.sve (4297 convois, 8577 halts)
 r2658 rebuild_destinations()=135, reroute_goods()=117, sum=252

fuzion_051's The World 3.sve (2791 convois, 839 halts)
 r2658 rebuild_destinations()=70, reroute_goods()=368, sum=438

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #64 on: September 22, 2009, 08:16:28 PM »
If they are for pak64 or some other plain vanilla pak (no addons etc) I would be very interested in your testgames.

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #65 on: September 23, 2009, 05:01:27 AM »
Unfortunately, each savegame needs ton of addons, sorry.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #66 on: September 24, 2009, 10:38:15 AM »
r2664 SDL has done it for me. The game is running 99.99% more efficiently. I doubt if you'll get it any better, but it's amazing what you can do when you put your minds to it. Thanks a million guys, I'm enjoying the game again. :D :D :D. I don't use GDI so I can't comment on that.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #67 on: September 28, 2009, 10:11:49 AM »
Hi Prissi,

I have created another patch, based on r2682 and relative to the trunk folder, which speeds up route searching. The major changes are :

(1)
The check for destination halt is moved inside the loop which iterates over reachable halts of the current halt. It helps to find the destination halt earlier on and skip some unnecessary iterations and checking.

(2)
A per-ware-category counter for each halt is added, which records the number of lines/lineless convoys serving that halt for a particular ware category. This info is then used in suche_route(). Only origin halt, transfer halts and destination halt will be added to the HNode array.

I have performed some tests by rebuilding all halts' reachable destinations and rerouting all halts' goods in one step, recording the time used. Below are the results (the figures are in milliseconds) :


Before applying the patch :

**** Colin
Rebuilding destinations takes :  174
Rerouting goods takes :  43746
Complete refresh takes :  43920

**** Yoshi
Rebuilding destinations takes :  5063
Rerouting goods takes :  2039
Complete refresh takes :  7102

**** 1982
Rebuilding destinations takes :  40
Rerouting goods takes :  332
Complete refresh takes :  372

**** Wipi
Rebuilding destinations takes :  8
Rerouting goods takes :  67
Complete refresh takes :  75

**** Ferndale
Rebuilding destinations takes :  3
Rerouting goods takes :  20
Complete refresh takes :  23

       
After applying the patch :

**** Colin
Rebuilding destinations takes :  170
Rerouting goods takes :  4172
Complete refresh takes :  4342

**** Yoshi
Rebuilding destinations takes :  5114
Rerouting goods takes :  684
Complete refresh takes :  5798

**** 1982
Rebuilding destinations takes :  34
Rerouting goods takes :  145
Complete refresh takes :  179

**** Wipi
Rebuilding destinations takes :  7
Rerouting goods takes :  24
Complete refresh takes :  31  

**** Ferndale
Rebuilding destinations takes :  2
Rerouting goods takes :  3
Complete refresh takes :  5


From the above, it seems that rebuilding destinations only takes a little more time, but the reduction in rerouting time is quite significant. You may wonder why such reduction is especially larger in Colin's save game : it is because the proportion of transfer halts is lower in his game, and thus can benefit more from this patch.

Further testing is welcome.



Incidentally, I have removed the following cleanup code from suche_route() :
Quote
   /* Need to clean up?
    * Otherwise we just incease the mark => less time for cleanups
    */
   if(  current_mark == 0xFFFFFFFFu  ) {
      slist_iterator_tpl<halthandle_t > halt_iter (alle_haltestellen);
      while(  halt_iter.next()  ) {
         halt_iter.get_current()->marke = 0;
      }
      current_mark = 0;
   }
I think it is not necessary to reset the markers, as suche_route() only checks the inequality between the current marker and a halt's marker.

Besides, I have renamed some variables to better reflect their functions to enhance code readability.

Knightly
« Last Edit: September 28, 2009, 10:19:10 AM by Knightly »

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #68 on: September 28, 2009, 11:07:18 AM »
Well, apart from the servicable_counter: Could the purpose not be fulfilled by the warenziele array anyway? If this is empty (or rather it will has only one entry) then this halt is only connected to us.

I.e. only adding when reachable_halt->get_warenziele[ware_catg_index].get_count() > 1 ? Since hat gehalten just adds to warenziele anyway.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #69 on: September 28, 2009, 11:15:00 AM »
Prissi,

The presence of reachable halts in warenziele does not indicate whether a halt is a transfer halt or not. A halt may have some entries in warenziele, but they may come from a single line's schedule. A transfer halt needs to have at least 2 lines/lineless convoys serving it, for a certain ware category.

Knightly

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #70 on: September 28, 2009, 05:34:04 PM »
Interesting. I tested only reroute_goods().
Most interesting thing is London_C.sve with max_hops 8000.
It's really the same as max_hops 2000.

2nd savegame (3 players, 6671 convois, 1193 halts)
 standard 9799 ms
 Knightly 3885 ms

3rd savegame (9 player, 870 convois, 952 halts)
 standard 677 ms
 Knightly 221 ms

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 8000
 standard 37259 ms
 Knightly 4548 ms
max_hops 2000
 standard 5517 ms
 Knightly 4534 ms

fuzion_051's The World 3.sve (2791 convois, 839 halts)
 standard 7979 ms
 Knightly 4476 ms

knightly

  • Guest
Re: poor game flow in large maps
« Reply #71 on: September 28, 2009, 06:07:23 PM »
Z9999 :

Thank you very much for testing. :)

Most interesting thing is London_C.sve with max_hops 8000.
It's really the same as max_hops 2000.

As I have mentioned above, only origin halt, transfer halts and destination halt will be added to the HNode array. Thus, the number of HNodes used in a single search is largely reduced. Judging from your figures :

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 8000
 standard 37259 ms
 Knightly 4548 ms
max_hops 2000
 standard 5517 ms
 Knightly 4534 ms

I think all or most route searches managed to complete within the 2000 max_hops limit. Probably the proportion of transfer halts is rather low.

Knightly

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #72 on: September 28, 2009, 06:17:08 PM »
Additional information. The percentage of transported passengers.

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 2000
 standard 9%
 Knightly 83%

 :award:

knightly

  • Guest
Re: poor game flow in large maps
« Reply #73 on: September 28, 2009, 06:59:26 PM »
I think the size of the HNode array can be reduced (by half?) to compensate for the additional memory consumed by the service_counters.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #74 on: September 29, 2009, 09:46:31 AM »
Here is my latest STD SVE you can see the improvement that has been made also please notice thatthe game has gone from 470mil in the red to 10mil in the black.

Thanks to gwer/Prissi/Knightly and everyone else who contributed to making this game playable. If I didn't mention your name I'm sorry, but I do know who you are, Fred, er, Joe, No its Vil something or was it Z9***.

Anyway Thanks

http://simutrans-germany.com/files/upload/Colin's Standard 2682.sve

knightly

  • Guest
Re: poor game flow in large maps
« Reply #75 on: September 29, 2009, 03:05:37 PM »
I have attached an updated patch, also against r2682 and relative to the trunk folder. It includes 2 bugfixes and reduces the size of HNode array by half.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #76 on: October 02, 2009, 11:12:42 AM »
Knightly kindly sent me a copy of the GDI version of his patch and I'm here to tell you, the flow of my game improved beyond all expectations. The traffic (all modes) flows smoothly, there is no jerkiness of movement and no pauses at Auto Save.

As I pointed out to Knightly, GDI version has never worked with larger maps on my computer. I've always used SDL.  With his patch I can now use GDI.

Anyone who has downloaded my latest SVE should try it with this patch.

Thanks Knightly.

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #77 on: October 04, 2009, 07:09:56 PM »
Only the service counter is not included, since to me it seems like the warenziel-list does essentially the same.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #78 on: October 04, 2009, 07:42:32 PM »
Prissi,

Only the service counter is not included, since to me it seems like the warenziel-list does essentially the same.
Sorry, but I don't think so.

A halt X served by a single pax line which has a schedule containing, say, 8 halts, will end up having 7 halts in warenziele[0] for pax. That fulfils your criteria :
I.e. only adding when reachable_halt->get_warenziele[ware_catg_index].get_count() > 1 ? Since hat gehalten just adds to warenziele anyway.
but X is definitely *not* a transfer halt. A transfer halt is where ware packets can switch lines/convoys. If you think that I am wrong on this, please state the reasons.

The concept of transfer halt is the *gist* of my patch, and distorting it will largely diminish the usefulness of this patch. My centralised search in ST EXP also focuses on transfer halts, and it works fine for a long time without any problem, and has significantly reduced search time. I can't see why you have to insist on removing the service counters (which is actually the core of my patch), unless it really takes up a lot of space or processing time per se.

However, the addition of service counters only consumes a little bit more of memory. 1000 halts with 16 ware categories will only use an additional (16 categories  + 4 byte pointer) x 1000 halts = ~20KB. And the additional processing time for clearing and incrementing the service counters is relatively small, according to my test results. You may perform profiling to be accurate.

Knightly
« Last Edit: October 04, 2009, 07:48:44 PM by Knightly »

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #79 on: October 04, 2009, 09:44:19 PM »
But your patch, if I have two convois with the same schedule, then it will be too larger than 1 ... Or did I mistake it completely? But it would be still an improvement for any case without this.

I will look at it again.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #80 on: October 05, 2009, 05:16:51 AM »
But your patch, if I have two convois with the same schedule, then it will be too larger than 1 ... Or did I mistake it completely? But it would be still an improvement for any case without this.

You are right, but only if both convoys are lineless convoys. I think most players will group 2 lineless convoys with identical schedules into a single line for easier management, so this is not much of a problem in general.

You can solve this problem by modifying hat_gehalten() to return a boolean value which indicates whether any halt has been added to warenziele in this function call, and increment the service_counter[catg] in rebuild_destinations() only if that return value is true. But I doubt if the additional processing time justifies the gain in general.

BTW, do you mind performing profiling on my patch? I am interested to know how much faster suche_route() is, and how much slower rebuild_destinations() is, after the modifications. Many thanks in advance! :)

Edit 1 :

To make sure that you understand the difference between using service_counter[catg] and your suggested check :
reachable_halt->get_warenziele[ware_catg_index].get_count() > 1
I have attached a simple diagram (1st attachment) to illustrate it. Assuming only pax are involved. The letters are the names of the halts, and the numbers in bracket refer to the number of halts in warenziele[0]. The blue circle is served by Line P (A>B>C>D>E), and the green circle by Line Q (E>F>G>H>I). In this setup, only Halt E is a transfer halt.

With my patch, only Halt E will be identified as a transfer halt, since there are 2 lines (P & Q) serving it (i.e. service_counter[0] > 1). Searching route from A to H will only add origin halt A, transfer halt E and destination halt H to the HNode array.

But with your suggestion, all halts satisfy your criteria (i.e. warenziele[0] > 1), thus any intermediate non-transfer halts may also be added to HNode unnecessarily during the search. In this particular case, nodes are added for A, B, C, D, E, F, G, H during the search from A to H, wasting processing time -- the waste is not just on adding the nodes, but also on additional processing time involved in processing that node afterwards.

As you can see, my original code and your suggestion are very different, and your suggestion will largely reduce the effectiveness of my patch in reducing search time. Service_counter[catg] is the cornerstone of my patch, and it is necessary to make my patch work as intended. So, unless you can find a better way to determine transfer halt, please do not remove service_counter from my patch.

As a sidenote, during my development of ST EXP's centralised search, I realised that most games usually have only 50% or less of its halts as transfer halts (of course, there are exceptions, depending on player's strategies). That is the reason why focusing on transfer halts in suche_route() can significantly reduce search time.

Edit 2 :

Just in case you are not sure why we don't need to add non-transfer halts to the HNode array, please take a look at the 2nd attached image. In this diagram, there is only 1 single line serving halts A to E.

When searching for the route from A to E, A as the origin halt will first be added to the HNode array. Then, A's reachable halts (namely, B, C, D and E) are checked, one by one : with B, it is checked against the destination halt to see if we have found the destination, but no, this is not the destination; next, check if it is a transfer halt, but no, so no more processing is needed.

Rationale : if B is a non-transfer halt, there is only a single line/lineless convoy serving it; if current node A has B as its reachable halt, then A must also be served by the same line/lineless convoy, which in turn means that B's reachable halts are included in A's reachable halt's list (except A of course) and will be checked while processing A's reachable halts. Thus, there is no need to add B to HNode array, and no need to check B's reachable halts.
« Last Edit: October 05, 2009, 07:30:15 AM by Knightly »

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #81 on: October 05, 2009, 12:45:13 PM »
But your patch, if I have two convois with the same schedule, then it will be too larger than 1 ...

Even so, nothing worse than current bahavior.

In current simutrans, search priority of hub station is very low, and passengers can't reach their destination. That causes poor game flow, if player set high max_hops.

Additional information. The percentage of transported passengers.

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 2000
 standard 9%
 Knightly 83%

In current simutrans, I can't play regbombay1's London_C.sve withmax_hops 8000 because of Re: poor game flow. But max_hops 2000 is not fun, bevause only 9% of passengers can travel.

@Knightly
Can I use your patch for any fork version of simutrans, if this was denied ?

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #82 on: October 05, 2009, 02:20:19 PM »
It will be incorporated. I will probably just get this a more descriptive name (like number_of_non_unique_schedules or so ... )

knightly

  • Guest
Re: poor game flow in large maps
« Reply #83 on: October 05, 2009, 03:03:11 PM »
@ Z9999

Can I use your patch for any fork version of simutrans, if this was denied ?

Sure, no problem :D Please take the liberty to use it anywhere you like.


@ Prissi

It will be incorporated. I will probably just get this a more descriptive name (like number_of_non_unique_schedules or so ... )

You mean "service_counter"? Actually I am not sure how it should be named. "service_counter" is the best I can think of, meaning "serviced by how many lines/lineless convoys", but I admit that it is not ideal ... If you can think of a better yet concise description, please feel free to change it. ;)

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #84 on: October 05, 2009, 08:07:45 PM »
@Knightly
 Thank you.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #85 on: October 06, 2009, 05:51:39 PM »
Prissi,

A suggestion regarding connections_searched in rebuild_destinations() : instead of incrementing this variable by 1 per line/lineless convoy, we can increment it by fpl->get_count(). I propose this because players seem to vary a lot as to the size of their schedules : some prefer to have 7-8 halts per schedule, but others may prefer >30 halts. Longer schedules take longer to process, thus by using fpl->get_count(), you can better control the pace of rebuilding destinations. Of course, your formula for decrementing units_remaining in haltestelle_t::step() needs to be changed accordingly.

Knightly

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #86 on: October 06, 2009, 06:02:08 PM »
That is a valid suggestion. ALso it came to my mind, that it is very easy to check, whether a schedule added something to a connection or not, i.e. whether there are more than one identical schedule: The counter of warenziele is large after addition. WIll go to implement that and your patch tonight I think.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #87 on: October 06, 2009, 06:10:58 PM »
The counter of warenziele is large after addition.

Good idea. A simple check like this should do.

For games like Yoshi's with numerous lineless convoys, I agree with Gerw that the only way to reduce the time involved in rebuilding destinations is to register them at the halts like registering the lines. Do you think it is feasible?

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #88 on: October 06, 2009, 06:32:11 PM »
Yoshis game is from an 87 version several years ago where line management was more clumsy ... and it does not contains so much lineless convois. I think this could be deferred, but if you want to have a go at it. Certainly it may give advantage; but then convois need to handle changes from and to lines even more carefully.

EDIT:
I did profiling, but the differences are small; moreover, most improvement seems from less calls to halthandle_t::is_bound() and halthandle_t(). But as z9999 said, I think most people actually finding a route is more important.
« Last Edit: October 06, 2009, 06:53:03 PM by prissi »

knightly

  • Guest
Re: poor game flow in large maps
« Reply #89 on: October 06, 2009, 07:43:40 PM »
I did profiling, but the differences are small; moreover, most improvement seems from less calls to halthandle_t::is_bound() and halthandle_t(). But as z9999 said, I think most people actually finding a route is more important.

Do you mind posting the profiling results? Many thanks.

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #90 on: October 06, 2009, 07:49:58 PM »
Well, they are about 12MB, and the change is not seen easily. But here you go, everything up to 0.5% contribution, no calling stack:

Code: [Select]
Flat profile: (improved system)

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total          
 time   seconds   seconds    calls   s/call   s/call  name    
  9.29     19.95    19.95    16647     0.00     0.00  karte_t::sync_step(long, bool, bool)
  5.83     32.47    12.52  1529605     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*, bool)
  5.00     43.20    10.73  5044991     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  3.82     51.41     8.21  1869586     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, schedule_t const*, spieler_t const*)
  2.97     57.80     6.39 1460434544     0.00     0.00  vector_tpl<ware_t>::get_count() const
  2.15     62.42     4.62  2094715     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  2.12     66.97     4.55 940084741     0.00     0.00  vector_tpl<ware_t>::operator[](unsigned int)
  2.03     71.34     4.37 696776484     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  1.87     75.35     4.01 192406260     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.82     79.27     3.92 130461686     0.00     0.00  planquadrat_t::get_boden_in_hoehe(short) const
  1.75     83.02     3.75 549425413     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.69     86.66     3.64 32334462     0.00     0.00  convoi_t::sync_step(long)
  1.67     90.25     3.59 233174821     0.00     0.00  grund_t::get_hoehe() const
  1.67     93.83     3.58 574663478     0.00     0.00  quickstone_tpl<haltestelle_t>::operator==(quickstone_tpl<haltestelle_t> const&) const
  1.65     97.38     3.55 152483261     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.64    100.91     3.53 937711102     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  1.54    104.22     3.31 240439540     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.52    107.49     3.27 18540007     0.00     0.00  convoi_t::calc_acceleration(long)
  1.48    110.66     3.17 139927198     0.00     0.00  grund_t::get_weg(waytype_t) const
  1.43    113.73     3.07 176234657     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.33    116.59     2.86 487695305     0.00     0.00  koord::koord(short, short)
  1.20    119.17     2.58 249793805     0.00     0.00  operator==(koord const&, koord const&)
  1.20    121.75     2.58 62523573     0.00     0.00  vehikel_t::get_gesamtgewicht() const
  1.19    124.30     2.55 54759565     0.00     0.00  quickstone_tpl<simline_t>::is_bound() const
  1.09    126.64     2.34 359156267     0.00     0.00  koord3d::get_2d() const
  1.04    128.87     2.23 32300103     0.00     0.00  convoi_t::step()
  0.95    130.91     2.04 67751873     0.00     0.00  grund_t::get_vmove(koord) const
  0.94    132.93     2.02 82602392     0.00     0.00  ding_t::is_moving() const
  0.90    134.86     1.94 16125608     0.00     0.00  dingliste_t::remove(ding_t const*)
  0.83    136.65     1.79 648278617     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::operator[](unsigned int) const
  0.75    138.27     1.62 89449878     0.00     0.00  fussgaenger_t::sync_step(long)
  0.69    139.76     1.49 665227174     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::get_count() const
  0.60    141.04     1.28 28862148     0.00     0.00  stadtauto_t::sync_step(long)
  0.55    142.23     1.19 174167252     0.00     0.00  hashtable_iterator_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::next()
  0.54    143.40     1.17 240375956     0.00     0.00  karte_t::lookup(koord) const
  0.54    144.55     1.15 143737674     0.00     0.00  obj_besch_t::get_child(int) const
  0.53    145.69     1.14   133776     0.00     0.00  route_t::intern_calc_route(karte_t*, koord3d, koord3d, fahrer_t*, unsigned int, unsigned int)
  0.52    146.80     1.11 13741184     0.00     0.00  haltestelle_t::get_ware_summe(ware_besch_t const*) const


Code: [Select]
Flat profile: (previous system)

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total          
 time   seconds   seconds    calls   s/call   s/call  name    
  9.45     21.54    21.54  1483245     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*, bool)
  8.50     40.93    19.39    17067     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.95     52.22    11.29  5431731     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  4.43     62.31    10.10 1645188374     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  2.85     68.81     6.50 1898991967     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.03     73.44     4.63 1596670257     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::operator[](unsigned int) const
  1.89     77.77     4.32  2050348     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.89     82.06     4.30 963837657     0.00     0.00  vector_tpl<ware_t>::get_count() const
  1.89     86.36     4.30 132048612     0.00     0.00  planquadrat_t::get_boden_in_hoehe(short) const
  1.82     90.52     4.16  1817492     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, schedule_t const*, spieler_t const*)
  1.71     94.41     3.89 188892750     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.69     98.27     3.86 155337440     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.66    102.06     3.79 1666172006     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::get_count() const
  1.65    105.82     3.76 237458275     0.00     0.00  grund_t::get_hoehe() const
  1.55    109.36     3.54 32458683     0.00     0.00  convoi_t::sync_step(long)
  1.51    112.80     3.44 246075434     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.51    116.24     3.44 141813284     0.00     0.00  grund_t::get_weg(waytype_t) const
  1.50    119.65     3.41 528617071     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.48    123.02     3.37 172490871     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.46    126.36     3.34 18589421     0.00     0.00  convoi_t::calc_acceleration(long)
  1.32    129.37     3.01 496337298     0.00     0.00  koord::koord(short, short)
  1.16    132.01     2.65 32234028     0.00     0.00  convoi_t::step()
  1.13    134.58     2.57 54660352     0.00     0.00  quickstone_tpl<simline_t>::is_bound() const
  1.10    137.08     2.50 367527603     0.00     0.00  koord3d::get_2d() const
  1.07    139.52     2.44 68549744     0.00     0.00  grund_t::get_vmove(koord) const
  1.04    141.90     2.38 252639444     0.00     0.00  operator==(koord const&, koord const&)
  0.98    144.13     2.23 577424393     0.00     0.00  vector_tpl<ware_t>::operator[](unsigned int)
  0.97    146.35     2.22 62518948     0.00     0.00  vehikel_t::get_gesamtgewicht() const
  0.94    148.49     2.14 83061006     0.00     0.00  ding_t::is_moving() const
  0.78    150.27     1.78 291959379     0.00     0.00  quickstone_tpl<haltestelle_t>::operator==(quickstone_tpl<haltestelle_t> const&) const
  0.78    152.04     1.77 85600845     0.00     0.00  fussgaenger_t::sync_step(long)
  0.78    153.81     1.77 15981170     0.00     0.00  dingliste_t::remove(ding_t const*)
  0.70    155.40     1.59 69182787     0.00     0.00  haltestelle_t::get_warenziele(unsigned char) const
  0.62    156.81     1.41 28987517     0.00     0.00  stadtauto_t::sync_step(long)
  0.60    158.18     1.37 246011854     0.00     0.00  karte_t::lookup(koord) const

Indeed, suche_route is much faster, it is no longer the most time consuming subroutine any more. I think the next release will be a big step towards playing larger maps or better perfomance on netbooks.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #91 on: October 07, 2009, 11:31:03 AM »
I have written another patch to speed up suche_route() a bit when checking those already-processed halts. Although we now only check transfer halts, transfer halts also have reachable halts which have already been processed. Originally, halthandle boundness is checked before checking marke, meaning that 2 checks are required. But the boundness check is actually unnecessary for these already-processed halt entries.

This patch moves marke out of haltestelle_t, and consolidates them into a static array. In this way, we can check the marker first, and skip the boundness check if this halt has already been processed before.

For small games, the effect of this patch is not noticeable; but for large games like Colin's and Yoshi's, there is a noticeable reduction in search time. In general, this patch will have a greater effect on games with a higher proportion of transfer halts.

The static array consumes 262KB of memory, which is the amount of memory saved by reducing the size of the HNode array by half in the previous patch.

Here are some testing results :


Before applying the patch :

**** Colin - Finished ****
Rebuilding destinations takes :  112 ms
Rerouting goods takes :  7487 ms
Complete refresh takes :  7599 ms

**** Yoshi ****
Rebuilding destinations takes :  4963 ms
Rerouting goods takes :  616 ms
Complete refresh takes :  5579 ms

**** 1982 ****
Rebuilding destinations takes :  40 ms
Rerouting goods takes :  149 ms
Complete refresh takes :  189 ms

**** Wipi ****
Rebuilding destinations takes :  9 ms
Rerouting goods takes :  19 ms
Complete refresh takes :  28 ms

**** Ferndale ****
Rebuilding destinations takes :  2 ms
Rerouting goods takes :  5 ms
Complete refresh takes :  7 ms

       
After applying the patch :

**** Colin - Finished ****
Rebuilding destinations takes :  115 ms
Rerouting goods takes :  6855 ms
Complete refresh takes :  6970 ms

**** Yoshi ****
Rebuilding destinations takes :  4945 ms
Rerouting goods takes :  528 ms
Complete refresh takes :  5473 ms

**** 1982 ****
Rebuilding destinations takes :  40 ms
Rerouting goods takes :  147 ms
Complete refresh takes :  187 ms

**** Wipi ****
Rebuilding destinations takes :  8 ms
Rerouting goods takes :  18 ms
Complete refresh takes :  26 ms

**** Ferndale ****
Rebuilding destinations takes :  2 ms
Rerouting goods takes :  3 ms
Complete refresh takes :  5 ms


Note : Colin's save game is different from the one used previously.

Further testing is welcome.
« Last Edit: October 07, 2009, 11:35:33 AM by Knightly »

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #92 on: October 07, 2009, 07:08:27 PM »
This will certainly perform different on different processors, the longer the pipeline, the better.

I am quite torn on this; even in your old patch you used an unchecked array, which was marginally ok, since it was only accessed with an predefined counter. However, for a large project like simutrans, I would like to keep objects together. The mark of a station belongs imho to the station.

Of curse, that is only my view. But there were many more places liek the different tree types. The are accessed via a 9 bit variable. Nevertheless I put them into a vector, which will check boundness at every access, to catch a broken register or some other programm error before really bad things happen. Even if this costs same percent performance.

People tend to forget, what things belong together. Keeping things together with their data was imho the main idea of OOP. Maybe I have become to fundamentalistic in my views. But I am certainly open to challenge my optionions by arguments.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #93 on: October 07, 2009, 08:44:38 PM »
Prissi,

This will certainly perform different on different processors, the longer the pipeline, the better.

Most probably you are right on this. Pipeline issue aside, this patch will avoid many unnecessary halthandle boundness checks. More specifically, each halt's handle will be checked for boundness for no more than once in a single suche_route() call.


I am quite torn on this; even in your old patch you used an unchecked array, which was marginally ok, since it was only accessed with an predefined counter.

If non_identical_schedules were to use vector, then I believe warenziele should also be a vector of vectors too, right? IMHO, if our code are written such that errors are already guarded against, why should we compel ourselves to use vectors to incur unnecessary overhead?


However, for a large project like simutrans, I would like to keep objects together. The mark of a station belongs imho to the station.

I think this is more a point of view than hard fact. Extension buildings are part of a station, no doubt. But for markers, I think its sole purpose is to serve suche_route(), but not inherently part of a halt by definition. It's only working data for suche_route().


People tend to forget, what things belong together. Keeping things together with their data was imho the main idea of OOP. Maybe I have become to fundamentalistic in my views. But I am certainly open to challenge my optionions by arguments.

I agree that things that go together should be grouped together in their respective classes. And I agree with the doctrines of OOP too. But sometimes we tend to assume that certain variables should belong to a certain class of objects; but if we think deeper, there may be no necessary connection between them.


As for the patch, I know in advance that you may not like the static array. Actually, if I do not need to initialise the array elements with zeros, I would have declared it as a static local array inside suche_route() like the HNode array, for I believe the markers are only working data of suche_route().


Edit :

I have made a small change to the patch (moving the init_markers() call out of an IF block in karte_t::init()). Updated patch attached.


Knightly
« Last Edit: October 08, 2009, 06:33:05 AM by Knightly »

Offline Spike

  • *
  • Posts: 1361
  • First Simutrans Developer and Graphics Artist
Re: poor game flow in large maps
« Reply #94 on: October 08, 2009, 09:23:01 AM »
Keeping things together with their data was imho the main idea of OOP. Maybe I have become to fundamentalistic in my views. But I am certainly open to challenge my optionions by arguments.

I agree that things that go together should be grouped together in their respective classes. And I agree with the doctrines of OOP too. But sometimes we tend to assume that certain variables should belong to a certain class of objects; but if we think deeper, there may be no necessary connection between them.

Trying to deliver arguments pro separate markers:

If the lifetime of data differs much, I think this is a sign that they are independent, and can/should be kept independently.

Stations have a lifetime of program runtime, the markers only for a search.

Also, if we think about threading, such marks must not be part of the station data, otherwise multi-threaded searches are not possible.

Online prissi

  • Developer
  • Administrator
  • *
  • Posts: 9562
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #95 on: October 08, 2009, 07:36:28 PM »
Looking at the code, I feel like it would make sense to make the markers part of halthandle_t, i.e. derive a class from quckstone_tpl. That way also the initialisation would be automatically correct. Even more, the marked and mar test could be then part of the more intelligent halthandle too. But I would like to here you opinion.