News:

The Forum Rules and Guidelines
Our forum has Rules and Guidelines. Please, be kind and read them ;).

Double diagonal track (RFC, PATCH)

Started by ij, January 05, 2015, 12:19:26 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

ij

Hi,

Here is a proof-of-concept patch for double diagonal tracks. It somewhat works: I can build, route/reserve through, and successfully drive on such track segments. The building and routing code was quite straight-forward to modify.

The reservations/driving, however, got rather tricky because in order to select correct weg on a doubled diagonal ground one needs to know either arrival or exit ribi (one of the tile boundary crossing ribis, not the actual driving direction) for the tile which seems to not be available so I had to record it to vehikle.

To me the approach looks reasonable from performance point of view given limited set of expensive looking changes but I'm hardly an expert on this area. Please comment, if you have some concerns.

It is unclear to me if the second weg is needed for something else than crossings which are not possible with a diagonal track in the first place.

What is not working for doubled tracks (or at least likely not working):


       
  • Signals (needs UI extensions to disambiguate doubles from each other during building, hopefully the signals backend code works out right away after UI has ability to build them but I've not evaluated the code yet at all so something unforeseen might show up)
  • Waypoints (well, they likely work somewhat but not precisely enough, would require both UI extensions and extented koord3d type for a limited subset of koord3d users)
  • Save/Load when a train is on such a tile
  • All building that continues from a doubled track (UI extensions needed)
  • Track building preview does not display double diagonals but ribi_t::alle instead, just build regardless
  • Some conditions with get_weg calls won't get the right weg because I've not figured out how that part of code should disambiguate the wegs, marked with FIXME
  • I seem to have managed to break building those annoying parallel ribi_t::alle entirely even though it wasn't my intention :-)
  • If something else than trains break, rest assured, I didn't test with anything else ;)
One other open issue is with maintenance cost (no implemented yet though as builder part is currently unimplemented except trivial ability to create double tracks). I think there will be rather inconsistent behavior if a doubled track is converted to ribi_t::alle track by building the link as the maintenance will decrease! I'd rather like to have maintenance cost per ribi to avoid it but implementing that would be another project in itself and would likely require changing the maintenance costs in paks to keep them balanced.

--
i.

ps. Since my previous post button press didn't do anything, I'm trying now without attachments first. So it's not missing by accident.

ij


ij

An example image.

Markohs

I didn't look at the code yet, but the concept is really interesting, I'll step aside and wait to see what the rest of developers think about this. Thanks for your work! :-)

jamespetts

Interesting. Is this intended to be a precursor to double ways on any sort of single tile whether diagonal or not, or is there some utility to having double ways on a single tile only when diagonal?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

DrSuperGood

I think the purpose was just to make diagonals more compact similar to how OpenTTD does them. Using this multi track can probably fit in N+1 tile wide diagonals where N is the number of lines. Before it was always 2N wide diagonals needed.

Ters

Unfortunately, the list of TODOs isn't particulary promissing. A lot in Simutrans assumes just one way of a given type on a given grund_t.

gauthier

This is amazing, although it would take a while to get used to it if it is implemented. Nice job anyway !

ij

Quote from: jamespetts on January 05, 2015, 01:23:29 AM
Interesting. Is this intended to be a precursor to double ways on any sort of single tile whether diagonal or not, or is there some utility to having double ways on a single tile only when diagonal?

There's still just one unique entry/exit per edge of a tile, so I don't think it would be very easily extented to other than doubled diagonals.

--
i.

Dwachs

Looks interesting. In the code there are a lot of assumptions concerning the parts of the code that have to be touched: at most 2 ways on one tile, at most one signal per tile, at most one wayobj (overheadwires) per tile.

As this patch also allows doube track for trams, double tram track on a road has to be forbidden as well.

As to your list of open problems:

-- signals: first, signals can be forbidden on doubled track for a start.
-- waypoints: I guess now a train will happily arrive on either part of the doubled track
-- save-load: arrival_ribi has to be saved, it is a trivial change. The support of old savegames is not problematic, as these will not contain double tracks.

will try now.
Parsley, sage, rosemary, and maggikraut.

Dwachs

here is an updated patch: fixes two crashes, fixes route finding for ships.

There is another issue with route finding: the current route finder cannot find routes that have to pass over both diagonals of a double diagonal track.

Signals on double diagonal are indeed broken. On the plus side, I could not build double tram track and road on one tile.
Parsley, sage, rosemary, and maggikraut.

ij

