The International Simutrans Forum

 

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

0 Members and 1 Guest are viewing this topic.

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 »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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...

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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 »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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 »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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 »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • 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