News:

Simutrans Sites
Know our official sites. Find tools and resources for Simutrans.

Curves

Started by ij, February 06, 2009, 09:38:11 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

ij

Hi all,

I've started to think about breaking free from isometric jail and allowing curves to be built.

Main motivation:
- One could then build real looking intersections with ramps & all. Nowadays it's very complicated with artificial height manipulation and 90deg turns since bridges cannot be built diagonally. And the result isn't all that impressive visually even when you succeed to connect everything.
- High-speed tracks can have appropriate radii in curves. E.g., TGV-Interconnect junction:
http://maps.google.com/maps?f=q&source=s_q&hl=en&q=48.691867,+2.719116

Thoughts about the implementations:
- Precalculate the curve when building. Take straight way piece and curve that along the calculated path.
- First start with arcs only. It's easy to do math with them. However, I really would want to see bezier or some other, more arbitrary form of curve to be possible. But so far I had little luck in figuring out inverses mapping with bezier.

Cons:
- Precalculated graphics consume some memory, so prissi won't be happy ;-). Though it is easily possible to cache identical curves. I hope one doesn't have too many curves in the area of a single view as it's probably not that cache friendly.
- Well, Simutrans would not be isometric-only anymore.

Problems:
- Diagonal graphics and horizontal/vertical graphics "won't fit" nicely I think since e.g., track width is different... However, it would still be nice to allow starting a curve from a diagonal track somehow.
- How to do UI?
- How to handle signals along the curve?
- Probably many other I'm yet to find out.

No patches yet since figuring all it out will take a lot of time since my German won't go beyond "spieler" (which I know from board game boxes :-))... So I'm not offended if somebody else finds it interesting enough to come up with the solution before I do.


jamespetts

A good tip for understanding what the various German words in the sourcecode mean is to use Babelfish or Google Translate, and put the English version in code comments next to the German word...
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

whoami

Quote from: ij on February 06, 2009, 09:38:11 PM
So I'm not offended if somebody else finds it interesting enough to come up with the solution before I do.
This sentence made me smile. Do you know how many parts of the program need to be rewritten, how many additional graphics (tracks and vehicles in more different angles) need to be painted for these ideas? Simutrans is tile-based, and many parts depend on that.

I guess that diagonal bridges are possible within the current scheme (tiles), but still a lot of work, maybe too much for the few cases where they would give real benefit. In the current program, even diagonal tracks exist only as a visual simulation, based on the tiles left and right of the visible track.

ij

Quote from: whoami on February 07, 2009, 03:42:28 AM
Do you know how many parts of the program need to be rewritten, how many additional graphics (tracks and vehicles in more different angles) need to be painted for these ideas? Simutrans is tile-based, and many parts depend on that.

IMHO, this is a no-problem. Free-angle rotation has been used for ages in sprite-based games with only limited set of "real" angles from where the actual graphics is produced. And the curves are produced from straight piece through math.

No I don't yet know how much must be changed and figuring it out takes some time since I just can't read quickly the code because I need to translate every nth word. :-)

The game will still remain pretty much tile based so there's no difference there really. After all it's just gfx trick on a limited area. The affected tiles will get allocated to the curve (it is possible to allow another curve when no overlap happens but that's not on top priority). There will certainly be some limit to prevent building 100 tiles long curves for obvious reasons.

VS

#4
The basic idea is nice. I definitely agree that breaking out of the isometrical "jail" would make the game more interesting. Having to follow the grid is rather unnatural (at least at the beginning).

On the other hand, how would user interface work now? I spent some frustrating times in RT2 trying to build certain track shapes, only to find that it can't be done because of the terrain.

Repainting ways is a lot of work, but still less than redrawing vehicles. So what can be done there? Currently we have 8 directions for vehicles. You are saying that combining these with offsets will work. I agree. The question is how well? For bigger paksets it will start looking pretty bad. Currently 128 is somewhat ugly on corners, where vehicles drive off the road etc. I wonder how smoother turns would look.

Well, after a lot of work, it might be possible to have larger 90° curves with radius, say, 3x3, with vehicle positions and rotations interpolated in between.

One immediate problem is that ownership of tiles will create strange "outlines" of tracks while te track itself will be smooth.

PS: oh, and one even bigger problem will be double tracks - currently you build two tracks next to each other. With smooth curves, they would mix together. And since vehicles must be on some tile... the required changes to game logic would be immense.

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

jamespetts

Hmm - how would all this work with (a) the default; and (b) my experimental system of reducing the speed of vehicles in corners?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

VS

Who knows?

Also - one track per tile can't work with anything as basic as simple curves. So I am almost sure it almost warrants a complete rewrite of vehicle and ground code.

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

isidoro

Quote from: ij on February 07, 2009, 10:22:49 AM
No I don't yet know how much must be changed and figuring it out takes some time since I just can't read quickly the code because I need to translate every nth word. :-)

