Skip to main content ↑ ↓
Topic: [patch] speed optimization of map generation (Read 13214 times) previous topic - next topic

[patch] speed optimization of map generation

This maps tries to accelerate map generation. In fact, two phases are modified:
(1) the search for suitable places to found a new city - most notable if the number of new citites was set way too high compared to map size
(2) the building process of the cities, there some results are cached for the evaluation of the cityrules.

I did not touch the industry generation. I think to most time consuming process now is the generation of intercity roads.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #1 –
wow, great!

Quote from: Dwachs – on
I think to most time consuming process now is the generation of intercity roads.

IIRC, now every city tries to connect to every other city if distance<max_distance, right?

I propose something like this:

1) connect city_A to city_B
2) if city_B is already connected to city_C AND distance<min_distance, DON'T try to connect city_A to city_C

to make it work better, cities should be processed from the biggest to the smallest and each should try to connect the others from the biggest to the smallest.

this way we'll have "clouds" of cities grouped together around the biggest and much less intercity roads to be built.

Re: [patch] speed optimization of map generation

Reply #2 –
Thank you :)
Quote from: fabio – on
IIRC, now every city tries to connect to every other city if distance<max_distance, right?
;D this was the old behavior, which changed some time ago to the wish you described below. Try the nigthly :)
Quote
I propose something like this:

1) connect city_A to city_B
2) if city_B is already connected to city_C AND distance<min_distance, DON'T try to connect city_A to city_C

to make it work better, cities should be processed from the biggest to the smallest and each should try to connect the others from the biggest to the smallest.

this way we'll have "clouds" of cities grouped together around the biggest and much less intercity roads to be built.
Now the intercity road building does 2 phases:
(1) try to built a tree structure of roads, such that all cities are connected to the road network.
(2) built some additional roads between cities that are connected to the same network, where the existing road connection is much longer than a new connection
Of course (1) and (2) are limited by max road length as specified in the new world dialogue.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #3 –
too bad i didn't have time to actually play for long. ;)

Quote from: Dwachs – on
Of course (1) and (2) are limited by max road length as specified in the new world dialogue.

to further optimise the map creation, max road length could be replaced by the max manhattan distance between two cities or a city and a pointon the network. this way, the road building routine should only be called if the manhattan distance is shorter than the given limit.

Re: [patch] speed optimization of map generation

Reply #4 –
This seems to work nicely - thank you for that!
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Re: [patch] speed optimization of map generation

Reply #5 –
Updated the patch. There appeared some crashes.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #6 –
what about this idea? is it doable and, specially, useful?

Quote from: fabio – on
max road length could be replaced by the max manhattan distance between two cities or a city and a pointon the network. this way, the road building routine should only be called if the manhattan distance is shorter than the given limit.

Re: [patch] speed optimization of map generation

Reply #7 –
Code: [Select]
+				// invalidate cache
+				if (location_cache)
+					for(uint16 x=0; x < besch->get_b(rotate); x++)
+						for(uint16 y=0; y < besch->get_h(rotate); y++)
+							bewerte_loc_cache( best_pos + koord(x,y),true);

 ???  "{" "}" is missing ?
Same monument was build twice. Should be a bug.
 

Re: [patch] speed optimization of map generation

Reply #8 –
Quote from: z9999 – on
Same monument was build twice. Should be a bug.
Thank you for testing.

I have not seen this. Which pak are you using? Do you mean that a monument (for Hajo etc) was built twice on the map or that an attraction (church, stadium etc) was built twice in a city? The patch should not interfere with both kinds of special buildings (I hope)  ???
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #9 –
Quote from: z9999 – on
Code: [Select]
+				// invalidate cache
+				if (location_cache)
+					for(uint16 x=0; x < besch->get_b(rotate); x++)
+						for(uint16 y=0; y < besch->get_h(rotate); y++)
+							bewerte_loc_cache( best_pos + koord(x,y),true);

 ???  "{" "}" is missing ?
Same monument was build twice. Should be a bug.

The code block should work without braces. But having them here is nicer and will prevent mistakes in future, if someone adds a line in there.

Re: [patch] speed optimization of map generation

