[suggestion] Tracklayout based on a triangle grid

[TossIB]

Hi everybody.

I'm a geometrics nerd and developed some track layout prototypes lately because I tinkered with the idea of doing my own TT like Transportation Game. As my time is rare and my programming skills low this would probably never be started seriously, but I think you might profit of me contributing what I've thought of so far.

Please correct me if I'm wrong, you want to do it full 3D but with an operant grid for tracks, buildings, etc., right?

Here we go

The basic idea is to choose a triangel grid with the track placed right on the edges of the triangles. (That's logically just the same than using hexagonal tiles with the track lying in-between the central points of two tiles.)
Right angles aren't supported by this grid, but I don't think that this is a serious problem, because most regions aren't right-angled in any way (except for America). Angles of 60° are much more natural, and if you have to connect two points which are placed diagonally into the grid your way of basic directions would be 41,4% longer if you have to use sqare tiles (4 directions) and only 15,5% longer if you have hexagonal or triangle tiles (6 directions).

layout4.png
Take a look at the picture.
The radius is approx. 3,46
A 180° turn will span the area of 8 parallel tracks.
There are 12 segments needed for a full circle.
All segments are equal and very near to the real circular line.

layout8.png
Take a look at the picture.
The radius is approx. 6,93 - twice the length of the small one.
A 180° turn will span the area of 16 parallel tracks.
There are 18 segments needed for a full circle.
There are two different types of curve segments which are a bit more twisted. They are used as follows:
-> Segment 1 to go from the basic direction to the angle used in track switches.
-> Segment 2 to go from track-switching-angle of the first direction to the track-switching-angle of the next direction.
-> Segment 1 to go from track-switching-angle to the basic direction.

Another (bigger) Radius isn't needed so I say, because you will have big trouble integrating it into the structure of track switches. And I think it looks good enough to simply add some straight track if you want parallel curves. (If the engine is working fine one can try to soften this fillers)

BTW: I strongly recommend to force the player to widen the distance between tracks when he want's to build a platform in between them. Double distance will look somewhat more realistic.

BTW2: If you place tracks on the edges of the triangles and assign the high marks to the corners you will have less problems placeing the track.

[Hyronymus]

Too late I believe, on the last meeting the majority voted for rectangular tiles (5 vs. 3)

[TossIB]

very unfortunate too hear

[Hellfire]

At first sight, your tracklaying strategy supports 3 directions, while with triangle grids, 6 are possible.

[TossIB]

Look at these pictures:

layout4d.png
6 main directions (the short segments)
6 track-switching directions or "diagonals" (the long segments)
-- 12 directions in total

layout4d.png
6 main directions (the longer track made of three short segments)
12 track-switching directions or "diagonals" (the long segments)
-- 18 directions in total

or 6 and 9 if you do not want to count the reverse direction of the same line. Which directions did you mean which are also possible?

[Hellfire]

Well... You've just showed the directions I meant. They weren't totally clear in your first pictures.

[Steve]

What program did you use to make those diagrams?

[ChrisCF]

First off, the nine-point layout is out of the question, since it doesn't even support a basic system of four compass points. The six-point layout is also less than ideal, since you are stuck to increments of π/6, which makes getting to the all-important intermediate points at π/4 impossible. If it could support directions as close together as π/12, then it might be useful.

[Steve]

What nine-point layout?

[charlieg]

I really like the look of this. I've been tinkering with the idea of starting my own transport sim and am getting closer and closer to actually doing so.

Consider this page BOOKMARKED!

The main problem with the triangular layout is not it's end representation, which is both natural looking and easy to conceptualize. The actual problem comes with the mathematics and code which are really more complex and less natural than the simplistic grid based approach. Of course, it's not rocket science but the difference in simplicity between the backends of the two approaches is significant enough to greatly deter people using hex/tris for most games.

[Hyronymus]

As Hellfire mentioned in the FRDF-topic for the cell-shape discussion: there's no valid decission on what to use yet. The votes reached a 62,5% majority for rectangular tiles, being 3,5% short of the required 66%. Hellfire we create a user poll tomorrow for all devs to vote (even those that can't make it to the meeting).

[TossIB]

What program did you use to make those diagrams?

I used PaintShop Pro 8 (Jasc) and it's capabilities to draw vector grafics. The triangels are approximated by the points (0|0) (15|26) (30|0), which is a rather good approximation.

