[feature patch, tested] Stacked stations

[neroden]

This allows different players to have stations on top of one another.

This is tested and really does work correctly.  Complex layers of multi-player stations can be constructed, save and load properly and everything.    When one player builds a station on top of his own station, it still gets merged properly.  Merging with the public player works correctly.

This requires a savegame version increment, because vehicles should now save their last_stop_pos in *3d* rather than 2d.  (This was one of the last things recorded solely in 2d.)  I currently wrote it to trigger with version 112.8, but this can of course be revised as appropriate when you commit the patch.

This removes the cached halthandle_t from planquadrat_t, and adds it to grund_t.  This should have approximately the same memory usage, since only a few locations on the map (bridges, tunnels) have stacked grounds.  It should improve cache locality by shrinking the size of the main map array of planquadrat_t. 

In fact, it should actually speed up the game, because almost all of the places which were looking up the halt, had already looked up the grund_t but did not have the koords.  (So they had to call welt.lookup(gr.pos) before, now they just get gr.this_halt).  It will slow things down a little for the routines where this was not the case, but that is very uncommon.

One piece of compatibility code for various very old broken games had to be removed because I couldn't figure out what it was supposed to do; it doesn't appear to be needed any more.  You will see these changes in simware.cc at ware_t::laden_abschliessen.

Being able to stack stations is a nice little feature which a lot of players have asked for, and it allows for things like the NYC Subway and London Underground to be modelled more realistically. So I hope this patch can be committed quickly.  Although it is conceptually simple, it touches a lot of code.

My thanks go out to all the previous programmers who have, in the past, changed various parts of the code from "2d" to "3d"; because nearly all the code was using 3d coordinates, this turned out to be pretty straightforward.   

The patch is attached.  It is also available on the "standard-stacked-stations" branch of my github, for those who use git.

[kierongreen]

Looking at this now, for reference this is -sizes before patch applied:

Code Select Expand


Message: sizes: grund_t: 20
Message: sizes: boden_t: 20
Message: sizes: wasser_t: 24
Message: sizes: planquadrat_t: 16


and after it is applied:

Code Select Expand


Message: sizes: grund_t: 24
Message: sizes: boden_t: 24
Message: sizes: wasser_t: 24
Message: sizes: planquadrat_t: 12


Given that wasser_t is the same size with the patch applied there might actually be a reduction in memory usage therefore unless a map has more bridges and tunnels than water. I'm looking through code now...

[kierongreen]

Modified patch below - my efforts at tidying up:
I've readded a planquadrat::get_halt - this searches the grounds at this tile so removes lots of duplicate code
I've also changed karte_t::get_halt_koord_index to allow for optional limiting of searches to halts owned by a particular player, and made the halt creation in this optional (but on by default). This then calls planquadrat::get_halt


A few notes/comments (not just relating to your code but halts in general):
You've removed scripting ability to check for halt on a tile - is there any planned replacement for this?

There's a function to check whether ownership matches, but this actually also checks whether one of parameters is public player, or NULL. As a result spieler_t::check_owner( owner_a, owner_b) is not equivalent to owner_a == owner_b. This could be confusing.

The fact that there a 3 concepts of halts and tiles has the potential to be slightly confusing. We have:
1) halts physically present on a tile
2) halts that can load on this tile (same as 1 but also including water tiles next to docks)
3) halts whose coverage extends over a tile.

Function names don't exactly make it clear what they refer to - so for example plan->get_haltlist() refers to coverage, not physical presence.

In simwerkz suche_nahe_haltestelle we have

Code Select Expand


#if AUTOJOIN_PUBLIC
    // now search everything for public stops
    for(  int i=0;  i<8;  i++ ) {
        const planquadrat_t *plan = welt->lookup(pos.get_2d()+koord::neighbours[i]);
        for(  uint8 i=0;  i < plan->get_boden_count();  i++  ) {
            halthandle_t my_halt = plan->get_boden_bei(i)->get_halt();
            if(  my_halt.is_bound() && sp==my_halt->get_besitzer()  ) {
                return my_halt;
            }
        }
    }
