News:

Simutrans Sites
Know our official sites. Find tools and resources for Simutrans.

poor game flow in large maps

Started by Colin, September 01, 2009, 10:50:53 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

z9999

#35

bool haltestelle_t::step()
(...)
else if(reroute_counter!=welt->get_schedule_counter()) {
// all new connection updated => recalc routes
if(  !reroute_goods()  ) {

and

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 ?


prissi

Thank you for spotting this out. Indeed, the update needs to be moved to the end ...

z9999

#37
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.

gerw

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...

prissi

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.

gerw

Quote from: prissi on September 20, 2009, 08:51:39 PM
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.

prissi

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.

Spike

Quote from: prissi on September 21, 2009, 09:07:51 AM
Not sure, what "BSF"

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

Colin

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. 
I may not agree with what you say, but I will defend to the death your right to say it

Thought for the day

When you are up to your backside in alligators, it is difficult to remind yourself that your initial objective was to drain the swamp.

gerw

Quote from: prissi on September 21, 2009, 09:07:51 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):
QuoteFor 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

#45
@Colin

Quote from: Colin on September 21, 2009, 10:41:16 AM
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.

prissi

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

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

z9999

#48
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.

prissi

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.

z9999

Quote from: prissi on September 21, 2009, 02:22:20 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.

prissi

I did some testing with this and yoshis game and I think I reasonable balanced it. Further tries are appreaciated.

knightly

#52
@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).

Colin

My apologies to Prissi. I did not realise that it was mainly your patch that fixed my game. Thank you mate.
I may not agree with what you say, but I will defend to the death your right to say it

Thought for the day

When you are up to your backside in alligators, it is difficult to remind yourself that your initial objective was to drain the swamp.

z9999

Quote from: prissi on September 21, 2009, 04:32:59 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.

Colin

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?
I may not agree with what you say, but I will defend to the death your right to say it

Thought for the day

When you are up to your backside in alligators, it is difficult to remind yourself that your initial objective was to drain the swamp.

gerw

Quote from: Knightly on September 21, 2009, 06:13:47 PM
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

@ Colin :

Quote from: Colin on September 21, 2009, 09:21:21 PM
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 :

Quote from: gerw on September 22, 2009, 07:25:58 AM
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 :)

gerw

Quote from: Knightly on September 22, 2009, 08:17:26 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?

prissi

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.

Spike

Maybe, for stations above some limit, newly arriving packets should be discarded from the game.

gerw

Quote from: prissi on September 22, 2009, 09:58:28 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?

Quote from: prissi on September 22, 2009, 09:58:28 AM
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.

Colin

Quote from: prissi on September 22, 2009, 09:58:28 AM
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?
I may not agree with what you say, but I will defend to the death your right to say it

Thought for the day

When you are up to your backside in alligators, it is difficult to remind yourself that your initial objective was to drain the swamp.

z9999

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

prissi

If they are for pak64 or some other plain vanilla pak (no addons etc) I would be very interested in your testgames.

z9999

Unfortunately, each savegame needs ton of addons, sorry.

Colin

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.
I may not agree with what you say, but I will defend to the death your right to say it

Thought for the day

When you are up to your backside in alligators, it is difficult to remind yourself that your initial objective was to drain the swamp.

knightly

#67
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

prissi

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

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