That's a very big problem with ST code that prevents many developers to join.  Once you get used to the German words, it's easier, but I guess that some people just quit before that.

ij

@VS: I was thinking of making the curve not from 8 directions pieces with + offset. Trying to summarize what I mean:

- Track/way is mathematically transformed into curve shape from straight imgs. In theory this is problem from sun direction point-of-view but there are hardly round enough shapes to make that a problem.

- Vehicles are runtime rotated using simple sin and cos formulae (same as sprite rotation) from eight directions, thus the angle is not limited to those eight (this could be reusable elsewhere in cornering but it might get expensive). Also the positioning along the curve is sin and cos stuff. Again sun shines from correct enough angle I thing, except perhaps in case of fully round car such as beetle. In general it's rather straight-forward but there could be defiances if the graphics won't match nicely when there's  need to switch to the adjacent direction img as source.

...thus no new images need to be painted for this. I hardly find this too big problem, though the img format is making it a bit challenging if I understood the format correctly: ((hlen, linepixels) x lines), can't use plain array lookup for that but it's only a small obstacle nevertheless.

UI is hard to get right, I hate UI design anyway ;-). I'd first do it so that you have two track ends of same type in correct position & directions, and a curve tool will connect them by starting the curve from the first empty tile. The tile type will be the same as those track ends. But upgrade, electrification etc are in conflict with double track a bit (on UI level only, more about that below). So far, I have no idea how to inform the user why the curve is not buildable.

I'm not fully sure what you mean by the "ownership problem", all tiles below the curve must be allocated to the curve, but see below a note about double track.

I think vehicles might be placed on the entering tile of the curve until they are cleared fully from the curve, and special curve resolution logic would then be applied. This should be easy to do and unambiguous.

I agree that double track is somewhat problematic, however, it's that for UI only. You made a nice tiled picture about that, lets prove the opposite using it... :-). First we need to "zoom" it 2x, ie., so that the tile edge will be where blue lines begin. Thus the centerlines of adjacent tiles/curves are red lines. Now consider what is the curved edge line. It is exactly the same (the blue line) for adjacent curves, so the tile sharing is actually false sharing. But for UI it might be harder to figure out which of the curves one means when clicking so that's certainly problematic. Thanks a lot for your comments btw, they helped me to realized how easy the double track problem actually turns out to be.

I haven't yet figured out the details of the ground code. I hope I can easily add some hook there to direct the handling of false shared tiles into a specialized curve code. Similar disclaimer applies to many other things above since I've not yet gone through every relevant bit of existing code.

...I'm not thinking of stations in curves atm, yet I'm sure somebody comes after them soon... :-D ...I suppose we could handle them with the same logic, but not top-priority
task I'd say.

VS

#9
Hm, first let's clarify something... are you still considering arbitrary bezier shapes, or do you want to restrict the whole thing to 90° (and possibly also 45°) curve segments? What I am writing below regards the latter case.

If you say you know how the curve problem can be solved, the better. I must admit I have still no clue about that. Maybe you misinterpreted the image? It shows a 6x6 tile chunk with red & blue lines both being ways in different radii (radiuses?). The ownership (which track does tile belong to) is background colour, violet is for both which is the conflict. Oh, I see now. And visuals are not important because important is where the middle goes. (Except for reserving some tiles in front for drawing the other pieces) But what about different sizes?

Vehicles advance over tiles in small discrete steps, so their visual arrangement in these turns could be computed fast with precalculated tables. Images, that is a bit worse. You definitely don't want to construct them on the fly.

One particular problem you will run into is vehicle routing. I have never looked at that code, but from all the hints it seems that route for vehicle consists of a list of tiles to move on. This is one of the issues I tried to hint at earlier (as always I assumed and left unwritten too much). I can't imagine well how that might work with a big curve? Or maybe this is easy - just modify the rules depending on what kind of track the tile has?




I don't know if it is helpful or not... but if I may have a suggestion: try to code first the vehicle movement, specifically for ships. That way you will get to face the first handful (mountain?) of obstacles, regarding vehicle positioning and graphics. The good part is that ships move on open water so you should not have to worry with ways getting into the picture. But routing will already come

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

jamespetts

Vehicle routing does indeed consist of a list of tiles for it to move on. I daresay, there are a lot of other things bound to tiles, too. One could develop a shadow position system, in which the vehicle has a "real position" and a "visual position", the former maintaining the current setup with tiles, and the latter making the curves look better - but that would be hard to code, I imagine, and harder still to maintain.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