#endif

Which to me doesn't look like it's doing what it should do (to me it should be looking for public stops, not those owned by sp?).




Anyway, I thought that if we are making change from 2d to 3d stops then now's a good a time as any to raise these issues...[/code]

[prissi]

The compability code for loading simware is not great. I would prefer to search all grund_t since there could be only one owner anyway.

Some stuff is also recalculated on the fly ever redraw, like the clipping for ways. Extending grund size still has 16 bits to cache stuff and make up some speed there.

Why the extra check for the AI. halt.is_bound() is to fail when there is something wrong. The construction success should have been checked above anyway.

Finally, I am not sure why at least three coding styles were used. Personally I would prefer
if(  bla  ) {
}
else {
}
which is the prevalent one in simutrans.

[neroden]

Modified patch below - my efforts at tidying up:
I've readded a planquadrat::get_halt - this searches the grounds at this tile so removes lots of duplicate code

Ah, it takes the player as an argument.  Yes, this makes sense.  I don't know why I didn't think of that.

I've also changed karte_t::get_halt_koord_index to allow for optional limiting of searches to halts owned by a particular player, and made the halt creation in this optional (but on by default). This then calls planquadrat::get_halt

This makes sense too.

A few notes/comments (not just relating to your code but halts in general):
You've removed scripting ability to check for halt on a tile - is there any planned replacement for this?

I couldn't figure out exactly what it would mean or what it was used for.  And I wasn't sure how to add "check for halt *owned by player X* on a tile", which is what we might actually want.  I did add scripting ability to check for halt on a ground.

There's a function to check whether ownership matches, but this actually also checks whether one of parameters is public player, or NULL. As a result spieler_t::check_owner( owner_a, owner_b) is not equivalent to owner_a == owner_b. This could be confusing.

Yes.  This was already confusing in the prior code.  It would be nice to clean it up.

The fact that there a 3 concepts of halts and tiles has the potential to be slightly confusing. We have:
1) halts physically present on a tile
2) halts that can load on this tile (same as 1 but also including water tiles next to docks)
3) halts whose coverage extends over a tile.

