News:

Simutrans.com Portal
Our Simutrans site. You can find everything about Simutrans from here.

Overtaking. Fun patch.

Started by isidoro, September 10, 2008, 02:47:39 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

isidoro

After reading http://forum.simutrans.com/index.php?topic=339.0, I decided to try my programming skill with it.  I'm highly proud to say that... it was a complete failure   ;D

Then I thought that a partial solution to that problem would be overtaking (yu-yu  :P).  Once a vehicle is going to stop due to another vehicle in the way, it can try overtaking.  I have read that this is a very sensitive topic here, so excuse me if this is not convenient.

After some tries, I came to this patch.  It is not serious, only a first approach.  You can try it with r2011 and pak64 and the attached savegame.

A vehicle (the overtaking vehicle) will try to overtake if:

  • The road is blocked by other road vehicle (the overtaken vehicle)
  • Neither the overtaken nor the overtaking vehicle is being overtaken or overtaking
  • The speed of the overtaking vehicle is at least 5 kmh over the maximum speed of the overtaken vehicle

The tiles involved in the overtaking are calculated.  For all these tiles, it must happen:

  • No stops, no crossings, no signs, no change in speed limit
  • Flat tiles (no slopes)
  • No other vehicles apart from the two involved

Problems:

  • Facing traffic is not checked apart from those tiles (I don't know how to take facing traffic apart).  It should be checked for some tiles more.  That means that you can see "some frontal crashes" (not actual crashes).
  • City traffic (that belonging to no player) is not overtaken (not checked)
  • Perhaps overtaking should not be allowed in bends and now it can happen
  • Calculation (specially for diagonals) should be polished
  • Don't know if there are performance issues

This is only some fun in order to learn something about Simutrans source.  Be kind to me.   :)

VS

#1
Quote from: isidoro on September 10, 2008, 02:47:39 AM
I have read that this is a very sensitive topic here, so excuse me if this is not convenient.
I'd say implementing this yourself does not count as a making problems ;D (as opposed to asking others to do it).

PS: I have no experience with Simutrans code, but... am I right that the "expensive" check for overtaking happens only in situations when the vehicle actually has something in front of it?

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

prissi

Some comments to get this done to be ready for inclusion:

First: Don not touch ding_t, if you can avoid it. I would suggest a flag in vehikel_basis_t for the static offsets. There are still six flags left to fill one byte. Add one for overtaking shift, which is better done directly in get_screen_offset() (One can think of making this function virtual for this purpose, if one worries about speed.)

The offsets should be init by set_diagonal_multiplier(), since the it should be clear if driveleft is enabled or not, and it is called only a single time. ding_t::init is not the right place, since trees and all other stuff rarely overtakes ...

Also the check for stree speed should just check if the car in question can still go with its maximum speed. I do not worry about 80kmh limit, if my bus runs only 75kmh ...

I would also not work in hop(). Use automobil_t::betrete_feld() (since it is car specific.) to update convoi counter.

And the check for overtaking should by probably better done in a step and not in a sync_step. Look at the way trains (or airplanes) are doing it: They use step for this, becuase during a sync step vehicles are moved in random order (and it is time critical). The trick is: They retrun false for the next tile free check, but the do not reduce the speed. Next time, (during a step) they check if the road is really blocked.

is_moving() will indeed report all moving stuff, no matter what direction. You can check for facing traffic (since you do not have crossings) easily by calculationg the direction on this tile (from previous and next coordinate) and the use ribi_t::rueckwaerts() to get the reverse. Any vehicle with this fahrtrichtung will come against you.

And one further comment on some formatting rules of simutrans. if() return; is not allowed, please use
if() {
   return;
}
(Stricht one statement per line rule.)

And avoid if(a) {
  if(b) {
     ...
  }
}
use
if(  a  &&  b  ) {
}
...

But others than these it is good to see somebody else again working with the source code.

isidoro

Quote from: VS on September 10, 2008, 09:03:40 AM
[...]
PS: I have no experience with Simutrans code, but... am I right that the "expensive" check for overtaking happens only in situations when the vehicle actually has something in front of it?

