Request for comment: Tilemap extension

(Jacob Kiesel) #1

Introduction

Hi everyone!

I’ve started work on some incomplete prototypes for a tilemap extension to Amethyst. My motivation for this is to make level editing for 2D games easy, and to allow voxel driven 3D games to be made in Amethyst.

Here’s a link to my very incomplete work thus far.

The basic gist of this is that it’s a system designed to generate the simplest possible accurate physics collider shapes for a given tilemap. It makes few assumptions about your tile data structure, and does not assist with the task of rendering the tilemap.

To accompany this, I’m imagining a tile rendering pass, and a tilemap editor. This system will make little to zero use of ECS, most likely just storing the tilemap as a resource.

Why do we need this?

Tilemaps are a battle tested way to quickly build and prototype levels for 2D games, and additionally voxel games have rising popularity with the indie development scene.

Why aren’t you using ECS?

To quote @Rhuagh

Just because we have a great hammer doesn’t mean everything is a nail.

There are two compelling reasons to keep this separated from the ECS.

  1. There are a LOT of tiles in a typical level, for a single screen in Mario you can get hundreds. They would have a very good chance of overloading the ECS, causing cache misses for all of the non-tile data.
  2. Tiles should be kept as minimalist and compact as possible when it comes to data representation, which can be difficult to do with an ECS.

Can I help?

Please do! Right now my biggest blind spot is efficiently generating a minimalist collider mesh for a tilemap. I can identify continuous bodies of tiles, and feed them into a mesh generator, but I don’t actually know how to generate the mesh.

(Paweł Grabarz) #2

I’m not exactly sure what’s wrong with ECS here. Sure it might be unnecessary to store the tiles in the same world with the rest of entities, but the “tile manager” resource could use another ECS space internally. The way you implemented “collides” maps very well to a marker component. ColliderIterator could be used in a system that stores computed collider and recomputes only when things change. This arch would allow to easily add another features on top without needing to modify the main Tile trait.

(Jacob Kiesel) #3

I had considered the internal ECS route before and the biggest reason I dislike it is that it makes the data format not consistent with the conceptual format.

Without ECS we get a data storage format like

width: 8
height: 7

OOOOOOOO
OXXOOOOO
OOOOXXOO
OOOOOOOX
OOOOXXOO
OXXOOOOO
OOOOOOOO

With ECS the format ends up being

[ TileTransform {
	x: 1,
	y: 1,
},
TileTransform {
	x: 2,
	y: 1,
},
TileTransform {
	x: 4,
	y: 2,
},
TileTransform {
	x: 5,
	y: 2,
},
TileTransform {
	x: 7,
	y: 3,
},
TileTransform {
	x: 4,
	y: 4,
},
TileTransform {
	x: 5,
	y: 4,
},
TileTransform {
	x: 1,
	y: 5,
},
TileTransform {
	x: 2,
	y: 5,
} ]

There’s a couple problems I see with the ECS format, it makes querying neighbors much more computationally difficult, which slows down the physics collider generation, and it also permits things like two tiles occupying the same space.

(Paweł Grabarz) #4

Yeah I realised that quickly too. Seems like we would either need a way to “pin” entities to a specific index in specs, or indeed not use it at all. That doesn’t prevent using sort-of ECS-like structure inside for similar benefits. That means using a few masked VecStorages and NullStorages that would allow you to use get(id)/insert(id)/remove(id) semantics over a set of “runtime tile traits” simiar to components.

(Jacob Kiesel) #5

Most of what I’m hearing here is a request for a more extendable internal Tile format. Is that correct? Thus far my code has had no opinion on what a tile should look like from a data perspective, so that’s definitely still a serviceable request.

(Khionu Sybiern) #6

In Minecraft, chunks get loaded and unloaded as necessary, so you only care about the chunks that are loaded, the rest stay on disk. It’s a necessary optimization.

I believe specs is working on implementing user-controlled indexing? With that, we can use coordinates for the indexing, even over ranges, instead of the standard “iterate over everything after a join op” we have now.

(Khionu Sybiern) #7

This kind of problem is incredibly common, it just comes down to validating your data.

(Jacob Kiesel) #8

I’m not sure why this couldn’t be done without an ECS layout.Each chunk would be a separate TileMap.

(Khionu Sybiern) #9

This is meant to be an extension of Amethyst, yes? We should default to using ECS unless there is a solid reason not to.

(Jacob Kiesel) #10

And I’ve got some.

That’s great, I design around what I have right now though and specs development is set to be slowing down, as @torkleyy is moving his efforts over to nitric.

The only reason I see to use ECS at this point is that it’s tradition, and something being tradition is never a good reason in my opinion. That stifles innovation and positive change.

(Khionu Sybiern) #11

Hardly. ECS provides a standard paradigm for the whole engine. That’s not as trivial as tradition.

I responded to this. It would be a matter of validation, a cheap thing assuming specs has the aforementioned indexing.

All depends on how cheap it is to access specific tiles, which is, again, a matter of indexing.