Yes, this is moderately confusing.  (I have run into some subtle bugs relating to #2.)

Function names don't exactly make it clear what they refer to - so for example plan->get_haltlist() refers to coverage, not physical presence.

Yes.  I'm not sure how best to distinguish the names and I wanted to minimize the number of name changes.

In simwerkz suche_nahe_haltestelle we have

Code Select Expand


#if AUTOJOIN_PUBLIC
    // now search everything for public stops
    for(  int i=0;  i<8;  i++ ) {
        const planquadrat_t *plan = welt->lookup(pos.get_2d()+koord::neighbours[i]);
        for(  uint8 i=0;  i < plan->get_boden_count();  i++  ) {
            halthandle_t my_halt = plan->get_boden_bei(i)->get_halt();
            if(  my_halt.is_bound() && sp==my_halt->get_besitzer()  ) {
                return my_halt;
            }
        }
    }
#endif

Which to me doesn't look like it's doing what it should do (to me it should be looking for public stops, not those owned by sp?).

Yep, you've found a copy-paste error.  I didn't test with AUTOJOIN_PUBLIC activated, and I had six or eight copies of very similar code to change.

You can probably clean this up using my_halt = plan->get_halt(welt->get_spieler(1));

[neroden]

The compability code for loading simware is not great.

What was it supposed to do?  I went through it and it looked like it could never execute.

I would prefer to search all grund_t since there could be only one owner anyway.

What are  we trying to fix with that code in simware?  It made some sort of sense back when stations were recorded in the savefile by location, but now they're recorded by halthandle.  Was there a case where a single station got created as two different stations, or what?

I couldn't figure out what the code was supposed to do.  That made it impossible for me to write a new version.

Some stuff is also recalculated on the fly ever redraw, like the clipping for ways. Extending grund size still has 16 bits to cache stuff and make up some speed there.

I also attempted to rearrange the contents of grund_t to improve cache locality, after noting which data in grund_t usually gets read at the same time.

Why the extra check for the AI. halt.is_bound() is to fail when there is something wrong. The construction success should have been checked above anyway.

I did not want to go through the entire AI code, which is very poorly written, in order to make sure that it *actually* checked the construction success on every single code path.  I think it doesn't actually check.  The AI code needs a lot of cleanup.

Finally, I am not sure why at least three coding styles were used.

I made a habit of matching the coding style in whatever section I was changing, in order to minimize patch size.  And this is an adaptation of a patch I originally wrote for experimental, and James has got his IDE set to yet another coding style.  *sigh*.

Personally I would prefer
if(  bla  ) {
}
else {
}
which is the prevalent one in simutrans.

I prefer to use K&R, personally, and I really dislike not having spaces after the if, so I habitually write:
if ( bla ) {
} else {
}

----
Thanks for the prompt review.  Kieron's patch looks good to me... I don't know how to address the scripting question.
---
Naming idea: rename planquadrat_t::get_haltlist to planquadrat_t::get_nearby_halts .  I think that would be clearer.

[kierongreen]

Ah, it takes the player as an argument.

My version does, original didn't

Updated patch correcting AUTOJOIN_PUBLIC code and making sure all elses use:

Code Select Expand


}
else {


Note however that existing code in many files still uses

Code Select Expand


} else {

so at some point this could be fixed too (but is beyond scope of this patch).

Incidentally I had added the ware conversion code back in - I think I got what it was trying to do... I think it's making sure that ware destinations are the actual station tile rather than any tile in that station.

Naming idea: rename planquadrat_t::get_haltlist to planquadrat_t::get_nearby_halts .  I think that would be clearer.

Yes something like this might be good... I've left it out of patch for now though.

[neroden]

Incidentally I had added the ware conversion code back in - I think I got what it was trying to do... I think it's making sure that ware destinations are the actual station tile rather than any tile in that station.

Unfortunately what you've written is wrong and will create new bugs, because it will redirect wares to a halt owned by a different player on the same tile.  :-P

Code Select Expand


--- simware.cc   (revision 6608)
+++ simware.cc   (working copy)
@@ -147,10 +147,10 @@
    // since some halt was referred by with several koordinates
    // this routine will correct it
    if(ziel.is_bound()) {
-      ziel = welt->lookup(ziel->get_init_pos())->get_halt();
+      ziel = welt->get_halt_koord_index(ziel->get_init_pos());
    }
    if(zwischenziel.is_bound()) {
-      zwischenziel = welt->lookup(zwischenziel->get_init_pos())->get_halt();
+      zwischenziel = welt->get_halt_koord_index(zwischenziel->get_init_pos());
    }
    update_factory_target(welt);
}


This code (except for update_factory_target, which is good) just has to be deleted, unless we can figure out when it is actually supposed to be executed.

The prior version of the code can *never do anything interesting*, because ziel is a halthandle.  It could only execute if there were two *different* halthandles, *both* bound, with the *same* init_pos.  When there was only one halt allowed per planquadrat_t, this should never happen, because any old handle would be deleted before the new handle was created.  (Perhaps it happened on loading very old saved games.)  But it will now be able to happen when stacked stations are allowed, and we have to *allow* it to happen.

So I don't know what it was supposed to do.  It was only doing anything interesting when loading very old saved games.  And we can't leave the code there in place, because it will break stacked stations.

I think it is unnecessary because I think  ::get_halt_koord_index handles the problem of loading those old saved games correctly.  (When called from ware_t::rdwr.)

I can't figure out how it was supposed to work.  It needs to be deleted.  It seems to work fine when it is deleted.

Apart from that bit, the second version of your (our) patch looks great.  Third version please? :-)

[kierongreen]

Thinking more, if this is to cope with errors in old games it would make sense to call it when no halt had been found (i.e. !ziel.is_bound()). Given this should only be a one off error my view would then be to delete the ware?

[prissi]

Apart from simware.cc compatibility code (which I can fix too) there is the question how stops of the some player connect, when divided by more than one height level. I.e. should a stop on a high bride or a deep tunnel automatically connect with all stops of the same player on the same tile?