Reply #10 –
Quote from: Dwachs – on
I have not seen this. Which pak are you using? Do you mean that a monument (for Hajo etc) was built twice on the map or that an attraction (church, stadium etc) was built twice in a city? The patch should not interfere with both kinds of special buildings (I hope)  ???

I found a bug.
It's not your patch, sorry for this.

Re: [patch] speed optimization of map generation

Reply #11 –
Anyway, simutans coding styles require braces for every if, while, for

Re: [patch] speed optimization of map generation

Reply #13 –
I had a quick loock; apart from manyy if etc. without braces, what is the advantage of replacing letters (easy to debug) by numbers? Also would it be not more useful to cache the rotation by using four pointers and to have different routines for 3x3, 5x5 and 7xx7 rules? And does the cache get really invalidated after every building actions? Because then of course previous invalid sites gets valid?

I cannot test it, as  have only a netbook at the moment with only 1 GB SSD ...

Re: [patch] speed optimization of map generation

Reply #14 –
Quote from: prissi – on
what is the advantage of replacing letters (easy to debug) by numbers?
In the cache, the result of testing all rules for one tile is stored. Which is done with bit fields, thus replacing letters with numbers was necessary.
Quote
Also would it be not more useful to cache the rotation by using four pointers and to have different routines for 3x3, 5x5 and 7xx7 rules?
I rewrote also the initialization of the cityrules. Only the places in the rules that are not "." are stored. It does not matter, whether the rules is 3x3 5x5 or 7x7. Also the mid point of each rule, which should be "n", is not stored.
Quote
And does the cache get really invalidated after every building actions? Because then of course previous invalid sites gets valid?
The cache is only active for the map generation phase. The cache will be cleared after the creation of each city. And yes, the cache is invalidated (in fact recomputed) when a road or building is built.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #15 –
Why is then cache then not active all the time? Too much memory consumption? Testing should be the same.

Re: [patch] speed optimization of map generation

Reply #16 –
Quote from: Dwachs – on
Only the places in the rules that are not "." are stored. It does not matter, whether the rules is 3x3 5x5 or 7x7.

so, could it be possible to extend cityrules to 9x9, 11x11, or even an arbitrary nxn (n being odd) without (excessively) increasing memory consumption?

e.g.


. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. S S S H S S . .
. S S S n S S . .
s s s s s . . . .
s S S S . S . . .
. . . . . . . . .
. . . . . . . . .

Re: [patch] speed optimization of map generation

Reply #17 –
Quote from: prissi – on
Why is then cache then not active all the time? Too much memory consumption? Testing should be the same.
Then one has to track every user action to invalidate some cache tiles. During map generation, changes happen in a few places only.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #18 –
You mean only the tiles changed will be recalculated? But this is not what the city rules do: Actually you need to reevalute a place around 3x3 (or what half of the largest rule size is, because a change in one place could a affect another place. An example is that houses will be built on diagonals only if there are already two houses. But now they may never by built then, or at least more slowly.

This is, of course, not a principal problem, if the changes are small the speed beenfit may outweight it. But I think it needs to be tested with many cityrules to make sure it does notbreak some of them, like the grids.

Re: [patch] speed optimization of map generation

Reply #19 –
Quote from: prissi – on
You mean only the tiles changed will be recalculated?
No, each city rule is tested in all rotations like before, only the evaluation of the single characters of a rule is taken from the cache. Only whether a tile fits to the characters of the rule. I mean the result of  'r', 'R', 'n' etc for a single tile.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #20 –
I tested this patch. The good news is, that is speds up city generation by a factor of 1.5 to 2. However, with disabled cache it is even faster by a factor of 3!

Therefore this is a worthy patch; however if the cache is completely removed from the code, the readability and the speed would even increase further.

With this in mind I would ask for some further tests on this, please.

Re: [patch] speed optimization of map generation

Reply #21 –
Quote from: prissi – on
I tested this patch. The good news is, that is speds up city generation by a factor of 1.5 to 2. However, with disabled cache it is even faster by a factor of 3!
8)
I will test later.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #22 –
Any progress on that?

Re: [patch] speed optimization of map generation