Quote from: Dwachs on January 05, 2015, 03:52:58 PM
here is an updated patch: fixes two crashes, fixes route finding for ships.

There is another issue with route finding: the current route finder cannot find routes that have to pass over both diagonals of a double diagonal track.

Signals on double diagonal are indeed broken. On the plus side, I could not build double tram track and road on one tile.

Thanks for testing and the fixes. I think I solved the double routing through a double diagonal problem now. That is, just pass on the arrival_ribi also to the marker and put weg 0 into the bitarray and weg 1 into the bridge/tunnel hash (IMHO this is somewhat hackish solution though but hopefully the performance of routing over non-double-diagonal tiles will be mostly unaffected by the change).

Signals and way_obj have ribis, so I suspect similar arrival_ribi trick with minor mods would work for them as for wegs but obviously building them is still not possible (I might do some hacky solution for signals at some point in order to be able to test signal mechanics with arrival_ribis unless I get the UI side for quad triangles of a tile figured out soon enough).

--
i.

kierongreen

Very interesting - to allow double tram on double road we'd need to have 4 ways on a tile. This would also allow tram on road crossing river. Might be worth adding at the same time if you're doing lots of changes.

ij

Quote from: kierongreen on January 06, 2015, 12:33:26 AM
Very interesting - to allow double tram on double road we'd need to have 4 ways on a tile. This would also allow tram on road crossing river. Might be worth adding at the same time if you're doing lots of changes.

Thanks, I'll keep this in mind even though the get_weg as is isn't capable for that it would be easy to extend it. Effectively the has_way2 flag would just become indicator for has_multiple_ways. Most of the changed code would work out of the box as long as get_weg would return correct weg type (the recently changed marker code would not work though, it would need more logic). I see how little I know of the internals, really, I didn't even know there is such limitation with river crossings.

--
i.

ij

Fixed few errors in the previous routing changes, and played with electrification. Building, routing, and driving across electrified double tracks now seemed to work, however, there was some issue with replacing them (the old wayobjs seem to remain there overlapping).

I also found one, yet unfixed, bug related to reservations. If the train cannot reserve the whole length to the next station, the double diagonals unreserve won't occur but  that's likely just some of the not yet addressed get_weg that will get it right.

--
i.

kierongreen

Not all paks have river crossings, most just have bridges I think.

prissi

Grund can now accomodate another flags, since the image_id is now 32 bits. Hence the flags for ground could be not extended by 16 bits ... so more ways will be easily possible, even with fast flag assited lookup. However, signals will be difficult, i.e. each signal would need to point to its affected directions.

One difficult thing: If a train encounters a no route, or you reverse it while on the double track section, it may continue on the wrong track. And crossing from one track to the other will be not looking as expected.

Markohs

I suggest you updating your git repo, since we have translated some classes from german to english and your patch can't apply straight as it is now. :)

ij

Quote from: prissi on January 06, 2015, 10:04:04 PM
Grund can now accomodate another flags, since the image_id is now 32 bits. Hence the flags for ground could be not extended by 16 bits ... so more ways will be easily possible, even with fast flag assited lookup. However, signals will be difficult, i.e. each signal would need to point to its affected directions.

Right, I'll need to add two signals if there is one for both tracks. I'm tweaking signal code already... I can already build on both sides of the double track correctly but it's not possible to do that at the same time for the same tile (yet).

Quote
One difficult thing: If a train encounters a no route, or you reverse it while on the double track section, it may continue on the wrong track. And crossing from one track to the other will be not looking as expected.

I've actually thought that already. The track jumping is a horror yes as it might displace your train to track of somebody else. I think that the route finder should be given the arrival_ribi in order for it to select correct set of starting ribis also for the doubled diagonal (currently it is just a hardcoded hack with ribi_t:alle).


--
i.

ij

Quote from: Markohs on January 06, 2015, 11:49:08 PM
I suggest you updating your git repo, since we have translated some classes from german to english and your patch can't apply straight as it is now. :)

Attached.

ij

Current version of the patches. I had to compress them due to message size limit.

Changes since v4:
- UI input side becomes aware of sub tile position, the pointer is under one of the four triangles for N, E, S, W (a preparation patch, apply it first)
- Fixed rotate and arrival_ribi
- Signal building on correct doubled track is now possible both with the single click and drag interface (no dual signals per tile yet though, although that currently looks almost a trivial extension to the existing code, just need to check if the signal is on the correct track). Signals also work with trains. There is likely still issue in the drag interface though, it is due to route finder code not yet being able take initial ribi mask and uses ribi_t:alle to look for a weg still as such, the drag interface might start from the wrong side of the double but that will eventually get fixed.

