The International Simutrans Forum

 

Author Topic: Proposal for developping two-lane one-way roads  (Read 25519 times)

0 Members and 1 Guest are viewing this topic.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Proposal for developping two-lane one-way roads
« on: January 05, 2012, 06:23:20 PM »

After analyzing the code and the brainstorming phase, this is my proposal.  I hope you are not too deceived:
  • To give the possibility of normal roads to be one-way with vehicles moving freely between the two lanes.
  • The proposal does not include, though a new separate project may be opened later, if wanted, to implement a new kind of way: freeway_t.  This way would have additional features and intrinsic different behavior from normal roads to qualify it as a new different way type:
    • they will be multilane with no restrictions (two, four, six, etc. adjacent lanes in the same direction)
    • sharp curves or slopes, intersections, and crossings will not be allowed
    • special ramps or bridges would be available with less slope and curvature for the main road to go up or turning right or left
    • entries and exits will be special, the same applies to increase and reduction of the number of lanes, etc.
    • the routing would be a mix between roads (in fact, we would have directions in freeway_t as well) and sea (free roaming)
    • the right side of the road is preferred (and these tiles are what appears in the route of the vehicle), though the vehicle may occupy other lanes too: would be excited if you allow me that physicist's joke
      This requisites would make freeway_t much more different from normal roads not only aesthetically, but also in terms of game rules: they would require a lot of space, more or less flat, etc., just like their real life counterparts

In fact, up to now, only what the proposal is not about, has been stated.  This is what is intended:
  • normal roads may only have two lanes, just like now, but may be one-way with the traffic occupying both lanes
  • there is no change in the way they are built: there can be curves, slopes and crossroads of any kind, just like now
  • there will not be special access ramps.  If needed, they should be done by normal means: artificial slopes, bridges, etc.
  • one-way and two-way roads would mix in a natural way, with no special restrictions
  • overtaking is preserved for two-way roads.  Though, as a technical side-effect overtaking would be smoother with no jumping as it happens now
  • new road signs will mark the directions of the road where the player considers suitable.  They will draw arrows on the floor showing the available directions for each lane.  Optionally, if the tile is next to a crossroads, directions allowed when entering the crossroads are drawn
  • in construction mode, those marks will be shown for all one-way roads to make construction life easier
  • when building a one-way road, the direction of dragging marks the direction of the road
  • if dragging is done over an existing one-way or two-way road, the direction or type of road is changed with no or small cost
  • additionally, a new sign will be added (marked in real life on the road surface with yellow crossing lines) forbidding cars to occupy these tiles unless they have a free exit, i.e., they are not allowed to stop there.
  • the project does not include in this phase, though it may be done in the future if wanted, to have one-lane only road (with the other lane filled with grass, sidewalk, etc.)


And now, the technical details for the coders' eyes only  8):

Road (not crossroads) changes

One-way roads will be marked by an additional flag: weg_t::IS_ONE_WAY.

When building a new of those roads, ribi mask is set so that the only exit is allowed and rest forbidden.  This way, no changes have to be made to the routing algorithm.


Vehicle and convoy changes

Now, a convoy may be overtaking or not.  With the new behavior, the vehicle may be in one of four states (an additional bit is required):
  • normal: not overtaking (value=0)
  • start overtaking: at the entrance of this tile, the vehicle is on the right lane, at the exit, it is on the left lane (value=1)
  • overtaking: the vehicle is fully on the left lane (value=2)
  • end overtaking: at the entrance of this tile, the vehicle is on the left lane, at the exit, it is on the right lane (value=3)

The naming can be preserved although, when in a one-way road, the vehicle on the left lane, may not be overtaking and just driving.

The necessity of these smooth transitions will be made clear when talking about crossroads.

That would make the shortest possible overtaking two tiles long, with one tile for starting, no overtaking tiles and one tile for ending...  But we gain in smoothness.


Crossroads

When thinking about the severe problem of crossroads I came to a solution on my own that, at the end, I think it is a reworking of TurfIt ideas, thus my joke of asking him to get rid of them...  ;)

The idea is to use four additional flags for each road tile (or if it is too much, only needed at crossroads).  These four flags are used together with a subdivision of the tile in four subtiles (I would call them Farthings, to honor the four Farthings of the Shire in The Lord of the Rings).  This would be a tile:


           *   North tile    *
*  *  *  ***********************  *  *  *
           *        |        *
           *  NW    |  NE    *
           * Farth. | Farth. *
West tile  *--------+--------*  East tile
           *  SW    |  SE    *
           * Farth. | Farth. *
           *        |        *
*  *  *  ***********************  *  *  *
           *   South tile    *


The Farthing flags in the tile are used to show which of the Farthings are occupied at the moment by relevant vehicles.  Before entering a crossroads tile, a convoy must make sure that the farthings it needs depending on from where it comes and to where it wants to go, are free.

For example, a vehicle coming from the South tile, right lane, that wants to turn right to the East tile, right lane, would only need the SE Farthing.

To speed things up, a static table with the farthings needed for all possibilities would be looked up by the vehicle.  There are 8x6 possible entries in the table and there should be two of such tables to account for the driving-on-the-left issue.

If we denote S, the right lane south tile and S* the overtaking (left) lane, these are the contents of that table for vehicles coming from the south:

           * N* lane  N lane *
           *        |        *
           *   North tile    *
*  *  *  ***********************  *  *  *
           *        |        *
  W lane   *  NW    |  NE    *   E* lane
           * Farth. | Farth. *
West tile  *--------+--------*  East tile
           *  SW    |  SE    *
 W* lane   * Farth. | Farth. *   E lane
           *        |        *
*  *  *  ***********************  *  *  *
           *   South tile    *
           *        |        *
           * S* lane  S lane *

Movement:
          ..                 ..
  S ->E   .X         S*->E   XX

          .X                 XX
  S ->E*  .X         S*->E*  X.

          .X                 XX
  S ->N   .X         S*->N   X.

          XX                 X.
  S ->N*  .X         S*->N*  X.

          XX                 X.
  S ->W   .X         S*->W   X.

          ..                 ..
  S ->W*  XX         S*->W*  X.


This way of doing things, may be used only in crossroads or, more generally, in all pieces of roads.  Besides those four more bits per each tile, it has the problem of stale reservations.  Care should be taken for it.

What has this to do with overtaking, and specially, smooth overtaking?  The idea is very simple.  Imagine a vehicle going, in our terminology from S* to E.  Transitions from * lanes to normal lanes would be end of overtaking transitions (named like that although it doesn't mean that it is always an overtaking).  The offsets applied to a convoy in that situation would be:
  • full overtaking offsets at the entrance of the tile (steps traveled =0)
  • no offsets at the exit of the tile (steps traveled equals to tile lenght in steps, steps_next)
  • an interpolation of the two for positions in between

That would make more or less smooth transitions for overtaking as well as for crossroads.


Non blocking intersections

I would also add a new flag to roads (that would make a total of 6 new flags): weg_t::IS_BLOCKING_FORBIDDEN.  Only crossroads marked with this flag would benefit from TurfIt algorithm that makes a car stop if it cannot leave that tile without being stopped.  That feature would incorporate that into the game, so that the player is responsible of placing those signals in conflicting crossroads to try to avoid jams.


And that's it, more or less.  If you consider these ideas worth of doing, I can plan: milestones, yardstones and inchstones.  There would be, as it is a tradition in Computer Engineering, two phases:
  • A first refactor phase, with no new functionality and only inside work done, preparing the way to the second phase
  • A second phase, with more functionalities, added one by one

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9568
  • Languages: De,EN,JP
Re: Proposal for developping two-lane one-way roads
« Reply #1 on: January 05, 2012, 09:50:05 PM »
I would have dedicated way with their own system type for one way roads. Signs will be not correctly overlaid and quite ugly. Also the sign system will not work with drive on left, where the arrow would be next to the road.

Also any crossing should not be blocked. It is also required by the law ;) No honestly, hassle with two kinds of crossing is too much for 99% of the average players I fear. I fail to see an additional advantage from such a thing too.

About reservations of your farthing (whatever this is, maybe the hobbits of Auenland?) Please use a better term which makes its meaning immediately clear. (sub_ribi_t?)

Back to reservations. I very very strongly advocate against it. They have be a constant pain with trains, and trains never ever disappear like that as citycars do frequently.

But I see a conceptual problem: Overtaking times depend on the overtaker. The reservation ahead needs to be done by the overtaken. And it needs to be renewed every tile, since it can accelerate etc. I am not convined that this will not take much more CPU power than the easier check for free tiles would require. I am sceptic, but that can only be shown be implentation.

But how citycars enter here? Citycars do not know where they go until directly at a crossroad. Then they choose an emtpy way at that time. Thus the could never reserve a way in advance and any prediction of overtaking and the like is difficult.

But maybe I have misunderstanding here.


Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #2 on: January 05, 2012, 11:46:55 PM »
I would have dedicated way with their own system type for one way roads. Signs will be not correctly overlaid and quite ugly. Also the sign system will not work with drive on left, where the arrow would be next to the road.

Do you mean a new weg_t::system_type instead of a weg_t new flag?  I don't understand the difference between them very well.  Please explain.

Talking about arrows on the ground, the idea is not to be forced to draw them on each tile, which doesn't look good to me, but that it were a choice of the player.  The image would be a generic arrow for each direction and offsets would be applied, much in the way done with signals and traffic lights...

Quote
Also any crossing should not be blocked. It is also required by the law ;) No honestly, hassle with two kinds of crossing is too much for 99% of the average players I fear. I fail to see an additional advantage from such a thing too.

No problem.  It was just an idea.  It was to reflect this kind of road sign named "box junction":
http://www.ukdrivingtheory.com/traffic-signs-road-markings.php

I think it means:  you should not drive there unless you are sure you are not going to stop on it, but I'm not sure.

Quote
About reservations of your farthing (whatever this is, maybe the hobbits of Auenland?) Please use a better term which makes its meaning immediately clear. (sub_ribi_t?)