Neither do I,  :) .  In my opinion, you're right.  The check is done whenever there is something in front of the vehicle.  Without overtaking, that check would be repeated every now and then but if overtaking succeeds, it is done no more.  But overtaking code is also an overhead in itself.

Quote from: prissi on September 10, 2008, 07:21:00 PM
Some comments to get this done to be ready for inclusion:

Thank you very much, prissi, for your answer.  I have to study it.  Some things are easy to change (coding style, etc.), some more complex.  I would like to get the code polished and sure will need your help. For the easy ones:

Quote from: prissi on September 10, 2008, 07:21:00 PM
The offsets should be init by set_diagonal_multiplier(), since the it should be clear if driveleft is enabled or not, and it is called only a single time. ding_t::init is not the right place, since trees and all other stuff rarely overtakes ...

I have noticed that.  As a static member I was looking for a place only executed once to set the offsets, but wasn't sure of where.  By the way, I need a way to measure distances on diagonals to fix the code there.  And I suppose that that has to do with the diagonal_multiplier topic of last revisions, hasn't it?

Quote from: prissi on September 10, 2008, 07:21:00 PM
Also the check for stree speed should just check if the car in question can still go with its maximum speed. I do not worry about 80kmh limit, if my bus runs only 75kmh ...

At the beginning I programmed that that way, but then I was concerned with facing traffic in order to simplify calculations.  I decided that the worst case is when facing traffic comes with maximum road speed.  To make it simpler, I decided that all tiles should be of the same road speed limit and I changed it.  But can be studied in more detail.

Quote from: prissi on September 10, 2008, 07:21:00 PM
But others than these it is good to see somebody else again working with the source code.

Thanks, again.  I will change the code as suggested.  I hope not to make a lot of questions...

prissi

Well, ding_t::init is unfourtunately executed very many times, some million times during game creation or object loading.

And the offsets on a diagonal (or normal tile) are calculated in get_screen_offset(). There you get the relative position of a vehile: Its position relative to the length to travel on this tile is display_steps/steps_next.

Do not hesitate to ask.

isidoro

Here is another version of the patch with some things done.  I have found some problems I would like to comment:

Quote from: prissi on September 10, 2008, 07:21:00 PM
First: Don not touch ding_t, if you can avoid it. I would suggest a flag in vehikel_basis_t for the static offsets. There are still six flags left to fill one byte. Add one for overtaking shift, which is better done directly in get_screen_offset() (One can think of making this function virtual for this purpose, if one worries about speed.)

This is, I hope, done.  I have passed all the stuff to vehikel_basis_t, and ding_t is untouched.  The offsets are added in get_screen_offset.  I see all now more logical.  But I found a big trouble.  I noticed that after doing that, the program stopped with a invalid pure virtual call.  After debugging, I noticed that it happened when pedestrians disappeared!  :-\  Then, I realized that this sequence of calls happened:

  • ~fussgaenger_t()
  • ~verkehrsteilnehmer()
  • mark_image_dirty()
  • get_screen_offsets()