Also add to haltlist gets random for two players on the same stop. This mean even the routing of passengers could change after reloading a game. A tie-breaker (if koord are equal, then first above ground with distance then below ground with distance) is needed now.

[kierongreen]

In my opinion all stations belonging to the same player should automatically connect.

The alternative is to force the player to build connecting structures (including in underground mode) such a lifts or escalators. The logical conclusion of this would be that only station buildings on kartenboden would give coverage - with all others having to be connected to these in some way. I think this would be over complicated.

The reason behind allowing more than one station on a tile seems to be primarily in multiplayer - where at the moment if a player built an underground station under a city for example then other players would not be able to build bus stops on the surface.

Agree about tie breaker for routing of goods and passengers though I'll work on that.

[Ters]

Routing of passengers changing at random is nothing new. I think I've even seen it without a save/load cycle. If a house is equdistant from two stations (horizontally), how does it select which to send its generated passengers to now? Stacked stations is really just the same problem.

As for how stations connect vertically, until all pak sets allow tunneling down with extension buildings, subterranean stations should connect up to ground level and all levels in between automatically. For above ground structures, this can become ridiculous after a while, but drawing a line is difficult, so I say just connect them. It will look a bit strange if another player has or builds a station in-between. I don't know if it will be contrary to this patch to prohibit station construction (or even construction at all) on levels in between connected stations of another player.

[kierongreen]

Good point about different tiles having same distance now. Should we consider a tie breaker for that too - or just cope with the slight randomness?

I don't think it would be particularly user friendly to prohibit station construction on levels between other players stations. Connecting all levels of stations automatically is really the only way to go I think.

[neroden]

Apart from simware.cc compatibility code (which I can fix too) there is the question how stops of the some player connect, when divided by more than one height level. I.e. should a stop on a high bride or a deep tunnel automatically connect with all stops of the same player on the same tile?

In my implementation, it does.

Also add to haltlist gets random for two players on the same stop. This mean even the routing of passengers could change after reloading a game. A tie-breaker (if koord are equal, then first above ground with distance then below ground with distance) is needed now.

Ah, right.  This doesn't occur in experimental so I didn't think of it.

[neroden]

It will look a bit strange if another player has or builds a station in-between.

In London in the Victorian era, at least once, one company owned the "surface bus station" and the "deep tube", while another company owned the "shallow Underground" line in between.  I think this is just fine.  The purpose of the patch is to make multiplayer play more intiutive.  I agree with kieron, connecting all levels is the only way to go.

---
I've also seen stations with an elevated railway line and a tunneled railway line owned by the same company, and a bus station owned by a different company sandwiched in the middle.

Regarding the simware issue:

Thinking more, if this is to cope with errors in old games it would make sense to call it when no halt had been found (i.e. !ziel.is_bound()). Given this should only be a one off error my view would then be to delete the ware?

That makes sense to me.
---
On second thought... I believe that if !ziel.is_bound() or !zwischenziel.is_bound(), the ware will *already be deleted* if it's on a convoi, upon arrival at the next station (I've seen this happen).  And if it's in a station, it will either be rerouted or deleted (at the start of the next month)  Again, I've seen this happen.  So again, the code in laden_abschliessen can just be removed entirely, it's redundant.

[prissi]

Passengers in stamndard choose the station which is on top of haltlist (and not overcrowded). This will be a different one after a reloading, and may affect passenger distribution between player a lot. But I will see into it, since there seems to be an overall consent.

[neroden]

Passengers in stamndard choose the station which is on top of haltlist (and not overcrowded). This will be a different one after a reloading, and may affect passenger distribution between player a lot. But I will see into it, since there seems to be an overall consent.

OK.  For reference, in experimental, we track journey times from point to point and we track waiting times (very memory intensive, but worthwhile).  The passengers will pick the station which they think will give the shortest journey time + waiting time.  So if you have a station which is further away with fast trains, and a station which is closer with slow buses, the passengers will go to the further station... but f that station gets overcrowded, waiting times at that station will go up, and then the passengers will go to the closer station.

I like this system a lot, but I guess you probably want to do something simpler for standard.