I don't know if that name is really clearer   ;D ...  sub_tile may be a better name, since they have nothing to do with allowed or forbidden directions.  A pity for such a poetical term, farthing... sigh... This is a German game,  it must be thoroughly rational...   ;)

Quote
Back to reservations. I very very strongly advocate against it. They have be a constant pain with trains, and trains never ever disappear like that as citycars do frequently.

I know of those problems and I pointed at them.  One has to be careful in the destructors to free the resources, you're right.  But I think they give a lot of simplicity and, maybe, performance...  To check for a free tile, one only has to check some bits instead of looking for vehicles, checking directions, etc.

There is a harder issue you maybe have not spotted: convoys are made of vehicles and those reservations should be done when the head vehicle is entering a new tile and freed when the tail vehicle is leaving a tile.  And sometimes, the convoy may have reservations in two tiles...

Quote
But I see a conceptual problem: Overtaking times depend on the overtaker. The reservation ahead needs to be done by the overtaken. And it needs to be renewed every tile, since it can accelerate etc. I am not convined that this will not take much more CPU power than the easier check for free tiles would require. I am sceptic, but that can only be shown be implentation.

Overtaking behavior continues as it is now.  You only reserve the sub_tiles you are on.  Not the one you are going to visit in the future.  Sub_tile bits only indicates the presence of a vehicle there at that moment.

Quote
But how citycars enter here? Citycars do not know where they go until directly at a crossroad. Then they choose an emtpy way at that time. Thus the could never reserve a way in advance and any prediction of overtaking and the like is difficult.

But maybe I have misunderstanding here.

The same concept applies.  The city car chooses its next tile and it checks if that tile is free by looking at the sub_tile bits.  I can further explain if necessary.

So, prissi, you didn't like any of the concepts expressed above?

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #3 on: January 06, 2012, 03:28:10 AM »
What is the purpose of adding flag: weg_t::IS_ONE_WAY? i.e. where would it's value be useful? If the ribis are set, the info is already there.

Smooth lane changes. Fine, but if applied to the regular overtaking, then it would have to start the transition a tile sooner such that it's already in the overtake lane before entering the tile with the overtaken. And similarly at the end when transitioning back will need an extra tile there too. Extra required tiles will reduce the chances of an overtake even more.

Crossroads (intersections as I call them).  Reservations were certainly something I considered when overhauling the weg_frei and no_cars_blocking routines. There's some cases still where cars can end up where they don't belong that would easily be solved by use of reservations. But those cases are generally rare and not overly impactive when they do occur, hence the trouble of adding a reservation system wasn't worth it IMO. For implementing avenues, it might be the only feasible way to simplify the logic some, but they bring a whole host of issues along with them. An extremely detailed plan is strongly suggested before starting down this path. (save/load is a huge issue).

  And sometimes, the convoy may have reservations in two tiles...
Actually they may have reservations in 6 tiles. Consider a road train convoi made up of 4 16 length vehicles on the diagonal...

Your Farthings are too simplistic, even for plain two way roads. Consider a Northbound car turning left, this reserves the SE and NW Farth. Eastbound and Westbound right turners can still reserve NE farth, SW farth, and share the intersection. Great.  But a Eastbound left turner would also grab SW and NE farths and proceed despite that movement being in conflict with the northbound left turner. More farths are required to handle this. Now go through all possible paths with the various one-way, two-way roads intersections identifying all conflicting/non-conflicting and .....

For intersecting avenues, a 2x2 block of tiles is what forms the 'real' intersection. The reservations must extend through that.

All intersections *MUST* be non-blocking.

All intersections *MUST* be non-blocking.

Again? All intersections *MUST* be non-blocking. Nobody enjoys trying to untangle a deadlock caused by cars moving to places they shouldn't. If you do, have I ever got the map for you.  ;)

How are diagonal roads handled? Remember internally there are no real diagonals, just tiles zig-zagging. In your diagram, the S tile, Central tile, and E tile could be just that forming a 90 deg turn, or the exact same tile layout may be part of a diagonal road instead. The allowable paths through the tile would be different for the two cases. e.g. For the diagonal road, both lanes need to move straight. Car in S lane through  SE farth ending up in E lane simultaneous with a car in S* land through SW Farth and NE Farth ending in E* Lane. However, if this is a 90 deg intersection instead, then the car in S lane might go SE Farth,  NE Farth, N lane. Now the car in the S* lane must be forbidden from making the right turn into E* lane as that conflicts with the other cars movement. My point here is that identical tile layouts require different movement rules. How can this be detected and handled?
« Last Edit: January 06, 2012, 03:36:19 AM by TurfIt »

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4603
  • Languages: EN, DE, AT
Re: Proposal for developping two-lane one-way roads
« Reply #4 on: January 06, 2012, 09:12:10 AM »
I really like the proposal.
Do you mean a new weg_t::system_type instead of a weg_t new flag?  I don't understand the difference between them very well.  Please explain.
system_type is a property of the way's descriptor (weg_besch_t) such as 'elevated', 'river', 'tram track'; whereas a weg_t::flag can potentially be assigned to any kind of road. The problem with system_type: how to mark an elevated highway? A flag seems then to be the better alternative.

My idea to construct one-way roads: Create a special sign 'Start of highway', all road tiles after this sign automatically become one-way. Imho the gui & construction discussion can be postponed to the point, where the actual movement code is ready.

Farthings: Vehicles driving diagonally will reserve 1 or 3 tiles in an alternating way. I see no problems there.

A new more fine-grained reservation system for roads may allow vehicles driving closer to each other. In particular in traffic jam situations.

Crossroads: With one way roads, one may have crossings with exactly one incoming and two outgoing lanes (or vice-versa). Such crossings are allowed to block without creating deadlocks (?) at least some farthings / lanes can be blocked safely (those lane that do not split / merge).

As to actual code changes: I suggest creating a fork at github.com

In the preparation phase, we could also make a massive translation of German code entities.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9568
  • Languages: De,EN,JP
Re: Proposal for developping two-lane one-way roads
« Reply #5 on: January 06, 2012, 09:43:24 AM »
About the farthing: I had to maintain once a program with stuf named Max, Moritz, Important, ...

It is fun at first, but were off pretty quickly. ALso farthing is only gasp by native british, I fear, since I have no idea what you are talking about. Even though I read Lord of the rings but the german edition.

System type: Just like 1 is elevated way, 10 could be oneway. That would also remove the need for a flag. (So no new falgs needed anymore ... ) Also the one way roads could have different crossings marks and so on.

But back to implementation. I though you want to use the subtiles also to find out whether a car can be overtaken or not. For this purpose any car has to maintain a row of reservations ahead to mark those as needed (if it cannot get thos, it needs to reduce speed ... ) All well for convois, but for citycars this is not possible at crossroads and the like.

An another thing you did not mention at all: How would you distribute cars between those two lanes? I think this is most important for a working system.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #6 on: January 06, 2012, 03:16:03 PM »
A lot of questions, and very interesting ones:
What is the purpose of adding flag: weg_t::IS_ONE_WAY? i.e. where would it's value be useful? If the ribis are set, the info is already there.
True, but you have to look at the next tile ribis to know if there is incoming traffic or not.  The flag would speed up things and also could be used to choose different images, marks, draw arrows when building, etc.
Quote
Smooth lane changes. Fine, but if applied to the regular overtaking, then it would have to start the transition a tile sooner such that it's already in the overtake lane before entering the tile with the overtaken. And similarly at the end when transitioning back will need an extra tile there too. Extra required tiles will reduce the chances of an overtake even more.
Not necessarily.  The interpolation may be changed to accommodate for that.  For instance, an end of overtaking transition may be like this:
  • overtaking offsets at the entrance and up to half of the tile
  • no offsets at the end of the tile
  • interpolation in the other positions

This patch is five lines long to do and it doesn't interfere with the rest of the code.  If you agree, I can give it a try...
Quote
Crossroads (intersections as I call them).  Reservations were certainly something I considered when overhauling the weg_frei and no_cars_blocking routines. There's some cases still where cars can end up where they don't belong that would easily be solved by use of reservations. But those cases are generally rare and not overly impactive when they do occur, hence the trouble of adding a reservation system wasn't worth it IMO. For implementing avenues, it might be the only feasible way to simplify the logic some, but they bring a whole host of issues along with them. An extremely detailed plan is strongly suggested before starting down this path. (save/load is a huge issue).

Actually they may have reservations in 6 tiles. Consider a road train convoi made up of 4 16 length vehicles on the diagonal...
 
I like the word crossroads to clearly separate that from crossings of two different way types.  And also I would not call my method reservations.  It is more an occupation, since the vehicle is really there.  For the rest, I fully agree.
Quote
Your Farthings are too simplistic, even for plain two way roads. Consider a Northbound car turning left, this reserves the SE and NW Farth. Eastbound and Westbound right turners can still reserve NE farth, SW farth, and share the intersection. Great.  But a Eastbound left turner would also grab SW and NE farths and proceed despite that movement being in conflict with the northbound left turner. More farths are required to handle this. Now go through all possible paths with the various one-way, two-way roads intersections identifying all conflicting/non-conflicting and .....
I was aware of that problem.  If you look closely to the example table of my first post, for a car heading north (hence coming from the south), the S->W transition reserves three subtiles to avoid that.  Not all cases are taken into account, but your present system doesn't either...  ;)
Quote
For intersecting avenues, a 2x2 block of tiles is what forms the 'real' intersection. The reservations must extend through that.
Not really.  The problem is that priss and you still see them as reservations.  They are not.  Your four tile look ahead algorithm is preserved as it is.  This reservations only indicates if there is a car or not in the path the car intends to follow.  It is more a replacement for no_cars_blocking and parts of ist_weg_frei than the whole of the latter.
Quote
All intersections *MUST* be non-blocking.

All intersections *MUST* be non-blocking.