And the pure virtual call was to gib_typ() in order to get the type of vehicle.  After reading this good article about this (http://www.artima.com/cppsource/nevercall.html), and not knowing how to tell apart pure virtual calls, I decided to implement the flag you suggested, but I found a little problem: the flag is in vehicle and not in convoi and didn't like the idea of setting and resetting the flag for all vehicles of the convoi each time.  So, I decided to include a flag in vehicle (read-only) which tells if the vehicle can overtake and is set in the constructor.  Once I know it is a vehicle that can overtake, I can safely cast to an automobil.

Quote from: prissi on September 10, 2008, 07:21:00 PM
The offsets should be init by set_diagonal_multiplier(), since the it should be clear if driveleft is enabled or not, and it is called only a single time. ding_t::init is not the right place, since trees and all other stuff rarely overtakes ...

When I tried to do this, in that place, get_tile_raster_width() gave me a different value than afterwards.  So, I programmed another function (set_overtaking_offsets()) and placed it afterwards.  I don't know if the place I chose is the best.

Quote from: prissi on September 10, 2008, 07:21:00 PM
[...]
I would also not work in hop(). Use automobil_t::betrete_feld() (since it is car specific.) to update convoi counter.

Done.

Quote from: prissi on September 10, 2008, 07:21:00 PM
And the check for overtaking should by probably better done in a step and not in a sync_step. Look at the way trains (or airplanes) are doing it: They use step for this, becuase during a sync step vehicles are moved in random order (and it is time critical). The trick is: They retrun false for the next tile free check, but the do not reduce the speed. Next time, (during a step) they check if the road is really blocked.

This, I don't really understand well.  The overtaking test is done in automobil_t::ist_weg_frei.  This is only called from convoi_t::step() in cases CAN_STARTx and WAITING_FOR_CLEARANCEx.  The function is not called from convoi_t::sync_step().  I've seen the waggon_t::ist_weg_frei() implementation and can only see that it separates the first cases (CAN_STARTx).  Is that what you meant?

Formatting rules have also been observed.  I will now try with avoiding frontal crashes, then with measuring more exactly in diagonals.


PatrickN

isidoro, I hope you realize that if this ends up working well enough to find its way to the official release, you may become a minor hero to all simutrans players. :)  I will nominate you for one of those monuments.

Painter, in and out of retirement.

prissi

To avoid the said situation with the pure virtual call I suggested to make get_screen_offset() a virtual function. This way it would be only only called for cars, if they are cars. Otherwise the basis get_screen_offset() is called.

The system with step is the following:
The car sees that there is a car in front.
Then, it checks the convoi state => cnv->is_waiting()==true => we are in a step
If akt_speed>16 (not stopped): Try to overtake
If overtaking fails return_speed->0 if suceed return simply true.

During a step however, vehicle may move, and vehicle may jitter a little bit before overtaking. Therefore, keep it to the sanc_step first, and then lets profile it.

isidoro

Quote from: PatrickN on September 12, 2008, 01:58:00 AM
isidoro, I hope you realize that if this ends up working well enough to find its way to the official release, you may become a minor hero to all simutrans players. :)  I will nominate you for one of those monuments.

Thanks, PatrickN.  You are very kind.  But let's not "sell the eggs before buying the hens"  :D  And a better candidate, if this has a happy ending, will surely be prissi because of his patience with my endless questions.  And talking about the king of Rome...

Quote from: prissi on September 12, 2008, 10:25:27 AM
To avoid the said situation with the pure virtual call I suggested to make get_screen_offset() a virtual function. This way it would be only only called for cars, if they are cars. Otherwise the basis get_screen_offset() is called.

Done.  Now code is much cleaner, I think.  My knowledge of Simutrans code is not deep, together with the death of many (the least fitted, I hope) of my neurons with lots of "happy hours" and the like, makes me not understand the sync_step/step dichotomy.  So, I decided to postpone that to the end.  In this version of the patch calculation has been adjusted and hopefully overtaking is done well, even for diagonals.

Some code has been added to check for facing traffic but it doesn't still work fully and needs debugging. I will do that next and also try to make city traffic overtaking possible.

Some other things have been fixed:
Quote from: prissi on September 10, 2008, 07:21:00 PM
Also the check for stree speed should just check if the car in question can still go with its maximum speed. I do not worry about 80kmh limit, if my bus runs only 75kmh ...
[...]
is_moving() will indeed report all moving stuff, no matter what direction. You can check for facing traffic (since you do not have crossings) easily by calculationg the direction on this tile (from previous and next coordinate) and the use ribi_t::rueckwaerts() to get the reverse. Any vehicle with this fahrtrichtung will come against you.
[...]

Both things should be done by now.  One question, though.  When checking for facing traffic, I do something like:

      grund_t *gr=welt->lookup(pos);