Any comments on the patches, in particular the UI side code appreciated, is it too intrusive or risky to change the UI/tool classes like that?

--
i.

ij

Changes since v5:

       
  • Working building, the interface got broken in v5 (and I didn't notice since I only tested signals and wayobjs using a savegame)
  • Signals fully working on both tracks (afaik)
  • Rebased the patches due to translations in trunk
Known issues:

       
  • Save/load not yet working if a train is on a doubled track
  • Reversing waypoint on doubled track seems broken, I need to locate code where the reversing happens
  • Wayobj upgrade still has issues, perhaps building also although building is visually correct for both directions
...I'm sort of hoping that wegbauer would get translated reasonably soon (if that is going to happen) as it would save some conflict resolution for me as I'll likely look next into the building interface. Plan for streets and tram tracks doubling is also forming in my head already, so hopefully that gets realized soon too.

--
i.

Markohs

The bauer classes are indeed the next ones being translated and refactored. I think and hope they will be ready this sunday.

Yona-TYT

What happened to this project?
Or maybe it was incorporated?

Ters

It's definately not incorporated in Simutrans. I don't know about Simutrans Experimental.

jamespetts

No, this is not in Experimental, either.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

prissi

Some of the loading issues are still a show stopper for a release. Imagine no route after loading a savegame, or trains going to astation half a a circle away. That is of course it would be nice if this gets to work properly. Also I am not sure what citycars would do on double diagonal roads with this patch.

I am not sure if the OpeNTTD system (entry and exit ribi) is needed to solve these issues completely. Getting the next ribie from the previous one seems quite prone to problems as soon as there are no route or schedule changes.

Fabio

Entry and exit ribis could be useful also for other (future) features, like ramps and roundabouts, once the proper interface is set up.


Sent from my iPhone using Tapatalk

ij

#28
Please don't worry, I've not abandoned this project. I was just waiting for a while for the translations of the code (and then realized it probably would be slightly longer and moved my "polling" to low priority queue). I'll likely continue this work in few weeks regardless of translations.

QuoteI am not sure if the OpeNTTD system (entry and exit ribi) is needed to solve these issues completely. Getting the next ribie from the previous one seems quite prone to problems as soon as there are no route or schedule changes.

Do you mean those parts in the change related to signals that fetch some ribis from the route of the convoy? Those parts obviously need to get the previous from something that is related to the route (as the convoy is not there itself). If you refer to the arrival_ribi related code, I don't understand what you mean as route/schedule shouldn't affect arrival_ribi once the convoy has entered a tile so determining previous for the the current position (the weg on which the convoy is) should not have such issue even if the route/schedule changes. The next ribi is determined from the weg ribis, not from the previous ribi that is just used to pick correct weg one among the two alternatives.

--
i.

prissi

OpenTTD uses 256 ribis, which hold diagonal ribis. Your approach of having instead two way is probably the better approach, as reservation etc. is really separated. But the determination of which way based on routing history and the non unique assigment of vehicles to a way could be issues. I.e. when a convoi looses its route, due to contruction. Given how player managed to have overlapping convois despite all checks, so a break point may be break ... One could have a unique lookup by an additional type (e.g. a vehcile_coord_t) which additionally contains a way number . But ignore this, I have to dig into your patch first. At the moment it was rather loud thinking.

Yona-TYT

Quote from: ij on April 18, 2015, 07:18:39 PM
Please don't worry, I've not abandoned this project. I was just waiting for a while for the translations of the code (and then realized it probably would be slightly longer and moved my "polling" to low priority queue). I'll likely continue this work in few weeks regardless of translations.




Good to know that the project is still alive.
greetings  ;)

Václav

Double diagonal track is very useful for lesser consumption of space needed for building of curves - but still, they are not easy to build. I had a problem to build them at all times I played TTD and openTTD.

And as I tested openTTD on my recently bought Lenovo A7-40, without mouse they are more difficult to build. So, I would suggest to pay attention to implementation of this feature.

Chybami se člověk učí - ale někteří lidé jsou nepoučitelní

DrSuperGood

OpenTTD had the problem that you could not have different track type in diagonals. This made upgrading from rail to monorail to maglev a real pain.

Václav

DrSuperGood: I am not sure how with OpenTTD, but in TTD it was not possible to have different track parallely for longer time - because after some time (I don't remember those years) older types became unnaccesible/unusable - because vehicles were not available for longer time for those tracks.

Chybami se člověk učí - ale někteří lidé jsou nepoučitelní