25 minutes ago, Alberth said:

Locomotion and rollercoaster tycoon opted for multi-tile elements in a plain grid. While it has some restrictions in attachment points, you are pretty much free in shape otherwise.

Trackmania is another very good example for this. A narrow curve uses 4*4 tiles, a wide curve 8x8 tiles etc. While playing the grid structure goes totally unnoticed and mostly this even holds if you view the scene top down.

38 minutes ago, Outliner said:

There is some question about what sort of data structure should be used to represent a grid that can have multi-tile elements

I used a simple regular grid, where its contents pointed to the element it was part of, and an xy-offset back to the "top-left" tile. The offset makes each tile in the element unique, and it becomes easy to find the "top-left" tile of an element eg for a unique identification of each element no matter where you click.

Another option is to give each tile a index number within the multi-tile element. Didn't consider that much though, so no idea if that works.

If you split your tile graphics for each tile separately, you can even pretend it's a single tile game for rendering, and the multi-tile stuff only exists in the game logic.

For giggles, I did a quick test of using octagonal tiles:

The spacing on the diagonal ones really throws it off; it doesn't seem any better than just using square tiles, it's kinda tricky to do the art (although once you get some marker vertices laid out, that gets easier) and you still have 'special' movement cases for diagonal movement, and diagonal movement is still just the same distance as moving diagonally on a grid. IMO, using this grid tessellation seems far more trouble than it's worth. Probably best to go with the meta-tiles.

3 hours ago, Alberth said:

I used a simple regular grid, where its contents pointed to the element it was part of, and an xy-offset back to the "top-left" tile.

What do you do when more than one element share a tile? For example, in an 8x8 wide curve it leaves an area inside the curve where track can be laid. If the entire 8x8 area is considered part of the element, then any other elements within that area would have to share tiles with the wide curve.

Even if we strictly specify that only tiles directly touching the track are part of the element, there would still be situations where a tile can touch more than one element. Each time a diagonal track crosses a corner it absorbs a tile to either side of the corner, so two parallel diagonal tracks can easily share tiles.

It would be fascinating to learn how Locomotion handles its diagonals. Perhaps it allows its square tiles to be split into two triangular tiles so an element can own half a tile. That way diagonal tracks don't own more tile than they need.

One way of dealing with such things is to subdivide the base tiles into smaller subtiles, and mark them blocked when a piece of road or track occupies them. Something like this:

When laying down track adjacent to this piece, you can check any subtiles the new piece of track will potentially occupy in this tile, and if any of them are blocked (shown in blue here) then you can't place that tile. You can represent each subtile as a bitfield, meaning that the above tile would require 4 64-bit integers to represent the collision data, making it fairly compact. You can use larger subdivisions to reduce the space requirements further.

54 minutes ago, JTippetts said:

You can represent each subtile as a bitfield, meaning that the above tile would require 4 64-bit integers to represent the collision data, making it fairly compact.

I like this idea, but making it memory efficient like this seems unnecessary because we wouldn't have a subtile array for each tile in the world. We would only need a subtile array for each tile of each meta-tile, excluding those meta-tiles that can share the same subtile array. Since it's not memory per world tile, it can't impact on how much world we can hold in memory at once.

Each world tile only needs slots for up to two meta-tiles in no particular order. We can use that to indirectly look up the collision data to check if adding the second meta-tile to this tile is legal based on the collision data of the existing meta-tile. It is also useful at runtime for doing collision detection with game characters.

One issue with this approach is that it means that up to two meta-tiles share the responsibility for rendering the same world tile. When the tiles are just images we can just use an alpha channel to determine which meta-tile is responsible for which part of each tile, and use a background image for the parts that no meta-tile claims.

It's not so easy if we want to render each tile as a 3D mesh to allow the player to get a closer look at the world. Each meta-tile would contribute a mesh to the world without difficulty, but it's not obvious how we would fill in the ground between the two meta-tiles when two meta-tiles share the same world tile.

Well, I personally would track subtile data for every tile. It's not necessarily always roads that might block part of a tile. Miscellaneous props such as rocks, signs, etc... might also block part of the tile. And such constructs don't always have to be part of a metatile setup. A metatile would cover multiple tiles, but something like a rock might occupy only a single tile; nevertheless, it would still have to be taken into account when placing a metatile or other construct near it. Consider this metatile made up of a 2x2 block of tiles:

You could come along later and build a road near it, in a similar curve, meaning that two metatiles would overlap and you would have to check subtiles to make sure it's legal to place the road:

And it's entirely possible that there was a rock already there before the first set of tiles was placed, so when placing that first road you would have to check any subtiles that might block it from being built:

In this case, the rock isn't blocking any subtiles the road needs, so it's legal to build.

A tile should be able to hold any number (not just two) of tile objects, as long as their subtile blockages do not interfere with one another. In this case, all of these objects (rock, road tiles) would be drawn as alpha-blended or alpha-transparent sprites on top of the ground that is already there.

It doesn't really change all that much if you are drawing 3D objects instead of sprites. The objects would still have a 'footprint' of subtiles they occlude, that still need to be checked. The only difference is the way you are drawing objects.

Of course, bridges and crossovers, or any kind of 3D construction, can complicate this, since you might have a train track passing underneath a road or vice versa. In this case, you might need to encode different kinds of information in the tiles, such as the elevation and total height of the occluding piece, to allow roads to be built even though the bridge would occlude the simple subtile footprint where the road needs to go. This can get complicated for a 2D tile representation, but it can be much simpler in a 3D representation since you have access to the actual mesh geometry of the object, and that mesh geometry has 3D information built into it. Placing a road underneath a bridge then becomes a collision test between the bridge and an extruded curve or shape representing the path of the road. As long as you know the clearance of the bridge, the path of the road, and the required clearance for the road to legally pass through, you should be able to make a determination on whether the road or bridge can legally be placed in the tile. (All sorts of things in general, when dealing with tile-based schemes, become easier if you do it in 3D.)

1 hour ago, JTippetts said:

A metatile would cover multiple tiles, but something like a rock might occupy only a single tile.

To keep things consistent I would make everything a metatile even if it occupies only a single tile.

1 hour ago, JTippetts said:

A tile should be able to hold any number (not just two) of tile objects, as long as their subtile blockages do not interfere with one another.

That's probably wise. Even if it seems unlikely that more than two things would fit onto a single tile, there's no reason to create such an artificial restriction.

1 hour ago, JTippetts said:

It doesn't really change all that much if you are drawing 3D objects instead of sprites. The objects would still have a 'footprint' of subtiles they occlude, that still need to be checked. The only difference is the way you are drawing objects.

It's a pretty big difference. It's easy to combine images with alpha channels. It's not at all easy to combine separate meshes together. The subtile concept is a great way to keep the meshes from colliding, but connecting the two meshes across the gap between them is not obvious.

One approach might be to ensure that there is no gap between meshes by requiring that every subtile be completely filled. So if a metatile touches a subtile, then the metatile is responsible for covering the entire subtile, and an algorithm could be devised to efficiently fill the uncovered subtiles in each tile.

You don't need to combine the meshes together, though. Just draw them separately.  As far as connecting meshes across tile boundaries, that's a function of how you create the mesh geometry, rather than of the subtile or tile system underlying your abstraction. If you construct the meshes so that they line up with one another, then all you have to do is instantiate them on the map and they should align.

Consider these 3D road tiles:

Wireframe:

Tiles broken apart to show pieces:

The pieces are constructed such that all you have to do is put them in the right place, and their edges will align with their neighboring tiles. By building a comprehensive set of these pieces, they can be mixed and matched to build any kind of road configuration. They don't need to be combined into one mesh before drawing, they can just be drawn individually (or in batches, depending on the particulars of the underlying 3D engine.) That's part of the reason I believe that 3D makes these kinds of things easier. Because the problem reduces down simply to instancing 3D meshes at appropriate locations, and with appropriate rotations, and every 3D engine in the world makes that job easy.

2 minutes ago, JTippetts said:

If you construct the meshes so that they line up with one another, then all you have to do is instantiate them on the map and they should align.

I see what you mean. The road metatiles would naturally be designed so that the end of one road segment perfectly fits with the start of the next one.

The difficult connection isn't at the point where one road segment continues another because that can be predicted and standardized. An example of a difficult connection is between a road and the rock sitting beside the road within the same tile. The rock could be anywhere, so there's no way to standardize that connection. Or consider two roads passing near each other and touching the same tile. Each road supplies its own mesh, but what do we do for the remainder of that tile to make it fit with the two roads?