[Tiled] Blank Tiles are Ignored and TiledMapTileLayer.TryGetTile() Returns Wrong Tile

[JayJeckel]

The TiledMapProcessor.CreateTilesIn*Order() methods ignore blank tiles, ie those with global identifiers of 0, when created the TiledMapTileLayer.Tiles arrays and, in any case where there are blank tiles on a tile layer, that results in the tiles being stored out of index order in arrays that are shorter than expected. As a result this causes TryGetTile() to return null when the given x, y coords do have a tile and to return a tile when the given coords to not have a tile.

For example. I have a map with a width/height of 10/10 and it has two tile layers. The first layer is filled by a tile with gid of 1 and the second layer is empty except for the top row and bottom right corner which each have gid tile 2.

The first issue is that if I call TryGetTile() with the x=0 and y=1 (the first tile in the second row which doesn't have a tile), I will get back the tile for the bottom right corner, ie x=9, y=9, and gid=2. The second issue is the reverse, if I call TryGetTile() with x=9 and y=9, I will get null instead of the actual tile.

The first issue appears to have an easy fix, just add a check to verify that the x and y of the tile being returned matches the x and y that was passed in and return null if that isn't the case. Though this is unnecessary if the fix to the second issue covered below is used.

The second issue seems to be fundamental to how the system is implemented, in that blank tiles are not added to the Tiles array at all. This may be a great idea to save space for products that have many extremely large maps, but as something that is applied out of the gate it seems like a touch of premature optimization. My solution was to remove the 'if (tileLayerData[dataIndex].GlobalIdentifier == 0) continue;' line from each of the four TiledMapProcessor.CreateTilesIn*Order() methods. This caused pretty much all of the demo projects to fail, but I traced it back to the TiledMapProcessor.CreateTileLayerModels() method and adding 'if (tile.IsBlank) { continue; }' as the first line in that method's foreach loop seemed to fix those errors and everything compiled correctly.

I am fairly new to MonoGame.Extended, so if there is some other reason that blank tiles were not being stored in the layer's Tiles array, please let me know, but to me being able to accurately check the correct tiles on all tile layers seems more useful than dumping blank tiles and complicating the ability to check them.

[lithiumtoast]

The problem is here yes? Because blank tiles were taken out the math on that line doesn't work as intended. Is that correct?

[Devion]

I would assume it is on line 27 (Array is initialized with the tileCount, this should be the Width/Height f the layer.

[lithiumtoast]

Well if blank tiles are to stored in memory at runtime then TiledMapTile can drop it's xy fields, reducing it to just a uint wrapper. Wether or not the content pipeline stores the xy fields in the .xnb binary file for each tile is a trade off depending on the size and how many tiles are used in each tile layer of the map.

[lithiumtoast]

Another idea is to switch to using Dictionary<Point, TiledMapTile> to store the tiles instead of an array for runtime. See here for an idea on performance implications. The largest map tile size in the demos is 500x500. I don't think using a Dictionary will be feasible due to memory overhead.

[JayJeckel]

Correct, LithiumToast, because blank tiles are removed by the processor, var index = x + y * Width; can cause TryGetTile() to give unexpected results.

A agree that switching to a dictionary doesn't seem advisable. If you use a Point key and remove x,y from the Tile, then you are increasing the x,y memory footprint from two 16bit ushorts to two 32bit ints, in addition to the added overhead of the dictionary, preallocated or otherwise.

I guess the x,y could be removed from Tile if blank tiles were stored, though I'm unsure if it would be necessary as the two ushorts only account for 4 bytes per Tile. For the example 500x500 map, that would account for roughly a megabyte per tile layer. Personally, I would accept the minor memory hit and keep the x,y coord variables.

[lithiumtoast]

So yeah I think that the runtime code needs to create an array the size of Width * Height instead and TiledMapTile can drop it's xy fields but only for the runtime code. The content pipeline code can stay as it is. Then each tile is just 4 bytes and the xy fields are implied by the position of the tile in the array by the math var index = x + y * Width;.

[Devion]

If I can add my 2 cents, keeping the X,Y inside the struct would be nice since it allows easier use to locate certain tiles with linq (ie. Where(X > .. && Y <... etc..).

[lithiumtoast]

If people want special iteration methods that go over an area of tiles I can write custom methods that accept a delegate that do just that while keeping the position of tiles implicit.

[JayJeckel]

I have dug into this a bit more, specifically the idea of removing the x,y coords, and it doesn't seem to be a completely straight forward task as both variables are used in other places within the API.

First, within the Content.Pipeline.Tiled's TiledMapWriter.WriteTileLayer() method. I'm not sure what this class is intended for, as it doesn't seem to be referenced anywhere else in the source code (something to do with saving a map's contents to file, since it is a wrapper around a BinaryWriter stream?), so I can't say what would be a correct change or what side effects such a change could have.

Second, the Tile's coords are used in Content.Pipeline.Tiled's TiledMapProcessor.GetTilePosition() method on both lines 349 and 351. As the method's name suggests, the coords are used to calculate the position that is then used to build the geometry of the tile. I'm not seeing any obvious way to replace the tiles' x,y coords with some other value that is within that scope, but to be fair I've only just started digging in the *Content classes, so I could very well be missing something.

Not sure how much this affects the proposal of removing the x,y coord variables, but wanted to share what I have found. :)

[lithiumtoast]

@JayJeckel With XNA / MonoGame, the content pipeline is a tool which runs on the developer's environment to import, process and build asset files into a final binary format that can then be loaded in game. Unless there is a reason to change the content pipeline code for Tiled maps I think only the runtime code needs to change to fix the core problem here. The reader / writer can even stay the same.

[JayJeckel]

Thank you for the clarification. I've tinkered with XNA on and off over the past six or seven years, but nothing heavier than a modular xnb extractor tool that I made to help mod Terraria assets but never got around to polishing enough for public release. Over the years I've mostly been involved in frontend development for Winforms desktop applications for windows, well, at least until I semi-retired last year. Anyway, enough of my rambling...

So I'm guessing then that TiledMapWriter, while not referenced in the MonoGame.Extended solution (according to VS2015's intellisense), is probably called by the Mono Content compiler when turning a tmx file into a xnb?