Again? All intersections *MUST* be non-blocking. Nobody enjoys trying to untangle a deadlock caused by cars moving to places they shouldn't. If you do, have I ever got the map for you.  ;)
I'm not deaf, TurfIt.  Errh,  I mean, blind...   ;)
That is an optional part, as I said above.  Your next issue is more interesting, though:
Quote
How are diagonal roads handled? Remember internally there are no real diagonals, just tiles zig-zagging. In your diagram, the S tile, Central tile, and E tile could be just that forming a 90 deg turn, or the exact same tile layout may be part of a diagonal road instead. The allowable paths through the tile would be different for the two cases. e.g. For the diagonal road, both lanes need to move straight. Car in S lane through  SE farth ending up in E lane simultaneous with a car in S* land through SW Farth and NE Farth ending in E* Lane. However, if this is a 90 deg intersection instead, then the car in S lane might go SE Farth,  NE Farth, N lane. Now the car in the S* lane must be forbidden from making the right turn into E* lane as that conflicts with the other cars movement. My point here is that identical tile layouts require different movement rules. How can this be detected and handled?
Cars make their, let's name them from now on, subtiles occupations based on where they are and where they are going.  So you example doesn't make sense.  A car coming from south and turning east will occupy SE subtile only.  A car going from S to N, occupies SE and NE, and so on.  Diagonals are not a problem since they are only a painting-trick (from the point of view of the motor of the simulation, the vehicle is really going zig-zag and occupations are made accordingly).

The important thing is to make S->E compatible with S*->E*, S->W compatible with S*->W* and so on.  But that is a very good point you noticed...

[...]
My idea to construct one-way roads: Create a special sign 'Start of highway', all road tiles after this sign automatically become one-way. Imho the gui & construction discussion can be postponed to the point, where the actual movement code is ready.
I'm more for a local approach.  That is: that you know in the place if a tile is one-way or not.
Quote
A new more fine-grained reservation system for roads may allow vehicles driving closer to each other. In particular in traffic jam situations.
I had that in mind too.  But maybe for a second phase...
Quote
[...]
In the preparation phase, we could also make a massive translation of German code entities.
That would be a great idea!  The language barrier I'm sure is keeping good coders apart from helping...  You are not aware of it because you understand the words...

About the farthing: I had to maintain once a program with stuf named Max, Moritz, Important, ...

It is fun at first, but were off pretty quickly. ALso farthing is only gasp by native british, I fear, since I have no idea what you are talking about. Even though I read Lord of the rings but the german edition.
From a small corner of my heart, but I have to agree with you.  In fact, a farthing is, paying attention to Merriam-Webster dictionary: a former British monetary unit equal to 14 of a penny
 
But in connection with Tolkien's novel:
Quote
The original parts of the Shire  were subdivided into four Farthings ("fourth-ings" or "quarterings"): the Three Farthing stone marked the point where the borders of the Eastfarthing, Westfarthing and Southfarthing of the Shire came together, by the East Road.
It means more or less quarter, but you have to have that cultural background to understand it, I agree.
Quote
[...]
An another thing you did not mention at all: How would you distribute cars between those two lanes? I think this is most important for a working system.

In fact, my idea is quite simple to implement:  a car follow its route in its present lane, if it finds a car ahead and it is a two-way road, nothing is changed from present behavior, tries to overtake or stops.  If it is on a one-way road, it looks if it can change lane and, if so, it does.

This can be refined with a sort of gravity that makes the cars return to the right lane when possible...  Since transitions (change of lanes) occur one per tile maximum, the car is not going to continuously bounce from one lane to the other...


Offline Fabio

  • Devotee
  • Administrator
  • *
  • Posts: 2898
  • The Pak128 Guy
    • Visit me on Facebook
  • Languages: EN, IT, RO, FR
Re: Proposal for developping two-lane one-way roads
« Reply #7 on: January 06, 2012, 06:51:51 PM »
Great proposal! I have a few side issues too.
~ Working with vehicle motion, you think you could change the behaviour so that if a vehicle finds a slower one in front and *cannot* overtake, instead of stopping slows down to the speed of the vehicle in front?

~ In cities there can be visually and gamewise 3 lanes: two at sides used by cars and a central one with tram tracks. Given that road vehicles code can handle only 2 lanes, I would like to have the road divided in 9 subtiles and a possibility to indicate which 2 lanes are used for traffic, mono- or bi-directionally, and which one to keep empty and be possibly used to lay a tram track on.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9568
  • Languages: De,EN,JP
Re: Proposal for developping two-lane one-way roads
« Reply #8 on: January 06, 2012, 09:32:40 PM »
fabio: Please keep the wishes out of the development and implementing discussion. Open a new extension request, if needed. I want to avoid turning this again into a wishlist, rather than focussing on the implementation.

The IS_ON_WAY would not be needed, if the besch has system_type=10 or whatever you choose (only 0,1,7, and 255 have a meaning here). An I agree with isidoro that a sign might not suffice; just imageing the end sign gets deleted or their are paris of entry-exit combinations.

Quote
In fact, my idea is quite simple to implement:  a car follow its route in its present lane, if it finds a car ahead and it is a two-way road, nothing is changed from present behavior, tries to overtake or stops.  If it is on a one-way road, it looks if it can change lane and, if so, it does.

This can be refined with a sort of gravity that makes the cars return to the right lane when possible...  Since transitions (change of lanes) occur one per tile maximum, the car is not going to continuously bounce from one lane to the other...

Thus cars will try to go on the right lane again when passing has ended?

How a car determines if the left lane is free. It will just ignore traffic behind and go left or will it also look backwards?

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #9 on: January 06, 2012, 11:30:47 PM »
Thus cars will try to go on the right lane again when passing has ended?
It is a possibility.  I don't know if it would be convenient or not.

On one side, going back to the right is more or less the expected behavior on highways and make the problem you point out below smaller.  On the other side, in cities, driving lanes depend more on the route you intend to follow, but I don't know if that would be easy to simulate without looking too far in the route and wasting some precious CPU time...

Maybe that is a task for normal steps (not sync steps) to calculate and being cached in a variable of the convoy (something like lane_affinity)?
Quote
How a car determines if the left lane is free. It will just ignore traffic behind and go left or will it also look backwards?
I haven't thought about this until you have pointed out.  Occupations may be used again.  Upon entering a new tile, if the car cannot go forward and the other lane in the tile the vehicle is in and the following tile are free, then occupy the relevant subtiles of the latter tile and change lines.

I guess you are pointing out what would happen if a fast car is driving fast on the previous tiles of the lanes I'm going to change to.  Well, not very realistically, but it should stop.  Interestingly enough, that same thing happened to me last week when driving on the highway: I was on the overtaking lane overtaking a car and a truck and the car suddenly changed lanes and I had to brake seriously.  It is a miracle that I'm here...  We're nothing...


Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #10 on: January 07, 2012, 02:59:50 AM »

A new more fine-grained reservation system for roads may allow vehicles driving closer to each other. In particular in traffic jam situations.
Have tried this... Couple issues:
1) Greatly increases the weg_frei calls dealing with subtile positioning
2) Graphic alignment is all over the place with the vehicles. Even leaving 1/4 tile between their true positions, some would still graphically overlap.


In the preparation phase, we could also make a massive translation of German code entities.
If you mean the German comments, sure. If you mean renaming variables, to what end? IMO they're fine as is.
I still haven't sorted back out the half-assed renaming of einstellungen to settings... Now instead of just einstellungen and umgebung to keep straight, we get a third one (settings) to remember.


------------

The interpolation may be changed to accommodate for that.  For instance, an end of overtaking transition

This patch is five lines long to do and it doesn't interfere with the rest of the code.  If you agree, I can give it a try...
I see... cheating then! A faster transition would certainly reduce the probability of the two driving through each other if the passer isn't fully in the passing lane upon entering the passees tile. Really depends upon the lengths of the convois and relative positioning in the tile. Certainly worth a try, and is really a separate patch from one-way roads so...


I like the word crossroads to clearly separate that from crossings of two different way types.
crossroads/crossings rather close IMO. intersections/crossings, no so much. Consistent terminology would be nice, but as long as we all understand, doesn't matter.


And also I would not call my method reservations.  It is more an occupation, since the vehicle is really there. 
The OP did use that word. "it has the problem of stale reservations"  ;)
But I get what you're trying now, although am now unsure how occupations have a problem with stale reservations...  ???

Also, as occupations mean the vehicle is currently in that position, I don't see the gain from using farths. Just query the vehicle?


If you look closely to the example table of my first post, for a car heading north (hence coming from the south), the S->W transition reserves three subtiles
Which would then needlessly block the E*->N path.


to avoid that.  Not all cases are taken into account, but your present system doesn't either...  ;)   
Do you have an example? convois only as citycars are still in a world of their own!


It is more a replacement for no_cars_blocking and parts of ist_weg_frei than the whole of the latter.
I think from a performance standpoint, best to stick to the current system of calculating the info as required. The farth proposal does have the attraction of simplifying sections of these routines, but at the cost of updating the occupancy status on each tile for each convoi as they move, even if that information is of no current use since no other convois are nearby. Maybe the farth info would fit into a structure that's being accessed anyways, and hence be readily available in the cache anyways, probably not though. There's really no room to add things requiring extra memory accesses at the moment IMO.


  So you example doesn't make sense.  A car coming from south and turning east will occupy SE subtile only.  A car going from S to N, occupies SE and NE, and so on.  Diagonals are not a problem since they are only a painting-trick (from the point of view of the motor of the simulation, the vehicle is really going zig-zag and occupations are made accordingly).
A car travelling the NE direction actually travels N>E>N>E>N>E and so on. In this case, we have a straight diagonal road. I would expect cars in both lanes to be able to travel side by side straight down this road. In you diagram, this corresponds to S->E for the car in one lane and S*>E* for the other. No problem.
The same tile layout as this diagonal road could instead be an intersection. S>E is still valid for a car in the right lane to make a right turn. S>N is also valid for straight through. S*>E* which was valid for the diagonal is no longer ok for the intersection. Turning right from the left hand lane is forbidden.
How to handle this detection of allowable routes given the same tile layout?