[...]
      const uint8 top = gr->gib_top();
      for(  uint8 j=0;  j<top;  j++ ) {


Should that loop start in 0 or in 1.  I've seen some code starting in 1 and I don't know why.


prissi

#9
The magic is in dingliste. SOme things need to be drawn before other things. (This is due to sorting order for drawing.) First is of course the way (but in old versions, waylist were not part of dingliste.)

And I though on your comments with the flag: THis might be useful, if you want to make citycars overtake, since those would use this routine too. But before more neurons die, I rather try the current state.

And the calculation for the direction needs to look one tile ahead (for diagonals), i.e. old_pos, next pos ...

isidoro

Quote from: prissi on September 13, 2008, 12:11:38 PM
The magic is in dingliste. SOme things need to be drawn before other things. (This is due to sorting order for drawing.) First is of course the way (but in old versions, waylist were not part of dingliste.)

So, it is safe to start the loop in 1 (since 0 is the ground tile image), right?

Quote from: prissi on September 13, 2008, 12:11:38 PM
And I though on your comments with the flag: THis might be useful, if you want to make citycars overtake, since those would use this routine too. But before more neurons die, I rather try the current state.

No problem.  My neurons have problems with alcohol only.   ;)   I've taken the flag back to life again.  It dies, it is born, it dies...  Following your advice, now city cars can be overtaken.  It shouldn't be difficult now to make them overtake too. But I need to know where to place the can_overtake check.  Again, we have a sync_step() and a ist_weg_frei() to program it.  I'll try to investigate it again, but any help would be appreciated. 

In order to make easy to make city cars and automobiles overtake, I've created a new class overtaker_t in simconvoi.h.  Classes convoi_t and stadtauto_t inherit from it.

Quote from: prissi on September 13, 2008, 12:11:38 PM
And the calculation for the direction needs to look one tile ahead (for diagonals), i.e. old_pos, next pos ...

That's done.  Now, cars are more proficient overtaking and rarely crash.  I've tried the patch with a saved game and see the first cars overtaking "live"   :D


prissi

By the way, citycars have no route. Thus, as long as all way ribits are twoways, citycars could just check by checking next tile until exhausted.

I am currently ill and on a conference next week, thus I am not sure, if I can finish integration of the patch. Making an extra class sound like a good idea for simutrans, I thing. (Without haveing looked into the code ... )

Ashley

This all looks very cool, should allow for the construction of dual carriageways too with one-way signs, very cool change :)
Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

prissi

Just on think when looking at it: Perhaps that has sign could be ignored for one way signs or unimportant maxspeed signs? And maybe no crossing (is_crossing checks only for railway crossings, to check for normal crossings, you better use ribit_t::is_twoway(ribi) for the masked ribi.

And the overtaker class should rather get a new cc/h file, since city cars have no convois ... and both, simvehikel.cc and smconcoi.cc are already quite long.

Anyway, more next week end.

isidoro

Thanks, Timothy.

Quote from: prissi on September 14, 2008, 10:03:39 AM
By the way, citycars have no route. Thus, as long as all way ribits are twoways, citycars could just check by checking next tile until exhausted.

This patch is a first attempt with that.  Now city cars may overtake.  But must be debugged.  BTW, is there a way of knowing the length of a city car?

Quote from: prissi on September 14, 2008, 10:03:39 AM
I am currently ill and on a conference next week, thus I am not sure, if I can finish integration of the patch. Making an extra class sound like a good idea for simutrans, I thing. (Without haveing looked into the code ... )

Next, apart from some debugging, I will try to avoid the overtaken to stop due to the overtaker, if possible.

I will also have less time next week.  But there is no hurry, is there?  Take care and get well, prissi.

isidoro

Sorry for double posting.  This should be a working version of the patch.  Some errors have been corrected:

  • City cars now overtake in diagonals and everywhere
  • Overtaken vehicles now don't stop when being overtaken
  • Multi-vehicle convois are now properly measured and hopefully properly being overtaken

In the attached savegame, if you use a patched executable, you can see "The king of the road", a green city vehicle overtaking nearly everything  :D.

I'm concerned about performance, though.  If you try it, tell me.

Quote from: prissi on September 14, 2008, 06:49:42 PM
Just on think when looking at it: Perhaps that has sign could be ignored for one way signs or unimportant maxspeed signs? And maybe no crossing (is_crossing checks only for railway crossings, to check for normal crossings, you better use ribit_t::is_twoway(ribi) for the masked ribi.

And the overtaker class should rather get a new cc/h file, since city cars have no convois ... and both, simvehikel.cc and smconcoi.cc are already quite long.

Feel free to change whatever you like, prissi.  You have a much deeper knowledge of Simutrans source code than I have.  I think you're right about the signs (if it is not heavily time-consuming).  And I didn't know that the crossing check was for railway only.  I understand ribis by now but don't know what is a masked one.

I agree again with the new cc/h file, but if I change my working copy, can I submit a patch with new files?  I'm new to svn.

wernieman

For with Version is the patch?

Do you need a "nightly" for it?? ;o)
I hope you understand my English

IgorEliezer

Quote from: wernieman on September 15, 2008, 08:58:25 PMDo you need a "nightly" for it?? ;o)