Fabio

Quote from: VS on February 07, 2009, 11:33:25 AM
Repainting ways is a lot of work

I support this idea, if possible, it's GREAT! I would just be more than happy to paint those new curves in the forthcoming new 128 tracks, ihihihihih

prissi

I think this endavour would need a rewrite of 30% of the code. The routing is tiles based, and the display routines too.

The only way out I see would be smaller tiles (like 16 or so) which contian on meta-tile. But this would mean a memory consumption 16x of the current, i.e. any map larger than 256x256 is unbearable with todays computer (and, since things rather point multicore than higher processing speed for single core, also for the next five years).

If you come up with a better solution, just go on. (For starter, most player would be happy enough to have closer diagonals.)

ij

@VS & jamesspetts: I took a look into vehicles and I think it would be at least possible to force hop() often enough though I don't fully understand if that will work with multi-car convois (right term here in codewise?) for all cars. I'll probably do as you suggest and experiment with ships (or vehicle movement on phantom curves). I'll concentrate on arcs first, only if they'll work then I might try to take a stab into dark side of math and go along with bezier.

@fabio: I wouldn't waste time just yet in painting :-/.

@prissi: What makes you think routing cannot go through a point-to-point curve? There's well defined start and end tiles in such a curve which joins it cleanly to the rest of the network, and some special trickery in between. Obviously the movement during the curve will have to break the tile boundaries in ways that are unnatural to the current code but I can't see how it would be any less possible than when a vehicle is moving a straight route over edges of tiles (in gfx-wise I mean). Maybe I miss something important still, that's well possible since my German hasn't improved much since the last day, but I don't see why smaller tiles are sooo mandatory for this.

One new thought I get from the pictures above is that the false sharing problem might be possible to address simply by pairing current pos and pos_prev (or a grund with appropriate ribis) in order to determine which of the two possible curves where in use. This would allow using real grund & tiles almost everywhere. Another alternative is to use start and end tiles only and short-circuit past them but that needs some hacks to deal with the actual movement then.

More I read the code, more possible it seems... :-)

isidoro

Quote from: prissi on February 07, 2009, 08:07:01 PM
If you come up with a better solution, just go on. (For starter, most player would be happy enough to have closer diagonals.)

Yes.  I remember one of my early posts: http://archive.forum.simutrans.com/topic/07660.0/index.html

jamespetts

ij,

please do consider carefully the system for vehicles detecting that they are in a corner and, if they are, how sharp that the corner is when looking at this. This is important for speed limits on corners.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

Ashley

#16
Hi lj.

This is an idea I've given more than a little thought to in the past, since it's a feature I hope to include within my own game one day. I have focused around the concept of expanding the tile-based model with an 8-directional system, with 3 route paths through the tile, since this offers the ability to produce complex graphical output while still maintaining a strongly tile-based graphical approach.

My original proposal is available to view on the simutrans forum archive, here but I'll restate parts of it here.