[Ters]

In London in the Victorian era, at least once, one company owned the "surface bus station" and the "deep tube", while another company owned the "shallow Underground" line in between.

Did this shallow station lie directly in between? My concern was when the middle station completely blocked any potential connection between higher and lower station, except by extreme detour. However, it is difficult, and perhaps confusing, for the game to differentiate acceptable overlap from blocking overlap. It is not a problem that must be addressed now, if it even is a problem. Just connect without care for height difference for now.

[kierongreen]

Right, just removed the compatibility code from simware. That leaves only outstanding issue as far as I'm concerned being the scripting...

I did add scripting ability to check for halt on a ground.

Where did you add this to the API? I can see where you took out the reference to simplan get_halt but not anything that's been added. Of course now the simplan get_halt is back in we could add it back into scripting - although now it needs a player argument...

[prissi]

Removing the code from simware.cc will lead to almost complete loss of packets; the problem is that simware creates stops for dummy halts when referring to non-existing (because not yet loaded halts). These will be discared after laden_abschliessen and hence ziel and zwischenziel will be invalid. The stops on tile (0,0) will retain no wares when removing this.

The easiest solutions is to add another parameter to laden_abschliessen():

Code Select Expand


void ware_t::laden_abschliessen(karte_t *welt,spieler_t * /*sp*/, bool recalc_halt_id )
{
if(  recalc_halt_id  ) {
// since some halt was referred by with several koordinates
// this routine will correct it
if(ziel.is_bound()) {
ziel = welt->lookup(ziel->get_init_pos())->get_halt();
}
if(zwischenziel.is_bound()) {
zwischenziel = welt->lookup(zwischenziel->get_init_pos())->get_halt();
}
}
update_factory_target(welt);
}

recalc_halt_id is then only set for file->get_version()<=111005

[kierongreen]

There's no nice way to add this parameter though - as laden_abschliessen() is called when looping through all halts and adding vehicles to convois. So the file version would have to be passed through all functions between loading in simworld and ware laden_abschliessen.

Alternatively we could store the file version in world, then it could be used anywhere else things like this might crop up... (making the "ugly hack" used for trees abschliessen less ugly at the same time?).

[kierongreen]

Right - final patch for the night. I've changed the squirrel api to point to grund_t get_halt hopefully this should work (I'm not familiar with the scripting but can't see why it shouldn't). laden_abschliessen has been modified to check welt->file_version which I've moved from being just in simworld.cc to actually being part of the karte_t class.

[neroden]

Right, just removed the compatibility code from simware. That leaves only outstanding issue as far as I'm concerned being the scripting...
Where did you add this to the API? I can see where you took out the reference to simplan get_halt but not anything that's been added.

