SFML community forums

General => SFML wiki => Topic started by: krzat on January 10, 2013, 04:58:08 pm

Title: [C#] TileMap renderer
Post by: krzat on January 10, 2013, 04:58:08 pm
Source: https://github.com/SFML/SFML/wiki/Source:-TileMap-Render

It's a tile renderer that doesn't pre-allocate vertices for every tile (useful for huge maps) and doesn't rebuild vertices every frame.

Somehow I've never seen this idea before. Instead of chunking (or creating vertex array of whole map), I use one vertex array to cover whole screen. Then I update in only when view area changed and new tiles have to be rendered.

The second trick:
if our screen has a width of 20 tiles max, then we will never see tiles 0:0 and 21:0 together. It means that tiles 0:0, 21:0, 42:0, etc. can occupy the same spot in vertex array.
Title: Re: [C#] TileMap renderer
Post by: Laurent on January 10, 2013, 05:02:08 pm
I think it's a lie to say that your class is CPU effective, GPU effective and RAM effective. In general, if you optimize one you it gets worse for another. Your code is not CPU effective, compared to the usual solution of storing everything as a big static vertex array.
Title: Re: [C#] TileMap renderer
Post by: eXpl0it3r on January 10, 2013, 05:13:59 pm
Instead of chunking (or creating vertex array of whole map), I use one vertex array to cover whole screen. Then I update in only when view area changed and new tiles have to be rendered.
Could you explain that a bit further in both ways - what you've experienced that people use and what you've now implemented? :)

Also are you aware of the wiki guildline:
Quote
Licensing
After a community poll decision every source code on this wiki is under the Public Domain License, unless the author of the source code specified a different license. In that case the source code is under the license the author specified.
It's always better to include a notice under which license the provided code is, even though there exists a default one. ;)
Title: Re: [C#] TileMap renderer
Post by: krzat on January 10, 2013, 05:15:25 pm
I think it's a lie to say that your class is CPU effective, GPU effective and RAM effective. In general, if you optimize one you it gets worse for another. Your code is not CPU effective, compared to the usual solution of storing everything as a big static vertex array.
Good point. I will better remove these claims.

Could you explain that a bit further in both ways - what you've experienced that people use and what you've now implemented? :)
I added better description.

Usually, people for tilemap drawing use one sprite per tile, huge vertex array or batching every frame (as I was doing before). I have never seen implementation that works like mine.

Also are you aware of the wiki guildline:
It's always better to include a notice under which license the provided code is, even though there exists a default one. ;)
Thanks, I just included it.
Title: Re: [C#] TileMap renderer
Post by: FRex on January 10, 2013, 09:04:38 pm
I think I'd rather waste few megabytes of ram(that's nothing these days) rather than risk CPU cycles if player runs at rocket speed through map.
Title: Re: [C#] TileMap renderer
Post by: Laurent on January 10, 2013, 10:12:30 pm
It's not just a few megabytes of RAM, it's also a few CPU cycles every frame to upload these data to the graphics RAM, and a few GPU cycles to process the invisible geometry. I'm not saying one solution is better than the other, but these things must be considered.

Usually, a compromise is used: the map is still static, but divided into smaller chunks so that only the visible chunks can be drawn/processed/tested/whatever.
Title: Re: [C#] TileMap renderer
Post by: krzat on January 10, 2013, 11:59:10 pm
I think I'd rather waste few megabytes of ram(that's nothing these days) rather than risk CPU cycles if player runs at rocket speed through map.
* it's not few if you have huge map: 8000x2000x2 -> 2,4 GB of vertices (80 Bytes per quad)
* What you mean by rocket speed? Assuming that you have 16px tiles and move 1000px per second, it's still just 2 columns/rows per frame max.
Title: Re: [C#] TileMap renderer
Post by: FRex on January 11, 2013, 12:28:57 am
Quote
* it's not few if you have huge map: 8000x2000x2 -> 2,4 GB of vertices (80 Bytes per quad)
Loading and discarding chunks as player moves around(minecraftian approach), adding tigh passes that serve as load zones (sourcian approach), using smaller maps,  using bigger tiles. The two former approaches give seamlessly 'unlimited' map sizes. But updating it every time view changes a few dozen pixels sounds like a weird way to do it. Keeping small rectangle in memory and loading more in the background as player moves(maybe even prepare chunks in other threads, using scoped arrays or something).
Quote
* What you mean by rocket speed? Assuming that you have 16px tiles and move 1000px per second, it's still just 2 columns/rows per frame max.
By rocket speed I mean so quick that you update your small array every few frames. ie view covering a lot of distance quickly. Static maps are practically free, all there is is bounding view to chunks plus the cost of at times loading chunks, on huge maps only.

There's also the crazy clever shader approach where you store your tiles in a single pixel each.
Title: Re: [C#] TileMap renderer
Post by: krzat on January 11, 2013, 12:59:14 am
Hmm, maybe you don't realize how my implementation works.

I don't update everything every time view changes(btw. you should know that it is fast enough for most games). I update only rows or columns that appeared on the screen since last update. I would say, that it is even faster than static array,  cause I draw only tiles that are visible and with only one draw call. Your approach would draw whole chunk even if we see only one tile from it.
Title: Re: [C#] TileMap renderer
Post by: FRex on January 11, 2013, 01:03:29 am
Quote
I update only rows or columns that appeared on the screen since last update.
How does that work? You have array covering the screen then 0,0 goes out, 21,0 pops in there and it's now displayed to the right of 20,0, how?
Title: Re: [C#] TileMap renderer
Post by: krzat on January 11, 2013, 01:58:06 am
I wrap coords. I have offset variable which points to the tile in top-left corner of the view.

Assume i have visible area from 0,0 to 19,19 (size is 20,20).

Now I move x+1, so column 0 becomes invisible, but column 21 appears. View is 1,0 to 20, 19 now.

I don't need column 0 anymore, so i perform modulus on column 20: 20 % 20 = 0. Now i can insert column 20 into space left by column 0.


I made benchmark:
(http://i.imgur.com/Y3PzC.png)
Visible area is 107 x 63 (16px tiles). Refresh indicates time spend on refreshing vertex array, Draw indicates time spend on drawing it. Refreshing one row or column has overhead less than 10% (compared to just drawing raw vertices). If we are moving very fast (9600 pixels per second) Overhead is around 50%. There are 53928 vertices in the array (two layers of quads).
Title: Re: [C#] TileMap renderer
Post by: FRex on January 11, 2013, 02:02:05 am
I see now. I was thinking of inserting 21 in 0s place like literally(without position change).
Title: Re: [C#] TileMap renderer
Post by: shackra on January 24, 2013, 01:48:28 am
May can someone show me this code implemented in C++? My mind cannot wrap itself around C# code :(. After all, I am a python guy!

some help?
Title: Re: [C#] TileMap renderer
Post by: krzat on January 24, 2013, 04:11:20 pm
Try this: http://pastebin.com/SrBE69EC
Title: Re: [C#] TileMap renderer
Post by: shackra on January 24, 2013, 06:15:30 pm
Try this: http://pastebin.com/SrBE69EC

cool! :'D
Thanks, I'll try to wrap my mind in this code :)
Title: Re: [C#] TileMap renderer
Post by: shackra on January 29, 2013, 06:51:42 am
Try this: http://pastebin.com/SrBE69EC

Krazt, May can you add more commentaries to your source code? I got lost at some parts of it! :(
Title: Re: [C#] TileMap renderer
Post by: krzat on January 29, 2013, 11:21:02 am
Done.

If you want this to work in your game, you have to write custom provider function.
Title: Re: [C#] TileMap renderer
Post by: Turbine on June 05, 2013, 09:58:56 am
Hmm, maybe you don't realize how my implementation works.

I don't update everything every time view changes(btw. you should know that it is fast enough for most games). I update only rows or columns that appeared on the screen since last update. I would say, that it is even faster than static array,  cause I draw only tiles that are visible and with only one draw call. Your approach would draw whole chunk even if we see only one tile from it.

Sorry for resurrecting this thread, this method is of particular interest to me. I've looked around to find what this technique is called or any algorithms, couldn't find any info on it.

Awhile back I thought of this too for not just activating/deactivating objects but dealing with tile data over a network. I'd be very interesting in seeing your method, mine was a little bulky. Having to consider multiple tile skipping, all angles while making sure it's faultless.
Title: Re: [C#] TileMap renderer
Post by: Ixrec on August 04, 2013, 09:49:11 pm
I think "culling" might be the term you're looking for, and I think there are a handful of specific algorithms used for certain types of culling. In particular I remember "depth buffering" from the OpenGL tutorial I read.