Writing A Tile-Based Game

[twoski]

I've started development on a component-based, top-down, tile-based game using monogame. So far i've been doing pretty good. I wrote a functional screen system, entity management system, entity factory, and the basic classes for the game grid and tiles.

[img_thumb]http://24.media.tumblr.com/d142d538028df2bf3ce8901be708b237/tumblr_mqk2z6uNsU1qmdokno1_1280.png[/img_thumb]

I'm at my first road block: I don't know how to handle drawing all these entities properly (ie. only calling the draw function for entities that are visible), and how to handle a grid that is potentially massive in size.

If i make my grid 2048x2048 tiles large, it takes a few seconds to load, then i promptly get an "out of memory error" from the draw function for the grid. I'm calling the draw function for all of the tiles, every frame, using the same sprite batch.

I have a few questions about sprite batches, if anyone here has experience with XNA/monogame i'd love to hear some input.

- Do spritebatches have some sort of built in z-level type thing? I want to draw certain entities/tiles above others.
- My grid is basically a 2d array of tile entities. Currently i'm just looping through the entire thing in order to draw each tile. I should be doing this differently, but which way is best?
- Is there any advantage to using several spritebatches?

[cartman300]

[QUOTE=twoski;41640864]- My grid is basically a 2d array of tile entities. Currently i'm just looping through the entire thing in order to draw each tile. I should be doing this differently, but which way is best?[/QUOTE]

I didn't work in XNA, but i have had a world with >13k tiles, i used a 2D array and then i just draw
the tiles in the array like this

for x = screen.startpos.x to screen.startpos.x + screen.width
    for y = screen.startpos.y to screen.startpos.y + screen.height
        tile[x, y].draw
    end
end

[supersnail11]

Render the static layers - map objects that never move and are never interacted with - to a texture as soon as you load the map. Then you can just redraw that texture instead of each tile individually.

[twoski]

[QUOTE=cartman300;41640923]I didn't work in XNA, but i have had a world with >13k tiles, i used a 2D array and then i just draw
the tiles in the array like this

for x = screen.startpos.x to screen.startpos.x + screen.width
    for y = screen.startpos.y to screen.startpos.y + screen.height
        tile[x, y].draw
    end
end

[/QUOTE]

Hm, that's what i assumed. The thing is, with my current camera system, i can smoothly zoom in and out, and move the camera freely with the arrow keys. I'm not going to let players zoom in any more than 100% but i might allow the ability to zoom out slightly. That might complicate things a little so for now i'll disable zooming.

[QUOTE=supersnail11;41641558]Render the static layers - map objects that never move and are never interacted with - to a texture as soon as you load the map. Then you can just redraw that texture instead of each tile individually.[/QUOTE]

I don't have any definitive decisions yet, but assume for now that any tile will be able to change its texture during gameplay. However, since my game does take place in space, i think it would be a cool idea to procedurally generate a background using black tiles and the occasional star tile, then render it to a texture. Then i only have to actually draw tiles that aren't empty space tiles.

I have no idea how to do this with monogame, but i've done similar things using OpenFrameworks.

[Dienes]

If you allow the players to zoom out to view the whole map with every tile needing update/redraw each frame, you will most likely run into issues.

You will have to limit the zoom (maybe provide some simplified overview map to compensate?) and limit the drawing loop to enter/exit at the first/last tiles that are within view boundaries (this is easily computed once before the loop starts).

Rendering static map areas to a texture works well for such games when you have a rogue-like-like FOV, where everything else is not in view and "frozen", but it looks like you aren't going for a FOV?

[twoski]

So i'm pretty sure this is the most expensive code ever so i'm just gonna rewrite my camera class so that it is fixed to the grid. Instead of camera zoom i'll just make a minimap.

batch.Begin(0, null, null, null, null, null, camera.View);

var query = from Tile tile in Tiles
where (tile != null && camera.ScreenBounds.Intersects(tile.Bounds))
select tile;

foreach (Tile tile in query )
{
   tile.Draw(gameTime, batch);
}

batch.End();

[Dienes]

Instead of linqing the visible tiles to a separate list, you might want to just mathematically determine where to start and end. E.g. if your tiles are 32x32 and your current viewport starts at an x-coord of 500, you know that you can just start drawing each row at index floor(500/32)=15. Do that for all 4 edges.

[robmaister12]

[QUOTE=Dienes;41648798]Instead of linqing the visible tiles to a separate list, you might want to just mathematically determine where to start and end. E.g. if your tiles are 32x32 and your current viewport starts at an x-coord of 500, you know that you can just start drawing each row at index floor(500/32)=15. Do that for all 4 edges.[/QUOTE]