Since the pipeline and runtime both use the same TiledMapTile class, how would you suggest removing the x,y coords from the runtime without having to modify the pipeline? My first thought was to turn TiledMapProcessor.CreateTileLayerModels()'s foreach loop into a for loop and use the loop's index to calculate the x,y. Though I'm assuming that one would have to use different index to x,y algorithms based on which render order the passed tiles are stored in. I'm a little iffy on that part, since I've currently only experimented with standard right to left, top to bottom render order. That said, perhaps I'm missing something and there is a much easier way to decouple the TiledMapTile class from the Tiled pipeline?

[lithiumtoast]

The content pipeline is actually decoupled from the runtime. This is possible because this line in TiledMapWriter. Then the TiledMapReader code gets called when a Tiled map is loaded. The binary information read by TiledMapReader has to match the binary information written by TiledMapWriter.

Anyways, all that has to change to fix this issue is TiledMapTileLayer by changing the size of the tiles array to be be Width * Height at line 27. Then at line 35 instead of indexing by i, index into the tiles array by x + y * Width. Now of course the X and Y fields of TiledMapTile are no longer really used since the position of each tile is implied by it's position in the array. So they could be removed, reducing the memory footprint of each tile at runtime by 4 bytes. (Remember that the pipeline and the runtime code for a tile don't have to be the same.) This is probably a good idea because we just increased the runtime memory required by having a large array of tiles the size of Width * Height.

[JayJeckel]

