Patch: Extended Signals [v6-r17618]

[crakinshot]

Extended Signals (SignalEx) essentially is a backbone modification to allow complex information for signals in code.

Originally, I started this so I could do UK based aspects and feathers. The main problem was simply not enough free-bits in the tile information. So the idea is, use the remaining bits to form an index (the last remaining 16 bits of a RailSignal class). A flag (m2:15) is used to specify whether the tile has extended signals. If so then the remaining free-bits of the tile are used to make a 15 bit index into a SignalEx pool. This pool is made up of SignalEx structures, which can then be extended in the future by other people to add new features.

So basically, A) easily extendible signal information, without it affecting the existing functionality (at all), and B) laying the foundations for what I wanted to do, and programmable signals. So essentially, if the flag in the tile is 0 then no extended signal information is stored in the pool. So only a specific few signals can be chosen to have extended information, rather than every single one, although everyone of them could be extended if wished (up to 2^15 signals).

[Update 1] Attached is the basic functionality for the extended signals, with SaveLoad support. Doesn't affect anything, nor are the extended signals being used. Consider as initial attempt and posted here for advice.

[Update 2] Creating SignalEx objects and attaching them to tiles has been added and tested. Save/Loading has been tested.

[Update 3] Some moving of code, added special case into after-load to ensure used-bits are wiped clean (unsure if this is actually needed), tested as working either way. Last thing to do is to add on handling when signals are removed from a tile, so that the SignalEx objects can be unallocated.

[Update 4] Shifted functions around, added general support for adding and removing signal extensions (rail_cmd.cpp). Also centralises any signal update to an update function SignalEx::Update(SignalEx* sx) so that it can be handled separately from the existing code. If _DEBUG then every tile that has a signal uses extended signals, if you query the map tile you can see the first 8 bits of the SignalExID in m7. SaveLoad has a bug, where the signalex pool isn't being cleared before a new map load... crashes the index setup.

[Update 5] Fixed the pool handling so cleared properly. General clean-up of code. Tested by forcing all signals to be extended. Added and removed couple hundred signals, pooling functionality appeared to be working well. Submitted to flyspray

[Update 6] moved the signalex id to tile m2. recoded handling of all m2 access in rail_map.h to check if extensions are in use, if they are then m2 is stored in the pool item. Also moved very basic checking functions from rail_map.h to rail_map_base.h to allow compiling when signalex_map.h uses those functions. Needs cleaning up.

[Update 7] Suspended. This simply won't get into the trunk (I may be wrong) unless something actually uses it, so I'm focusing on signal extensions now and game-play changes which would require the use.

[Tekky]

I like your idea of storing extra information in signals outside the map array. In fact, I have had a very similar idea myself some time ago.

The reason why I did not implement my idea was that I determined that, in order to implement my other ideas, I would need to somehow establish a link between a train's orders and the signal's orders.

For example, if the signal is supposed to send low-priority trains (for example freight trains) down one line and high-priority trains (for example passenger trains) down another line, the signal orders would somehow have to be able to determine whether a train is marked as high-priority or not. Such information could be defined in the train's orders. I was thinking of allowing the user to define a list of property variables for the train, so that the signal orders could access the property variables. For example, the train could define the property variable "isHighPriority" and set its value to "true" and this property could then be read by the signal orders, in order to determine which line to send the train to. Also, the train's orders should also be able to manipulate these propertly variables. For example, after a train has finished its full-load order, it should be able to set its property "isHighPriority" to true, and after unloading, it should set this property back to false, so that loaded trains are given priority over empty trains.

Such "programmable signals and train orders" would of course not be interesting to the average user. However, for advanced users, I am sure it would allow a great amount of flexibility.

[crakinshot]

Well I was thinking of altering the pathfinders so that, if the tile had a SignalEx ID in the tile, would send some information to a signalex cost function. That way you're not actually making the signals choose, just giving extra information to the pathfinders in the form of A) don't pass, and B) here is the cost for passing me, given the train information, and direction you gave.

Personally, I'm not sure about TTDPatch's restricted signals and programmed signals, it seems very complex and I wonder whether anyone would enjoy using them. Indeed, I believe the devs here don't like them. I'm heading toward theatre-based programmed signals. So, a signal will define theatre's (paths, areas) and then you'd place simple conditions upon those theatre's for trains. Not entirely, worked it out yet.