This, it's 4 divisions and 2 additions for any sized grid instead of a 4,194,304 intersection tests for a 2048x2048 grid.

You can still do zooming, I've done it. You just calculate the edges of your screen post-zoom. If your camera class has a width, length, center, and scale factor (which I'm going to assume is a float where 1 is no zoom and 2 is zoomed in 200%), the left edge would be:

float scaleWidth = width / scale;
int leftEdge = (int)(center.X - scaleWidth / 2);

[twoski]

So I took 2 giant steps back and simplified everything. Rather than doing all these expensive loops through the entire tile array i'm just drawing them based on the screen's position. I also limited the screen's ability to zoom and shit, because that would just cause more headaches. I can always just make a minimap or something.

So now i've got efficient draw code for the tiles and a camera that can move around freely (its bounds are clamped though).

Now i guess i need to figure out my next move. I want to make the black background have stars but that also might be icing on the cake i can deal with later.

[media]http://www.youtube.com/watch?v=Xr_IGv8c394[/media]

[twoski]

ediT: i'm dumb, fixed it

I'm trying to figure out how to create a grid with a large number of tiles. If i make a grid that is 4096x4096 i end up getting a stack overflow. Is there some sort of method for creating these large amounts of tiles safely? Creating 4393216 tiles when the map loads seems like a bad idea (and that number only increases exponentially if i make the grid larger).

[robmaister12]

Are you creating tiles recursively or something? Why are you getting a stack overflow?

If it takes too long, you can try splitting the world up into larger chunks and load the visible chunks up-front and spin off threads to asynchronously load the rest of the world. (or incrementally load the tiles as part of the game loop)

[twoski]

Sorry, not a stack overflow, an OutOfMemory Exception. It happens when i try to make a 4096x4096 grid.

for (int i = 0; i < GRID_SIZE; i++)
{
                for (int j = 0; j < GRID_SIZE; j++)
                {
                    Tiles[i, j] = (Tile) factory.New("Tile");
                    Tiles[i, j].GridPosition = new Vector2(i, j);
                    Tiles[i, j].Color = new Color(i, j, 255 - i);
                    Tiles[i, j].LoadContent();
                }
            }

Eventually my grid will be both procedurally generated and will be serializable so some sort of multithreaded method for loading it seems like a good idea.

[Dienes]

What does Tile.LoadContent() do? I hope you are not loading the image every time for each tile? Because having a 16x16 RGBA sprite for each of the 2048x2048 tiles would result in 4GiB of memory usage...

[twoski]

[QUOTE=Dienes;41660253]What does Tile.LoadContent() do? I hope you are not loading the image every time for each tile? Because having a 16x16 RGBA sprite for each of the 2048x2048 tiles would result in 4GiB of memory usage...[/QUOTE]

My asset loader thing caches results so if i'm loading the same 16x16 sprite for all of the tiles, then the first tile is the only one actually doing any of the work, the rest of the tiles are just using whatever the asset loader cache has.

When would be the appropriate time to load the content for the tiles? Surely loading the content the first time the tile becomes visible would be awkward.

[Perl]

You should load the textures for all the tiles in the world into a map when you load the world.

[twoski]

I commented out the part where the tiles load their content and the program still runs out of memory. Is threading the answer to this problem?

edit: So i had a moment of clarity. I think i need to split the grid into chunks of say, 256x256. Then load/unload chunks based on the screen position. This leads to more questions, like if there is an entity on a chunk that needs to update and do game logic, how would i go about doing that? Delete the chunk and leave all entities intact to continue their updating?

[SimonRhys]

This probably is completely the wrong way to do things but how I do it is have the 2D array for the map, then have an array of all the tiles and just populate the map array with references to the correct tile in the tile array.

Hope that made sense! Like I said this could be completely inefficient and horribly wrong :v:

[Tamschi]

[QUOTE=SimonRhys;41671111]This probably is completely the wrong way to do things but how I do it is have the 2D array for the map, then have an array of all the tiles and just populate the map array with references to the correct tile in the tile array.

Hope that made sense! Like I said this could be completely inefficient and horribly wrong :v:[/QUOTE]

It's as efficient as it gets unless you switch to shorter tile indices instead of pointers/references.

[twoski]

So you're saying just instantiate one of each different tile type then use those instances on the entire map?

What if i want tiles to have individual data though? Like for instance, if i wanted each tile to have its own independent oxygen levels or somesuch. If i had a grass tile then if i changed its oxygen level, every grass tile would have its oxygen level change, if i'm following what you are saying correctly.

Making the map chunk based is surprisingly not that hard, i'm just curious as to what i should be doing with the chunks when they aren't in view. If i have entities in those chunks that may need to do game logic stuff then i can't just outright delete the chunk.