This can be refined with a sort of gravity that makes the cars return to the right lane when possible...  Since transitions (change of lanes) occur one per tile maximum, the car is not going to continuously bounce from one lane to the other...
Good for highways, for cities???


On the other side, in cities, driving lanes depend more on the route you intend to follow, but I don't know if that would be easy to simulate without looking too far in the route and wasting some precious CPU time...

Maybe that is a task for normal steps (not sync steps) to calculate and being cached in a variable of the convoy (something like lane_affinity)?I haven't thought about this until you have pointed out.
Scanning ahead along the route to determine which lane to be in would be a basic requirement for avenues to work at all.



  Occupations may be used again.  Upon entering a new tile, if the car cannot go forward and the other lane in the tile the vehicle is in and the following tile are free, then occupy the relevant subtiles of the latter tile and change lines.
Some scheme that avoids the car just stopping would be better. If it starts trying to change lanes several tiles before it must be in the lane, that might work. Then only stopping when it must. Of course cars coming up behind might then change lanes to pass the stopped car. Or worse, two cars stopped side-by-side each trying to change to the others lane! Lot's of little issues like this to contend with.



Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #11 on: January 07, 2012, 12:31:36 PM »
[...]
If you mean the German comments, sure. If you mean renaming variables, to what end? IMO they're fine as is.
I still haven't sorted back out the half-assed renaming of einstellungen to settings... Now instead of just einstellungen and umgebung to keep straight, we get a third one (settings) to remember.
But I surely have more chances to understand a Chinese person walking down the street than einstellungen or umgebund.  Let's be serious...  If a certain translation was not completely accomplished, it doesn't mean that translation is not needed and have not been asked for several times from different people.

 If we want to favor a truly open development project, German is a serious issue.  Another thing is if we want to keep it for a more reduced set of developers.  But that is not a good strategy, imho.  You shouldn't be afraid of opening it.  What goes or not to the trunk is still a decision of head developers.  And if somebody comes and doesn't agree, all he has to do is a fork.  And time will tell who were right.
 
Quote
I see... cheating then! A faster transition would certainly reduce the probability[...]
I wouldn't call that cheating.  When developing the overtaking patch, I remember a not very polite comment about vehicles similar to frogs, jumping instead of overtaking.  There is a continuum of possibilities from the present behavior to interpolating an entire tile (half, quarter, tenth, etc.)  Maybe one of them is suitable...  If sometimes vehicles overlap a little, that is not news in ST.
Quote
[...]But I get what you're trying now, although am now unsure how occupations have a problem with stale reservations...  ???
Well, with these things, you always have to be careful.  An stale occupation would prevent other vehicles from driving there.  But by adequately freeing occupations at destructors there should be no problem...
Quote
Also, as occupations mean the vehicle is currently in that position, I don't see the gain from using farths. Just query the vehicle?
The idea is simplify all calculations.  If you don't use occupations, you have to query all the vehicles in the tile, look for directions, etc.  With railways everything is simpler because we have only one lane per tile.  But with roads, everything complicates a lot because we have two lanes.  Subtiles is a way to make roads look more like railways...
Quote
Which would then needlessly block the E*->N path.
I guess that you mean E->N is needlessly blocked in a S->W movement.  E*->N must be blocked by all means.  I don't see here such a big problem.  Moreover, what is your alternative for crossroads with different type of roads arriving at them and still sometimes a transition is by all means needed because the road the vehicle is going to is a two-way road?
Quote
Do you have an example? convois only as citycars are still in a world of their own!
You said that.  And I mean all kind of traffic, not just convoys.
 
Quote
I think from a performance standpoint, best to stick to the current system of calculating the info as required. The farth proposal does have the attraction of simplifying sections of these routines, but at the cost of updating the occupancy status on each tile for each convoi as they move, even if that information is of no current use since no other convois are nearby. Maybe the farth info would fit into a structure that's being accessed anyways, and hence be readily available in the cache anyways, probably not though. There's really no room to add things requiring extra memory accesses at the moment IMO.
Well I can admit a decrease in performance for memory issues if that means more cache misses, but not for updating 4 flags each time a vehicle hops...  Even those four flags may have no memory cost at all depending on architecture, since they may be accommodated in unused part of the memory of the object (i.e. if the object has an uint8, the system will probably reserve a uint32 or uint64 space for it...)

But I would say more...  Performance issues come in very big maps with a lot of traffic.  In those cases, the checks are very common and a bloated ist_weg_frei with lots of decisions and jumps (thus breaking the pipelines every time) is worse than the simple lookup of 4 bits...
Quote
A car travelling the NE direction actually travels N>E>N>E>N>E and so on. In this case, we have a straight diagonal road. I would expect cars in both lanes to be able to travel side by side straight down this road. In you diagram, this corresponds to S->E for the car in one lane and S*>E* for the other. No problem.
Or even N->W instead of S*->E*, if it is a two-way road.
 
Quote
The same tile layout as this diagonal road could instead be an intersection. S>E is still valid for a car in the right lane to make a right turn. S>N is also valid for straight through. S*>E* which was valid for the diagonal is no longer ok for the intersection. Turning right from the left hand lane is forbidden.
How to handle this detection of allowable routes given the same tile layout?
This has nothing to do with the issue in hands.  If we have this kind of intersection:

*   |   *
*   |   *
*       *******
*                E* lane
*                E lane
*       *******
*   |   *
*   |   *
  A   B

and A wants to turn right to the E* lane and B wants to go straight ahead, my system will prevent one of them from going on.  It has to wait, so that a crash will not happen.  Cars know other cars intentions and that is not realistic, but they do it now too...

You mean that A shouldn't go to E* in the first place, but that is something to be enforced somewhere else in the code if wanted at all.  For instance, not allowing turning left from the left lane and forcing a S*->E transition or, for instance, forcing all vehicles to move to the right lane when approaching a crossroads.
Quote
[...]
Some scheme that avoids the car just stopping would be better. If it starts trying to change lanes several tiles before it must be in the lane, that might work. Then only stopping when it must.
I don't think that is much different from current behavior.  Cars stop in Simutrans when they cannot advance.  It's just that.
Quote
Of course cars coming up behind might then change lanes to pass the stopped car. Or worse, two cars stopped side-by-side each trying to change to the others lane! Lot's of little issues like this to contend with.
 
The fist one to get the occupations of the next tile, will win and change lane.

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #12 on: January 07, 2012, 08:16:37 PM »
If sometimes vehicles overlap a little, that is not news in ST.
Vehicles overlapping/driving through each other was my main motivation to rework the weg_frei and ncb routines, to atleast minimize the occurances. IMHO new routines should continue trying to reduce these rather than add new. That said, I do agree using the first part of the shared tile to do a gradual lane change is good. So, let's see the patch..  ;D


If you don't use occupations, you have to query all the vehicles in the tile, look for directions, etc.  With railways everything is simpler because we have only one lane per tile.
I'm back confused between occupations and reservations again...
For occupations, are the subtile positions (formerly called farthings) marked as occupied only when a vehicle is actually on the position?
Or, when a vehicle enters a tile, it marks all subtile positions required for its journey through the tile as occupied? aka reserverations.



I guess that you mean E->N is needlessly blocked in a S->W movement.  E*->N must be blocked by all means.  I don't see here such a big problem.  Moreover, what is your alternative for crossroads with different type of roads arriving at them and still sometimes a transition is by all means needed because the road the vehicle is going to is a two-way road?
I think I've added confusion here as in this example I'm talking about applying the subtile occupancy to the existing two way roads with driving on the right.

To develop the current ncb routine, I mapped out all possible paths through the intersection, determined which ones conflict with one another, then reduced it all to the set of rules in the routine. This allows the maximum number of non conflicting movements to all be occupying the intersection at the same time. e.g two straight, two left turns, one straight + two right turns, one left + two right, four right. The proposal of four subtile positions would eliminate some of these possibilities. Hence why I said too simplistic, need more positions to cover all possible movements.

Adding oneway roads to the mix just means mapping out even more paths. Many more.


You said that.  And I mean all kind of traffic, not just convoys.
Citycars have their own weg_frei routine which has not been changed for the new logic. Hence, they still do a lot of the stupid stuff I fixed for the convois. On my todo list to revist...


But I would say more...  Performance issues come in very big maps with a lot of traffic. 
Thus far, profiling shows the performance degradation on such maps is due to routing the sheer number of passenger rather than moving the convois needed to move them.


   This has nothing to do with the issue in hands.
Everything to do with it...
Refer to attached picture. One way roads, allowable paths marked. The circled intersections are identical, ribi=7. Yet the allowed paths are different.

Yes I mean vehicles should not be turning across lanes. Simutrans traffic laws should be based on some semblance of order.


I don't think that is much different from current behavior.  Cars stop in Simutrans when they cannot advance.
The idea was to give vehicles some freedom in lane choice so that they can change lanes before they have to be in a particular lane. Have you ever played Cities in Motion? There the lanes are all pre chosen based upon the route. Once the vehicle arrives at the lane change point, it must change or else it stops. This can result in rather nice traffic jams, especially when it stops blocking both lanes. I would hope if we're going to add multi lane roads to Simutrans that we can be smarter about the vehicle behaviour.

But, as I've said before, the vehicle behaviour is IMHO the easy part. I've yet to see any real details on the actual construction of the roads (internal representation, GUI, etc)...


P.S. Could you try leaving two blank lines after your text before the start of the next quote? The forum quote routine is really messing with your messages mashing the paragraphs all together, two blank lines seems to be a workaround...

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9568
  • Languages: De,EN,JP
Re: Proposal for developping two-lane one-way roads
« Reply #13 on: January 07, 2012, 08:41:45 PM »
Sorry could not resist: First you wanted to remove all german, yet suggested farthing, which was again very cultural ... it is not easy to be consistent. ;)

And so far we had about 12 german developer and about four non-german; and since 2004 most new stuff is in english.

But that is minor in comparison to the implementation.