The main idea being, you can make a GUI and set up the theatres and conditions with a menu and mouse clicks on the map... rather than actually coding logic. Then ultimately, it would all combine down to a single number for pathfinder cost. So it wouldn't drastically alter the pathfinders. In addition, you'd have automatic setup for a basic signal. i.e. a signal would look ahead for the first 'left' turn and 'right' turn and make the three paths (including straight) into three theatres/branches. So, from a user point of view, if you wanted slow trains to 'favour the left branch' you'd simply make an extended signal, click on the left branch (the one that was automatically defined) and set a new cost condition.

But this is all extension. The immediate work is to get very basic support for extended signals accepted for the trunk. Then other patches can slowly add on support for signalEx, without breaking anything in the process.

There are only 16 bits free in the tile (for signalrail) and if anything else is accepted into the trunk, that uses them, It'll make life difficult for me. Better to add on extended signals here and now and then allow people to extend upon them with as much as they like. Ideally, you'd have a flag in m6 to say you're using an extended signal and then use the whole of m2 for the index. If not then m2 is defined as before. But this would change so many things. What I have no doesn't affect anything and it pure extension.

[planetmaker]

Sounds like an awesome idea I have to admit.

I see one big collision though: the railtypes which might or might not be in the pipe somewhere and which probably also would eat a few bits of the map array...

Wouldn't it suffice to use just the bit for the free signal type for this and have the pool items store the signal direction and tile type they're associated with, which could then be looked up?

[crakinshot]

Well I've abstracted the tile bit handling into the SignalExMap static functions. They can be changed to suit. I'm not sure there is a free bit in the signal type. PBS is (101) I think thus the 3rd bit is being used?

Anyhow, it only takes 1 bit to define if it has extensions. If it does then it'll use up all the free bits to make an index. But if that first flag is set to 0, then the other bits could be used for other things. Unfortunately, you'd then only be able to use those other things if signal extensions was disabled.

One way to go is as you say, 1 bit flag then move existing bits from the tile array into the pool item. But that might require a lot of changes if access to those bits aren't centralised. Ideally, you'd do this for m2... if its an extended signal then all m2 data is now in the pool item and m2 is a 16-bit index into the pool. But this would require altering everything that directly alters m2 for a RAIL_WITH_SIGNAL class.

To be fair to who ever made the Pooling class, it holds up really well when adding in a couple hundred of these extended signals in one go.

[crakinshot]

Okay, I've managed to put in the m2 location handling. If the tile has extended signals then m2 data is in the pool item, otherwise the m2 data is in _m[t].m2, as before. Altered the rail_map.h functions so that they access the correct variable (either from the pool or from the tile).

When an extended signal is made for a tile the m2 data is copied from the tile to the pool item. Similarly when the extended signal is destroyed from a tile the m2 is first copied back to the tile, from the pool item.

Code needs cleaning up, but I think its pretty much there, in its basic form. It won't actually do anything yet; not until someone uses and extends upon the SignalEx structure.

[Tekky]

I really like the work you are doing.

However, I am not sure if it is a good idea to limit this to signals. Instead, it may be better to allow a TileEx pool item to be defined for every kind of tile, instead of just for signals.

For example, I was thinking about storing all information about the 'track segments' of a rail network in a separate graph outside the map array, where a 'track segment' is defined as a length of track from one junction/switch/signal to the next junction/switch/signal. Since such a 'track segment' is the smallest building block required by the pathfinder, the pathfinder will be more efficient if it uses entire track segments instead of working on individual tiles. Also, such an approach would allow the user to set properties to the individual 'track segments', for example to restrict it to one-way, set a minimum or maximum speed, etc.

Therefore, in my example, it may be useful for every railroad tile to contain the index of the 'track segment' pool item that it is part of. This 'track segment' pool item could be implemented as a sub-class of the TileEx class or as a C/C++ union. In the rare case where a tile contains several pieces of extended information, such as both 'track segment' and extended signal information, a more complex TileEx pool item would be required.