First off, the nine-point layout [...]

I think you meant what I called "layout8" (nine segments for a 180° turn)

[...] is out of the question, since it doesn't even support a basic system of four compass points.

Do you really need those directions? BTW the compass only shows on line, the line from south to north. East and West is an invention, which allowed it to place an rectangular grid over maps. So it's not a that big deal.

The six-point layout is also less than ideal, since you are stuck to increments of π/6, which makes getting to the all-important intermediate points at π/4 impossible. If it could support directions as close together as π/12, then it might be useful.

I really don't think that beeing stuck to increments of π/6 is that bad and I also don't consider the "intermediate points at π/4" "all-important". please post some arguments, why these directions are imortant for you.



Let me point out, why /\ is better than []:

Down below there are two pictures (aerial photos) of Munich.
» While in the first picture (the central station is in the bottom left edge) all is full of 90° angles one could say this ist the basic angle my grid has to follow. But the scale of this photo is much to high. It's the scale of a game like Traffic Giant, where you have to manage short range public transportation (in german: Öffentlicher (Personen-)Nahverkehr).
» In the second picture (the central station is on half way from the middle to the bottom) the scale is more similar to the scale of a game like TT. And there aren't many 90° angles IMHO. You could use any grid you like cause there isn't any natural structure identifiable (this might be different in some areas of America...).
»» The argument "rectangular grid may look more realistic, cause everything is build in right angles" is not true at the scale used (at least in europe, but I think also in Amerika, Japan, China, ...)

» As I said before, the minimal way of basic directions to connect two diagonally placed points in triangular and rectangular grid will be 41,4% longer than bee-line for rectangular grid (4 directions) and will only be 15,5% longer than bee-line for hexagonal or triangular grid (6 directions).
» Your detour will be 22.5% longer in rectangular grid.
»» It's as simple: Using triangular grid will result in shorter detours.

» Hills and valleys are important, no question about that. When you have to use rectangular grid, you soon will recognize a problem. A (flat) square with it's four corner at four different hights is overdefined and may not be possible in all cases. So you have to insert a breaking line which devides each square into two triangles. Therefore making a hill always means inserting an edge (the diagonal) which is not supported by the basic directions. So hills an valleys made in this grid are working against it. It's like the grid saying "use these four directions" and every hill telling you "forget your four directions, you need eight equally supported directions, couse there are diagonals everywhere in mountainous parts".
»» The rectangular grid uglifies itself as soon as you want to insert a hill! The triangular grid doesn't know the whole problem at all.

I really like the look of this. I've been tinkering with the idea of starting my own transport sim and am getting closer and closer to actually doing so.

Consider this page BOOKMARKED!

Like to hear this.

The main problem with the triangular layout is [...]

You're certainly right, but I think the (IMHO) many advantages justify the more complex code and maths.