Interesting. So the pipeline still ignores blank tiles when creating the xnb and thereby not increasing its size, but since TiledMapLayer is putting each non-blank tile into its appropriate place in the Width * Height sized array, the rest of the array's tiles are still left with the default(TiledMapTile) value which is a blank tile. Very ingeniously simple solution that I must say would never have occurred to me, but which makes complete sense now that I see it. This leaves all the black tiles with 0,0 x,y coords, but since those are to be removed anyway, that isn't really an issue.

I am curious how you are going to handle the effects to the pipeline code from removing the x,y from TiltedMapTile for the runtime. From your comment about the runtime and pipeline code not needing to be the same, are you thinking to create a separate tile struct for the pipeline or am I still missing something in this area?

I ask because I'm trying to implement this in my own source and after your simple solution to storing blank tiles, I'm kinda gun-shy that my solutions to removing the coords are just ridiculously over complicated.

[lithiumtoast]

I better just explain the whole process of the content pipeline in the context of Tiled maps so we can see where solutions are.

• TiledMapImporter deserializes a .tmx file into some object the content pipeline can use, in this case TiledMapContent. TiledMapProcessor takes that TiledMapContent object and transforms it into a new object. The purpose is to create some form of the asset which can quickly be written and read at runtime. Here we are not doing anything extremely computationally heavy; just processing the tiles in the correct render order, and then creating the render geometry. We even use the same TiledMapContent as output. Other processors for other types of assets might be more computationally heavy. The point is that the player of the game doesn't have to wait for this code to run, hence one of the reasons for using the content pipeline. -TiledMapWriter then takes this TiledMapContent object and writes it to a binary stream. In most cases this would be the same file stream for the .xnb that is to be loaded at runtime. -TiledMapReader then reads the .xnb at runtime, creating a runtime object TiledMap.

TiledMapTileContent is the deserialization representation of a tile from the .tmx file. TiledMapTile would have to be split into two structs; one that is created when processing the tiled map, and the other that is used for runtime.

Currently, TiledMapTile is used in the content pipeline through a link from the runtime code, effectively duplicating the code from one file.

So yes, you are right, it looks like the content pipeline would have to be changed slightly.

[JayJeckel]

Oh, awesome, I was kind of on the right track. And thank you for the breakdown of the pipeline, it fleshed out a few things that I wasn't exactly sure of. The link for linking classes from one project to another is also much appreciated as that is not a feature I've ever taken advantage of before. :)

As a quick test, I added the suggested changes to lines 27 and 35 of TiledMapTileLayer, removed the pipeline's link to the runtime's TiledMapTile, created a new TiledMapTile struct (probably could have a better name, but just wanted to quickly test it out) to the pipeline, gave the new struct GlobalTileIdentifierWithFlags, X, and Y fields and GlobalIdentifier and Flags properties, removed the X and Y from the runtime TiledMapTile struct, and I was able to build the solution and run the Tiled demo with no issues what so ever.

Using the first map of the Tiled demo with its five 40x10 tile layers as a test ground, I checked the memory usage of the runtime for (1) the current way of ignoring blank tiles, (2) storing all tiles with X and Y, and (3) storing all tiles without X and Y, I got the following results (all values are in bytes as reported by VS2015 on Windows 10):

	Total	L0	L1	L2	L3	L4
(1) Ignore Blanks, With X/Y	2,236	1,524	316	220	148	28
(2) All Tiles, With X/Y	16,140	3,228	3,228	3,228	3,228	3,228
(3) All Tiles, No X,Y	8,140	1,628	1,628	1,628	1,628	1,628

Looking at those numbers, there is an increase in memory usage from storing all tiles at runtime, which I believe is a worth while trade off to allow accurate retrieval of tile information, but removing the X,Y coords does reduce the memory usage by almost half.

All in all, this seems like a fairly simple to implement proposal for the project.

[craftworkgames]

I think it's great that you guys have been discussing different ways to approach this problem and keep the memory optimized. Just to be clear though, we need to fix the issue even if that means using a little more memory.