Since it would be expensive to always look up the TileEx structure if one exists, the map array should also have some additional bits defined which determine what kind of information the TileEx structure holds. That way, it would not be necessary for an algorithm to look up the TileEx structure in order to determine whether it contains any information relevant to algorithm, since what is stored in the TileEx structure is described in the map array. For example, it should be possible to determine whether a TileEx structure contains extended signal information by looking at a certain bit in the map array. That way, an algorithm that needs to access extended signal information would only need to dereference the TileEx pool item if a specific bit in the map array indicates that it contains extended signal information.

[crakinshot]

hmm, so generalise it even further. The real problem is that it would need an actual 'unused bit' in the tile. Unfortunately, there isn't a common single bit to be had. For instance, a house-class tile used all the bits (including m7). To do what you ask for you'd have to add on an additional byte to the tile array, dedicated solely for the TileEx flag and the remaining 7 bits to define some basic look ups (has SignalEx, etc...). You can't limit to just the rail, road, crossroad, station, etc, tiles either as they don't have a common unused bit either.

If I get you right, you are also suggesting tiles share an extension ID. So that the pool items are not limited to one tile. Not impossible to do, but would have to be done correctly so that a counter was maintained in the pool item, so you only delete the item when no tile links to it. But then you'd have multiple m2 backups. :/

I'm interested to know whether you're trying to do the junction information? I personally will need something similar in the long run for my feathered signals (signals that indicate what route is set). I was going to simply have the information stored in SignalEx struct. Along the lines of start and end TileIndex.

The main issue though might be the performance. At the moment, if a tile has a signal then further checks see if its an extended signal. What you'd be asking for is for that check to be the absolute first check/access for every tile lookup. This is an example of how I've handled the m2 access for the signal-tile checks.

Code: Select all

static inline TrackBits GetRailReservationTrackBits(TileIndex t)
{
 	assert(IsPlainRailTile(t));

	uint16 &m2_ref = (HasExtendedSignals(t) ? _signalex_pool.Get(_m[t].m2)->m2 : _m[t].m2);

	byte track_b = GB(m2_ref, 8, 3);
 	Track track = (Track)(track_b - 1);    // map array saves Track+1
 	if (track_b == 0) return TRACK_BIT_NONE;
	return (TrackBits)(TrackToTrackBits(track) | (HasBit(m2_ref, 11) ? TrackToTrackBits(TrackToOppositeTrack(track)) : 0));
 }

So for any tile access you'd have to check the tile 1 extra time, then a code branch and a possible dereference into the TileEx structure. Could make the whole-screen re-drawing quite a lot more labour intensive.

[Tekky]

The real problem is that it would need an actual 'unused bit' in the tile. Unfortunately, there isn't a common single bit to be had. For instance, a house-class tile used all the bits (including m7). To do what you ask for you'd have to add on an additional byte to the tile array, dedicated solely for the TileEx flag and the remaining 7 bits to define some basic look ups (has SignalEx, etc...). You can't limit to just the rail, road, crossroad, station, etc, tiles either as they don't have a common unused bit either.

Yes, houses and stations don't have any free bits. However, both houses and stations use m2 as a station/town index. In other words, they already implement the possibility of having extended tile information outside the map array. The only difference to your extended signal information patch is that several tiles can reference the same station/town index, whereas an index to a SignalEx structure would never be shared among several tiles. Therefore, it may be the best solution to implement your SignalEx/TileEx patch in such a way that it can also be used for storing station and town indexes.

The main problem I see with the above approach is that it may be necessary to store several sets of extended information for the same tile. For example, since one tile can contain up to 4 block signals (2 double signals) and up to 2 path signals (=PBS signals) when using parallel diagonal track, you would likely require 4 SignalEx structures. However, even if one single SignalEx structure were sufficient for the whole tile, there would still be a problem if the storage of additional extended information were required, such as an additional 'track segment' index in the example of my last post. I am not sure how this could be best accomplished, since it would be expensive to make tiles point to lists of different kinds of extended information. However, if such cases are rare, this solution may be acceptable.

If I get you right, you are also suggesting tiles share an extension ID. So that the pool items are not limited to one tile. Not impossible to do, but would have to be done correctly so that a counter was maintained in the pool item, so you only delete the item when no tile links to it. But then you'd have multiple m2 backups. :/