Imho subtiles (farthing) could be mapped directly from dir via an array. However in that case not only the dir but the next tile is important too: Like going SE will form S to E return lower left nut from E to S will need the revers subtiles. (That way will be consitent with diagonals imho, or?) Using 16 dirs should not be too difficult, and can still give consitent image lookup.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #14 on: January 08, 2012, 03:57:33 AM »
[...]
I'm back confused between occupations and reservations again...
For occupations, are the subtile positions (formerly called farthings) marked as occupied only when a vehicle is actually on the position?
Or, when a vehicle enters a tile, it marks all subtile positions required for its journey through the tile as occupied? aka reserverations.
They are occupations but with a tile grain, at least at the beginning if you don't want to go further in as Dwachs suggested.


Quote
[...]
To develop the current ncb routine, I mapped out all possible paths through the intersection,
[...]
That is the reason why I said at the very beginning that my idea was a reworking of your idea.  Occupations are more or less the same as what you do.  The differences are:
  • I do it with a precalculated static table and thus is code much cleaner and faster
  • I put four simple subtiles to do it easily.  Think that one can put another subtile centered in the tile if needed, or even more if needed.  Moreover, subtiles may not represent the same space when on a diagonal tile if wanted.  No problem with that either since we know if it is diagonal or not.


Quote
Adding oneway roads to the mix just means mapping out even more paths. Many more.
And that may be much more difficult to program, with more bugs, and much slower.  I'm sure that you have already tried and forgot about it, didn't you?


Quote
[...]
Thus far, profiling shows the performance degradation on such maps is due to routing the sheer number of passenger rather than moving the convois needed to move them.
And that only supports my first statement: you're worried about updating four bits each time a vehicle hops and you know that the problem is somewhere else?


Quote
Everything to do with it...
Refer to attached picture. One way roads, allowable paths marked. The circled intersections are identical, ribi=7. Yet the allowed paths are different.
I think that you are not getting it at all (either that or I'm too blind to see your point).  In the picture you have attached, we have two options, even if we have the same ribi (=7, if you are right).  If you mean that all your paths should be allowed at the same time and subtiles don't allow them, you should consider that a vehicle coming from S in the above picture either goes to N or goes to E.  It cannot go to both at the same time!  So that possibility is right to be forbidden at the same time.  The same applies to the below picture, but even worse, why didn't you mark the other possibility for the blue arrow, to go to N besides going to N* and E*?


Quote
Yes I mean vehicles should not be turning across lanes. Simutrans traffic laws should be based on some semblance of order.
But that is something to be enforced somewhere else, not by subtiles...


Quote
[...]Have you ever played Cities in Motion?[...]
I have played and I agree that it has problems with that.  I've also seen trivial deadlocks with ships, for instance.


Quote
P.S. Could you try leaving two blank lines after your text before the start of the next quote? [...]
Done.


Sorry could not resist: First you wanted to remove all german, yet suggested farthing, which was again very cultural ... it is not easy to be consistent. ;)


I see it the other way around, prissi.  You have a code filled win sursurrendungs, fahrmatrinneings, and so on...  and you're worried about a small farthing...   ;)   I repeat that you German guys don't remotely grasp how difficult those long German words are for someone without knowing one of the northern languages.  And that is because you are used to them since you were children.  But for a Portuguese, Spanish, French, Italian, etc.  those words and sanskrit one and the same,  I promise...

Quote
And so far we had about 12 german developer and about four non-german; and since 2004 most new stuff is in english.

It is a joke again...  I suppose.  Do you find that proportion for an international project normal?  And I have revisited the code for the documentation and have to continuously use Google translate.   Not to mention that I have played a lot...  But even there my first translation for Wolke was Cloud, to name only one...  But this is out of topic of this thread...


Quote
[...]Imho subtiles (farthing) could be mapped directly from dir via an array.[...](That way will be consitent with diagonals imho, or?)[...]
My original idea is based on imagining a pole just in the center of the tile and imagining also that the tile were a roundabout (I know it isn't ;) ), and reserving/occupying the corresponding subtiles.  That way, I think that no overlapping should occur and, if later a finer grain is looked for, well, there is no problem in occupying just the subtiles you are really on...

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #15 on: January 08, 2012, 04:41:14 AM »
They are occupations but with a tile grain, at least at the beginning if you don't want to go further in as Dwachs suggested.
Sorry but I still don't have a clear picture of what you're proposing here.
Can you provide an example with a vehicle approaching the intersection, and moving through it until it exits detailing its motion, the occupation statuses as it moves, and what other vehicles that might be approaching would be seeing?

If the occupations are only marked when a vehicle is actually on them, I don't see how deadlocks would be avoided. Which is the reason I keep ending up back with reservations. Take two convois approaching an intersection that are both to make a left turn. One from the N, one from the S. Based upon the subtile paths you identified, they both will be using 3 subtiles positions. If allowed into the intersection without reserving the subtile in the opposite lane, then they're both going to enter the intersection, proceed through the two straight positions, then end up blocked by each other when they want the final position.


I put four simple subtiles to do it easily.  Think that one can put another subtile centered in the tile if needed, or even more if needed.  Moreover, subtiles may not represent the same space when on a diagonal tile if wanted.
I think more than four subtiles will be required.  Five would work to replace the existing logic for twoway roads, but until every path is identified (what I've been meaning by mapped out) for oneway roads, we don't know how many will be required to accommodate them. This mapping is required regardless of what algorithm is finally chosen to control intersections.


I think that you are not getting it at all (either that or I'm too blind to see your point).
We're definitely not achieving a meeting of the minds here.


In the picture you have attached, we have two options, even if we have the same ribi (=7, if you are right).  If you mean that all your paths should be allowed at the same time and subtiles don't allow them, you should consider that a vehicle coming from S in the above picture either goes to N or goes to E.  It cannot go to both at the same time!  So that possibility is right to be forbidden at the same time.  The same applies to the below picture, but even worse, why didn't you mark the other possibility for the blue arrow, to go to N besides going to N* and E*?
Two options with the same ribi *is* the problem. Unless there's some other way to distinguish between them, how to know the allowable paths?

Obviously the vehicle can't go both ways at once... Where did you come up with that? I'm showing the possible paths a vehicle could take.

On the diagonal road, I show the left lane vehicle only allowed to turn left into the left lane. Making a turn into something other than the closest lane is illegal in any civilized place.


But that is something to be enforced somewhere else, not by subtiles...
Um  yes. I think you're getting hung up on this subtile business. I like the concept, hence am trying to understand more about how you envisioned them to work. There are a few holes to fill...

But, I'm also looking big picture at all the elements that are needed to implement oneway roads. The proposal I've seen so far covers maybe 10% of what's needed; The vehicle movement part which is relatively trivial. Where's the rest?




Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4603
  • Languages: EN, DE, AT
Re: Proposal for developping two-lane one-way roads
« Reply #16 on: January 08, 2012, 10:10:26 AM »
As to the subtile / farthings concept: As far as I understand, it is used to decide whether a path over a crossroad is free / safe / would not block.

The required checks can be made by static table lookups or computations. Here is the procedure of a vehicle approaching a crossroad:

1) determine the path through subtiles (given that we know where the vehicle wants to go as well as on which lane it is currently)
2) if path not free -> stop
3) if path does not block the crossroad -> drive on
4) if path is blocking: proceed with next tiles in vehicles route go to step 1)

The path through subtiles can be pre-computed.

The check whether a given path blocks the crossroad can be computed / precomputed too.

The occupation flag for a subtile is cleared when the convoy leaves the subtile.

The occupation flag is set on all subtiles on the vehicles path (?). (Does this replace the no_cars_blocking routine ?)

If a train on a tram track is on the crossroad (or has reserved a block on its track across the crossroad), then cars cannot cross the tram track, thus blocking certain paths between subtiles. In the sketch, each of the borders TN... between subtiles can be reserved and blocked by trams.

Code: [Select]
           *   North tile    *
*  *  *  ***********************  *  *  *
           *        |        *
           *  NW    TN NE    *
           * Farth. | Farth. *
West tile  *-TW-----+--TE----*  East tile
           *  SW    |  SE    *
           * Farth. TS Farth. *
           *        |        *
*  *  *  ***********************  *  *  *
           *   South tile    *




Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #17 on: January 08, 2012, 06:42:31 PM »
I think that Dwachs perfectly got the point.  It is probably my fault not to make my proposal clearer.  I'll try to explain some of your points:


Sorry but I still don't have a clear picture of what you're proposing here.
Can you provide an example with a vehicle approaching the intersection, and moving through it until it exits detailing its motion, the occupation statuses as it moves, and what other vehicles that might be approaching would be seeing?
Imagine four two-way streets coming together at an intersection shaped like a + sign.  Four vehicles are running towards the crossroads and are going to arrive at the same time.  All of them want to turn left.  All four paths are incompatible in my design with four subtiles.

Then, the first one to arrive at the crossroads will check if the crossroads is not occupied and will mark its path subtiles as occupied and hops.  The rest will see that their desired path is not possible and stop.  Once the first vehicle passes the crossroads, it will free the occupation and the first of all other three that check the crossroads will pass and so on.

Another example: the same four vehicles, all wanting to turn left, but one, that wants to turn right: S->W, E->S, N->E and W->S.  Imagine that the first to arrive is the one that wants to turn right (W->S), it reserves the SW subtile and drives on.  Then the other three arrives, but only one of them (S->W) is able to occupy the subtiles it wants and drives on.  The other two must wait.

But subtiles does not prevent deadlocks in itself.  They are not intended for that.  They must be combined with something like your 4-tile checking to guarantee that no vehicle will have to stop at the crossroads and, thus, deadlocks.  The two things are different and compatible...


Quote
Obviously the vehicle can't go both ways at once... Where did you come up with that? I'm showing the possible paths a vehicle could take.
But, as Dwachs says, we know in advance which of them the vehicle is choosing when entering the crossroads...  There is only one certain, real possibility, isn't it?


