New Map Rewrite effort

[Killer 11]

that older map rewrite failed becouse when it was done there was no way to merge it with main code without totaly breaking it.

[glx]

We apply all OpenTTD trunk updates to our branch, so the merge will be easier when all our work will be done.

[belugas]

IMHO if this continues, it will become increasingly difficult & time-consuming to even switch to a new structure.

I don't agree on this, nor the rest of the team, i'm sure. One of the goals we are pursuing is to isolate that structure, in order to change it more easily. So this is why we need accessors. This is a requirement in order to implement the new structure.

Investing this time in the development of the new structure seems to me a far better way to go (on the long run!). Trying to only achieve results on short term will eventually kill any project.

That new structure has already been designed by the devs a long time ago. So we don't have to do much work to define it! Implementation is another trick, but nothing is impossible to do. The hardest part is already behind us now.

Do the OpenTTD developers have a vision of the way to go towards a new map structure?

Suggestions of reading :
The code written by devs
The documentation that goes along with it

So to say it shortly, don't worry, be happy
And thanks for sharing thoughs.

[Korenn]

IMHO if this continues, it will become increasingly difficult & time-consuming to even switch to a new structure.

I don't agree on this, nor the rest of the team, i'm sure. One of the goals we are pursuing is to isolate that structure, in order to change it more easily. So this is why we need accessors. This is a requirement in order to implement the new structure.

Investing this time in the development of the new structure seems to me a far better way to go (on the long run!). Trying to only achieve results on short term will eventually kill any project.

That new structure has already been designed by the devs a long time ago. So we don't have to do much work to define it! Implementation is another trick, but nothing is impossible to do. The hardest part is already behind us now.

That's not what he was talking about! His point was that there should be no new commits for patches that change the way the map array work while work on the new map array is done, because that requires re-writing when the new map array is merged, only creating more work and stress that will slow down the merging process.

Which I totally agree with. So there should be no new 'lights on bridges' patches that change how and where the map array data is stored or its size while this work is going on! ofcourse a condition is that the new map array shouldn't take too long A deadline would be interesting, if the rewriting team would consent to that.

[Rubidium]

One thing I've noticed, when a train goes uphill or downhill, instead of sliding up or down the slope the train and it's carriges act as if each tile is flat, and when it reaches the next tile it jumps. Like it's going up or down stairs.

Thanks for letting us know.

This bug should now be fixed. It is in SVN and will be in the next nightly.

[belugas]

So there should be no new 'lights on bridges' patches that change how and where the map array data is stored or its size while this work is going on! ofcourse a condition is that the new map array shouldn't take too long A deadline would be interesting, if the rewriting team would consent to that.

A deadline... that is the most dangerous thing to lay down
It's hard to give one. We never imagined the current step would have been reached that fast. So I think the best estimate would be : "When it's finished". And it may be finished earlier if you all test it thoroughly, as Thalass (thanks again) did!
As for those who are doing map related patches : don't stop doing it. We will adapt (or reject ) if they get merged in trunk.

[DaleStan]

For those of you who want deadlines, go find The Manager FAQ and hunt up the bit about the lost keys. (Then read the rest of it, and the Hacker FAQ. Both are good reads.)

And then quit asking. Expressing interest is useful, but "When will it be done" usually isn't any more useful than me asking when you're going to find your keys.

[kasper_vk]

kasper_vk: Could you please explain what you mean by map-related patches? Do you mean things like this project, or things like my yellow signals patch, or both?

I most certainly do not mean this new map rewrite effort: I'm very exited about it en hope it will end up being merged into the main code stream!

....

That's not what he was talking about! His point was that there should be no new commits for patches that change the way the map array work while work on the new map array is done, because that requires re-writing when the new map array is merged, only creating more work and stress that will slow down the merging process.

Which I totally agree with. So there should be no new 'lights on bridges' patches that change how and where the map array data is stored or its size while this work is going on! ofcourse a condition is that the new map array shouldn't take too long A deadline would be interesting, if the rewriting team would consent to that.

Korenn understood exactly what i meant with my post!

I did mean things like Egladils y.s. patch, but it seems some nuance is in please. So if I may correct myself:
Any new change / patch / feature that somehow could delay this New Map Rewrite Effort should imho be postponed until this NMRE this succesfully merged into the main code-stream.

Just to be sure:
- I'de love to see more map-related new features!
- But most of my map-related wish list is impossible without this new map structure...
- So I encourage this NMRE (I would even want to help, if I had the time)
- I've read those wiki pages several times before

[prissi]

Do your guys like to see the simutrans code? It is C++, however uses the tile idea nearly the same way.

Imho at some point it might be a good idea to sotre at least the x,y of a tile on the tile itself. These 4 bytes won't kill you and will improve performance, since you do not need to pass around x,y all the time.

[Bjarni]

Do your guys like to see the simutrans code? It is C++, however uses the tile idea nearly the same way.

the nightly build server can't handle C++ code (except for a minor part for windows. Everything else will fail)
Because of this, we need to do it in plain C.

Imho at some point it might be a good idea to sotre at least the x,y of a tile on the tile itself. These 4 bytes won't kill you and will improve performance, since you do not need to pass around x,y all the time.

without looking at the rewritten source code, I guess it contains TileIndex, which can easily be translated to x,y

Having a pool of tiles, where each block contains 64*64 tiles, moving to a tile next to the current one will most often be moving within the same array

Thinking about it, the fastest solution would be to malloc the whole map array when starting a new map/loading a map. This way we can really quickly move around the map and TileIndex is not needed since it's the same as the index in the array. The issue will then be that we only got one tile for each x,y and we want two tiles for a tile if it got a tunnel and another one if a bridge is present too and so on. The solution to that would be to have a pool of tiles and we can make a linked list of tiles in each place in the array.