Yes, as I pointed out in my first paragraph of this message, such extension ID sharing is also how station indexes currently work in OpenTTD, although I don't believe that they use reference counting.

I'm interested to know whether you're trying to do the junction information? I personally will need something similar in the long run for my feathered signals (signals that indicate what route is set). I was going to simply have the information stored in SignalEx struct. Along the lines of start and end TileIndex.

My basic idea is that it would be more efficient for the pathfinder and track reservation system to work with whole 'track segments' (as defined in my previous post) instead of working with individual tiles or track pieces. I am hoping that not being bound by the limitations of the map array will allow greater flexibility.

For example, I hope it will allow different types of train reservations which could be used by a train scheduling system, which could take things like train priority into account. These train reservations would be stored outside the map array in the graph of 'track segments'. For this to work efficiently, every railroad tile in the map array would require an index to the 'track segment' that it is part of. In the case of the different track pieces on the tile being part of different track segments, a link to one of these 'track segments' would be sufficient, as all neighboring 'track segments' can easily be retrieved using the graph of 'track segments'.

Please see this post of mine (only that single post, not the entire thread) for further information about my proposed different types of reservations.

The main issue though might be the performance. At the moment, if a tile has a signal then further checks see if its an extended signal. What you'd be asking for is for that check to be the absolute first check/access for every tile lookup. This is an example of how I've handled the m2 access for the signal-tile checks.
(...)
So for any tile access you'd have to check the tile 1 extra time, then a code branch and a possible dereference into the TileEx structure. Could make the whole-screen re-drawing quite a lot more labour intensive.

I don't think it will be very expensive to check a single bit in a map array in order to determine whether a tile contains extended information, since the entire tile contents will already be in the Level 1 CPU cache. It will only get expensive if this extended information must be dereferenced, since this will most likely be a 'cache miss'. However, I am no expert on CPU profiling.

[crakinshot]

Hmm, well it might be possible, but it wouldn't be a clean extension as you'd have different locations for the flag bit for each tile class.

Personally, if I was going to do what you were thinking about I'd simply use an external tree/graph. Essentially what you are talking about is doing what the pathfinder already does. Except you follow every path and then store the tree/graph in memory. Then it would just be a matter of maintaining the pointer to the segment node a train is currently in. It would be by far the cleanest way to integrate your idea, IMO.

[Eddi]

I just skimmed the thread and wanted to chime in.

Tekky talked about subclassing a generic TileEx pool item. that is not a great idea, because of the internals of the pool memory management it is necessary that all members of the same pool must have the exact same size, so subclassing is not really possible

[Rubidium]

Tekky talked about subclassing a generic TileEx pool item. that is not a great idea, because of the internals of the pool memory management it is necessary that all members of the same pool must have the exact same size, so subclassing is not really possible

You're forgetting the most important part here: "when writing your code for 0.7 or before". Or in other words, with current trunk you can subclass... you need to do some tricks to make it really useful though. See vehicles/stations/waypoints.

[Tekky]

Hmm, well it might be possible, but it wouldn't be a clean extension as you'd have different locations for the flag bit for each tile class.

I wouldn't worry much about that. Sometime in the future, the whole map array will have to be expanded anyway. This expansion could be used as an occasion to reorganize the entire map array, to make it cleaner and more consistent. Such a reorganization would be not much work, as long as the implementation of the map array is limited to files in the category 'map accessors', which I believe is already the case. Until then, it won't hurt much if a small amount of additional processing is required due to the flag being in a different location for each tile class.

Personally, if I was going to do what you were thinking about I'd simply use an external tree/graph. Essentially what you are talking about is doing what the pathfinder already does. Except you follow every path and then store the tree/graph in memory. Then it would just be a matter of maintaining the pointer to the segment node a train is currently in. It would be by far the cleanest way to integrate your idea, IMO.

I'm afraid that even if the pathfinder always uses this external graph, it will still be necessary that the tiles have references to the track segment they are part of. For example, if you bulldoze a tile with a track piece on it, the external graph will have to be updated, since the layout of the track segments will have changed. If that tile does not contain a reference to at least one track segment in the graph, the entire graph will have to be traversed.