Quote
On the diagonal road, I show the left lane vehicle only allowed to turn left into the left lane. Making a turn into something other than the closest lane is illegal in any civilized place.
Well, your example below will hardly be built in any civilized place, I guess.  When in a one-way road, exits are on the right, not on the left...   :P   Precisely to avoid those dangerous lane crossings...  But you would be amazed the kind of things I've seen built in the supposed civilized places.

To name a funny one (I will omit the name of the country), a town wanted to build a big roundabout to deal with traffic in a dangerous intersection.  It happened that the roads arriving at the intersection had exactly the same design of a winning-prize roundabout design in a latest international competition.  So they built it.  They didn't take into account that the winning design was for the UK (where driving is on the left) and, I assure you because I have driven there, that it is an adventure...   ;D


Quote
[...]But, I'm also looking big picture at all the elements that are needed to implement oneway roads. The proposal I've seen so far covers maybe 10% of what's needed; The vehicle movement part which is relatively trivial. Where's the rest?
If this is only the 10% I don't dare imagine what would be the other 90% of this delivery...

But you know: every long journey begins with a first step...

[...]
The check whether a given path blocks the crossroad can be computed / precomputed too.
[...]
All your post is what I try to explain... but this point I don't understand.  What is a path that blocks the crossroads?


Quote
The occupation flag is set on all subtiles on the vehicles path (?). (Does this replace the no_cars_blocking routine ?)
With a tile granurality, yes.  For instance, a car may check several tiles ahead to see if it can safely drive through a crossroads, but it will only occupy the relevant subtiles of the crossroads tiles.


Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #18 on: January 08, 2012, 06:45:24 PM »
The occupation flag for a subtile is cleared when the convoy leaves the subtile.
The occupation flag is set on all subtiles on the vehicles path (?). (Does this replace the no_cars_blocking routine ?)
That sounds like using the occupation flag as a reservation to me... Which is I think the only way it can work, but is not that way we're being told the proposal is for ? ??
I think the intent is to replace the ncb routine. It would be rather tedious to extend it in it's current format to handle oneway roads.


If a train on a tram track is on the crossroad (or has reserved a block on its track across the crossroad), then cars cannot cross the tram track, thus blocking certain paths between subtiles.
Weren't trams changed a while ago to be completely independent of road vehicles?
While I'm all for trams getting stuck in traffic too, shouldn't be undoing something that was specifically previously changed...


----
On the subject of my issue with 'identical' intersections yet different allowable paths:
How about a second set of ribis for the second lane? The way builder would have to guess the intended type of intersection and set the ribis for both lanes as appropriate. As this is one of those 'read my mind' areas, some GUI would be necessary to allow a player override of the auto chosen type.

As a refinement/extension/alternative to the above:
How about treating intersections the same as crossings by adding an explicit extra object to them. ie. crossings have a crossing_t object added (and a unique crossing_logic_t too), do the same by adding a intersection_t object. This object would contain the subtile occupancy statuses/reservations and have a type property which defines the allowable paths through it. Anything affecting traffic flow through the intersection could be pulled into this object. e.g. traffic lights which in their current form won't work sensibly with avenue intersections. Still requires a GUI to allow the player to select the specific type of intersection.

Whichever method is used for identifying allowable intersection paths, the route finder is going to need changes to utilize this information anyways. I don't see how the original proposals claim of the routing algorithm being untouched can be true.

----
On the lane affinity subject:
I think the best place for this information is in the route itself; If the route finder needs to be modified anyways...

multilane_route_t derived from route_t containing koord4d (or something) derived from koord3d but containing the extra lane information:
  many tiles from an intersection where convoi will be turning - no info, free lane choice.
  once within x tiles of the turn, flag set telling the convoi to start trying to get into the required lane.
  right before the turn, flag telling the convoi it must be in the lane, stop until it can.
New derived types to avoid cluttering up the routes for convois that travel on waytypes where lanes make no sense.

The only alternative I see to this is for the convois to scan ahead x number of tiles every hop looking for an upcoming turn. That seems too CPU intensive to consider.

One further issue is with waypoints. If located anywhere near a turn, will mess things up. I think the routefinder should keep stepping through the schedule, adding to the route, until it arrives at an actual stop. i.e. waypoint will no longer be at the end of the route. This also solves several other 'weird' behaviours that convois exhibit, and implements prissis suggestion of Waypoints act no longer as signals.
{what? can't even cut and paste anymore without formatting being mangled... sigh. This new forum editor is really getting on my nerves...}

----
And finally - station stops.
Should they be allowed on the left too? or only the right (driving side)?
If forced to be on the driving side only, then a stop on a tile immediately after an intersection turn could be trouble; The vehicle would be in the wrong lane and need some exemption from the traffic laws to allow turning into the far lane...


-------
EDIT:
Then, the first one to arrive at the crossroads will check if the crossroads is not occupied and will mark its path subtiles as occupied and hops.  The rest will see that their desired path is not possible and stop.
OK. Subtiles infront of the vehicles current position are being marked occupied. aka reservations.  ;D


But subtiles does not prevent deadlocks in itself.  They are not intended for that.  They must be combined with something like your 4-tile checking to guarantee that no vehicle will have to stop at the crossroads and, thus, deadlocks.  The two things are different and compatible...
Subtiles that aren't marked occupied upon a vehicles entering an intersection would lead to deadlocks though... But being used as reservations of the complete path in a tile is good.
And correct, subtile reservations are only good to ensure the vehicle can complete its path through the tile, the existing check of whether it can leave the tile before entering are still needed.


But, as Dwachs says, we know in advance which of them the vehicle is choosing when entering the crossroads...  There is only one certain, real possibility, isn't it?
Not for citycars.  ;)


Well, your example below will hardly be built in any civilized place, I guess.  When in a one-way road, exits are on the right, not on the left...   :P   Precisely to avoid those dangerous lane crossings...  But you would be amazed the kind of things I've seen built in the supposed civilized places.
Not sure where you live, but around here left turns off avenues are always made from the left lane. On controlled access highways, usually exits to the right, but sometimes left too which always causes chaos...


To name a funny one (I will omit the name of the country), a town wanted to build a big roundabout to deal with traffic in a dangerous intersection.
Please don't talk about roundabouts. Next someone will want them in Simutrans too.  8)

I also live next to a region that's going nuts adding roundabouts everywhere, whether it makes sense for one there or not. And nobody knows how to drive on them properly.


If this is only the 10% I don't dare imagine what would be the other 90% of this delivery...
But you know: every long journey begins with a first step...
umm. The actual building of the roads and modifications to the weg structures themselves to support it?

A proposal of my own: Get me some roads to drive on (and from which I can obtain the required pathing information), and I'll get you some vehicles actually using them?
« Last Edit: January 08, 2012, 07:14:15 PM by TurfIt »

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #19 on: January 08, 2012, 07:13:41 PM »
.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4603
  • Languages: EN, DE, AT
Re: Proposal for developping two-lane one-way roads
« Reply #20 on: January 08, 2012, 08:36:01 PM »
Quote from: isidoro
Quote from: Dwachs on Today at 11:10:26 AM

    [...]
    The check whether a given path blocks the crossroad can be computed / precomputed too.
    [...]

All your post is what I try to explain... but this point I don't understand.  What is a path that blocks the crossroads?
A path through one crossroad blocks the crossroads,  if at least one subtile of the path is in front of an ingoing or outgoing lane that is neither start or end of the path.

Consider this sketch:  traffic is allowed to enter tile from S / E, outflow only through N. The paths S->N*, E* -> N do not block any other path, vehicles that want to take these paths are allowed to enter the crossroad regardless whether they can leave it immediately or not.

Any other path through this crossroad is blocking.

  N*  N
*   |   *
*   |   *
*       *******
*                E* lane
*                E lane
*       *******
*   |   *
*   |   *
  S   S*

Think of this as ramp to enter motorways (drive-on-right). The highway goes S->N, the ramp is E->N. I as car driver driving on the motorways will try to change to the left lane in order to let any ingoing traffic from the ramp (E) allow to enter the motorway without braking / stopping. (what a sentence)


Quote from: TurfIt
Weren't trams changed a while ago to be completely independent of road vehicles?
While I'm all for trams getting stuck in traffic too, shouldn't be undoing something that was specifically previously changed...
I must have missed this completely. I could not find any checks regarding interaction cars <-> tram in the code :-X


--
Lane affinity: imho these decision should be made in the driving code, not in route finding. Overtaking is also not decided during route-finding.

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #21 on: January 08, 2012, 08:52:41 PM »
Any other path through this crossroad is blocking.
Considering the top of a 'T' intersection to be not blocking was only just added by my weg_frei revision. The main reason why driving side is not saved in the savegame, and different online players can no longer have different driving side preferences. i.e. driving side is no longer a local display preference. If a player doesn't want cars stopping in the 'T', they need to use a traffic light intersection which vehicles always consider unsafe to stop in.


I must have missed this completely. I could not find any checks regarding interaction cars <-> tram in the code :-X
Perhaps I'm wrong, but I'm sure I remember once upon a time trams and cars interacted. Prissi?



Lane affinity: imho these decision should be made in the driving code, not in route finding. Overtaking is also not decided during route-finding.
The final decision of which lane would be done in the driving code, but the route code would drop 'hint's of what lanes the vehicle should be in. This way the convoi doesn't need to be continually scanning ahead trying to figure out where it's headed after x number of tiles.  Similar to how we're discussing subtile occupancy flags instead of simply querying all the vehicles in the intersection as is currently done, but applied to the lane instead - use lane flags instead of scanning tiles yet again.

Overtaking is also a more dynamic situation. No changes should be required here as it only applies to twoway roads. Vehicles 'overtaking' on a oneway road with free lane choice don't require anything like the overtaking checks. Note also: I've been rewriting the overtaking code to allow much more frequent passes. Been stalled for a couple months, but finally had my Eureka moment last week to solve a sticky issue with road trains. Now to actually code the Eureka...  :D

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9568
  • Languages: De,EN,JP
Re: Proposal for developping two-lane one-way roads
« Reply #22 on: January 08, 2012, 09:38:56 PM »
Tram and cars never interacted. A long time ago citycars did not interact either ...