[Dienes]

Unless you work out a really clever way of separating logic-dependent lightweight information and memory-heavy parts, you don't have a choice. To bring up somewhat of an existing example of this very issue: What if in Minecraft you walk too far away from your house? Right, your wheat stops growing.

[twoski]

Now i'm just stumped, it seems like what i want to accomplish is fairly impossible now if i'm limited to only having a part of my map active at any given time. If there are entities in other parts of the map that aren't within an active chunk then i can't do anything other than disable them until the camera is on that chunk. I would have thought i'd be able to create a metric fuckton of tile entities since all they contain is a vector position, a color struct and a texture2D.

How do games like space station 13 do it? that game has a fairly large map with entities all over the place always active, and it's even networked.

[Dienes]

I don't know that game, but when you say networked, are there official servers involved? They have much more power to handle that stuff and serve the clients.

Another thing that comes to mind is that when you reenter a chunk, you check how long it was paused and then update the entities there accordingly. I believe this is what happens in games like Animal Crossing and this mobile Simpsons thing.

[twoski]

There are no official SS13 servers, it's all just listenservers. The game is almost always laggy since the netcode is atrocious, but it still manages to continually update entity data across a pretty big grid of a variety of networked entities.

The game i'm making is similar to an RTS. You are looking topdown and you click on units and move them around. Let's say a unit gets in a fight with an enemy and you leave its chunk. I'm just worried that i won't be able to accurately handle stuff like combat and whatnot if i have no tile information to work with. I'm essentially going to save the chunk data, delete it, then when it gets recreated i have to make a bunch of extrapolations based on what was going on when i removed it, right? But if 2 actors are mid-battle when i leave the chunk and were 1 second away from dying, if i re-enter the chunk 3 seconds later i would be 2 seconds late in finding out that one of them died.

Maybe i should just be deleting the tiles and leaving entities that were currently "active" at the time of leaving the chunk to continue updating. I'm not sure what my hard limit for entities is, all i know is that it's below 4096^2 when i run the game on my pc. I assume that this limit would differ depending on which computer runs the game.

[Dienes]

Yes, but I understand that for an RTS this is not very useful.

Another way is to go low-level and squeeze your data into as few bits as possible. E.g. just having a 16bit int instead of a 32bit one for that counter gives you 8MiB back. If you do that enough, put flags into bitsets, maybe even get rid of full classes and .net containers, it might make it possible for you to have such a huge map fully available.

In the early days, developers used all kinds of nasty wizardry to achieve the impossible on those limited machines they had.

[twoski]

Okay so i did some crude math. Using my new chunk system, at MOST there will be 4 chunks of 256*256 which are active. Which means 262144 tiles will be active if all 4 chunks are active. Assuming that there are a LOT of entities on these 4 chunks, a realistic upper bound would be around 524288 entities (including tiles). That's one entity on every single tile in those 4 chunks. I think that's doable. I was able to make a grid of 4194304 tiles without running out of memory in my tests. Now assume that in my grid i am removing chunks but leaving entities which are not sleeping to continue updating. That's plenty of space for entity data i think.

Maybe i'm completely wrong here though?

[Dienes]

These are still huge numbers. Remember that you are trying to keep a certain framerate, that your entity update functions can be quite complex plus that there will be a lot more things going on beside your tiles and entites.

I have my doubts, but wish you luck :v:

[twoski]

What i also failed to factor in was that in my initial grid tests, my tile class derived from my entity class which had a bunch of unnecessary bloat. My tile class only needs a texture, position, and color so i made the appropriate changes. What if inactive chunks had their tiles/ents replaced with skeleton entities which have all the unnecessary bloat removed and just handle the most basic game logic? entities would be replaced with skeleton entities which just keep track of the entity health and position so i can ditch all the shit like color, texture, and so forth. This would mean i have to save all of the unnecessary data to a file or something so i can re-assign all that stuff to entities in chunks that become active again. Which would mean i need some sort of entity index system.

[Alternative Acc]

[QUOTE=twoski;41673982]
How do games like space station 13 do it? that game has a fairly large map with entities all over the place always active, and it's even networked.[/QUOTE]

It's based on the BYOND engine which does pretty much everything regarding that. You don't need to care about things like these as the engine handles them.

[twoski]

Alright, i'm just going to stick with a smaller grid for now and focus on actually getting the game working. If it's worth playing then i'll investigate improving the grid size.

[twoski]

Chunk system works perfectly.

[img]http://31.media.tumblr.com/3efd9bf2f07cf8c7b9558e82b7aeff7a/tumblr_mr0xflkrhX1qmdokno1_1280.png[/img]

It turns out a 2048x2048 grid is very spacious so i can start working on entities now.