[...] Hellfire we create a user poll tomorrow for all devs to vote (even those that can't make it to the meeting).

Also like to hear this and thanks for informing. (Although I found this thread myself lately.)
But, I'm no dev anyway... so I'll have to try to convince as many as possible

[Steve]

I'm no longer against triangles, as long as a few key things are met:

We keep the range of straight peices, shown in layout4d.
We allow the wider curves so things are just straight, any making things look A LOT prettier. Kinda like Loco does it.
We have the 6 points around the triangle that things can join to.. could we add one in the middle? Then we'd have a pretty square grid, with the traingle cells.

I'm not sure about landscapes made by the tiles.. if we don't allow the triangles to bend, then it'll be very 3 dimensional. If we could bend them along the lines of symmetry though, we'd make nicer shapes.

I'm against a vote right now. I don't have enough information to make an informed choice.

[ChrisCF]

Do you really need those directions? BTW the compass only shows on line, the line from south to north. East and West is an invention, which allowed it to place an rectangular grid over maps. So it's not a that big deal.

It is, because if you can't build in the two fundamental directions of 2-dimenional geometry, you're already making people's lives difficult. Two perpendicular axes are rather easier to deal with than three non-perpendicular axes. With the range of motion you suggested with nine directions, it's impossible to build straight along one of the axes of the two-dimensional region - generating a track to run vaguely along that axis in three-dimenional space just doesn't bear thinking about.

I really don't think that beeing stuck to increments of π/6 is that bad and I also don't consider the "intermediate points at π/4" "all-important". please post some arguments, why these directions are imortant for you.

Tell you what, how about *you* demonstrate why they are *unimportant*?

Remember that we're not only dealing with railway tracks here - roads have to fit the bill too, and it should be patently obvious why right-angled junctions make sense, and therefore have to be supported.

Now, the most important point of all ...

Ignore height for a moment. For the purposes of deciding a tile shape, for things to be laid *on* the tile, height is irrelevant.
With a square tileset, you have two directions purely along the sides of the tiles. Those unit vectors are (1,0) and (0,1). According o basic rules of geometry, to form a basis on the space and therefore be useful in this context, these unit vectors must be both linearly independent, and span the space provided. They don't have to be perpendicular, just linearly independent.

First: linear independence.

The short explanation is that vectors are linearly independent if when you follow each of them in one direction, you can't get back to the origin. Remember that vectors have specific direction. On a two-dimensional grid, let's assume that you can only travel north (1,0) or east (0,1). South (-1,0) and west (0,-1) are not used, since we have two axes, not four. Using only north and east moves, it is not possible to return to the origin (try it). The more formal definition is that there are no values for a(1,0)+b(0,1)=0 where a and b are not zero. The reason I ignored negative moves earlier is that taking six southward steps is the same as -6 northward steps - you still don't finish up at the origin without moving along both axes in both directions.

With three axes, as you'd get with triangles, you have three unit vectors along the sides of the triangle, (1,0,0), (0,1,0) and (1,0,0). Let's say you follow each in turn for three units. Looking at the numbers, you'd expect to find yourself at the point (3,3,3), right? 3(1,0,0)+3(0,1,0)+3(0,0,1)=(3,3,3). Only you're not at a point (3,3,3), you're back at the origin. The upshot of this is that you can't achieve measurement along one axis without looking at another - which in a nutshell is what linear independence is all about. You can't move along one axis without moving along another. Since you have to satisfy both linear independence and vector space span to form a basis, the triangular model doesn't provide a basis for measuring your terrain. The maths just makes more sense, and will be more understandable in 3D space with three perpendicular directions. Ultimately, if it's more understandable, then it will be within the ability of more people to contribute to it. No point having a beautifully complex model if few of the other coders can get their head around it when you mysteriously disappear. In terms of the code, maintainability has to be placed before complexity, because it is something which will be around longer. Before you answer, how do you know that you won't disappear?

»» It's as simple: Using triangular grid will result in shorter detours.

You're quoting numbers and not proving them.

"forget your four directions, you need eight equally supported directions, couse there are diagonals everywhere in mountainous parts".

Then you can rather handily work along the diagonals, which provides the eight you need. And I think that when you say four and eight, you rather mean two and four. A rectangular grid strictly speaking has two directions - think in Newspeak, where down is simple -up.

At this point, it's probably worth mentioning that the result of any vote should take account of the majority found in the developer vote - after all, any other way insists that the original votes cast were more-or-less invalid.

[eis_os]

About the city shots, I see more square-ich houses

Here are my pros for []:
Most houses in the world are quadratic, sure there are some examples for /\ Houses but it's common for use to think in squares. Or we have round shapes of buildings... That a building is /\ is less common...

Building roads on them is very easy...

Simple math, how do you check the distance a train travel, count the squares

Well some overdo terrain shot:
http://www.inter-ee.net/allvb/winrt/winrt.png

Cons []:
You have to break every square in two triangles.

Here are my pros for /\:
Curve building is easier
Easier to handle triangles for display.

and the negative ones:
Complex math, for Square Objects you lost space...
People get used to use squares in their live.

[Hellfire]

With three axes, as you'd get with triangles, you have three unit vectors along the sides of the triangle, (1,0,0), (0,1,0) and (1,0,0). Let's say you follow each in turn for three units. Looking at the numbers, you'd expect to find yourself at the point (3,3,3), right? 3(1,0,0)+3(0,1,0)+3(0,0,1)=(3,3,3). Only you're not at a point (3,3,3), you're back at the origin. The upshot of this is that you can't achieve measurement along one axis without looking at another - which in a nutshell is what linear independence is all about. You can't move along one axis without moving along another. Since you have to satisfy both linear independence and vector space span to form a basis, the triangular model doesn't provide a basis for measuring your terrain. The maths just makes more sense, and will be more understandable in 3D space with three perpendicular directions. Ultimately, if it's more understandable, then it will be within the ability of more people to contribute to it. No point having a beautifully complex model if few of the other coders can get their head around it when you mysteriously disappear. In terms of the code, maintainability has to be placed before complexity, because it is something which will be around longer. Before you answer, how do you know that you won't disappear?

Your argument is right for three axes, but you don't need three axes for a triangle grid.

Look at the following image.


At the left is a square with its two axes. If the dotted line is added and the Y-axis is rotated 30 degrees clockwise, you'll get two triangles. All points in these triangles can be formed by a linear combination of the two vectors and as a bonus, the vectors are linear independent.

[TossIB]

I think we should unify some terms and definitions first (otherwise we end up fighting cause we don't understand the other one):

Here's what I suggest:
direction = Each way, a train (and all the other vehicles) can run.
basic direction = The most trivial directions supported by the grid. There are four in rectangular grid and six in triangular or hexagonal grid.
axis = like basic direction, but back and forth is considered as one axis
grid = a pattern of points and connecting lines (rectangular or triangular)
tile = the basic shape formed by the grid (rectangular or triangular or hexagonal)
Your OK with these definitions or shoud we change something?

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

It is, because if you can't build in the two fundamental directions of 2-dimenional geometry, you're already making people's lives difficult. [...]

In most cases, 2-dimensional geometry also means, that you have a rectangular grid (just think of paper, even without lines on it, there is a rectangular grid indicated by the edges of the paper). In computer environment you dont have any edges or indicators. If the complete system is based on triangels, than you'll never miss the 90° angle. Have you played "The Settlers"? In there, the whole world is based on triangles, and you really don't miss the rectangles. I think, that peaple will learn pretty fast to think in triangular grid.
At this point it depends ones personal preferences.

With the range of motion you suggested with nine directions, it's impossible to build straight along one of the axes of the two-dimensional region - generating a track to run vaguely along that axis in three-dimenional space just doesn't bear thinking about.

See above. I think you won't miss it.

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

I really don't think that beeing stuck to increments of π/6 is that bad and I also don't consider the "intermediate points at π/4" "all-important". please post some arguments, why these directions are imortant for you.

Tell you what, how about *you* demonstrate why they are *unimportant*?

For this reason, I posted the two photos of Munich, two demonstrate, that rectangular grid is not obvious in reality, at least not for traffic lines (roads and railtrack) at a scale similar to the one used in games like TT (second picture).
The other argument is, that rectangular grid is question of what's more common, but not a natural law. So there's no need to do, what everyone does. But I think, that most players will grow familiar with the triangles very fast.

Remember that we're not only dealing with railway tracks here - roads have to fit the bill too, and it should be patently obvious why right-angled junctions make sense, and therefore have to be supported.

Look at the Photos again. Right-angled junctions are obvious in small scale, but in TT-like scale and for interurban streets there are not many right angles.

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

Now for the technical stuff.
First of, I'm learning all this geometry stuff in my math classes (and I'm not bad in it), so please don't hesitate bombarding me with technical terms.

Two perpendicular axes are rather easier to deal with than three non-perpendicular axes.

Agree.

Ignore height for a moment.

NSure. For the following we'll look at a 2-dimensional area (the ground where the grid is).

With three axes, as you'd get with triangles, you have three unit vectors along the sides of the triangle, (1,0,0), (0,1,0) and (1,0,0).

What are you doing there??? We have only two dimensions, and your vectors have three.

Since you have to satisfy both linear independence and vector space span to form a basis, the triangular model doesn't provide a basis for measuring your terrain.

Three vectors are never ever able to make up a basis for a 2-dimensional area. So no wonder about that. But your conclusion is not true.

I'm afraid to tell you, but you've lost yourself in the geometry.
You only need two vectors to form a basis (cause three vectors will never be linear independent in two dimensions). You're totally free in choosing these vectors (but they have to be linear independent). So you choose two of the three axis provided by the grid (for the ease of use).
See the picture below (VectorBasis.png) for two examples of suitable basic vectors.

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

Ultimately, if it's more understandable, then it will be within the ability of more people to contribute to it. No point having a beautifully complex model if few of the other coders can get their head around it when you mysteriously disappear. In terms of the code, maintainability has to be placed before complexity, because it is something which will be around longer. Before you answer, how do you know that you won't disappear?

Certainly right. I'm here to explain, and I hope, I'll be able to make my suggestion fully understandable for pretty much everybody. There is no sense in trying to master a system that noone really understands (That's why I've no comprehension of capitalists and/or bankers). For the contributors, it should be no problem to provide converters for models, cause transferring vectordata from one basis to another is a totally common operation in computer grafics.
mysteriously disappearance might be possible but is not planned

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

»» It's as simple: Using triangular grid will result in shorter detours.

You're quoting numbers and not proving them.

Right. Here you are:
Take a look at the picture below (Diagonal.png) to see what I meant with "the minimal way of basic directions to connect two diagonally placed points in triangular and rectangular grid"
Start and End are positioned "worst case".
In the triangular grid, the bee-line is 6 * 1/2 sqrt(3) = 5.196... long, the way following only the basic directions is 6 * 1 = 6 long, ca. 15,5% longer than bee-line.
In the rectangular grid, the bee-line is 3 * sqrt(2) = 4.242... long, the way following only the basic directions is 6 * 1 = 6 long, ca. 41,4% longer than bee-line.
So the detour will be 22.5% longer in rectangular grid.

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

Then you can rather handily work along the diagonals, which provides the eight you need.

The point is, that diagonals do not equal the basic directions. You have to use different technics for Junctions, hills, bridges, overhead electrical wire, signals and so on. Will be rather confusing IMHO.

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

About the city shots, I see more square-ich houses

As I do. But do you really see one House in the second picture? They are extreamly small.
In a game one should see houses somwhat larger, but I don't think that building single houses and placeing them on the grid is the way to go. I suggest building whole districts (manually or by a algorithm) of urban area with buildings, small streats and narrow alleys, gardens, trees and so on which are not snaped to the overall grid, but the district itself should be placed into the grid.

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

We keep the range of straight peices, shown in layout4d.
We allow the wider curves so things are just straight, any making things look A LOT prettier. Kinda like Loco does it.

The one doesn't work without the other. Either Layout4 or Layout8.

We have the 6 points around the triangle that things can join to.. could we add one in the middle? Then we'd have a pretty square grid, with the traingle cells.

Don't understand what you mean.

I'm not sure about landscapes made by the tiles [...]

tiles should be smothed in any way. Just start out small and make it more sophisticated later. (I already have some ideas for that, but this would confuse the discussion - there are enough ways to do a great landscape)

BTW: Can someone tell me, why I've allways posted 2 pictures with each post
BTW2: Hope to write shorter posts next time

Fixed your [color] tags. ~Hellfire

[ChrisCF]

From your diagrams, it appears you are using a grid of parallelograms, which would form a basis, but you're ignoring one side of your triangle there. So what you're actually proposing is a parallelograms divided into equilateral triangles, which is no different from using squares divided into right-angled triangles, so now I'm confused as to hy this is different from what we're already proposing.

You might claim that right-angles aren't prevalent in the natural layout of networks, but you haven't provided any evidence that might suggest that equilateral triangles are prevalent. You also probably missed the obvious reason for right angles - visibility in close quarters. Traffidc approaching at a right angle is equally visible (in theory) from both directions along an axis.

I also don't see how you "proved" the longer detours, since by my count, each of those main lines spans exactly three tiles (remembering that one "tile" in this case is the shape formed by your basis vectors), while the detours in both cases are both 6 unit vectors.

Either way, your suggestion has two axes still. Since (unless something else was decided) people were looking at laying tracks in almost any direction, this removes the advantage of using triangles for your routing grid.

On the positive side, I can't see anything which would stop us using triangles for the landscape, and measuring the track and object locations on a square grid.

Some examples of roads and rails meeting at right angles:

A railway junction in Bristol
M4 meets M25
An area with both urban and rural areas - note that it's not hard to find a pair of roads (whether or not they meet) that run at right angles to each other, so the angle needs to be suppported.

[uzurpator]

Nuff said

[Steve]

I'm for the above kind of system really. Spliting the world into bigger blocks for buildings (although they may not be restricted to one block, they are angled over a couple for example) and then using a smaller grid for track points. But rather than just having points in the middle, could we have them in the center of cells too? You wouldn't need as many per side of a tile though, perhaps 5 by 5 (with the ones of the edges technically being in 2 tiles and the ones in the corner on 4).

I'll see if i can make a quick doodle in photoshop.