@isidoro: I just read the pak48 thread answer. Sorry, if I only pick on the problems. Maybe that is from university where I constantly have to grade stuff and write reviews of other people works. I try to mention also the things what can be kept next time.

Ok, now my idea how I understood this:

At hop_check() first too many cars, way is there, traffic light, signs railroad and other crossings are check. If all is fine, a sub_tile_t bitfield (eg. NW/NE/SE for turning right when dirve_left and coming from west) is calculated. Then way->reserve_sub_tiles( sub_tile bitfield ) is called. If this returns true, the sub_tiles are reserved and one can drive on (return true). If not, and
a) way->get_system_type()==ONE_WAY and convoi_t then calculate lane change sub_tiles and try again.
b) citycar at crossing: Check next direction.

The sub_tile reservation will be cleared it the vehicles is removed (if letztes in verlasse_feld()) or if verlasse_feld and convoi_t::state!=DRIVING

Ok, so far so good. What about more than one crossing? I that case hop_check needs also the reserve the subtiles on the next crossing an so one one the next tile not no a crossing anymore or end of route. This may even result in less blockings and more throughput and less CPU power.

The challenge is the deletion of those reservations. The convoi can do this since it knows its route, but how about a citycar? It probably need a slist_tpl with the koord3d and subtiles reserved.
But one thing is not clear, and I think that turfit was also mentioned it. How does the sub_tiles for lane change on diagonal road look like? Any such subtiles would be identical to the already left lane traffic? Or not?
« Last Edit: January 08, 2012, 09:49:28 PM by prissi »

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #23 on: January 09, 2012, 01:38:49 AM »
Oh my God!  This is real brainstorming...   :o

@prissi: don't mention it.  You do a great job and you did answer, as usual, and that alone is a lot.  The problem, if any, is on my side.

@TurfIt:  Isaac told me a trick.  Just click on the arrow button (the last at the line before the emoticons) and you get the previous editing behavior.


[...]On the subject of my issue with 'identical' intersections yet different allowable paths:
How about a second set of ribis for the second lane? [...]
I don't think that a second set of ribis is a good idea.  The ribis on the adjacent tiles can tell you, if wanted what happens in the other lane.


Quote
Whichever method is used for identifying allowable intersection paths, the route finder is going to need changes to utilize this information anyways. I don't see how the original proposals claim of the routing algorithm being untouched can be true.
I think nothing needs to be touched in route finding.  Present ribi masks will tell if a route is allowable or not.  I like your idea that the route finder and the route data are modified to hint the car to which lane it should stick.  Something like marking the first eight tiles with something telling use the lane you want, the next four with keep to the left because you are going to turn left, and the next four marked with keep to the right since this road is going to be two-way soon...  That is better than recalculating that every time.  And two bits can be hidden anywhere in koord3d...


Quote
[...]
And finally - station stops.
Should they be allowed on the left too? or only the right (driving side)?
If forced to be on the driving side only, then a stop on a tile immediately after an intersection turn could be trouble; The vehicle would be in the wrong lane and need some exemption from the traffic laws to allow turning into the far lane...
Nice point.  It can be merged with the last point.  If they are allowed on the left on one-way roads, the vehicle is marked to move to the left some tiles ahead.  Buy it can be done in a later stage if really wanted...

Quote
Please don't talk about roundabouts. Next someone will want them in Simutrans too.  8)
I see them quite easily to do,  but you know that I'm a little big mouth myself...  ;)


[...]
Consider this sketch:
[...]

  N*  N
*   |   *
*   |   *
*       *******
*                E* lane
*                E lane
*       *******
*   |   *
*   |   *
  S   S*
Now I understand what you mean.  But one hint first, in my notation, normal drive lanes (i.e. lanes on the right when driving on the right) are marked without *.  The other with *.  That way you can always identify a "transition" (change of lanes) when you go from something with a * to something without it and vice versa.

My point here has always been that that has nothing to do with occupations but with the driving code itself.  A car coming from E or E* and wanting to go N (remember that the route only marks which tile the car wants to go), can be forced to do E*->N (with my notation) if one doesn't want to go into the other lane, if wanted.  Although I would allow all cases without problems.


Quote
Lane affinity: imho these decision should be made in the driving code, not in route finding. Overtaking is also not decided during route-finding.
I think that a mix of this and TurfIt idea may be better: the routing code may add for road routes one of these hints:
  • Drive to the lane you want
  • Go to the right the sooner you can, but don't stop if you can't
  • Go to the right right now in this tile or stop
  • Go to the left the sooner you can, but don't stop if you can't
  • Go to the left right now in this tile or stop

This would allow the car to freely choose the lane while driving based on the traffic with some hints or obligations based on its route, not being too CPU intensive.

At hop_check()[...]

Perfect.  That would be the case of a car coming from S that wants to turn left.  And if we add either the aforementioned hints or looking ahead in the route, the normal S->W movement can be changed to a S->W* on the fly, before reserve_sub_tiles.  That change of lanes would depend on:
  • Hints: if they seem suitable to be implemented
  • Traffic disposition at the moment (for instance, a car just in front of me and no compulsory hints
  • Some static rules based on road configuration like the ones Dwachs mentioned
 


Quote
Ok, so far so good. What about more than one crossing? I that case hop_check needs also the reserve the subtiles on the next crossing an so one[...]
My opinion here is that the check should include some tiles ahead (like TurfIt's routine), but the reservation is only done in the next tile.

That will save some of the problems you mention and alleviate the deadlock problem.  A deadlock is a problem that depends on topology...  It is global.  Even if you keep all intersections free, there can be a deadlock.  So why bother with all that complication?  Check some tiles and occupy only the next.


Quote
But one thing is not clear, and I think that turfit was also mentioned it. How does the sub_tiles for lane change on diagonal road look like? Any such subtiles would be identical to the already left lane traffic? Or not?
I see two approaches here, but it's too late and my brain is tired after going to the movies:
1) When in a diagonal tile, subtiles are also four and occupy the same bit field than on a normal tile, but they refer to N, W, E and S subtiles.
2) Do nothing.  Keep the same thing as with normal tiles:

                                *****************
                                *       |       *
                                *   B   |  <B   *
                                *   v   |       *
                      Tile 4    *-------+-------*   <- Tile 5
                        |       *       |       *
                        V       *   B   |   A>  *
                                *   v   |       *
                *********************************
                *       |       *       |   ^   *
                *   B   |  <B   *  <B   |   A   *
                *   v   |       *       |       *
     Tile 2     *-------+-------*-------+-------*   <- Tile 5
       |        *       |       *       |   ^   *
       V        *   B   |   A>  *   A>  |   A   *
                *   v   |       *       |       *
*************************************************
*       |       *       |   ^   *
*   B   |  <B   *  <B   |   A   *
*   v   |       *       |       *
*-------+-------*-------+-------*   <- Tile 3
*       |       *       |   ^   *
*   B   |   A>  *   A>  |   A   *
*   v   |       *       |       *
*********************************
*       |   ^   *
*  <B   |   A   *
*       |       *
*-------+-------*   <- Tile 1
*       |   ^   *
*  A>   |   A   *
*       |       *
*****************


I think there is no problem.  Car A is going in diagonal towards NE.  Car B is going in diagonal towards SW.  No problem, they can circulate at the same time with subtiles occupations/reservations.

Now imagine that it is a one-way road instead and A wants to change lanes in tile 3.  Easy.  It is a W->N* transition.  At the entrance of tile 3 it will reserve SW and NW subtiles and be on the right lane.  At the exit, it will be on the left lane.  Just done.  This is a transition and it is done playing with the offsets when drawing.

Next week hard work starts... but if I have time, I will try that five-line long patch to see how those transitions look when overtaking...  In theory they work but, who knows, they may be ugly...

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #24 on: January 09, 2012, 03:35:57 AM »
Just click on the arrow button (the last at the line before the emoticons) and you get the previous editing behavior.
Close, that gets you the tags back atleast. VS pointed me to a profile setting to turn off the WYSIWYG editor. Now much better.


I don't think that a second set of ribis is a good idea.  The ribis on the adjacent tiles can tell you, if wanted what happens in the other lane.
I'm going to have to revert to asking for a detailed example again as I'm just not getting this... my example had identical ribis but different routes...


I think nothing needs to be touched in route finding.
Perfect example of me saying something, then giving the wrong reasons for it.  :)
Route finding doesn't need to be touched, but it might be an idea to add a slight bias towards preferring a oneway road over a two given traffic should be more free flowing on oneway roads.


And two bits can be hidden anywhere in koord3d...
koord3d is a packed 40 bit structure. It be full. That's why I suggested a new koord4d (or something) so the extra byte that'd be needed will only be for routes on multilane roads.


if one doesn't want to go into the other lane, if wanted.  Although I would allow all cases without problems.
I think this is one of the sources of confusion in getting my same ribi problem across. I think you're allowing lane changes in intersections. I'm not. Another one of those 'in civilized places' things...


the routing code may add for road routes one of these hints:
  • Drive to the lane you want
  • Go to the right the sooner you can, but don't stop if you can't
  • Go to the right right now in this tile or stop
  • Go to the left the sooner you can, but don't stop if you can't
  • Go to the left right now in this tile or stop

This would allow the car to freely choose the lane while driving based on the traffic with some hints or obligations based on its route, not being too CPU intensive.
Finally one of my ideas successfully communicated.  ;D
This is indeed what I had in mind.


