Sign in to follow this  
samp20

Implementing infinite map in 2d

Recommended Posts

samp20    102
I'm currently working on a 2d top down version of the popular game minecraft. I've made reasonably good progress in java, however I'm considering switching to c++, and was wondering if there's a better way to render my tiles.

Essentially the map will be infinite which means it needs to be divided into chunks. The issue for me however is working out the most efficient way to render these chunks. From my understanding the most popular way for normal 2d tile maps is simply loop through each tile that falls within the screen and render it. This however I fear will be too slow with working out what chunk to grab the tile from, I may be wrong however and this be a perfectly viable solution.
The way I'm currently doing things (in java) is creating an individual buffer for each chunk then drawing the entire thing. The buffer is then only updated when a tile changes. The downside to this however is it uses a lot of memory, and potentially I run the risk of certain graphics cards not being able to handle the larger image sizes. It does however seem to run very fast.

One final note is that I will eventually be adding dynamic lighting to the tiles, so the final solution would need to be able to handle it.

Thanks in advance [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]

Share this post


Link to post
Share on other sites
SuperVGA    1132
[quote name='Sam P' timestamp='1305645486' post='4811954']
I'm currently working on a 2d top down version of the popular game minecraft. I've made reasonably good progress in java, however I'm considering switching to c++[/quote]
Way to go!


[quote name='Sam P' timestamp='1305645486' post='4811954']
The issue for me however is working out the most efficient way to render these chunks. From my understanding the most popular way for normal 2d tile maps is simply loop through each tile that falls within the screen and render it. This however I fear will be too slow with working out what chunk to grab the tile from, I may be wrong however and this be a perfectly viable solution.
[/quote]
Well, how would you work our which tile to render? Given a 2d array or even a 1d array, it's pretty simple. In the latter, it's y*width+x, depending on your datastructure, obiously.
The stuff that matters here is how many tiles to show on the screen at once. Should it be locked, and scaled with the resolution, or will the tile size be fixed, and therefore more tiles on the screen? Also, if you don't compose your maps of multiple chunks, you'll be limited to addressing to the highest reachable number in the used type.
That should be alright, but how about stuff not moving with the tiles? Most 2d games (and 3d)have other objects that move independently on the tiles.

For now, there's a lot of stuff to think about, but you'll probably find a subdivided grid to be easiest to work on with tiles, and compose sets of tiles into batches and render more tiles with one call. Also, for other objects if you intend to have many, i suggest a quadtree which makes searching and collision detection somewhat easier.

[quote name='Sam P' timestamp='1305645486' post='4811954']
The way I'm currently doing things (in java) is creating an individual buffer for each chunk then drawing the entire thing. The buffer is then only updated when a tile changes. The downside to this however is it uses a lot of memory, and potentially I run the risk of certain graphics cards not being able to handle the larger image sizes. It does however seem to run very fast.
[/quote]

How are you doing this? Because it sounds right to me. -Are you creating a texture of multiple existing tiles and render them at once like that? How about creating a small texture where each texel represents a tile, and let that pixel map into a tilemap instead? You'll be saving space i think.

[quote name='Sam P' timestamp='1305645486' post='4811954']
One final note is that I will eventually be adding dynamic lighting to the tiles, so the final solution would need to be able to handle it.
[/quote]
Nice! Looking forward to seeing that. It's certainly possible with the approach you suggest, and also the methods i mentioned.

Share this post


Link to post
Share on other sites
samp20    102
[quote name='SuperVGA' timestamp='1305652322' post='4811998']
Well, how would you work our which tile to render? Given a 2d array or even a 1d array, it's pretty simple. In the latter, it's y*width+x, depending on your datastructure, obiously.
The stuff that matters here is how many tiles to show on the screen at once. Should it be locked, and scaled with the resolution, or will the tile size be fixed, and therefore more tiles on the screen? Also, if you don't compose your maps of multiple chunks, you'll be limited to addressing to the highest reachable number in the used type.
That should be alright, but how about stuff not moving with the tiles? Most 2d games (and 3d)have other objects that move independently on the tiles.
[/quote]

The tiles I'll be drawing will stay a constant size (32x32px), so yea the number of tiles could vary. from what I gather a loop like the following would be the way to go:
[code]for(x=0;x<tiles_wide;x++){

for(y=0;y<tiles_high;y++){
//work out which tile to draw
}
}[/code]


The part which may add complexity however is working out which tile to draw. With a 2x2 array of 4 chunks I would store the coordinate of the top left chunk. When doing the above loop logic tells me I should convert the viewport coordinates into chunk coordinates, then from those work out which chunk from the 2x2 array to use. To work out which tile from the chunk to draw I would then convert the viewport coordinates into tile coordinates and % (mod) with the chunk width.
In my mind this sounds like a lot of work to be doing inside a loop and would require some optimisation to work efficiently (then again I may just be underestimating the power of computers nowadays).

[quote name='SuperVGA' timestamp='1305652322' post='4811998']
For now, there's a lot of stuff to think about, but you'll probably find a subdivided grid to be easiest to work on with tiles, and compose sets of tiles into batches and render more tiles with one call. Also, for other objects if you intend to have many, i suggest a quadtree which makes searching and collision detection somewhat easier.
[/quote]

When you mention batches I think that is how I'm doing things currently. Each chunk of the map has an image buffer to store the rendered version of the entire chunk. It is however quite a large image (1024x1024). when a chunk is loaded the tiles will be drawn to this buffer, and only redrawn when the tile changes. The buffer itself is then drawn to the screen each frame. This does however add extra complexity if (and most likely) I choose to add animated tiles (sorry forgot to mention earlier).

Also when I come around to adding entities I most likely will use a quadtree. It actually sounds like it will work quite nicely with the 2x2 array of chunks that I'm using, and will come in handy for collision detection between entities too. [img]http://public.gamedev.net/public/style_emoticons/default/laugh.gif[/img]

[quote name='SuperVGA' timestamp='1305652322' post='4811998']
How are you doing this? Because it sounds right to me. -Are you creating a texture of multiple existing tiles and render them at once like that? How about creating a small texture where each texel represents a tile, and let that pixel map into a tilemap instead? You'll be saving space i think.
[/quote]

As mentioned earlier yea I was using a texture of multiple tiles. Where you mention using a smaller texture with each texel representing a tile, that's pretty much what I'm doing to store the tile data, however I'm using an array instead. The use of the large texture was to try and optimise the render loop, however in the long run I'm thinking I would be better off rendering tile by tile.

Thanks for you're advice, you've certainly helped me come to some sort of decision, and hopefully it's the right one. If not speak up quickly before I get too carried away [img]http://public.gamedev.net/public/style_emoticons/default/wink.gif[/img]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this