It's always going to be a trade off between memory and speed but it shouldn't be a trade of between memory and being broken.

@JayJeckel How did you make that table? It would be interesting to compare a few different implementations and map sizes.

[lithiumtoast]

@JayJeckel Interesting. Just out of curiosity, could you do a comparison for Dictionary as well?

@craftworkgames The only solution to this issue is the "all tiles" solution or use of a Dictionary so TryGetTile behaves as expected.

[craftworkgames]

The only solution to this issue is the "all tiles" solution or use of a Dictionary so TryGetTile behaves as expected.

Right. So now we just have to measure the differences and pick one.

16kb of memory for five 40x10 tile layers seems okay to me. I'm curious how that scales though. I wonder what it's like for a 500x500 map.

[JayJeckel]

@craftworkgames The tables' info is from VS2015, the Diagnostic Tools panel under the Memory Usage tab. I Take Snapshot to gather the info, then used the View Heap to look through it. Once I had the numbers I manually created the table using githubs markdown syntax. :)

As requested, I did some more tests for comparison of numbers, including using dictionaries to store the tiles by point keys and testing a couple 500x500 maps.

For the dictionary aspect, I create a dictionary and pass it to a ReadOnlyDictionary, similar to how the tile array is stored in a ReadOnlyCollection. Also, in each test, (4a) and (5a) are the same as (4) and (5), respectively, except I preinitialized the capacity of the dictionary to the number of non-blank tiles in that layer.

---

CORRECTION: After getting this all written up, I realized that the numbers below don't necessarily correspond to the layer they are listed under. In the VS2015 Memory Usage report, the numbers are simply listed in descending order, not by the order of the layers as they are set in the map or layer list. Duh on me, my bad. By my estimate for the first two tests, the layers fall as LO:Ground, L1:Platforms, L2:Details, L3:Water, and L4:Tile Layer 5 (which is empty in each map used for testing).

---

The first test uses level01 map from the tiled demo. Winner (5a); however (3) through (5a) are all roughly equivalent.

Map 40x10	Total	L0	L1	L2	L3	L4
(1) No Blanks, With X/Y, Array	2,236	1,524	316	220	148	28
(2) All Tiles, With X/Y, Array	16,140	3,228	3,228	3,228	3,228	3,228
(3) All Tiles, No X/Y, Array	8,140	1,628	1,628	1,628	1,628	1,628
(4) With X/Y, Dict	8,520	5,612	1,132	1,132	572	72
(4a) With X/Y, Dict	8,296	5,612	1,132	908	572	72
(5) No X/Y, Dict	7,368	4,824	984	984	504	72
(5a) No X/Y, Dict	7,176	4,824	984	792	504	72

The second test uses a quick custom map I made that, based on eyeballing, has tile ratios roughly equal to those in the default level01 map. Winner (5a), by a wide margin.

Map 500x500	Total	L0	L1	L2	L3	L4
(1) No Blanks, With X/Y, Array	839,432	745,472	76,028	13,276	4,628	28
(2) All Tiles, With X/Y, Array	10,000,160	2,000,032	2,000,032	2,000,032	2,000,032	2,000,032
(3) All Tiles, No X/Y, Array	5,000,160	1,000,032	1,000,032	1,000,032	1,000,032	1,000,032
(4) With X/Y, Dict	4,951,032	4,380,336	490,632	54,164	25,828	72
(4a) With X/Y, Dict	3,396,752	3,041,768	282,984	54,164	17,764	72
(5) No X/Y, Dict	4,243,800	3,754,584	420,552	46,440	22,152	72
(5a) No X/Y, Dict	2,911,560	2,607,240	242,568	46,440	15,240	72

For the third test, I wanted something that provided more concrete numbers. So, for this test, I created a 500x500 map with 5 layers. Layer 0 has all tiles filled, layer 1 has half tiles, layer 2 has a third tiles, layer 3 has a quarter tiles, and layer 4 is empty. Winner (3), by a gigantic margin.