My opinion here is that the check should include some tiles ahead (like TurfIt's routine), but the reservation is only done in the next tile.
If we're adding reservations, might as well add them fully. Vehicles can currently enter an intersection in front of one that's already checked for clearance and block it.


Even if you keep all intersections free, there can be a deadlock.  So why bother with all that complication?  Check some tiles and occupy only the next.
Keeping intersections free greatly reduces the chances of a deadlock occuring. Once you have so many vehicles that they circle the block, then yes, nothing will stop it. Although in that case, the general term of gridlock applies.


---
any thoughts on the intersection_t object I proposed?


Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9568
  • Languages: De,EN,JP
Re: Proposal for developping two-lane one-way roads
« Reply #25 on: January 09, 2012, 09:29:45 AM »
I would not use lane changes on crossings. And for turning right, the car has to be on the right lane in most countries, so keep this simple and we can use a table for lookup table of subtiles on turning (if one uses an extend fahrtrichtung with 16 directions. It would make several stuff simplier. Why do no one comment on that?)

And if one start with reserving subtiles, it should be consequently at least four crossings ahead. (And then the driver could not see farther anyway ... ) ANd then keep them to may ist_weg_frei much less CPU hungry and easier to understand.

And adding stuff in route finding for cars is clearly not my favourite. Also extending koord3d will immeadiate increase memory foodprint of every structure by 4 bytes, clearly is not a good idea.

A car could check itself upon entring a way has IS_ONE_WAY system type when it will leave this way and to which side, or if it has a stop on the way. It set then a route index (exit_oneway_index) and the side (LR). Before if can move freely. With such an route_index, it can also estimate, if it can pass a car and so one, i.e. all overtaking checks would be simplier.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #26 on: January 09, 2012, 03:24:23 PM »
@TurfIt:  I think that your confusion comes because you imagine that the lane is to be included in the route plan and it isn't.  The route is a collection of tiles the car have to visit.  The lane is something the car is at, but not something the car is going to (except in tansitions).

I would not use lane changes on crossings. And for turning right, the car has to be on the right lane in most countries, so keep this simple
The matter is more complicated that it may seem at first sight:
  • here, where I'm living now, when entering a roundabout, you enter without changing lines, but when you exit it, you must exit on the right lane only
  • sometimes, in the game, it may happen that there is not other chance than to change lines in the intersection.  Imagine a T crossing with the vertical road one-way, and the horizontal two-way.  A vehicle arriving at S* and wanting to turn right must change lanes at the intersection (S*->E), because otherwise it will go in the wrong direction
  • if you say that the car shouldn't be there, at S*, upon arriving at the crossroads, in the first place, then the program should check and force, by hints or other method the car to go to the right but, then, if there is a traffic jam, we will see the left lane of some tiles before the crossroads empty and the other lanes full, which is both unrealistic and not pretty


Quote
... and we can use a table for lookup table of subtiles on turning (if one uses an extend fahrtrichtung with 16 directions. It would make several stuff simplier. Why do no one comment on that?)
In my case, because I don't understand.  Can you explain it further?


Quote
And if one start with reserving subtiles, it should be consequently at least four crossings ahead. (And then the driver could not see farther anyway ... ) ANd then keep them to may ist_weg_frei much less CPU hungry and easier to understand.
I see a lot of headaches and also memory consumption there.  The more you reserve the more likely you get to a deadlock...

Quote
And adding stuff in route finding for cars is clearly not my favourite. Also extending koord3d will immeadiate increase memory foodprint of every structure by 4 bytes, clearly is not a good idea.
koord3d is now 40 bits long but when in an array, it will become 48 or 64 I guess.  A new uint8 shouldn't add more memory footprint.  Am I overlooking something?

But...
Quote
A car could check itself upon entring a way has IS_ONE_WAY system type when it will leave this way and to which side, or if it has a stop on the way. It set then a route index (exit_oneway_index) and the side (LR). Before if can move freely. With such an route_index, it can also estimate, if it can pass a car and so one, i.e. all overtaking checks would be simplier.
I agree with you that this is a much simpler approach and you only loose the time you are going to revisit the precalculated route.  Also it allows things like this:
  • if you are four tiles before exit_oneway_index, try to change to the correct lane, and if you can't, drive slower until you can and, eventually, stop if you reach exit_oneway_index without being able to change lines...

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4603
  • Languages: EN, DE, AT
Re: Proposal for developping two-lane one-way roads
« Reply #27 on: January 09, 2012, 04:46:11 PM »
Quote from: Isidoro
I see a lot of headaches and also memory consumption there.  The more you reserve the more likely you get to a deadlock...
Its actually the other way round: the less you reserve the more likely are deadlocks. If every convoy only starts driving if it can reserve its complete route, we would never get deadlocks.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #28 on: January 09, 2012, 06:36:14 PM »
Not exactly.  It is a common misconception.  If you reserve a lot of tiles you will easily arrive to others reservations or places.  If those other vehicles also reserve a lot and happen to need one of your already reserved tiles...  we have the deadlock.

By the way, I have released the five-line long patch to see how smooth overtaking looks like.  It is on the Patch Releases section.


Offline Isaac.Eiland-Hall us

  • Benevolent Dictator
  • Administrator
  • *
  • Posts: 3659
  • PanamaCityPC.com/support/
    • Facebook Profile
  • Languages: EN
Re: Proposal for developping two-lane one-way roads
« Reply #29 on: January 10, 2012, 06:45:20 PM »
I don't want to complicate things, but just want to make sure you've considered: What about a T-intersection between two one-way roads? In such a case, both lanes of the road coming into the T may turn into both lanes of the one-way road. Might that help, or does it help to ignore such a thing? :)

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #30 on: January 10, 2012, 07:12:37 PM »
That road configuration should be possible with the ideas above. It's really a matter of going through *all* possible configurations ensuring they work with the chosen logic.

The ideas above are IMHO more than sufficient to develop working vehicles driving on oneway roads. But we don't actually have the roads...
So, reiterating my previous proposal, somebody get me the roads, and I'll get you the vehicles on them.

Offline Isaac.Eiland-Hall us

  • Benevolent Dictator
  • Administrator
  • *
  • Posts: 3659
  • PanamaCityPC.com/support/
    • Facebook Profile
  • Languages: EN
Re: Proposal for developping two-lane one-way roads
« Reply #31 on: January 10, 2012, 07:22:20 PM »
What's needed to get you roads? Do you mean just a new road intended for one-way? I'm probably not the best person to do so (because for whatever reason, I'm not good at figuring out what's needed for new dats), but I would be glad to try and get something to work with, at least.

Which pak? pak64, I assume? I'm not sure what international one-way roads look like, only for the US. :-/

Offline TurfIt

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 1326
Re: Proposal for developping two-lane one-way roads
« Reply #32 on: January 10, 2012, 07:35:18 PM »
I mean the code to build them, internal structures to represent them, and any other code bits'n'pieces to actually get them onto the map in a usable form.
The graphics, well that's really the last step.  ;D

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Proposal for developping two-lane one-way roads
« Reply #33 on: January 10, 2012, 08:28:27 PM »
More or less, I think that everyone agrees on the main technical points, but some details should be settled.  The most difficult task, if we follow the precepts of Software Engineering, is not to program, but to know what to program and, specially, the interfaces, not the algorithms...  If they are settled by the main developers, I offer myself to write the milestones, yardstones and inchstones and, if I believe in them, even write some code.

Some things I think should be settled by the main coders.  Three of them, for example:
  • although I think that a new system type is now preferred by them against a new flag, I don't understand if this make one-way roads incompatible with elevated roads or not
  • allowed or denied change of lines in crossroads.  The general tone I feel is that some of them should be prohibited, but I don't see it.  Another reason against it:  the player may have changed the configuration of a crossroads while a vehicle has already entered a one-way road leading to it.  The vehicle has already decided to which lane to attach at the entrance of the old crossroads configuration.  What has to be done when it arrives to the new crossroads that force a forbidden change of lanes there?  For example, a one-way road was changed to a two-way and the lane the car wanted to go is now forbidden...
  • reservations

Another possibility is that a working patch or development appears and continue from that in a more classical way of doing things.  I'm not going to do it, though.  It is a lot of time not to be sure if it will go in or not.
 

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9568
  • Languages: De,EN,JP
Re: Proposal for developping two-lane one-way roads
« Reply #34 on: January 10, 2012, 09:31:28 PM »
koord3d is used in packed struct of all ding_t and grund_t. Increasing its size, will align all structs to the next larger sint32. Given the millions of trees and grund tiles, this will have notable impact.

Quote
although I think that a new system type is now preferred by them against a new flag, I don't understand if this make one-way roads incompatible with elevated roads or not

No, maybe using the system types ==64 ONEWAY and 64 ONEWAY_ELEVATED. Or just treating system types 1 and 64 as flags.

Quote
allowed or denied change of lines in crossroads.  The general tone I feel is that some of them should be prohibited, but I don't see it.  Another reason against it:  the player may have changed the configuration of a crossroads while a vehicle has already entered a one-way road leading to it.  The vehicle has already decided to which lane to attach at the entrance of the old crossroads configuration.  What has to be done when it arrives to the new crossroads that force a forbidden change of lanes there?  For example, a one-way road was changed to a two-way and the lane the car wanted to go is now forbidden...

It could just stop and start on default lane (depending on driving side).

When a vehicle has 16 dirs those can be mapped directly to subtiles. Just put them in such an order, that division by 2 (or four) gives the desired image.

S to N: +*/+* dir::N
S to E: ++/+* dir::SE
S to W: **/+* dir::SW
N to S: *+/*+ dir::S
N to E: *+/** dir::NE
N to W: *+/++ dir::NW
E to S: **/*+ dir::SE
E to W: **/++dir::EW
E to N: ++/+* dir::SW
...
And a second mapping for overtaking vehicles (one the other lane)

That mapping will be reversed when driving is on the other side. With such a mapping a direct tile reservation is very fast. Citycars wont reverse tiles, if the did not have too. Maybe the have to carry a list (or a minvec) of koord3d and subtiles reserved.

As long as a cars goes a reserved path, it cannot change lanes. But that is imho ok.

About crossings: With the envisioned implementation you cannot have oneway crossings. There is no way the program can find out which are the allowed directions. Imaging you have a threeway crossing, with ONEWAY type (since it would keep its previous type). This crossing was formed due to a sideway attached to the one. If this is exit only, the allowed directions cannot be guessed. Same for entry only.

It was to look at least on the next tile. Giving those problem, only turning when in default lane seems like a good start to me.