Did I lose that from my submitted patch?  *sigh*.  :-(

Of course now the simplan get_halt is back in we could add it back into scripting - although now it needs a player argument...

This is probably the right thing to do, thanks very much.

Removing the code from simware.cc will lead to almost complete loss of packets; the problem is that simware creates stops for dummy halts when referring to non-existing (because not yet loaded halts).

Order of loading helps a lot with this.  Halts are loaded before convois:

Code Select Expand


DBG_MESSAGE("karte_t::laden()", "load stops");
  // now load the stops
  // (the players will be load later and overwrite some values,
  //  like the total number of stops build (for the numbered station feature)
  if(file->get_version()>=99008) {
    sint32 halt_count;
    file->rdwr_long(halt_count);
    DBG_MESSAGE("karte_t::laden()","%d halts loaded",halt_count);
    for(int i=0; i<halt_count; i++) {
      halthandle_t halt = haltestelle_t::create( this, file );
      if(!halt->existiert_in_welt()) {
        dbg->warning("karte_t::laden()", "could not restore stop near %i,%i", halt->get_init_pos().x, halt->get_init_pos().y );
      }
      ls.set_progress( get_size().y/2+128+(get_size().y*i)/(2*halt_count) );
    }
  }

DBG_MESSAGE("karte_t::laden()", "load convois");


This means that ware packets in convois are always going to be loaded properly, because all halts are loaded already.

Obviously packets still waiting in factories do not have destinations.  So we only have to worry about packets which are waiting in halts.  This tells us what to do.  Insert a section in karte_t::laden after the loading of halts which goes through the wares at each halt to correct the halt destinations and eliminate the dummy halts.  Which is when laden_abschliessen is called, I see...

Thanks for telling me what this code was supposed to be doing!

Now, it still only applies to old saved games, right?  Because new saved games save the halthandle ID, and so they can use that even before the halt is loaded.  In that case kieron's patch seems correct to me.

Alternatively we could store the file version in world, then it could be used anywhere else things like this might crop up...

There's some subtly nasty problems with doing that.  Most importantly, the loaded file version is one thing, and the saved file version is another thing entirely.  They are often different.

So your implementation is wrong, because it grabs the wrong version (the save version, not the load version).

It's probably best to actually pass

Code Select Expand

const loadsave_t*
through *all* the calls to laden_abschliessen, although this is a big project.  Any instance of laden_abschliessen may care about the load file version.  It's already passed to all instances of :rdwr.

I can perhaps prepare a revised patch... while I'm doing it, it would be a good time to translate the name of laden_abschliessen.  "load_finalize"?

Alternatively "loaded_file_version" could be saved in karte_t.  Distinct from save_file_version.  This would be a bit of a hack, but I don't think the same karte_t is ever loaded twice.

[kierongreen]

Erm, I'm pretty sure the saved game version I use should be fine. For new maps I set it in karte_t() to:

Code Select Expand


file_version = loadsave_t::int_version( umgebung_t::savegame_version_str, NULL, NULL );

Which is indeed the saved game version - however for loaded maps the code is already there to read it in karte_t::load(loadsave_t *file):

Code Select Expand


file_version = file->get_version();

Which is the load version.


Edit:
Regarding the scripting I've changed the plan get_halt to call grund get_halt instead. This should work I think since plan get_halt required 3 coordinates to be passed from squirrel according to current API (maybe z was ignored before?).

[neroden]

Erm, I'm pretty sure the saved game version I use should be fine. For new maps I set it in karte_t() to:

Code Select Expand


file_version = loadsave_t::int_version( umgebung_t::savegame_version_str, NULL, NULL );

Which is indeed the saved game version - however for loaded maps the code is already there to read it in karte_t::load(loadsave_t *file):

Code Select Expand


file_version = file->get_version();

Which is the load version.

Aha.  You are correct.  Sorry, I saw the first line and not the second.

I would strongly suggest changing the name of karte_t::file_version for clarity.  How about loaded_file_version?  That would probably be fine.

Edit:
Regarding the scripting I've changed the plan get_halt to call grund get_halt instead. This should work I think since plan get_halt required 3 coordinates to be passed from squirrel according to current API (maybe z was ignored before?).

That's excellent.  We need to have grund_t::get_halt available for scripts in any case.

I'm not sure what the scripting is actually being used for in scenarios, which raises the question of what functions we *want* to have available for the scripting.

[Ters]

NB: Written before neroden posted.
Having the loaded version in karte_t as file_version is a bit risky. It is easy to assume that this is also the version the game will be saved as. Or (less likely) that the game is still operating according to that version. Passing loadsave_t around seems like the "right" thing to do to me, but a different name might also do.

[kierongreen]

Ok changed name to load_version...

[prissi]

Another (more hackish) solution would be to set a satic variable on simware.c and reset it after finishing loading. But putting it into karte_t is much better, as there could be more routines which require this (I needed somethign similar for monorail conversion, and relied on hardocded names then). Adding to karte_t is much better.

[kierongreen]

Ok, am commiting now given consensus... If anyone discovers errors with scripting please shout!

Code Select Expand


r6609 | kierongreen | 2013-08-03 22:32:35 +0100 (Sat, 03 Aug 2013) | 1 line

ADD: (neroden) stacked stations



Edit: Note that saved game is not incremented yet - should we wait until city growth patch is added before incrementing?

[prissi]

With the many changes coming,. the next larger version will be anyway a 120 or so.