Map 500x500	Total	L0	L1	L2	L3	L4
(1) No Blanks, With X/Y, Array	4,168,156	2,000,032	1,000,032	668,032	500,032	23
(2) All Tiles, With X/Y, Array	10,000,160	2,000,032	2,000,032	2,000,032	2,000,032	2,000,032
(3) All Tiles, No X/Y, Array	5,000,160	1,000,032	1,000,032	1,000,032	1,000,032	1,000,032
(4) With X/Y, Dict	19,957,584	9,084,672	4,380,336	4,380,336	2,112,168	72
(4a) With X/Y, Dict	15,515,496	7,570,488	3,650,264	2,534,744	1,759,928	72
(5) No X/Y, Dict	17,106,552	7,786,872	3,754,584	3,754,584	1,810,440	72
(5a) No X/Y, Dict	13,299,048	6,489,000	3,128,808	2,172,648	1,508,520	72

Looking at the numbers, in test 1 the dictionary is roughly equal to the array version in footprint and test 2 the dictionary is quite a bit smaller in the preinitialized version. However, in test 3 even preinitializing couldn't help offset the large sizes of the dictionaries in a tile heavy map. Based on the first two tests, I'm inclined to go with the dictionary, but looking at how it scales, ala test 3, I think the array may be the better way to go. The array may have a larger footprint on smaller games, but they have the room to spare, and the memory savings for larger tile heavy maps -- the ones who really need to watch each byte -- seems too important to pass up.

[craftworkgames]

Thanks mate. Really awesome work 😄

The array may have a larger footprint on smaller games, but they have the room to spare, and the memory savings for larger tile heavy maps -- the ones who really need to watch each byte -- seems too important to pass up.

I agree with this conclusion. I think we need to optimize for larger maps since they are the most likely to run into issues as they scale.

It seems that using an Array is clearly the better option since arrays have better lookup performance (when indexing) than Dictionaries. If I'm reading it right it seems pretty clear that Dictionary doesn't really provide any benefits for larger maps.

As for the X / Y issue. It's quite obvious that they are taking up about twice the amount of memory. It's been a while since I've poked around that area of the code but I think we can get rid of them.

There was a question on the forums a while back about querying the tile layers. I'd like to spend some time considering what that means. Hopefully that'd flesh out if we actually need X / Y on the tile.

[JayJeckel]

The linked question appears to be asking mostly about tilesets, something I haven't looked much into as of yet in the prototyping for my game. From the perspective of the TileLayer, Since TryGetTile is currently the only way to get a layer's tile by X/Y coords, I don't believe much will change in relation to querying if the X/Y are removed from the tiles. If you could elaborate on what needs to be looked into, I would be happy to delve into the issue.

@LithiumToast did say something above about adding some methods for iterating on areas of tiles, perhaps expanding on that idea would address the issue?

[lithiumtoast]

It's possible to create a void ForEachTileIn(Rectangle region, Action<Tile> action) method that just loops over the appropriate tiles by doing some math with the implicit positions of the tiles in the array.

[craftworkgames]

I think we should get the TryGetTile issue fixed and discuss the rest in a new issue #359

[lithiumtoast]

@JayJeckel Is this ready to be fixed?

[JayJeckel]

Sorry, it has been a busy week. Yea, I believe we have hit it from the various angles and that storing all tiles in an array, giving the pipeline its own tile class, and removing the X/Y coords from the runtime tile class is valid and ready to be implemented. :)

[craftworkgames]

@JayJeckel Are you going to submit a PR for this?

[JayJeckel]

I've never done a PR before, but yea I'll google up a tutorial and get one worked up when I get some free time this week.

[JayJeckel]

To follow up, I've been swamped the past week or so, but I've scheduled some free time this weekend and will get the PR all worked up then.

[JayJeckel]

Ok, PR submitted and I think I did everything right, but please let me know if I messed up or missed something.