[RFC] Tile map components and rendering

[Xaeroxe]

This RFC was inspired by recent discussions on Gitter.

A very large volume of games rely on some form of grid for level building, whether it be something like Mario, Minecraft, Starcraft, or Metroid. The need for this kind of grid is so ubiquitous that I believe there's a very strong argument for building an optimized purpose built infrastructure for it in Amethyst.

Using entities to represent each tile for this runs into problems of its own, as it causes component storages to very rapidly become poorly optimized for memory usage. Additionally, when using this approach in a 3D space we very quickly run into problems with just having more entities than permitted by the engine. So my proposal is to introduce a new component and rendering capabilities into the engine.

The new component might look something like this:

pub struct TileMap<I, A> {
    width: u32,
    height: u32,
    length: u32,
    tiles: Vec<Tile<I, A>>,
}

Where the Tile structure looks about like this:

pub struct Tile<I, A> {
    id: I,
    mesh: MeshHandle,
    material: Material,
    attributes: A,
}

The generic I is mostly intended for use with a user provided identification system, so that they can easily determine if something is, for example, a lava tile. A is intended for use to store arbitrary attribute information provided by the user. So now the TileMap can be attached to an Entity and then each Tile is drawn in 3D space at the position it occupies within the TileMap. This could also permit some more aggressive CPU side culling, where we only draw the tiles that are on the edges of the 3D TileMap.

This can also function as a 2D tilemap if you just set the height to 1.

Additionally once physics are in place it would likely be desirable to automatically generate the collision mesh that other entities can use to interact with this TileMap, probably by marking Tiles as "passable" or "impassable".

[Xaeroxe]

cc @huhlig

[OvermindDL1]

For note, I've never done a tile structure like that, it would be very heavy, instead I just use unsigned integers as tiles (of either 16-bit or 32-bit depending on my needs) and those just index into a unique ECS world of entities where an entity can have all manor of things defined on it (including a component that holds the 'count'). I've never done a raw mesh/material like that myself and I'd personally find it very limiting (especially as I often dynamically create new Tile types). When the count hits 0 I delete the Tile entity from the local tilemap ECS 'world', and with things like 'count' I can easily do things like, oh, make a buildable 2d spaceship or something where the 'count' of various tiles makes it very simple to calculate certain things, or engine locations can push it around, or so forth, without needing to iterate every tile every tick.

[Xaeroxe]

MeshHandle and Material could be stored elsewhere, but the id type would need to be able to be mapped to a MeshHandle and Material somehow just so we can render the tile.

[OvermindDL1]

I handled that by just having them be components on the internal tilemap ecs world (using the standard caching system).

[Xaeroxe]

I do like the "sub-world" idea though. @huhlig drafted this on Gitter:

/// Resource 
pub struct TileMap<I, A> { 
    width: u32, 
    height: u32, 
    length: u32, 
    tiles: Vec<Entity>, 
}

/// Resource 
pub struct TileManager {
    world: World
}

Personally I'd prefer these be Components rather than resources, as I think that approach might be a bit more flexible, i.e. having multiple grids.

[OvermindDL1]

As I've mentioned elsewhere, in my ECS engine I used a LOT of different 'worlds' in different contexts, the tilemaps for user-buildable spaceships was one big use of it... ^.^;

[AnneKitsune]

You also need to keep in mind that some games, especially in 3d, will want to use the concept of cache. With your TileMap example, it would look like

// resource. Chunks can be unloaded from memory and stored in a file via a system.
pub struct Map{
  chunks: Vec<Chunk>
}
// resource, id can be pos or int or anything
pub struct Chunk<I>{
  id: I,
  size: Vector3,
  tiles: Vec<Tile>
}
// mesh and material should be shared between same tile types, to accelerate gpu rendering and save a TON of memory. The idea of attributes as generic is very clever, I like it!
pub struct Tile<I, A> {
    id: I,
    mesh: MeshHandle,
    material: Material,
    attributes: A,
}

Chunk are basically a way to segment the data, making search algorithm more efficients. For example, if you want the tile at position X=5, you can use chunk_id = 5/chunk_size_x and position in chunk = 5%chunk_size

Of course I'm not saying that this is THE implementation. Just a thought about potential use cases and optimisations.

[OvermindDL1]

Yeah I handled that by having the multiple tilemaps share a Tile ECS world as well.

[huhlig]

Poking my nose around this again and playing with some implementations.

// Top level TileMap
pub struct TileMap<M, C, T, A> {
    id: M,
    width: u32,
    height: u32,
    length: u32,
    chunks: Vec<TileMapChunk<C, T, A>>,
}