I'm not sure that was a good explanation, so I will add an example:

say we got a normal tile at TileIndex 7343. We got a road on that tile, which is stored in the normal array(Let's call this one A). Now some railroad builds a tunnel underneath and we need an extra tile for that tunnel (to ensure that we got enough memory reserved for PBS blocks, turning tiles, signals in the tunnel and so on). To get that extra tile, we get a new tile from the pool (we call this one B)

now to access B, we use the x,y to get the number 7343 and we can access A. Then A is the start of a linked list of all tiles on that x,y, so we use that to access B. We can then get a new tile from the pool (C) and make B link to C if we want a new tunnel underneath the same tile or say a bridge.

I think this is the best solution since it's not extremely complicated and accessing tiles do not slow down on large maps like a pool would. We should consider the parameters for the extra tile pool though. This idea might need a bit more work since it's like 10-15 minutes old by now

[bobingabout]

Do your guys like to see the simutrans code? It is C++, however uses the tile idea nearly the same way.

the nightly build server can't handle C++ code (except for a minor part for windows. Everything else will fail)
Because of this, we need to do it in plain C.

shouldn't be too hard to convert from C++ to C. probably way easier than converting from Basic or Pascal or something else like that.

[KUDr]

Bjarni:

it is really nice idea . Yesterday I realized that I will need some additional PBS/tile store in some cases like crossing/junction or for tiles with train on it. So I have implemented so called TileExtension (something like base class for any specific additional extended tile information). It supports subclassing and virtual methods (could be RailCrossing, Bridge, Tunnel, and so on), all in plain C. The tile itself contains now 4 bytes more on 32 bit platforms for pointer to the first extension. So we can link any number of extensions to each tile.

1) Is it something similar what you are thinking about?
2) Whould it be possible to find some C++ -> C compiler? It would make my life much easier.

[DaleStan]

Just do a some search and replaces:
Remove the public, protected, and private keywords, and the using declarations.
class foo{func(params)[const]; ...}; -> typedef struct{...}foo; func([const] foo*,parms);
obj.func(params) -> func(obj,params)
rettype Class::func(params)[const] -> rettype func([const] Class*this,params)

Or you could just learn to work within the parameters of the problem, which in this case include a language specification.

[KUDr]

DaleStan: do you have some similar "simple trick" also for the templates? It is bit off topic, I know, but could be interesting...

[prissi]

I was rather thinking about he things dealing with the two height level codes or the way bridges or tunnels (which are a second ground on the same tile in simutrans) are coded. 1:1 translation seems extremly unlikely to me, since lots of templates are used.

Anyhow, short conclusion:

Every tile has a tile list structure, holding all objects of this tile. This is something like union {ding_t *one; ding_t all[size]; } so it uses no additional space for the often case of a sime object(thing). Signal, vehicles, everything would be stored there.

Of course, this concept might be disadvantageous with 64bit, since all pointer sizes doubles. Then you could have tile with more than on thing.

But I am glad, you are changing this ugly map thing, that is utmost uportant!

[Bjarni]

1) Is it something similar what you are thinking about?

yeah, something like that. I didn't claim to have the final solution, more like we should investigate to see if that is the way to go (I think it is, most likely in a modified version though)

2) Whould it be possible to find some C++ -> C compiler? It would make my life much easier.

well, if you use objects, it's not like it's going to be easy. There is the middle way of objective C, which OSX uses to interface with OS functions (like video, sound and so on)
The question is if it will work on all platforms and if it is the stuff you need. Again this calls for an investigation to see if that is the way to go

[DaleStan]

DaleStan: do you have some similar "simple trick" also for the templates? It is bit off topic, I know, but could be interesting...

Oops. obj.func(params) -> func(obj,params) should be obj.func(params) -> func(&obj,params), and I missed obj->func(params) -> func(obj,params)

Three ways come to mind, but, none are particularly simple (and yes, I'm playing fast and loose with reference object vs pointer here):

1) Move the function into its own (not include-guarded) header
template<typename _Ty> rettype func([const] _Ty&foo,params) ->

#undef FUNC_NAME
#define FUNC_NAME func__##_Ty
rettype FUNC_NAME([const] _Ty*foo,params)

#define _Ty correctly and #include the header every time you need it. You may want/need inline or static modifiers to keep the linker from complaing about multiply defined symbols.

2) template<typename _Ty> rettype func([const] _Ty&foo,params) -> rettype func(magicnumber,[const] void*foo,params)
where magicnumber encodes the template params somehow.

3) template<typename _Ty> rettype func([const] _Ty&foo,params) ->
rettype func_Ty1([const] _Ty1*foo,params)
rettype func_Ty2([const] _Ty2*foo,params)
rettype func_Ty3([const] _Ty3*foo,params)
...
(version 1, but with search/replace hackery instead of preprocessor hackery)

As I said, none particularly simple. Template classes would have to use 1 or 3, and would probably be even less simple.
All versions require corresponding updates to the calls.

[Red.xiii]

Been following your progress on the Wiki, you've all done some amazing work.

Well Done and keep it up

[DeletedUser21]

Seems that it's almost finished now!
I hope to see the results soon!

[belugas]

You can even start to smell it by now

We are preparing the merge of it. It is not perfect, there are some issues to work out before.

Devs and us will be working them out, as soon as we finish moving everything from current SVN into svn://svn.openttd.org/branch/tfc_newmap , created yesterday.

But wait before trying to compile it... We have to move files first