A Fun Nightly with this fun patch would be nice. ;)

VS


My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

isidoro

I've branched in r2011, but I have tried it with r2022 and works the same.  A patched nightly would be nice.  At least for Windows.  I cannot produce it.  I left the "dark side of the force" time ago...   ;D

wernieman

Just look at the nightly-Webside ...

http://www.wernieman.de/simutrans/index.en.html

Look there for the:
sim-....._2008-09-15_v100.1_r2022-overpatchV7.zip

But ... I don´t testet it ...
I hope you understand my English

VS


My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

vilvoh

#22
Could you please upload some screenshots of that glorious moment? Just to ensure I'm not dreaming.... ;D

Escala Real...a blog about Simutrans in Spanish...

isidoro

Quote from: wernieman on September 16, 2008, 09:55:11 AM
Just look at the nightly-Webside ...

I've tried it with Wine and works fine.  Thanks!

PatrickN

Quote from: vilvoh on September 16, 2008, 10:56:34 AM
Could you please upload some screenshots of that glorious moment?  ;D Just to ensure I'm not dreaming....
I'd say a youtube video would be more appropriate. :)

Painter, in and out of retirement.

DirrrtyDirk

But why? ??? There is a nightly version available that has this patch included - so everyone should be able to see it for himself live not just on picture or video...
  
***** PAK128 Dev Team - semi-retired*****

PatrickN

I downloaded the nightlys for windows and they won't run.

Painter, in and out of retirement.

VS

Call me an ungrateful bastard, but when it is finally witnessed in person, the vehicles jumping to opposite lane aren't that much of great show ;) Nevertheless it is important improvement and also another proof that Simutrans liiiiives!

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

DirrrtyDirk

Sure is - and my windows version worked without a problem.
  
***** PAK128 Dev Team - semi-retired*****

vilvoh

#29
This is great!!!  ;D...thanks very much Isidoro and Prissi for your work. Nominated for the Couple of the Year Awards!!


P.S: the video is on the way... ::)
P.S. II: Other thing, Do you think that this patch has posibilities to be included in the official release? After polishing it, of course...

Escala Real...a blog about Simutrans in Spanish...

VS

I can't really speak for prissi, but as far as I can tell, all involved parties aim for it to go in.

If its addition doesn't drain too much computing power and doesn't obscure codebase, why not? Plus it requires no new graphics. So, this is 100% usable from the moment it is merged into code, just by itself...

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

DirrrtyDirk

Also, judging by the degree of interest that prissi has shown so far, I would not rule the possibility out...  ;)
  
***** PAK128 Dev Team - semi-retired*****

VS

Dirk, do you ever sleep? I probably don't :)

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

DirrrtyDirk

Sure I do - just not yet.  ;D Right now my life's rhythm is quite out of sync with daylight cycles - but that's probably going to change again soon.  ;)
  
***** PAK128 Dev Team - semi-retired*****

vilvoh

Quote from: PatrickN on September 16, 2008, 09:12:30 PM
I'd say a youtube video would be more appropriate. :)

Your wishes are orders for me.....video.......yeah!!


Escala Real...a blog about Simutrans in Spanish...