QuoteIn the beginning, there was nothing. And Hajo said: "Let there be welt". And welt there was. And Hajo filled welt with planquadrat_ts. And Hajo saw that it was good.
Since I have to delve into the internals of the code to make a proposal for a two-lane unidirectional road implementation, I thought it would be nice to write down my quest impressions while wandering through the code. Please make suggestions, corrections...
Let's start.
Information applies to r5023.
CHAPTER 1: WORLDwelt (world) is the most important object in Simutrans. It's of class
karte_t (simworld.h). It has a bidimensional array of
planquadrat_t, named
plan. For each bidimensional coordinate,
koord, (x,y), there is a
planquadrat_t object. You can retrieve it with the method
planquadrat_t *lookup(koord).
karte_t is a singleton (only one world per invocation), but Hajo was not sure about that decision, as we can see in boden/grund.h:
Quote /**
* Pointer to the world of this ground. Static to conserve space.
* Change to instance variable once more than one world is available.
* @author Hj. Malthaner
*/
static karte_t *welt;
planquadrat_t (simplan.h) objects are containers for ground elements (
ground_t) that share the same position of the map, but have different heights. You can get the element at a certain height with the method
grund_t *get_boden_in_hoehe(sint16). You can directly get the ground object from the welt with
grund_t *karte_t::lookup(koord3d).
grund_t (boden/grund.h) objects contain a list (
dinge) of all things (
dings) that belong to a certain 3d position of the map.
grund_t objects may have ways (road, railway, ...), from 0 (no) to 2. They are always at index 0 and 1 in the object list
dingliste_t. (other objects follow at higher indexes).
grund_t objects also have an image (
bild) that depends on the type of slope, climate, etc. All other objects belonging to that grund_t also store their images themselves. The methods in connection with the ways the object has are (other types used in them are explained below):
- Methods to know how many ways there are: bool hat_wege(), uint8 has_two_ways()
- Methods to get (or know if there is) one of the ways: weg_t *get_weg_nr(int), weg_t *get_weg(waytype_t), bool hat_weg(waytype_t)
- Methods to know the type of way: uint8 get_styp(waytype_t), bool ist_uebergang() (has tram)
- Methods to know the allowed directions for a certain way: virtual ribi_t::ribi get_weg_ribi(waytype_t), virtual ribi_t::ribi get_weg_ribi_unmasked(waytype_t)
- Method to get the way object: wayobj_t *get_wayobj( waytype_t)
- Methods to build/destroy ways: sint64 neuen_weg_bauen(weg_t *, ribi_t::ribi, spieler_t *) (build new way, spieler=player), bool weg_erweitern(waytype_t, ribi_t::ribi) (extend way), sint32 weg_entfernen(waytype_t, bool ribi_rem) (delete way)
- Method to move along a way: bool get_neighbour(grund_t *&to, waytype_t, koord dir) (returns the grund_t we arrive to, if any, if we want to move (+-1,0) or (0,+-1) without leaving the way). If type is invalid_wt then only slopes are checked and no concrete way is followed.
grund_t objects may be of one of these types (
virtual typ get_typ()):
- 1 grund_t::boden (normal ground)
- 2 grund_t::wasser (water)
- 3 grund_t::fundament (foundations for other objects: houses, etc.)
- 4 grund_t::tunnelboden
- 5 grund_t::brueckenboden (bridge ground)
- 6 grund_t::monorailboden
grund_t objects may have none or several of these flags:
- 0 grund_t::keine_flags (no flags)
- 1 grund_t::dirty (needs to be redrawn)
- 2 grund_t::is_kartenboden (is the actual ground which grass/water/house/way on it)
- 4 grund_t::has_text
- 8 grund_t::marked (will have a frame (ditto))
- 16 grund_t::draw_as_ding (is a slope, etc.)
- 32 grund_t::is_halt_flag (is part of a halt=stop)
- 64 grund_t::has_way1 (has, at least one way)
- 128 grund_t::has_way2 (has two ways attached)
grund_t is an abstract class. Known subclasses are:
boden_t (boden/boden.h),
wasser_t (boden/wasser.h),
fundament_h (boden/fundament.h),
brueckenboden_t (boden/brueckenboden.h),
monorailboden_t (boden/monorailboden.h). Tunnels (
tunnelboden_t) are a subclass of
boden_t.
Way types (
waytype_t) are such fundamental data in Simutrans that they are defined in simtypes.h (together with integer sizes, for instance). They are:
- -1 waytype_t::invalid_wt
- 0 waytype_t::ignore_wt
- 1 waytype_t::road_wt
- 2 waytype_t::track_wt
- 3 waytype_t::water_wt
- 4 waytype_t::overheadlines_wt
- 5 waytype_t::monorail_wt
- 6 waytype_t::maglev_wt
- 7 waytype_t::tram_wt
- 8 waytype_t::narrowgauge_wt
- 16 waytype_t::air_wt
- 128 waytype_t::powerline_wt
Things are that, things (abstract
ding_t in simdings.h). They have an owner (
besitzer) and may or may not be physically located in a position of the
welt. Vehicles and ways are things, but not only. There are a lot of types (smoke, buildings, tunnels, bridges, depots, roadsigns, ground objects, labels, all kinds of vehicles...). Interestingly enough, a thing may be a vehicle and a way at the same time, which opens a huge world of possibilities... They also have an associated image (
bild). If we know the index of a certain thing, we can retrieve it with
ding_t *grund_t::obj_bei(uint8).
And what about time? Well, let's hear the wise words of Prissi, the Magician:
Quote from: prissi on June 17, 2011, 05:30:47 PM
Each stuff [thing] can have three periodic calls: for very regulary and fast actions which require exclusive access on the map (moving cars, collision avoidance) there is sync_step, called before every frame. Slower actions like route_finding, way building etc. is done in step(), where the map can change in between slightly. Some objects (most notable trees) require seasonal changes, which are covered by the relatively new action method of check_season();
All objects that must be advanced in synchrony must therefore implement the interface
sync_steppable (in ifc/sync_steppable.h).
welt keeps a list of
sync_steppables (
sync_list) and periodically calls the only method they have to implement to become a fully-fledged
sync_steppable guy:
virtual bool sync_step(long delta_t).
- delta_t represents how many simulation ticks the object must advance.
- It returns false when the thing wants to be removed from the sync_list and deleted.
Scheduled additions and deletions from the
sync_list are done carefully through intermediate lists and also in sync.
And
welt moves around in its
sync_step method:
void karte_t::sync_step(long delta_t, bool sync, bool display),
- with delta_t the simulation ticks to advance,
- sync implies that things will be added/deleted to the sync_list and sync_step methods will be actually called,
- anddisplay means that some time consuming things like message displaying, follow convoy or water animation won't be done (like in some steps of fast forward mode).
CHAPTER 2: WAYS (AND ROADS)One of the things that we can find on a
grund_t are ways (abstract
weg_t in boden/wege/weg.h). In fact, ways are a subclass of a subclass of
ding_t (abstract
ding_no_info_t in simdings.h). An example of a way is a tile of asphalt road.
A
weg_t may have one or more of these flags (
uint8 flags) activated:
- 1 weg_t::HAS_SIDEWALK (void set_gehweg(bool), bool hat_gehweg())
- 2 weg_t::IS_ELECTRIFIED (bool is_electrified())
- 4 weg_t::HAS_SIGN (bool has_sign())
- 8 weg_t::HAS_SIGNAL (bool has_signal())
- 16 weg_t::HAS_WAYOBJ (has_wayobj())
- 32 weg_t::HAS_CROSSING (bool is_crossing())
- 64 weg_t::IS_DIAGONAL (bool is_diagonal(), if there is a curve in one direction followed by another curve in the opposite direction, the diagonal image is used if available)
- 128 weg_t::IS_SNOW (bool is_snow())
Besides, a
weg_t may belong to one of these
system types:
- 0 weg_t::system_type::type_flat
- 1 weg_t::system_type::type_elevated
- 7 weg_t::system_type::type_tram
- 64 weg_t::system_type::type_underground unused
- 255 weg_t::system_type::type_all (also used for rivers) (With this sytem type a way will by only listed in the extension menue by convention. Ways, whose description do not return an icon, will not be listed at all.)
To get the way type, use:
virtual waytype_t get_waytype(). Although the type of the ding_t is always
ding_t::way, of course:
Quotetyp get_typ() const { return ding_t::way; }
One can imagine that each way tile is like a city with four invisible walls: nothern, souther, eastern and western. There may be a wall or a connection to the adjacents way tiles. This is marked by the
ribis (Richtungsbits) o bits of allowed directions.
weg_t::ribi is a 4-bit long bit field, each bit is 1 if that direction is allowed. The order is WSEN. To retrieve this information, use:
ribi_t::ribi get_ribi_unmasked().
Even if there is a connection to an adjacent tile, it is possible that a certain direction is forbidden for vehicles. This is marked with the ribi mask (
ribi_maske). It is another 4-bit long bit field. This time, a 1 means that the corresponding direction is forbidden. To retrieve or set this information, use:
void set_ribi_maske(ribi) or
ribi_t::ribi get_ribi_maske(). To retrieve the combined final effect of ribi and ribi mask, use:
ribi_t::ribi get_ribi().
Because of a
weg_t is a
ding_t, it has an associated image. However, that image depends of the ribi, the slope, the climate, etc. There is a method to calculate the image used (
void calc_bild()). This method is to be called each time we modify the ribi values with:
void ribi_add(ribi_t::ribi),
void ribi_rem(ribi_t::ribi ribi),
void set_ribi(ribi_t::ribi ribi).
The
weg_t has a description,
Beschreibung, o simply
besch when it is hanging out with friends (
weg_besch_t in besch/weg_besch.h). Those descriptions come from the paksets. The information includes everything pak-dependent: introduction date, maximum speed,... With these two methods, you can retrieve/set the description:
void set_besch(weg_besch_t *) and
weg_besch_t *get_besch(). The maximum speed is not taken directly from the description only, since it may be altered by other objects in the
grund_t. For instance, a 80km/h tramway inside a city has a maximum speed of 50km/h.
Inside
weg_besch_t, we only find these properties relevant to the problem in hands:
uint8 wtyp (type of way),
uint8 styp (system type).
Known subclasses of
weg_t are:
strasse_t, road, (boden/wege/strasse.h),
kanal_t (boden/wege/kanal.h) and
schiene_t, railway, (boden/wege/schiene.h).
Another objects that may appear in a
grund_t in connection with ways are
way objects (
wayobj_t in dings/wayobj.h). These are objects whose images change depending on the configuration (ribis) of the way tile. The most typical of these are catenaries of the like.
In this point of our travel, we have to choose among the different subclasses of
weg_t.
strasse_t (in boden/wege/strasse.h) is chosen, since we are dealing with roads.
strasse_t is a boring class, though. It only returns its type if asked, allows for the inclussion of sidewalks, or does domestic chores... It has no known subclasses either (a bachelor, to say it so)
[[
To be continued...]]
Thank you very much !!!
I took the freedom to edit some incorrectnesses.
Please do.
I changed the wording of your corrections. I have a question, though. If there can only be one way per grund_t, what is the purpose of grund_t::has_way2 flag and associated methods: has_two_ways, etc.? Maybe a leftover of a past implementation?
Oh, I misunderstood you there! There can be 0..2 ways on one tile, the are at index 0 and 1 in the object list (dingliste_t). Edited it back.
Ups! We have been editing at the same time... :o Please, redo.
Please post Chapter 3 in a new post.
Great idea to put documentation forward.
Great documentation Isidoro, very well explained, keep up the good work!
Thanks both. Nonetheless, things are getting complicated with next chapter... (vehicles).
Edit: I've made some additions to Chapter 1 dealing with simulation time since they affect vehicles. They are in green. Please check.
These web editors are nice for a beginner, but they are a pain in the long run. For instance, colors and lists don't marry well...
Great, I wish I would have something like that when I started ... Some additions in blue from me.
Quote from: isidoro on December 18, 2011, 02:24:23 AM
These web editors are nice for a beginner, but they are a pain in the long run. For instance, colors and lists don't marry well...
Click the "toggle view" button to change between GUI editor and old tag editor.
@prissi: much appreciated. With vehicles things are getting more complicated. I will surely need more help from you guys, when that part is posted.
@Isaac: thanks, much better. I'll keep a copy offline though, just in case I mess it all.
I'd say this should also go into the wiki - and yeah, an offline copy never hurts. hehe
The more I dig into the code, the more I see that the project is feasible. My initial plan was to continue chapter 3 with vehicles and convoys but I think now that "Ribis and Slopes" is much better. Any comments/corrections are welcome, but I would prefer you to cite the relevant part and allow me to correct the problem myself since now I keep a local copy and it is difficult to sync everything otherwise.
I think that this documentation about ribis and slopes would be a thousand times clearer with some clarifying pictures. Maybe some of the pakset authors (and therefore artists) dare contribute for this and, this way, contribute to the code without even knowing a line about programming...
CHAPTER 3: MORE RIBIS, AND SLOPES TOO (r5023)Slopes are implemented with the help of class
hang_t in dataobj/ribi.h. Although there is a provision in Simutrans for use the so called
double grounds, we will deal here with normal behavior.
Slopes are special tiles that are not flat. One or more that one of their corners may be raised one height unit. If one or three corners are raised, we arrive to a shape formed by two triangles: one of them flat and the other, in slope. If two corners are raised, we have two cases. First happens when the raised corners are opposite corners and second case is when the raised corners lay on one side of the square of the tile. In the former, a
V shape happens. In the latter, we have a
flat slope, suitable to build an upwards road there, for instance.
A slope is thus expressed through a bit field indicating which corners are raised, following this diagram:
^
[8] NW | NE [4]
\|/
<---+--->
/|\
[1] SW | SE [2]
v
So, a flat slope going up from north to south (a
north slope in game terminology) will have its SW and SE corners raised, and has therefore number 3 (1+2).
There are some flags too (and the corresponding static methods to check them (
bool ist_einfach(uint8), etc.):
- 1-wegbar_ns: a way in the north south direction is allowed, either flat or in slope: 0, 3, 12, 15 cases
- 2-wegbar_ow: idem. in the east west direction: 0, 6, 9, 15 cases
- 4-einfach: it is a flat slope: 3, 6, 9, 12 cases
And some types of slopes, at least for flat slopes:
- 0-hang_t::_typ::flach: flat
- 3-hang_t::_typ::nord: going up from north to south
- 6-hang_t::_typ::west: going up from west to east
- 9-hang_t::_typ::ost: going up from east to west
- 12-hang_t::_typ::sued: going up from south to north
- 15-hang_t::_typ::erhoben: flat, but all raised
And static methods to get information regarding slopes:
- bool is_sloping_upwards(uint8,sint16 offset_x,sint16 offset_y): used to see if the previous tile and the slope make us go up
- bool ist_gegenueber(uint8,uint8): (is opposite), true if both slopes are flat and have the opposite corners raised. For instance, a north slope and a south slope will give true
- uint8 gegenueber(uint8): gives the opposite slope if the argument is a flat slope, or hang_t::_typ::flach, in other cases
- uint8 rotate90(uint8): gives another slope that is the argument but rotated 90 degrees clockwise. For example, a north flat slope would give an east flat slope. This method does not require their arguments to be flat
The direction bits or
ribis mark what is possible and not possible when moving along in Simutrans. For a way tile, they are like doors that allow o deny communication with neighbor tiles. The denial may be due to the real absence of a path to the neighbor tile (there is no road there), or because there are signs or other things forbidding to go there.
Ribis allow for all known railway graphic tiles. But some notable possibilities are not accounted for. For instance, there is a ribi that allow connection for all possibilities: from north to east, from north to south, etc. But there is not a ribi to allow to go from north to west, and from south to east, but disallows to go from north to south at the same time. To say it more concisely, once the vehicle is inside a tile and intends to move to a neighbor tile, to make a decision, it doesn't remember from what direction it came. It only sees opened/closed doors to those tiles.
Ribis are made of a combination of the four basic directions in this bit order WSEN. Thus, all possible directions are:
0-ribi_t::_ribi::keine (no) 1-ribi_t::_ribi::nord
2-ribi_t::_ribi::ost (east) 3-ribi_t::_ribi::nordost
4-ribi_t::_ribi::sued (south) 5-ribi_t::_ribi::nordsued
6-ribi_t::_ribi::suedost 7-ribi_t::_ribi::nordsuedost
8-ribi_t::_ribi::west 9-ribi_t::_ribi::nordwest
10-ribi_t::_ribi::ostwest 11-ribi_t::_ribi::nordostwest
12-ribi_t::_ribi::suedwest 13-ribi_t::_ribi::nordsuedwest
14-ribi_t::_ribi::suedostwest 15-ribi_t::_ribi::alle (all)
One must be careful when using this. The physical bit order is WSEN, with W the most significant bit, but the constants are expressed just the opposite way: NESW... Here we will keep the constants' convention.
Some constants regarding ribis are defined, in order to group similar ribis:
1-ribi_t::einfach (only one-exit, i.e. dead end): N, S, E, or W.
2-ribi_t::gerade_ns (exit in N, S, or both): N, S, or NS
4-ribi_t::gerace_ow (exit in E, W, or both): E, W, or EW
8-ribi_t::kurve: NE, SE, NW, or SW, since they represent curves when in a way (except for diagonals, which are, in fact, curves in opposite directions: curve left-curve right-curve left-curve right,... Diagonals are also considered
kurve, when we look at them inside one tile)
16-ribi_t::twoway (exactly two exits, straight or curve): NS, EW, NE, SE, NW, or SW
32-ribi_t::threeway (three or more exits): NSE, NEW, NSW, SEW, NESW
And the corresponding static methods are defined:
- bool is_twoway(ribi)
- bool is_threeway(ribi)
- bool ist_einfach(ribi)
- bool ist_kurve(ribi)
- bool ist_gerade(ribi): dead end or straight line
- bool ist_getade_ns(ribi) and bool ist_gerade_ow(ribi)
- bool ist_orthogonal(ribi,ribi): returns true if both are dead-ends or straight lines and orthogonal (90 degrees angle)
- bool ist_exakt_orthogonal(ribi,ribi): the same, but it should also works for diagonals. Unfortunately, it doesn't work for all cases. For example, ist_exakt_orthogonal(NE,SE) returns true, which is good, but ist_exack_orthogonal(NE,SW) returns also true, and should be false. For 3-ways, return value doesn't make sense too, but these cases aren't probably intended to be used though.
- bool ist_kreuzung(ribi): is cross -> always false (most probably a leftover from the past, not used any more)
Some other static methods serve ribi transformations:
- ribi rueckwaerts(ribi): returns the opposite ribi, that is, one with allowed and forbidden directions opposite from the given one. Exception are the dead-end ribis: for them, the opposite dead-end is returned. And also straight lines, for which themselves are returned. This is the table:
All or nothing: Dead-ends: Straight: Curves: 3-ways:
0 -> NESW N->S NS->NS NE->SW NSE->W
NESW -> 0 E->W EW->EW SE->NW NSW->E
S->N NW->SE NEW->S
W->E SW->NE SEW->N
As you can see in the table, if you apply the method two times, you don't always get the original ribi. - ribi get_forward(ribi): tries to return all the directions that don't get farther than the direction expressed by the ribi, if any.
This is the table:
All or nothing: Dead-ends: Straight: Curves: 3-ways:
0 -> NESW N->NEW NS->0 NE->NE NSE->0
NESW -> 0 E->NSE EW->0 SE->SE NSW->0
S->SEW NW->NW NEW->0
W->NSW SW->SW SEW->0
- ribi rotate90(ribi): returns the ribi rotated 90 degrees clockwise: N->E, NE->SE, etc.
- ribi rotate90l(ribi): the same, but counterclockwise: N->W, NW->SW, etc.
- ribi rotate45l(ribi): tries to rotate 45 degrees counterclockwise. It works nice in the main series. For other, who cares:
N->NW->W->SW->S->SE->E->NE->N, and so on...
0->0, NESW->NESW, NS,ES->0, NSE->NE, NSW->SW, NEW->NW, SEW->SE
- ribi rotate45(ribi): the same, but clockwise
- dir get_dir(ribi): for ribis with a correspondig compass direction, returns that direction, for all others, returns dir_invalid
These methods are mainly based on precalculated tables, to gain some speed. One of them is
doppelr. This is the content:
All or nothing: Dead-ends: Straight: Curves: 3-ways:
0 -> 0 N->NS NS->NS NE->0 NSE->0
NESW -> 0 E->EW EW->NS SE->0 NSW->0
S->NS NW->0 NEW->0
W->EW SW->0 SEW->0
So, this table gives the straight direction and opposite for dead-ends and straight lines. The correspondig getter method is: ribi doppelt(ribi) (watch out the
t).
We have some helper methods that returns ribis from a great variety of data:
- ribi ribi_typ(koord): returns in what direction is the given coord from (0,0). If (0,0) is passed, ribi_t::keine is returned.
- ribi ribi_typ(koord from, koord to): returns in what direction is to going from from. Most of times it will give a diagonal (NE, NW, SE, or SW). It will only return a dead-end (N, S, E, or W) when from and to are aligned in exactly that direction. I guess (though not confirmed) that if this method is used to automatically choose a path from a point to another when building a road, for instance, there is a preference first to build diagonals and then straight ways.
- ribi ribi_typ(koord3d) and ribi ribi_typ(koord3d from, koord3d to): same as before, but with a 3d point and excluding the z coordinate.
There are two static methods that connect ribis with slopes and slopes with ribis:
- ribi ribi_typ(hang_t::typ): indicates, more or less, in which direction one goes up in this kind of slope. For instance, in a north flat slope one goes up if going to the south. In a slope with the SW corner raised, one goes up if going to the southwest. In a slope with all the corners raised except the southwest, one also goes up if goint to the northwest...
- hang_t::typ ribi_typ(ribi): it returns the corresponding flat slope for the dead-end ribis (north slope for the N ribi, south slope for the S ribi, and so on). In all other cases, it returns 0. In other words, for the four main directions of the compass it returns the flat slope that have the lowest corners in that direction
Finally, when talking about one direction of the compass a vehicle is driving to, we have:
ribi_t::_dir::dir_invalid=0, and
ribi_t::_dir::dir_nord=4
N
ribi_t::_dir::dir_nordwest=7 NW ^ NE ribi_t::_dir::dir_nordost=6
\|/
ribi_t::_dir::dir_west=1 W <--+--> E ribi_t::_dir::dir_ost=5
/|\
ribi_t::_dir::dir_suedwest=2 SW v SE ribi_t::_dir::dir_suedost=3
S
ribi_t::_dir::dir_sued=0
The same value is assigned to
dir_invalid and
dir_sued, is this a bug or a feature (those lazy southerners...)?
To be continued...
Very good, you spotted already some errors I think.
The behaviour of ist_exakt_orthogonal() is an error and needs to be fixed. And ist_kreuzung can certainly go ...
You start to mix directions and ribis somewhere in the lower part. directions "dir" are only eight and they are used to indicate the direction of vehicles. They cannot be combined (or at least the should not, i.e. they should be always <=7). Thus vehicle return dir, but ways return ribi.
Insofar dir_invalid could be 255. I am not sure it will be change the behaviour at all.
Thanks, prissi.
I've changed the direction part to the end. I didn't know it referred to different objects. I've also added a tag with the revision in the title of the chapter.
Next is vehicles and convoys and, hopefully, my proposal. Now I'm on vacation and have more time...
I'm very happy that things here are going on very well. :D
Keep it up dudes.
Chapter 4 is short, but intense...
CHAPTER 4: SIGNS (r5023)For Simutrans, all signs, traffic lights, and even signals in railway are
roadsign_t (in dings/roadsign.h), even if they are not on roads at all. The name is like that, probably for historical reasons.
roadsign_t is also
sync_steppable because traffic lights (and now private barriers) want to chage configuration once in a while.
Signs affect the directions a vehicle may follow, since some of those directions may be prohibited by the sign.
Ways have flags (
HAS_SIGN and
HAS_SIGNAL) and when set, the roadsign is searched and the information is retrieved. This is done due to performance.
Note that the
roadsign_t destructor resets the ribi-mask, and that means that only one sign must be allowed per tile.
To set the direction of the roadsign and the tile ribi mask accordingly, the
void roadsign_t::set_dir(ribi_t::ribi) method is used. These ribi_mask are considered when finding a route or when a vehicle hops from one tile to the following one in its route. This double checking is needed because something may have changed (a road is destructed, a new sign appears, etc.) since the time the route was calculated.
We can get information about sings in their description class (roadsign_besch_t in besch/roadsign.h). Their type can be one of these:
- roadsign_besch_t::types::NONE
- roadsign_besch_t::types::ONE_WAY: road forbidden direction
- roadsign_besch_t::types::CHOOSE_SIGN
- roadsign_besch_t::types::PRIVATE_ROAD: no city cars allowed beyond this point
- roadsign_besch_t::types::SIGN_SIGNAL
- roadsign_besch_t::types::SIGN_PRE_SIGNAL
- roadsign_besch_t::types::ONLY_BACKIMAGE ?
- roadsign_besch_t::types::SIGN_LONGBLOCK_SIGNAL
- roadsign_besch_t::types::END_OF_CHOOSE_AREA
A sign also holds the following information:
flags (types, as seen previously),
wtyp (way type), and
min_speedWe also find two useful methods:
bool is_traffic_light() (if on road and we have more than 4 images, it is a traffic light, since normal signs have only 4 images, one for each direction), and
bool is_signal_type() (if it is a railway signal: normal, pre or, longblock).
To be continued...
And chapter 5 is long, long, road, with many a winding turn...
CHAPTER 5: VEHICLES AND CONVOYS (r5023)Vehicles are other things (
ding_t). In fact, they are moving things. Their base class is
vehicle_basis_t (in vehicle/simvehikel.h). A
fahrer_t (driver), in ifc/fahrer.h, is what makes a vehicle a full vehicle, i.e. a
vehikel_t, also in vehicle/simvehikel.h. This class inherits from both previous classes:
vehikel_basis_t and
fahrer_t. No other class implements the
fahrer_t interface.
vehikel_basis_t, however, is the superclass of other moving objects (
movingobj_t in vehicle/movingobj.h) and
verkehrsteilnehmer_t, or users of the road, in (vehicle/simverkehr.h). The latter will give rise to the private city cars (
stadtauto_t) randomly moving in the streets of the game and, not less important, pedestrians (
fussgaenger_t), both in the same file as their parent.
If we want a
vehikel_t or several of them to move, we have to form a group of them, i.e. a convoy (
convoi_t in simconvoi.h). Convoys are
sync_steppable (movable, thus) and overtakers (if on roads). In the convoy code, there is an interesting remark by Hajo wondering if it is better to use pointers (they are faster) or handles (one can know if the object pointed to is still alive or not). Some objects are dealt with pointers, some with handles, in the game.
Let's have a look at convoys:
- Max vehicles is 4, except for railways, which is 24
- route_t route: the route of the convoy to the next destination: set of coordinates followed by the first vehicle of the convoy to go there
- linehandle_t line: line assigned to the convoy, if any
- schedule_t *fpl: schedule of this convoy (set of destinations it will follow)
- array_tpl<vehikel_t*> fahr and uint8 anz_vehikel: the set of vehicles that make up the convoy, and their number
- bool withdraw: the convoy is marked to die or not
- bool no_load: whether nothing will be loaded in this convoy
- bool recalc_data_front and bool recalc_data, whether the vehicles and/or the front vehicle hop
- sint32 wait_lock: time, in ms, this convoy must wait, due to traffic lights, a traffic jam, etc.
- sint32 brake_speed_soll (brake target speed), sint32 akt_speed_soll (target speed), sint32 akt_speed (current speed), sint32 previous_delta_v
- ribi_t::ribi alte_richtung: old direction
- sint16 steps_driven: only used when entering/leaving depots, sint32 sp_soll target steps each time the convoy moves
When moving, convoys and, of course, vehicles, move one or several integer space units called
steps, although in screen representation, finesse is more.
And these are interesting methods:
- uint32 move_to(karte_t &, koord3d &, uint16 start_index)
- void betrete_depot(depot_t *dep): called if entering a depot
- koord3d get_pos()
- uint32 get_length() and uint8 get_vehikel_anzahl(): get physical length of the convoy and number of vehicles
- bool sync_step(long delta_t): moving the convoy
- void step(): all other tasks: route search, loading,...
- void start(): start a convoy
- void ziel_erreicht(): called when the first vehicle reaches the target
- void suche_neue_route(): there has been a problem and a new route must be calculated. In fact, it only changes the state of the convoy to ROUTING_1 and resets the wait_lock, so that the convoy is not forced to wait
- vehikel_t* get_vehikel(uint16 i), vehikel_t* front(), vehikel_t* back(): get the vehicle at a given position (0, first), first vehicle, or last one
- void vorfahren(): setup vehicles before starting to move
- void warten_bis_weg_frei(int restart_speed): wait until the way is free
- virtual bool can_overtake(overtaker_t *other_overtaker, int other_speed, int steps_other, int diagonal_vehicle_steps_per_tile): I did it, I didn't document it, I don't know now
A convoy is a finite automaton and may be in one of these states:
- convoi_t::states::INITIAL: stopped and in depot
- convoi_t::states::FAHRPLANEINGABE: schedule has been changed and this convoy needs to recalculate things
- convoi_t::states::ROUTING_1: convoy must find a route to the next destination (because it must leave a station, some road tile in its precalculated route was destructed,...)
- convoi_t::states::DUMMY4: leftover kept to load old games
- convoi_t::states::DUMMY5: dito
- convoi_t::states::NO_ROUTE: the convoy is stopped because it has no schedule or cannot find a route to its next destination. In this situation, the wait_lock variable is set to a high value because, otherwise, the vehicle would continuously try to find a new route and waste a lot of CPU time
- convoi_t::states::DRIVING: the convoy is moving
- convoi_t::states::LOADING: the convoy is loading at a station
- convoi_t::states::WAITING_FOR_CLEARANCE: the convoy is stopped, but it is temporal (a traffic light, for instance). Start of waiting states
- convoi_t::states::WAITING_FOR_CLEARANCE_ONE_MONTH: same as WAITING_FOR_CLEARANCE, but have been waiting one month.
- convoi_t::states::WAITING_FOR_CLEARANCE_TWO_MONTHS: same as WAITING_FOR_CLEARANCE, but have been waiting two or more months If a new month starts in this state, you will get a "Convoi stucked" message.
- convoi_t::states::CAN_START: Convoi wants to leave depot
- convoi_t::states::CAN_START_ONE_MONTH: dito, but already waiting a month
- convoi_t::states::CAN_START_TWO_MONTHS: waiting two months ... If a new month starts in this state, you will get a "Convoi stucked" message.
- convoi_t::states::SELF_DESTRUCT: Convoy is marked for deletion. Exception, not a waiting state
- convoi_t::states::LEAVING_DEPOT reached from CAN_SART* In this state not all vehicles do full movements, as some are still in depot
- convoi_t::states::ENTERING_DEPOT In this state not all vehicles do full movements, as some are already in the depot
- convoi_t::states::MAX_STATES: to know how many there are
There is a lot of information in a vehicle pertinent to our matters. We must pay attention to these variables, since vehicle information is kept in them and usually the methods involved in managing a vehicle have few parameters, if any:
- ribi_t::ribi fahrtrichtung: (not a tropical disease, but in fact it means travel direction)
- uint8 use_calc_height:1 (a bit, true on a slope)
- uint8 drives_on_left:1 (another bit, true if in the UK and some other countries)
- uint8 steps, steps_next (steps the vehicle has traveled in this tile now and total steps this tile has (255 per tile, unless traveling in diagonal. Some less in that case))
- koord3d pos_next (state variable: the position of the next tile the vehicle is going to visit)
- sint8 hoff (vertical offsets for going uphill/downhill)
- uint32 fahre_basis(uint32 dist): basic movement, i.e., converts distance to travel to steps, try to advance as much as possible, and returns distance really traveled
- virtual void get_screen_offset(int &xoff,int &yoff,sint16): to calculate smaller steps (more resolution) for displaying
- virtual bool hop_check() and virtual void hop(): while traveling, a vehicle moves inside a tile until it is time to hop (jump) to the next. First method checks if hopping is possible (done by the first vehicle of the convoy) and second method actually hops. You know: Faith, hop, and charity, and the greatest of these is hop.
- virtual void betrete_feld() and virtual void verlasse_feld(): called when leaving (resp. entering) a tile when hopping
- virtual bool is_stuck(): true if didn't move for some time
- vehikel_basis_t *no_cars_blocking(grund_t *,convoi_t *,uint8 current_direction,uint8 next_direction,uint8 next_90direction): check for next vehicle if next tile is free
- ribi_t::ribi calc_richtung(koord start, koord end) and ribi_t::ribi calc_set_richtung(koord start, koord end): first method is not a static method though it should be. It calculates the adequate direction to go from start to end. Second method is similar, but it also sets the steps this tile has, since diagonals are shorter.
- virtual overtaker_t *get_overtaker()
- static void set_diagonal_multiplier(uint32 multiplier,uint32 old_multiplier), static uint16 get_diagonal_multiplier(), and static void set_overtaking_offsets(bool driving_on_the_left): set/get some static information. In the first case, diagonals adjustment so that they take less steps to travel thru a tile in diagonal. In the last case, the offsets one has to apply to a vehicle when overtaking depending on the direction and whether driving is done on the right side of the road or the left side
As said above, a vehicle must implement the
fahrer_t (driver, person who drives) interface. This is the contract (all methods are abstract):
- bool ist_befahrbar(grund_t*): (is accesible)
- ribi_t::ribi get_ribi(grund_t*): allowed directions depending on the ground
- int get_kosten(grund_t *,sint32 max_speed,koord from_pos): when searching for a route, how expensive it is to choose this possibility
- bool ist_ziel(grund_t *current,grund_t *starting): returns true for the way search to an unknown target (copied verbatim)
To be continued...
WOW ! You are actually documenting before implementing. That is better than in the multi-million-dollar SW workshop I'm working in... :P
And a fairly entertaining author's style. Nice.
I did some edit in blue.
And this interface exists more ore less (minus overtaker) since 2002. Thus documentation before implementation is not really adaquate ...
Thanks, missingpiece and prissi.
Here's the next chapter:
CHAPTER 6: SCHEDULES AND ROUTES (r5023)
A schedule (German fahrplan) is, in Simutrans terminology, a set of destinations a convoy must follow in its daily routine.
A route is a set of tiles a convoy must visit in order from its present position to the next destination. Routes are expensive to calculate (specially for open ways like the sea or air, where there are more possibilities) and this calculation is done as less frequently as possible and it is cached by the convoy. This means that if changes are made to the map, the route of the convoy may be stale and needs recalculation.
The convoi_t::drive_to method is used to (re)calculate the route of a convoy from its present position to the next destination. If calls the bool vehikel_t::calc_route method of its first vehicle and, if successful, it calls convoi_t::vorfahren (advance).
The bool vehikel_t::calc_route method just calls the route_t::calc_route method with the same parameters. And this latter method just calls route_t::intern_calc_route to do the hard work. Well, to be frank, the poor route_t::calc_route method also helps parking.
bool route_t::intern_calc_route returns true if it is able to find a route and false, otherwise. The method follows a A* sort-of algorithm (not sure of this) with a limit of MAX_STEPS steps. The cost function depends on the type of road, maximum speed, elements on a tile, upwards slopes (those set in fahrer_t::get_kosten), but also curves and sharp turns increment that value so that they are in fact discouraged.
Guess 1: Maybe, a kind of heuristic should be implemented for route calculation for ships and aircrafts so that nearer to destination tiles are tried first.
Guess 2: When there is only one possibility (and this happens a lot in roads and railways between crossroads, some calculations may be saved if we continue to the next crossroad). If fact, a single cost may be given to the entire path up to the new crossroad, since the only decision we can make is at crossroads (those are the important tiles to find a route).
To be continued...
Brilliant documentation, keep up the good work!
A question:
QuoteRoutes are expensive to calculate (specially for open ways like the sea or air, where there are more possibilities)
I can see why sea routes are expensive to calculate, but why is an air-route expensive? There are not any obstacles, are there? It is just getting the plane in the air, getting the plane on the ground again, and connect those two points with at most one diagonal and one straight line?
Am I overlooking something?
Quote from: Combuijs on December 31, 2011, 09:36:52 AMAm I overlooking something?
I'm not sure about it. Perhaps, mountains and buildings are considered as obstacles. And airplanes don't go through a straight line from an airport to another. Like ways and vehicles, they must obey the grid too, then they move along the N-S and E-W axises and in diagonals (NW-SE and SW-NE). Therefore, if the airports aren't aligned, the airplane will need to make at least a 45º turn in mid-air, 2 point for take-off and more 2 for landing, 5 points in total.
Air routes are dirt cheap to calculate, since nothing is calculated at all. If a max height for planes is mposed, then this might be another problem, but for now these are cheap (but long, du to take off circling, parking etc.)
Very expensive are boat routes. The worst case is the way around a large island. I really optimised very very much of this. The only thin "cheaper" would be a hierachical pathfinder, which exist as a patch. However, thoses routes were not very convincing and it was not much faster.
And finally, route search is also invoked by choose signs/signals, using the find_route function. Thus the behaviour of fahrer_t will change when target_halt is set.
Happy new year (we will need it) and thanks all for your kind comments.
Don't take the documentation too literal. Some things come from code inspection, some are guesses, some are things I remember from the forums (for example, prissi saying that sea routes is expensive), etc.
It seems to me that, at least in sea, there are a lot of possibilities (a lot of tiles) the algorithm has to check before reaching destination. In this kind of algorithms, an heuristic (that is to say, a guess) may be chosen. That consists of choosing, among all possibilities for the next tile that with
more chances to belong to the correct solution. In our case, tiles physically nearer to the destination should be tried first. It is only a chance. It may happen that in that direction there is only land and we must later go round that land...
When we have roads, there are much fewer tiles to check.
Going back to topic. Here comes another chapter. I'm near the end...
CHAPTER 7: MOVEMENT OF CONVOYS (r5023)The nature of convoys as
sync_steppable makes them suitable candidates for moving. Everything starts at the
bool sync_step(long delta_t) method of convoys.
In that method, the property
wait_lock is updated and, if still possitive, nothing is done.
Convoys are finite automata and, thus, their life cycle consists of jumping from one state to another. The only states that are urgent and, therefore, updated in a
sync_step are
LEAVING_DEPOT and
DRIVING. Let's see the latter.
In that state, the first thing that is done is to update the actual values of acceleration, speed (
akt_speed), and accumulated distance (
sp_soll). Next, the convoy is moved the accumulated distance by the
vehikel_basis_t::fahre_basis(distance_to_move) method. This method returns the actual distance the vehicle was able to move. If lucky, that distance will be the distance we asked it to move, but may be less. The rest of vehicles of the convoy are also moved and the smoke is generated.
The core work of all this is done by the
fahre_basis method. As it has just been said, it receives the distance we want the vehicle to move and returns how much of that distance the vehicle was able to move. The following is done in that method:
- the distance is converted to tile steps
- if the distance to be traveled doesn't imply hopping (jump to the next tile) just update the steps traveled and return
- In the other case, hop as long as it needs be.
- This hopping may be ended either because we have reached our target distance or because the hop_check method fails
- All calculations in the hop_check method are done by the first vehicle of the convoy. It checks:
- if we have reached destination
- if next tile exists, is passable for this kind of vehicle (ist_befahrbar) and the route for this convoy is not empty (else the convoy is marked for choosing a new route asap)
- if combined ribi and mask allow entrance (else new route)
- if the destination tile is free (no other interferring vehicle is there, ist_weg_frei) (else make the vehicle wait until free, warten_bis_weg_frei(restart_speed), which sets the convoy state to WAITING_FOR_CLEARANCE)
For road vehicles (
automobil_t), a road is passable if:
- it is a road and the max speed of the road is greater than 0, and
- the convoy is electric and the road is electrified, and
- road signs allow entrance (max speed of vehicle is greater than min speed sign, we are the player allowed to pass a barrier, choose signs...)
The
vehikel_t::hop method does the following:
- it calls verlasse_feld (leave tile), to do cleaning up tasks upon leaving a tile
- it updates position, direction and corresponding image
- it calls betrete_feld (enter tile), to do initialization tasks upon entering the new tile
- speed limit, if any, is calculated
- if this is the first vehicle of the convoy, running cost is calculated and stop adjutsments done if necessary
- information for the convoy is updated (some things depend on all vehicles)
- speed for this vehicle is updated too
One of the most complicated methods in this part of Simutrans is
bool ist_weg_frei (is the way free?). There is a specialitation of this method for each kind of vehicles. In fact, the
schiff_t::ist_weg_frei method, used by ships, is so simple that it ignores all other ships in the tile, and that allows several of them to occupy the same tile at the same time.
That method deserves a special chapter in itself for our purposes.
The rest of states are dealt with in the
convoi_t::step method, which is called with much less frequency. This method is appropriate for things that doesn't alter the position of the vehicle or are too CPU intensive: calculating routes and checking schedules, mainly. The frequency a vehicle tries to do this (for instance, finding a route after being unsuccessful) is also set in this method.
To be continued...
Maybe in a far future the wisdom collected here could lead to real double tracks as well...
This last chapter things, I don't understand it fully, but since I think I have enough information to make my proposal, here it is. The proposal will be done shortly.
CHAPTER 8: IST_WEG_FREI and friends (r5023)The full prototype of this method is:
bool ist_weg_frei(int &restart_speed, bool second_check). It is called each time we want to know if a way tile is free and the vehicle can go there. It returns two values: a boolean, indicating whether the way is free or not and, if not, the speed at which the vehicle should restart when eventually the way is free.
Sometimes, the method calls itself a second time to check, for instance, if the vehicle in front of us can or cannot move. These checks are more relaxed and are indicated by a value of
true in the second parameter of the method.
In order to analyse this method, we will refer to the number of the lines as in r5023.
bool automobil_t::ist_weg_frei(int &,bool) method goes from line 1938 to 2235. These are its main tasks:
- All checks are done only for the first vehicle of convoys. All others are supposed to find their way opened by the first one.
- if it is an intersection of two different ways, it returns way free to leave it as soon as possible
- 1948-1962: some simple checks are done first: if too many objects in the tile (return way not free), if the way has been destroyed (return way not free),
- 1965-2036: these checks are in connection with road signs: if red traffic light (return way not free), if choose sign and not able to get to a free target tile destination (return way not free)
- 2041-2193: these checks are done if the vehicle is not overtaking. If it were overtaking, road is supposed to be clean because it is checked for that before trying to overtake
- 2195-2229: final overtaking checks, see below
So the most important part happens in lines 2041-2229: let's visit them:
- 2044-2049: current and next directions are calculated (curr_fahrtrichtung and next_fahrrichtung. These directions may be one of the 8 directions of the compass. To account for diagonals, three tiles must be used. But in some occasions we only want to know the relative position of the next tile from the current tile. These are calculated in variables curr_90fahrtrichtung and next_90fahrtrichtung. Let's see an example:
------------------- * - position of vehicle
| curr| next| | Current direction: NE (diagonal)
| * | | | Current 90 direction: E
------------------- Next direction: E
| prev| Next 90 direction: E
| | Current position in variable str
-------
- 2050: a call is made to no_cars_blocking. This method checks if another car is blocking our way and, if so, a pointer to that is returned. Otherwise, it returns NULL.
- 2055-2193: something in connection with crossroads and a 4 tiles check that I don't understand
- 2196: if no blocking car is found, return way free
- 2197-2202: if the blocking car is stuck, stop this vehicle, abort overtaking and prevent it from generating stuck messages, since the blocking car will generate them for it
- 2204-2227: if the blocking isn't stuck and is just ahead of us and it is something overtakable and it is not itself being overtaken, then:
- 2208-2211: if the vehicle is overtaking itself, return way free
- 2213-2223: if not overtaking or overtaken, check if it is safe to overtake, prepare for it and return way free
- 2226-2227: else, abort overtaking and return way not free
The
vehikel_basis_t *no_cars_blocking(grund_t *,convoi_t *,uint8 current_fahrtrichtung,uint8 next_fahrtrichtung,uint8 next_90fahrtrichtung) method really checks if there is at least one vehicle stopping us. We will have a look at it:
- 559-579: for each vehicle or city car in that tile different from ourselves, it checks
- 583-587: if the vehicle wants to take the same exit of the tile, return that vehicle
- 589-614: very complicated calculations dealing with what happens in crossroads when traffic is turning, etc. checking if we have free way or not
Finally, overtaking is dealt in more or less a simplistic way. A normal or a street car may be in one of three states:
- overtaking: and it knows how many tiles overtaking will take
- overtaken: and it knows how many tiles being overtaken will take
- normal state: neither of the above
When the vehicle is drawn, it is drawn with an offset depending on the state. When in
ist_weg_frei, if there is a blocking car ahead, conditions are checked in
convoi_t::can_overtake, and if possible, the aforementioned numbers of tiles are calculated and the states are set.
Each time a vehicle enters a new tile, the number of tiles (overtaking/overtaken) is decremented and, if zero is reached, the state is reset to normal.
To be continued... or not?
The checks at crossroads and way crossings (railroad, channels etc.) are to may sure a car does neither have to stop directly on them to prevent traffic jams. For this, it even has to take into account the directions of driving (e.g. right turn is always possible, if next tile is empty, while left trun has to wait for block traffic for driving on right side).
Quote from: isidoro on January 04, 2012, 11:41:56 AM
2055-2193: something in connection with crossroads and a 4 tiles check that I don't understand
Don't understand??? :o Why it's a thing of beauty! ;D Drove me nuts getting it to work. Seems so simple yet...
As prissi mentioned, we don't want a vehicle stopping in an intersection (or on a crossing) potentially blocking traffic; And ultimately potentially causing a deadlock. So this routine simply scans ahead along the vehicles route making sure every tile is free until it finds one where it's safe to stop. The 4 tiles is the routine giving up after 4 consecutive intersections and allowing the vehicle to proceed anyways. Possibility of a deadlock, but otherwise the overall traffic flow is slowed too much in certain circumstances.
Quote from: isidoro on January 04, 2012, 11:41:56 AM
589-614: very complicated calculations dealing with what happens in crossroads when traffic is turning, etc. checking if we have free way or not
These calculations cover every possible route through the intersection, ensuring as many vehicles as possible can all be in the intersection, at the same time, all taking non conflicting routes; For standard two way roads (left and right driving sides) only. This routine is the very reason I was considering only controlled access highways with no intersections (except the access ramps which would have their own specialized logic). The extra logic to handle multilane one way roads, and all the possible intersection types that come from joining one way and two way, and one lane and two lane, and etc.. in all combinations is mind bogglingly humongous.
Thanks both. Now it is much clearer for me.
Quote from: TurfIt on January 04, 2012, 08:18:46 PM
These calculations cover every possible route through the intersection, ensuring as many vehicles as possible can all be in the intersection, at the same time, all taking non conflicting routes;
[...]
Nice architectural work... ;D Wouldn't you mind loosing it too much? :P
The method I'm devising would take that off to accommodate for one way intersections and transitions (going from one-direction to two-direction and vice versa) too...
Tomorrow afternoon I think I will have enough time to finish the technical aspects of my proposal. It seems simple to me, but I may have overlooked something....
Isidoro, this is absolutely amazing work to read all this from the code and document it so detailed and precisely :)
It's been very interesting to me to read and compare it to my memories, to see what changed and what stayed the same. It seems the team has improved the class hierarchies a bit, to make responsibilities more clear, and also added a few more details to the ribi-related data.
Good luck with the two lane road project! After this analysis of the code I believe that you can do it :D
Thank you, Hajo. You are very kind.
In fact, code as prissi says is pretty well documented itself. Problem for me is German, though... And I also have played a lot and took contact with it when developing the overtaking patch.
I have already made my proposal. I hope some of you, guys, are not too deceived by it, but it is what it seems to me feasible enough:
http://forum.simutrans.com/index.php?topic=8906.msg82865;topicseen#msg82865
I plan to add all the corrections to my visit to the code and put it together and, if you want, publish it in the wiki or somewhere else.