Reply #23 –
Here is the updated patch: I removed the cache completely.

We could also allow cityrules larger than 7x7, as long as the larger rules are not completely full, they should not have an impact on performance.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #24 –
That patch ought to result in the same towns? Because usually I get towns only half of the size of the town I get without that patch. For the same number of resulting inhabitants it is at least faster 2-5 times.

EDIT: Maybe I got just a very unlucky run. This will take a lot of time for testing.

Re: [patch] speed optimization of map generation

Reply #25 –
Actually this patch consists of two parts:

1) is related to city rules and stores only the relevant entries not the whole string

2) is related to city placement, where the check whether a new city has a certain distance to all existing cities is speeded up.

The impact of (2) is most notable for generating a map with many cities, where only a few of them can be placed due to limited space. However this part calls the random number generator different times than the trunk version, which means maps are different between patch and trunk version.

Maybe the speedup can be also achieved by setting max number of cities in the new world dialogue to size.x * size.z / ( minimum_city_distance^2) + something ?
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #26 –
I just run the same map several times with the old and the new generator. I did not count the numbers of cities, I just looked at the city info dialog. It was also 16 cities on a 512x512 map, so this should be a piece of cake. But I will test more thouroughly, with predefined random seed ...

EDIT: Ok, on a perfectly flat map without trees, both cities are slightly different but with same number of inhabitant; only your patch is four times faster. Will include it now.

Good work!

Re: [patch] speed optimization of map generation

Reply #27 –
Quote from: Dwachs – on
We could also allow cityrules larger than 7x7, as long as the larger rules are not completely full, they should not have an impact on performance.

this would be great! I didn't even fill all the rules in 7*7, but i would love to use something like 9*5 (which is 9*9 with 4 empty rows), 11*5 or 13*5. This would allow much more variety in blocks structure (2*2, 4*2, 6*2) in a more deterministic way. I'm looking forward to see it implemented. :)

Re: [patch] speed optimization of map generation

Reply #28 –
Quote from: fabio – on
like 9*5 (which is 9*9 with 4 empty rows), 11*5 or 13*5. This would allow much more variety in blocks structure (2*2, 4*2, 6*2) in a more deterministic way.

I don't think that is possible, because simutrans tests 4 rotations.
It is not due to the size of cityrules.

Re: [patch] speed optimization of map generation

Reply #29 –
@prissi: Accidentally, all the entries with '.' are stored in the rules, which should produce some unneccessary overhead when testing.

@fabio: Imho it would be no big deal to allow rectangular rules.
Parsley, sage, rosemary, and maggikraut.

Re: [patch] speed optimization of map generation

Reply #30 –
Quote from: z9999 – on
I don't think that is possible, because simutrans tests 4 rotations.
It is not due to the size of cityrules.

I know this. Rules need to be 7*7, 9*9, 11*11, 13*13 (maybe). But with Dwachs patch the cityrules store only non-empty entries.

e.g.
Quote from: fabio – on

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. S S S H S S . .
. S S S n S S . .
s s s s s . . . .
s S S S . S . . .
. . . . . . . . .
. . . . . . . . .

is _actually_ 9*9, but it uses only the memory of a 5*7 rule.

some cityrules can use smaller patterns, but being able to use such a bigger pattern would produce more interesting and complex city structure without a dramatic increase in memory usage.


EDIT: Dwachs replied before me. :::)

Quote from: Dwachs – on
@prissi: Accidentally, all the entries with '.' are stored in the rules, which should produce some unneccessary overhead when testing.

so there's no memory saving using lines of '.'?

Quote from: Dwachs – on
@fabio: Imho it would be no big deal to allow rectangular rules.

really? in a way my pattern of rules need a big width but no more than 5 rows. additionally, the central 'n' could be replaced by another symbol (say 'X') placed anywhere in the rule and showing the very tile in which the house or road needs to be built according to the rule itself. ;)

Re: [patch] speed optimization of map generation

Reply #31 –
Quote from: fabio – on
so there's no memory saving using lines of '.'?
since revision 2716 these entries are ignored (and invalid ones too).
Parsley, sage, rosemary, and maggikraut.