// Individually sized Chunk (use const generics when available)
pub struct TileMapChunk<C, T, A> {
    id: C,
    offset: (u32, u32, u32),
    length: (u32, u32, u32),
    tiles: Vec<Tile<T, A>>,
}

// Individual Tile Data ()
pub struct Tile<T, A: Sized> {
    id: T,
    tiledef: TileDef,
    attributes: A,
}

// Tile Definition
// Non unique Reference Data
pub struct TileDef {
    mesh: MeshHandle,
    // Should figure out a way of handling layered 
    // textures and animated marching squares
    texture: SpriteHandle,
}

// Lazily Loaded, multi-frame, mode aware sprite handle
// When rendered, it should be with 2 parameters, current
// mode and current frame, this selects from a 2d matrix of
// sprite positions. Oddly enough this should be able to handle
// both sprite animation/direction and animated marching tiles
pub struct SpriteHandle {}

// Owner of Spritesheet Image(s) and Handles
pub struct SpriteSheet {
    images: TextureHandle,
    sprites: Vec<SpriteHandle>,
}

[OvermindDL1]

tiles: Vec<Tile<T, A>>,

Wouldn't this cause the Tile's to get copied between chunks? I've always just used an ID only (and the ID was just an entity ID into a tile-specific ECS world/context). If I needed tiles with different 'attributes' I just created a new Tile (entity) and used it. When a certain one was no longer in use it would get reclaimed. That allowed for infinite variety and infinite customizability.

[huhlig]

Perhaps I am not understanding you. In this case all a Tile is in this case is an ID, a handle to a tile definition (which is your tile entity) and an optional attribute struct. The attributes being part of the array are often simple booleans or floats optimized for quick algorithmic traversal, I.E. things like A navigation and AI. If an A doing a heuristic search for pathfinding has to look up every tile you're basically going to throw away your cache constantly. I don't see why you would copy tiles between chunks as a chunk is merely a region of space and another chunk shouldn't logically overlap but even if you did, you would be copying an ID, a handle and whatever tile specific attributes you defined.

[huhlig]

Also, I'm still not sure I see the benefit of keeping an indirect reference to tiles. It makes mutation more difficult, is cache efficient and is in a lot of cases is just as big in size. ECS really isn't designed for sequential map data.

[OvermindDL1]

If an A* doing a heuristic search for pathfinding has to look up every tile you're basically going to throw away your cache constantly.

Actually for something like this it would exist as a secondary bitarray (I generally had a tile as passable or not passable) rather than in the tile system (it was a component table in the tilemap specific ECS context), which made for even less memory usage.

Also, I'm still not sure I see the benefit of keeping an indirect reference to tiles.

I'm just speaking of keeping a Tile ID as just an Entity ID. As the Tile ID (Entity ID of a tile) was used then it would increment the count of (and potentially store the location of, depending on the components on the Tile ID (Entity ID)). A TileMap with, say, 'engine' tiles (like a tile-based user-built spaceship) would impart a certain amount of moving power based on the overall mass and the count of the engine tiles, this became a trivial calculation. Something like a 'turret' tile would store the locations of the tiles within, this would cause an extra tile-specific map to be stored in the entity table that would be quickly iterated to perform rendering of a rotating turret on top of the tile (that had it's own stats like HP, weapon power, etc...). A tile could potentially have many components, like a factory tile could keep getting upgraded to have more functionality. Each system that operates over the tilemap's components almost never touch the tilemap directly (I cannot actually think of a case in mind) but where just concerned with the specific components that allocated tiles may have. ECS is quite designed for sequential component data, not the Tile placements themselves (which was rarely ever touched even to begin with, generally only when a tile 'changed').

[karroffel]

In Godot we don't have fixed-size tilemaps, they are infinite and sparse.

It roughly works like this

struct TileSet {
    texture: TextureHandle,
    tiles: Vec<TextureRect>,
}

struct TileMap<A> {
    tileset: TileSetHandle,
    entries: HashMap<Vector2, u32>,
    custom_attributes: HashMap<Vector2, A>,
}

If you want any kind of A* then that's not a functionality of the tilemap anymore, so I don't think you need to worry much about caching here. All the A* should be contained as duplicated data in a more friendly format for path finding.

For rendering you can make use of instanced rendering and some other neat tricks to make it pretty efficient.

[fhaynes]

Moving to RFC Repo

[Xaeroxe]

This issue isn't an accurate reflection of our tilemap plans currently, so I'm going to close it.