The International Simutrans Forum

Community => Community Discussion => Topic started by: jamespetts on October 11, 2015, 11:23:41 PM

Title: Geometary question
Post by: jamespetts on October 11, 2015, 11:23:41 PM
Apologies for asking what may be to those whose geometary skills exceed mine a rather silly question: how does one calculate the minimum radius of an S bend? The reason that I ask is this: I implemented at the end of last year a new system for determining the speed limits around corners based on this formula (https://books.google.co.uk/books?id=NbYqQSQcE2MC&pg=PA30&lpg=PA30&dq=curve+radius+speed+limit+formula+rail&source=bl&ots=mbfC3lCnX4&sig=qClyuNSarnvL-zgOj4HlTVgYOr8&hl=en&sa=X&ei=sBGwVOSGHMyBU4mHgNAC&ved=0CCYQ6AEwATgK#v=onepage&q=curve%20radius%20speed%20limit%20formula%20rail&f=false). A required input of that formula is the radius. An S bend in Simutrans occurs in this sort of way:
____
        \______

This is a pair of self-correcting 45 degree corners. For a 90 degree bend, I just take the meters per tile value and multiply by the number of tiles that it takes from the beginning of the corner until the way is at 90 degrees to where it started. For this type of curve, however, I am not sure that I have the formula right. I am currently taking the number of tiles that it takes to reach the second 45 degree bend after having reached the first, and multiplying that by twice the meters per tile to get the radius (there may be an error with the code for counting, but that is a separate point). However, where one 45 degree bend is right next to the other, as is fairly common when slewing railway tracks to one side, the radius is calculated at 250m (with Pak128.Britain-Ex's 125 meters per tile setting), which, according to the formula, produces a maximum speed of 46km/h (assuming that a tilting train is not used). This seems far too slow, but I am not sure whether or not it is right nonetheless. Is the minimum radius of a slew ending up 125m to the side in a total distance of 250m 250m?

Even if it is, I wonder whether I am representing this properly and whether I need to take account somehow of the number of straight tiles before and after the slew over which it might in theory be smoothed.

Any thoughts on the topic would be most welcome.

(Incidentally, I am not sure whether this is the right board for this, but such a general question did not seem to fit easily into any of the categories, so my apologies if this is not in the right place).
Title: Re: Geometary question
Post by: Sarlock on October 12, 2015, 01:32:21 AM
The question is whether that is a slew with a straight track and two 45 degree sections or just a track laid at 10 degrees that has to slew for purposes of Simutrans.
Title: Re: Geometary question
Post by: jamespetts on October 12, 2015, 10:06:35 AM
The trouble is that there is no way of distinguishing between those situations: one might find many cases where a 125m sideways slew in 250m is actually necessary (to avoid buildings or other obstructions close together), but in other cases, there is much more space and the slew could have been made much more gently were it not for the tile system.
Title: Re: Geometary question
Post by: Ters on October 12, 2015, 10:51:18 AM
This is one of many cases in Simutrans where there is no text-book formula. Just tweak the numbers until you have something that feels acceptable (thought probably never quite right) in all cases you can think of and leave it at that.
Title: Re: Geometary question
Post by: isidoro on October 12, 2015, 11:59:52 PM
I would consider just the same calculation you made for the 90 degree curve but just divide by two the outcome radius.  I don't know if that matches what you are doing now, since I couldn't understand your post fully.

The rationale for what I say can be seen in the picture.  If the red one is the 90 degree turn with radius R, the green one is the S turn, which is equivalent to two turns with half radius.
Title: Re: Geometary question
Post by: jamespetts on October 13, 2015, 10:24:23 AM
That is what I am doing now, and that produces a 46km/h speed limit for a one tile slew at 125m/tile, which seems far too low.
Title: Re: Geometary question
Post by: Ters on October 13, 2015, 11:31:51 AM
What jamespetts shows in the first post is not two 90 degree turns, but two 45 degree turns. As far as I know, that is also how Simutrans has treated it for as long as I have been playing it.
Title: Re: Geometary question
Post by: jamespetts on October 13, 2015, 11:34:08 AM
What I think that I shall have to do is have a simuconf.tab parameter set an arbitrary radius for all 45 degree turns, as, unlike 90 (or greater) degree turns, 45 degree turns can in Simutrans and often do represent turns that are much more gentle than an actual 45 degree turn (whose radius would in theory be half that of a 90 degree turn over the same distance).
Title: Re: Geometary question
Post by: sdog on October 13, 2015, 06:30:29 PM
There is a definite solution, determined by the boundary conditions. The Radius must be 1/√2 d, where d is the distance between the parallel tracks. Proof to follow.

correction: R= 1/(2-√2) d
Title: Re: Geometary question
Post by: jamespetts on October 13, 2015, 06:33:47 PM
Oh? I should be interested in an explanation for this.
Title: Re: Geometary question
Post by: Ters on October 13, 2015, 06:56:24 PM
Quote from: sdog on October 13, 2015, 06:30:29 PM
There is a definite solution, determined by the boundary conditions. The Radius must be 1/√2 d, where d is the distance between the parallel tracks. Proof to follow.

This sounds like a solution just for two 45 degree bends back to back. (This is my gut feeling only.) That might cause too much penalty for a situation where the arcs realistically would span far fewer degrees on a circle with a much bigger radius, though Simutrans can't represent the difference.
Title: Re: Geometary question
Post by: sdog on October 13, 2015, 07:29:26 PM
correction above, made a mistake: R= 1/(2-√2) d

see here:
https://goo.gl/yTQzHZ

graphical test:

gnuplot> d = 1; r = d/(2-sqrt(2))
gnuplot> e = d/(2*(sqrt(2)-1))
gnuplot> g(x) = 0.5*d
gnuplot> f(x) = sqrt(-x**2 + r**2)-r+0.5*d
gnuplot> plot [-2*d:2*d] [-d:d] g(x), -g(x), f(x-e), -f(x+e)
Title: Re: Geometary question
Post by: Octavius on October 13, 2015, 07:48:30 PM
I've done some calculations and I think the fairest option is to make the radius R=(x^2+y^2)/(2y), with x the distance from the centre of the slew to the midway point to the next corner (or the previous, whichever is less), measured parallel to the track, and y being half the distance over which the track moves to the side. See equation 6 in the attached pdf (which apparently has to be packed as a zip file).

(It's hard to put equations and math drawings into a forum post, so I TeXed my reply.)
Title: Re: Geometary question
Post by: jamespetts on October 13, 2015, 07:57:56 PM
Sdog and Octavius: can you let me know what the radius would be calculated as for a one tile slew at 125m/tile on each of your systems?
Title: Re: Geometary question
Post by: sdog on October 13, 2015, 08:04:02 PM
Quote from: jamespetts on October 13, 2015, 07:57:56 PM
Sdog and Octavius: can you let me know what the radius would be calculated as for a one tile slew at 125m/tile on each of your systems?

d =  125
octave:2> r = d/(2-sqrt(2))
r =  213.39
octave:3> x1 =  d/(2*(sqrt(2)-1)
x1 =  150.89


[/quote]
Quote from: Ters on October 13, 2015, 06:56:24 PM
This sounds like a solution just for two 45 degree bends back to back. (This is my gut feeling only.) That might cause too much penalty for a situation where the arcs realistically would span far fewer degrees on a circle with a much bigger radius, though Simutrans can't represent the difference.
Yes, 45 degree is one boundary condition.

From James' initial post:
"This is a pair of self-correcting 45 degree corners."
Title: Re: Geometary question
Post by: jamespetts on October 13, 2015, 08:05:34 PM
A radius of 213m is going to produce a speed limit even less than that produced by the current formula, which calculates the radius as 250m, and seems to be an excessive limit for a 1 tile slew given that it is not possible in Simutrans to have any less sharp slew than this.
Title: Re: Geometary question
Post by: sdog on October 13, 2015, 08:14:40 PM
Well, that was the answer to the question of the subject.

For your simulation i can not provide answers, only suggestions. Completely disregard such S bends. No speed penalty whatsoever. In nearly all cases where it is found in the open it is just an aliasing problem. The way of players to make tracks at a non-cardinal directions, or getting forced to a coarse grid. In the few other cases it is not too bad when it is overlooked, mostly because a sharper bend is to follow, that would have been softened were there no aliasing, e.g., at stations or points.
Title: Re: Geometary question
Post by: jamespetts on October 13, 2015, 08:16:59 PM
Yes, you are probably right to an extent: I think that there should be some assumed radius of a 45 degree curve, but a much lower amount, set in simuconf.tab so as to be customisable. Thank you for the equation, though: that does confirm that working out the actual radius in this case is not workable in the context of Simutrans.
Title: Re: Geometary question
Post by: sdog on October 13, 2015, 08:25:09 PM
Quote from: jamespetts on October 13, 2015, 08:16:59 PM
Yes, you are probably right to an extent: I think that there should be some assumed radius of a 45 degree curve, but a much lower amount, set in simuconf.tab so as to be customisable. Thank you for the equation, though: that does confirm that working out the actual radius in this case is not workable in the context of Simutrans.
No, you can. Even when you give up condition (ii) and have an arbitrary angle. Then you introduce x_+/-1 as new boundary condition, for example by measuring how far the next bend is, and taking half that distance. Say it is 8 tiles away, then you have a 4*125m = 500 m as condition for x_1. Some changes have to be made, introducing trigonometric functions.
Title: Re: Geometary question
Post by: Vladki on October 13, 2015, 08:28:44 PM
Ah this is a really interesting discussion. I tried to do my math and geometry in the meantime and for 45° S bend I came up with the same result as Sdog. r = (1+1/sqrt(2))*d ~ 1.707*d

I used only pythagoras, and the attached picture. You can see the tile grid, black is simutrans track, green is smooth S curve. In this example tiles have size 2 (miles, km whatewer). So the shift is 4, and radius is cca 6.8.

I still not sure how to exactly calculate the 90 degree (2x45) bend, specially what number to use as a base for calculation. On the attached picture you can see blue bend (which is what is probably used now) and green bend which IMHO represents the curve much better. UPDATE: I think I have it. Such bends have d=0.5, 1.5, 2.5, 3.5, etc, and then use the same formula as S-bend.

As to the discussion of 1-tile shift S-bend. The calculation is right for cases when such bend is needed to get around obstacles.
If someone lays a track on flat empty map, so that it is full of such bends, just to simulate a track that goes to Nort-North-West, then he deserves it ;) - it can/should be rebuilt to have only one S bend more tiles wide.
Title: Re: Geometary question
Post by: Octavius on October 13, 2015, 08:39:55 PM
In my case it would depend on the length of straight track before and after the slew. If the slew is in the middle of an infinitely long straight track, the radius would be infinite. If before and after the slew is 1 km of straight track, the radius would be 2562.5 m for two 12.68 degree turns. If the straight track is only 250 m, the radius would be 312.5 m. So you're probably limited by the preceding or next curve, which would have a radius of no more than 1207.1 m in case of the 1 km straight, but a quickly accelerating train may be influenced by the slew. For slews of more than one tile things may be more interesting.

(Note: in the linked file are also some thoughts on 90 degree=2×45 degree turns)
Title: Re: Geometary question
Post by: Vladki on October 13, 2015, 08:55:44 PM
Octavius: I read your file, you seem to cover every possible option. Your solution perhaps could be generalised, not to distinguish between 90 degree and S bend. Just consider each 45 degree bend separately, check the distance to next bend on both sides, take the nearest one, and divide the distance by 2. That is the distance where the curve begins (on both sides). And wow, we get back to the formula sdog and I found, just with different variable. R=(1+sqrt(2))*x  where x is half of distance to nearest other bend.
However this gives again the same result for 1-tile s-bend (i.e. sharp corner).

A few more thoughts about corners on junctions. On czech wikipedia I found table of switches with radius and allowed speeds:
R=150 m, 30 km/h
R=190 m, 40 km/h
R=300 m, 50 km/h
R=500 m, 60 km/h
R=760 m, 80 km/h
R=1200 m, 100 km/h
R=2500 m, 120 km/h
As you can see 40 km/h switch (the most common) fits quite nicely my and sdog's calculation of radius for 1-tile S-bend.

Further I have found some rules for radius/speed. cetrifugal acceleration is a=v^2/R, and max allowed a is 0.65 m/s^2 (for czech railways). v=sqrt(0.65*R). combining this with R=1.707*d we get v=sqrt(1.11*d). d is shift of track after S bend in m. For 125 m/tile we get these speeds: 42, 60, 73, 85, 95, 104 km/h. Well, not very high anyway. If we count in max allowed superelevation of 150mm, we get to v=sqrt(2.86*d) and speeds: 68, 96, 118, 136, 152, 167 km/h. That's much better.

ref in czech https://cs.wikipedia.org/wiki/Pr%C5%AFjezd_obloukem
Title: Re: Geometary question
Post by: Ters on October 13, 2015, 10:04:06 PM
I was also thinking of analyzing long runs of tiles to calculate some sort of average curvature that probably reflects the ideal course the player would have built if it wasn't for tile grid. But I never bothered to mention it, because it will either be computationally expensive, or require lots of changes in the code to keep track of cached values and invalidate them when necessary. Perhaps to the point of throwing the tile based ways out in favor of splines, as in Railroad Tycoon 2&3, Locomotion(?) and several others, starts to look like a reasonable alternative.
Title: Re: Geometary question
Post by: jamespetts on October 13, 2015, 10:49:06 PM
I think that it is now clear that using the correct radius formula for corners of less than 90 degrees is not workable in an ordinal direction tile based system such as Simutrans. I had also considered the calculation of straight runs, but rejected it for similar reasons that Ters suggests. Given that totally reworking Simutrans to a spline based system is out of the question, the only thing to do is to assign an arbitrary and high radius value to 45 degree corners, preferably from simuconf.tab.

Thank you all very much for your feedback - it is appreciated.
Title: Re: Geometary question
Post by: sdog on October 13, 2015, 11:19:45 PM
Quote from: Ters on October 13, 2015, 10:04:06 PM
Perhaps to the point of throwing the tile based ways out in favor of splines, as in Railroad Tycoon 2&3, Locomotion(?) and several others, starts to look like a reasonable alternative.
You don't even have to make it so difficult. Real railways use cycloids for curves. Splines would be an interpolation method that is more complicated and worse than real railways. Cycloids are the curves with the least resistance.

http://mathworld.wolfram.com/Cycloid.html
Title: Re: Geometary question
Post by: isidoro on October 14, 2015, 12:26:17 AM
Considering some of your ideas, this picture shows a method to interpolate quite reasonable curves from tile based ST.  Please see the attached picture.

BTW: I can see lot of potential in the forum.  It seems as if everybody is dormant, though.
Title: Re: Geometary question
Post by: sdog on October 14, 2015, 12:44:28 AM
Quote from: isidoro on October 14, 2015, 12:26:17 AM
It seems as if everybody is dormant, though.
... procrastination strategy, reaction on increased stress
(http://www.texpatsabroad.com/uploads/5/7/0/6/5706846/4286986.jpg?624)
(https://accountingprofessor.files.wordpress.com/2013/11/phd112713s.gif)
Title: Re: Geometary question
Post by: Sarlock on October 14, 2015, 05:41:52 AM
(http://www.ssgholdings.ca/simutrans/images/straight-tracks.png)

These are all "straight" tracks at different angles, forced to be skewed by the simulation.  Computationally, they have differing radii if the curves are taken literally.
Title: Re: Geometary question
Post by: Vladki on October 14, 2015, 06:03:11 AM
To simulate tracks from sarlock picture, you would have to do a very smart algorithm: like if there is a long enough periodic sequence of 1-tile s-turns, just consider it to be straight track. Or you can just tell players not to do that, and build one wide s-turn instead.

Isidoro: it seems that you got the same formula as sdog and I. Just using different input values. Your algorithm could be perhaps extended to make use of what octavius proposed in his pdf.

First is to find corners that form an s-turn. They are the closest corner for each other, and are in opposite direction. Then the common midpoint could be ignored, and nearest midpoint outside the S considered. Then the simulated S-turn could be less than 45 degrees.
Title: Re: Geometary question
Post by: Ters on October 14, 2015, 09:27:25 AM
Quote from: sdog on October 13, 2015, 11:19:45 PM
You don't even have to make it so difficult. Real railways use cycloids for curves. Splines would be an interpolation method that is more complicated and worse than real railways. Cycloids are the curves with the least resistance.

That's missing the point. It has nothing to do with type of curve and the mathematics behind them, but with the complexity of throwing out all the code that operates on discrete tiles. (I was perhaps misusing the word spline, but cycloid is probably not the word I was after either, because I don't think you can represent a straight line with a cycloid.)
Title: Re: Geometary question
Post by: sdog on October 14, 2015, 06:56:17 PM
Quote from: Ters on October 14, 2015, 09:27:25 AM
That's missing the point. It has nothing to do with type of curve and the mathematics behind them, but with the complexity of throwing out all the code that operates on discrete tiles. (I was perhaps misusing the word spline, but cycloid is probably not the word I was after either, because I don't think you can represent a straight line with a cycloid.)
It was very clear from your post, that it is not meant for simutrans. I was referring to a hypothetical game that would use free-form curves as its paths. By the way, wouldn't even have to be as complicated as the mentioned games have it. One can simply parametrize the curve and do all the calculations with no regard for the actual shape of the track/curve. In particular when one gives up a graphical representation, as it were.

You can either have a piecewise function with straight line segments, or consider a line as limit of  a cycloid with r->0.

Quote
These are all "straight" tracks at different angles, forced to be skewed by the simulation.  Computationally, they have differing radii if the curves are taken literally.
May I take this as another incentive to emphatically recommend to make a threshold, such that S-bends are not penalized at all, but rather treated as straight curves?

The argument is: They are almost exclusively a consequence of the square-tiled nature of simutrans, and as such ought not to have an adverse effect on gameplay.

Trying to make an order of frequency of such S-bends, based on my own games and countless screenshots:

(a) Double-to-single track, here they simply represent part of a point.
(b) At railway stations
(c) Diagonal tracks at angles different from multiples of pi/4.
(d) grade crossings of diagonal tracks
(e) navigating obstacles in cities, mountains.

Of the few cases where such curves have a different purpose, there is a speed limiting feature in place already anyway (b), (e). For all other cases (a, c, d, e) they are a workaround for game limitations, the player oughtn't have to suffer twice.
Title: Re: Geometary question
Post by: Ters on October 14, 2015, 07:26:14 PM
Quote from: sdog on October 14, 2015, 06:56:17 PM
It was very clear from your post, that it is not meant for simutrans. I was referring to a hypothetical game that would use free-form curves as its paths.

It was Simutrans I was writing about. I was clearly writing about replacing an existing tile-based way system. So the "hypothetical game" would be a hypothetical version of Simutrans Experimental.
Title: Re: Geometary question
Post by: sdog on October 14, 2015, 07:50:56 PM
Quote from: Ters on October 14, 2015, 07:26:14 PM
It was Simutrans I was writing about. I was clearly writing about replacing an existing tile-based way system. So the "hypothetical game" would be a hypothetical version of Simutrans Experimental.
Sorry for misunderstanding you, or for writing too sloppily; giving cause for misunderstandings. Another try, shall I?

It seemed very clear to me that you did not seriously consider to start coding and replace the tile based system simutrans uses with a system using some free-form curves, e.g., splines. But rather that you offered it as a way of how speed limits for complicated bends could be properly evaluated. In contrast to the current system where it would be nearly hopeless because of some reasons you gave in detail.

Speaking hypothetically: If one were to do that, one could fit piecewise curves to the grid points we have now. Then get speed limits from this curve, and assign each tile a speed limit based on it. This would only have to be done once for each given way. However, it is not trivial at all. Simply interpolating would not do. As we want to get away from the actual points, at least that is what James appears to be doing in his mind when assuming much wider curve radii. The difficulty would then not so much lie in the computational requirements, but rather in the unpredictable results of optimization. There are just too many degrees of freedom. If the pieces of a piecewise function were known, variation of parameters to get the optimal way would be trivial. However, since those could be chosen differently, something nasty, like a genetic algorithm (or something computer-sciency) would be required. A very intriguing problem! (Although, of very limited use for this game.)
Title: Re: Geometary question
Post by: jamespetts on October 14, 2015, 08:10:06 PM
This is not entirely straightforward, as one would not think it realistic for trains to be able to proceed at full line speed (e.g., 320km/h) in situations (a), (b) and (e), but one ought to be able to go at full line speed in situation (c). Without a radical change of the basic system of the sort unlikely in the short to medium term, one will have to adopt a solution which will be wrong for at least some situations. The real question is whether it is more intuitive for players (in the Simutrans world) to imagine all corners as coming with at least some penalty and that high speed lines should be entirely straight in the Simutrans world, or that it should be possible to simulate any angle of track in a very indirect way despite the game only actually representing 4 angles (i.e. 8 directions) directly?

I suspect that the former is easier to understand, but a simuconf.tab system as I proposed earlier would allow pakset authors or customisers to choose the alternative if the please by altering the value in simuconf.tab to 0.
Title: Re: Geometary question
Post by: sdog on October 14, 2015, 08:43:47 PM
(a) and (d) would be speed limited not because of the S-bend, which is an aliasing artefact (i.e, continuous to discreet) but speed limited by the point or grade crossing itself, if at all. (Aren't points specified to the line speed?) As it is now, one way, which is straight, is not speed limited while the other way that joins is.

For (b) the speed is already practically reduced by the station and signalling. It is in game more than rare that trains would go through at speed. And when for most simple cases, where (b) is in fact only caused by other aspects.

(e) ought indeed cause a reduction in speed. This is the point where the approximation of having no speed limit fails. However, this is not such a frequent case, that it would interfere with the simulation.

You are building a system that is not easy to understand anyway, go for what you consider better for the game. In this case I was partly convinced by Prissi, who considered the experimental way of bends too limiting for good play.
Title: Re: Geometary question
Post by: jamespetts on October 14, 2015, 08:48:37 PM
It is not the fact of points that limit speed, but the fact of diverging at an angle and there therefore being a sharp turn: this is why it is common for signalling to give an indication to a train of the route that it is to take so that the driver knows the speed: even where, for example, the main and relief lines both have speed limits of 160km/h or 110km/h, the speed limit for crossovers between the two might be closer to 50km/h (especially in earlier times where very large radius points had not been developed).

As for (b), this might apply to trains that are stopping at stations, but not to those passing through, which generally pass at line speed. (e) is not uncommon in the games that I have seen, at least where track passes through built up or mountainous (or even mildly hilly) areas, and it is often necessary to slew to avoid crossing a river at a junction of a tributary or a bend.
Title: Re: Geometary question
Post by: Ters on October 14, 2015, 09:39:27 PM
Quote from: sdog on October 14, 2015, 07:50:56 PM
It seemed very clear to me that you did not seriously consider to start coding and replace the tile based system simutrans uses with a system using some free-form curves, e.g., splines. But rather that you offered it as a way of how speed limits for complicated bends could be properly evaluated. In contrast to the current system where it would be nearly hopeless because of some reasons you gave in detail.

Almost. I was using it as a yardstick for how much work I think it will be to implement what I wrote about earlier in the post. That they could be so close, that one (almost) might as well go for the real thing.
Title: Re: Geometary question
Post by: isidoro on October 15, 2015, 12:02:33 AM
Regarding Sarlock's "straight" lines:

It's all a question of scale, I think.  A mathematical algorithm can only possible see what comes out from the data you input to it.  In order to detect "straight" lines like Sarlock's, you have to give "a few" tiles before and "a few" tiles after the point in question.  How many is "a few"?  That's the question.

For straight, one tile.  For 45, two tiles, etc.

But I'm with James that it makes little sense, at least to me, to consider those things "straight" if you can have trains much smaller than the number of tiles to detect those "straight" lines.

And that also applies to the algorithm some of us have proposed above (mine too), how can a train "sense" a big, big 90 degree curve if she isn't long enough to be in the two 45 degree turns at the same time?
Title: Re: Geometary question
Post by: Vladki on October 15, 2015, 06:22:47 PM
I dont think that the relation between train length and corner distance is important. Real track curves can be longer than the train and still affect its speed.