Last I heard, we’d either use specs as a wrapper for nitric and a couple other things, or we’d move to nitric entirely.

This engine is very WIP, as you’re well aware. Trying to design anything without respect for that fluidity is essentially refusing to juggle while balls are thrown in your face.

(Jacob Kiesel) #12

There’s simply a difference in opinion here that I’m not sure we can reconcile on this forum.

Fair, but why bother writing validation code if you don’t have to? If your design simply doesn’t permit invalid configurations that’s less code you have to write.

Such an index would basically have to work identically to how I’ve implemented my system in order to have the same benefits, because you need to take three coordinates and in O(1) time get the correct data. If we can’t use the same indices that we do for entities, and we have to make a completely separate ECS world I’m still introducing just as much cognitive load and a shift in paradigm.

I should have phrased that differently, I don’t have any interest in taking my design and bending it to an ECS API without clear demonstrations as to why that would be superior from a performance, usability, or maintenance perspective.

(Jacob Kiesel) #13

Now there is one thing I think we can do to get a best of both worlds situation. If we have a 3 dimensional point and use that as a “tile index” into several tilemaps, each carrying “component” data for a tile, then we get all of the flexibility of an ECS, and the high performance of not relying on specs specific implementation of an ECS. We could even have different “storages” where the one I’ve provided is a vec storage, and you could, for example, also have a hashmap storage for rare tile components.

Come to think of it this is more or less exactly what an ECS is conceptually, I just don’t care for the notion of trying to force this into specs.

(Jacob Kiesel) #14

I’m also still not sure how I feel about tiles having “generations” either as they would in a specs system. Currently there’s no such thing as a vacant space in a tile map, there’s simply tiles that collide and tiles that don’t.

(Jacob Kiesel) #15

So @Khionu I owe you an apology. We can implement this with an ECS with no drawbacks. Specs storages specifically has some requirements in it’s current form that would hurt us, however we can make our own "TileStorage"s that don’t have those drawbacks. This way we can still have the same benefits shred gives us, without being hindered by the exact implementation of Entity.

(Khionu Sybiern) #16

I’m glad you were able to work your way to see the other side of the table, and I appreciate the apology. I would like to try to have a discussion with you, perhaps another time/venue, about ECS in the engine, with respect to how our perspectives have differed.

#17

Hey guys,

first of all, having amethyst support tilemaps sounds awesome. That would give hobbyists and small game studios a cheap and effective way to build their maps.

I have read your comments, and I have a few thoughts on that.

I see five possible designs of tilemaps for amethyst from the RFC and your comments.

  1. Have a Tilemap<Data> for each Component of a Tile that is a Resource and does not touch the ECS otherwise. This differs from having a single Tilemap entity in that it probably needs special cases for rendering, since it is not an Entity with Drawable attached to it.

  2. Have a Tilemap<Data> for each Component of a Tile that is a Component that is attached to an entity in the ECS. Then Drawable could be attached to that component as well and it would not require a special case for rendering. Each data field of a tile would get its own tilemap, as usual in ECS.

  3. Have a TileChunk<Data> component type that stores an array of tile data for a certain space. This has a big advantage for maps that require dynamic loading and unloading of parts, since the loading and unloading could then just be handled by a system in the ECS. And all the optimizations for drawing and collisions could be done chunk-wise then.
    A big disadvantage though is that now we need a mapping from coordinate to entity. While the TileChunk<Data> can care for its internal mapping itself, we do not know in which TileChunk<Data> to look for a certain coordinate. We do not want to search through all TileChunk<Data>s for a certain location, since that takes linear time, where the Tilemap<Data> just takes constant time.
    I propose to use a resource CoordinateToTileChunkMap that gets updated by some TileSystem. This system would also care for all loading and unloading of chunks.
    The CoordinateToTileChunkMap could be a hashtable, an array, or a tree. Whatever fits best. Probably a linear hashtable would work best for the general case. Still, entities that stay in the same chunk for longer times might have a component that points to their chunk as cache, to speed things up if necessary.

  4. If we can decide at which id we store an entity, then we can flatten away the TileChunk<Data>s.
    The CoordinateToTileChunkMap would then not map to handles to chunks, but to handles to the first entity in a chunk. The entities of the chunk would be stored consecutively in the ECS, so the id of the actual tile could be calculated from the id of the first tile in the chunk.
    I honestly don’t see any advantage of this over design 3.
    It has the disadvantages that loading and unloading puts more stress on the ECS, it renders VecStorages for everything else than tiles pointless, and it requires the ECS to manage ids in a certain way.

  5. Have tiles be unordered entities. This completely ignores the fact that tilemaps are a geometric data structure and makes it impossible to exploit any of its geometric properties. We would need a CoordinateToTileMap that is a tree over every single loaded tile, which can be a lot, especially in 3D worlds. This design also comes with all the disadvantages of design 4.

I would go with design 3 for this RFC. This allows us to use Systems as usual to manage the chunks, but does not require us to operate on tile level for each operation, which has a potentially large overhead.