Essentially at present every tile has "ribi" or direction values, represented as a bitmask. There are 4 directions, 1,2,4 and 8, and by combination of those values you can derive the ways in which a vehicle may move within that tile. The proposal was to extend that system to 8 directions, to permit more realistic/better looking curves, and true diagonal tracks. (See attachment) Additionally, those route-paths would be made monodirectional and individual. So instead of a simple "route mask 7" producing a T-junction, you could instead say "route mask 2->4 and 1->4 and 4->1 and 4->2" (but not 1->2/2->1. There would then be a compositing engine to make the correct graphics for that tile, and the routefinding graph would be updated accordingly.

Since this proposal was "rejected" (nobody wanted to work on it at the time) I have been working on improving the concept, since it was a system I have planned for inclusion in my own game project at some point. I've decided to extend the idea to allow also for the mythical "double tracks" concept. This would see the number of ways through a tile increased threefold, to 24. The idea here being that, for example, north-to-south a tile may have up to three different paths that a vehicle may take, "left", "center" and "right". The specific way in question would contain a property in its description to set the various different allowable combinations, e.g. railway track would not permit hairpin or even 90 degree bends, only smooth corners.

The upshot of this is a very flexible system which allows:
1. Attractive looking corners and switches
2. Double tracks (e.g. two way tracks within one tile)
3. "Special" arrangements, e.g. a two-way road with single tram track running down the center, where the tram track can then expand into double-way tram track in sections (for passing loops). This would allow the trams to only block the road traffic in the two-way sections of tram track.
4. An easy tile-based way-building system, and ability to keep a strictly tile-based routefinding and graphical system, a vehicle would still be located by the tile it occupies (though this isn't necessary, see below).

Such a system could continue to use pre-drawn graphics, although the complexity of such would be slightly daunting, or composite the graphics on-the-fly from pre-drawn or pre-computed primitives.

In the composited approach, ways could have different "layers" specified, e.g. railway would have a "ballast" layer, drawn first in composition, followed by a "sleepers" and then "rail" layer. For crossings of different ways the composisition layers would be interlayered, e.g. road/rail crossing would be constructed: ballast, sleepers, road, rails - producing the proper effect.

I will try and produce some more mock-up images to illustrate the concept...


I was also thinking along similar lines for more complex curves using a bezier drawing approach, but tbh I didn't really see the added complexity of this from a UI/graphics/tile space perspective to be worth it. Would definitely be the way to go if you're going to go down the full-3D route (which is something else I have experimented with, sadly I am no good at producing 3D models, so the 3D simutrans project rather died before it got started, if only Raven hadn't dissapered...)

Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

The Hood

If something like Timothy's system ever made it I would be very happy!  Once I thought that pigs couldn't fly, but first rivers, then underground slopes, and now the talk is of realistic switches and double tracks!!!  What is happening?!

I had had an idea like Timothy's first picture myself but my utter lack of coding ability or time to learn code meant I dismissed it as an idle thought.  If someone can make this work with simutrans, then that would be amazing! 

isidoro

#18
One problem in the first picture is that, in tile corners, the track invades a little adjacent tiles, doesn't it?


EDIT: for routing there can be "special tiles" with a destination tile.  Let's say, we are in tile (3,4), a special tile.  It is a curve.  The exit is in tile (5,6).  The routing algorithm will store (3,4) and then (5,6), so no problem.  The problem would be drawing the vehicles only.

Ashley

The archived thread I linked to has some discussion of that problem, I suggest solving it by having the overlapping tracks triggering a "masking" effect on the tiles they intrude on, which would prevent construction within the intruded half of the tile. Then "half tile" structures could potentially be constructed on those tiles if desired.

It is most unfortunate that the geometry of our universe is such that octagons do not tessellate on their own, as they would be the perfect shape for tiles otherwise (8 directions, with no intrusion/overlapping). Sadly my attempts to come up with a sane way of using octagonal tiles as the basis for a game world didn't lead to much. I think it'd be theoretically possible to use multiple overlapping ocatagon grids, however it'd be quite complex to do and potentially impossible to provide a simple interface to.

Thus we are left with the problem of either using the corners of tiles (which leads to issues of having to draw parts of the graphics of one tile on its neighbours) or even harder using arbitrary curves and spanning the sections across multiple tiles, then keeping track of which ones are intruded upon... There's a little demo of using bezier curves for ways here which may be helpful in illustrating this kind of way building.

In terms of having vehicles actually follow these ways, I was always planning on simply modelling vehicles in 3D space and transforming their position in 3D into screen coordinates in 2D to blit the sprites. Then it's simply a matter of mapping the various ways as a series of points in 3D space and making the vehicle follow them (using 3D physics). I have no idea how this would be done within the bounds of Simutrans however.
Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

gerw

I also thought about nicer curves, together with dwachs. Our approach was a little bit different:

Basically you have the same track tiles as now. But additionally you have some predefined curves (and switches) - like in Rollercoaster Tycoon. So maybe a 3x3 curve, a 4x4 curve and some kind of switches etc. With this system you are also very flexible and old savegames would be compatible (that's maybe difficult with isidoro's approach).

Václav

I think that creating of real curves would be easy - but then all trains have to be repainted for them.


And also I would not like to think about changes in code and required CPU's output and so on.

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

Zeno

First of all (and with all my respect to all other opinions), I can't find many sense to drawing real curves in a tile-based game. If the game was full 3D like Trains&Trucks it's obvious that some more realism is needed, but since everything in Simutrans is tied up to a tile, I don't find any reason to not doing the same with tracks. Actually, take a look on ships (which theorically don't need a road/track).

In the other hand, I have to admit current curve system is really ugly (being generous); probably some modelled predefined curves would make it look much smarter (TGiant also used them?); actually I like that idea. But making a vehicle run through a predefined 4x4 curve with only 8 views probably wouldn't be very nice; not to tell I don't like very much the idea of drawing vehicles in 16 views ;)


gerw

It seems that transport gigant uses 16 views (http://www.transportgigant.com/images/ss/TG_Screenshot_trees.jpg), but I think this are still too few...

Zeno

Quote from: gerw on February 11, 2009, 08:44:50 PM
... but I think this are still too few...
Drawing 16 would be insane, not to mention 32 ;D

vilvoh

Specially for pixel artists.... ::)

Escala Real...a blog about Simutrans in Spanish...

Ashley

I'm currently working on a technical demo for the proposed system above, trying to procedurally generate track graphics using bezier curves at present. Drawing a full set of track graphics for this system by hand would require over 100 images, and that's just for straight sections and curves! (Although the switches could then easily be generated automatically)

Procedural generation can potentially give me that full set of graphics from only a couple dozen lines of code, which is obviously a lot more time-efficient and memory efficient, procedural generation is quite an interesting area, swapping CPU clock cycles for memory and bandwidth.

As far as vehicle images go, I believe a similar approach could be taken here. Certainly a 3D model can be rendered in any view necessary, and it may even be possible to take a series of 2D images and interpolate intermediary rotation images from them. Actually drawing vehicle graphics isn't within the bounds of what I'm coding at present however.
Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

isidoro

Quote from: gerw on February 11, 2009, 08:44:50 PM
It seems that transport gigant uses 16 views [...]

Not to count that Transport Giant is a flat game (not going uphill or downhill)...

Spike

Quote from: Zeno on February 11, 2009, 10:00:22 PM
Drawing 16 would be insane, not to mention 32 ;D

Locomotion has 32, I believe, maybe more.

Ashley

Been playing around with bezier curves a bit, written a little demo, still a work in progress ofc. Next step is to find a way to map an arbitrary image onto the curve. Then it's a matter of auto-generating curves to represent paths through the tile, combining those graphics to produce switches, and applying a perspective transform to the output to give nice dimetric projection sprites.

As an aside, bezier curves are really cool things.

http://entropy.me.uk/pytile/bezier_demo.zip
Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

Fabio

A quick idea:
there could be a second image for ways (like a second layer) only BW, where black is (are) the path(s) for the vehicles and white is the rest. the vehicle displaying routine should try to stick the vehicle to this line.

Ashley

#31
Bit further now, the sleepers still look slightly off with the sharper curves, think I know how to fix that however.

This technique could fairly easily be extended into the third dimension, for producing 3D track models (even with slopes etc.) It'd also be possible under such a system to have completely free-form track, splitting and branching as necessary. Hardest part really is the control mechanisms in such a case IMO. Making it intuitive and easy while still retaining fine-grained control.

Download the demo from:
http://entropy.me.uk/pytile/bezier_demo_0.0.2.zip
Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

Combuijs

Correct link is: http://entropy.me.uk/pytile/bezier_demo_0.0.2.zip

Is there any way to clear the current track in the left window?

Drawing from 9 to 5 does not look good (and it gets worse when curves are sharper, but that may not be practical).

Closing the application gives errors:

C:\Downloads\Simutrans\bezier_demo_0.0.2\bezier.exe:211: DeprecationWarning: integer argument expected, got float
C:\Downloads\Simutrans\bezier_demo_0.0.2\bezier.exe:99: DeprecationWarning: integer argument expected, got float
C:\Downloads\Simutrans\bezier_demo_0.0.2\bezier.exe:209: DeprecationWarning: integer argument expected, got float

but at least the application does close...

Pressing a key ("del": guess why...) ends the program more unexpectedly with the same errors.

Apart from this, nice enough track. What happens if you do this for 10000 tiles?
Bob Marley: No woman, no cry

Programmer: No user, no bugs



Ashley

Fixed the link, bbcode doesn't like quoting in the same way as html :)

Not yet, you can also draw two tracks along the same path in opposite directions, and produce some really strange curves (e.g. looping back to the same point). I'd intend that in a finished game the maximum angle within one tile would be 45 degrees.

The deprecation errors are nothing to worry about, it was coded in a hurry, will fix it so it doesn't do that in future though.

It'd be very slow to do this for 10000 tiles, which is why I wouldn't :) It'd be used to generate tiles once, then cache the relavent parts of the image for later composition. Indeed, you'd likely just generate the curves individually, then composit them together to produce switches using standard blitting methods for speed. Everything done so far is simply a technical demo to allow me to learn how to do this stuff, it'll eventually get integrated into the pytile engine I've been developing.
Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

isidoro

Thinking about the effort you are making, a reflexion came to my mind.  Why not pass the graphics engine to OpenGL without modifying the underlying ST tile model.  A lot of pak makers surely have Blender 3D models of buildings and vehicles.  For those vehicles whose 3D models aren't available, the graphics engine can put the flat image.  For the others, the 3D rendering.  Once a full 3D pak is available, the viewpoint can be freed or even you could "ride a vehicle"...