Hi
What’s the best way to render a whole lot of 2d tiles to screen at once? I’m doing a brute force approach at the moment which utterly destroys performance on my machine 
I could do openGL / orthographic but I’d like to try using just java 2d tech, partly for learning reasons, partly to be able to reach a larger audience should I actually complete my project 
I’m happy using java 1.5 only features, if that’s important.
hi!
Only one idea! You have this big tilemap and you iterate over that, right?
This is very CPU-killing.
Why don’t you cut this tilemap into pieces.
You iterate over those and you can reduce the CPU-time by checking if this area is on the Screen.
You have a 5000*5000 tilemap:
= 25000 Iterations
You have a 50005000 tilemap and cut it to a 100100 AreaMap (500500 Tiles per Area)
(four areas visible on screen!)
= 500500*4 = 10000
So! What do you Think!
That my friend is called either an octree or a quad tree depending on how many “splitting” you do. If its 8, then its octree, if its 4 then its a quadtree.
Whats is best if you implement a heirarchy. This would contain a Node, and children that can be nodes, but can also be geometry. Also, the concept of a bounding volume is needed too, a bounding volume is the minimum volume in which all the children of this node is contained under. This way, you can only check 1 bounding volume if its in the view or not and that node and all of its children can be skipped (in rendering).
This concept is mainly 3D, not sure how well it transfers over to J2D, because J2D might already be doing that and just skipping rendering internally…not sure
Google for octree and quadtree, you’l get more info from there.
DP
A quadtree is completely the wrong way to go about this. A tilemap has a built-in design optimisation which is that you know how big the tiles are, and how big the screen is, and where you want to draw from. So just draw the tiles you can see. Even in plain Java2D you should be getting hundreds and hundreds of fps if using a BufferStrategy to draw them as the tiles you blit don’t require any sort of transparency. So just draw the entire screen of tiles, every frame.
Cas
I would calculate the rect of tiles that would be onscreen and just render them. Also use volatile image for the tiles i think is faster.
Using a VolatileImage for storing the tiles is a bad idea, you’ll have to deal with “content lost”/“content restored” problems for every tile each time you want to draw it which will kill your performance. BufferedImages are fast enought and 100% safe (afics), try drawing only the tiles on viewport and use BufferStrategy . If you want it faster, try adding to the command line -Dsun.java2d.opengl=True, it’s impressive, at least on a linux box 
Eek! I’m not doing anything as stupid as rendering tiles that are off screen! As previously mentioned, quadtrees are unneeded - it’s a grid - I can tell the top/left bottom/right coords and just iterate between those.
No, it’s just the tiles that are on screen causing me problems.
I render into a screen which is 800x600. My tile size is 16x16 pixels meaning I get 1875 tiles painted per frame. This is what’s going slow.
I’m currently using BufferedImages and Java 1.5.
An idea I had was that instead of drawing to the screen, maybe I could render first to a large buffered image and then just repaint the parts which have changed between frames?
Any other ideas for accellerating the actual rendering of 2d tiles (not doing culling - I’m not attempting to draw anything offscreen)
[quote]An idea I had was that instead of drawing to the screen, maybe I could render first to a large buffered image and then just repaint the parts which have changed between frames?
[/quote]
This is a well known technique called ‘dirty rectangles’ and yes, it can help if you are doing software rendering.
To get hw accellerated rendering, the ‘Java2D FAQ’ in the Java2D forum might give you some pointers. (In fact I’m moving this thread there).
So you say, but you haven’t said why, and am i supposed to take your word for it?!
He never mentioned that all the tiles have the same dimensions, heck, alot of tile maps do infact have different dimensions (look at Zelda as an example). Even so, a quad tree is still probably the best choice as it can cull large amounts of data in one simple check. That, or you can iterate over every single tile thats currently visible (which can be alot) and see if its inside the view or not…I think the answer between those two is quite obvious
The tiles are all the same size.
Quad trees are the wrong approach because QTs are a space subdivision scheme for where you don’t know immediately what is in/out of view. With a grid, you know instantly what’s in or out (you know the top, left, right, bottom tile positions - iterate through the grid inside these values and you get everything which is visible.
Since a regular grid does a perfect in/out test by nature of its design, there’s no need for another space subdivision scheme on top of it.
All the 2d zelda games use tiles of the same dimensions everywhere. Not only because it makes sense for the levels, but because the actual hardware only deals with tiles of a set size. Which zelda games are you thinking of?
[quote] Even so, a quad tree is still probably the best choice as it can cull large amounts of data in one simple check. That, or you can iterate over every single tile thats currently visible (which can be alot) and see if its inside the view or not…I think the answer between those two is quite obvious
[/quote]
As has already been mentioned, with a regular grid you don’t check every tile, but can easily figure out the bounds in the array which are in view. The only point a quadtree might help would be the culling of moving sprites (player, npcs, items, etc.). However unless you’ve got a huge level then the cost of maintaining the quadtree is likely to outweight the cost of doing a manual culling of each one individually.
kaffiene: Assuming you’re already using managed images so your drawing is a fast as possible, the main snag is likely to be your tile size. With managed images you get rather fast drawing speed but still incur a certain overhead for each drawing op. For small tiles like yours that starts getting rather significant. I found 32x32 tiles (for a 640x480 resolution game) are about the right compromise. If you really do need small tiles sizes in certain areas then you can perhaps split your levels into two layers - one of large (say, 64x64 or 128x128) tiles for the base and major structures, then a smaller, sparser detail layer with 16x16 images.
Indeed - managed BufferedImages (obtained from GraphicsConfiguration.createCompatibleImage), and drawn onto a 2 or 3 page flipping BufferStrategy should have no trouble achieving the monitor refreshrate on modest hardware.
Are you storing all the tiles in seperate images, or in a single tile set image?
The latter is preferable as it should be far more efficient - significantly reducing state changes in the pipeline.
Last time I did that (with a single tileset loaded from an image file, and sliced into multiple BufferedImages, yet sharing the same backing pixel data) it was much slower than just using individual images (although faster loading, so I loaded a single tileset image and sliced it into seperate pixel data chunks and buffered images). However this was before the days of an OpenGL pipeline, so that may behave somewhat differently.
Remember also with this that your tileset image can’t be bigger than 256x256 (or equivilent) or it won’t be used as a managed image, but will always be stored in system memory.
Of course, by the time you’ve reached this point you’re trying to second guess what the voodoo Java2D pipeline may or may not be doing under the hood. And I’d be asking if you should just be switching over to LWJGL, where high performance 2d is pretty much a known and solved problem. ;D
Heh, well I could whip this up in openGL in a second, but I wanted to aim for as large a market as possible.
I’m not too keen on enlarging the tile size overly much. I think I’ll investigate the dirty rectangles approach and see how much that buys me.
I have to disagree, I just upgraded my tile based game drawing a grid of (6464)+ 1616px tiles using volatile images from bufferedimages, it is one helluva lot faster, this is also withot any culling, with a view area of slihtly smaller than 800*600. Make a class called that wraps around a volatileimage and make this do the checking each tile it is drawn - this is the way jrpg does it.
If you dont want to use volatile images for some crazy reason then depending on the size of ur map(too big will take too much memory, i would recommend rendering the tiles to a bufferedimage the size of the map and hen just rendering that each frame, that is faster for me.
Also i would recommend you steer clear of bufferedimage.getSubimage(…), due to my exerience of much slowness
I don’t understand what you stated. How come blitting from VolatieImage objects directly instead of BufferedImage or just Image could a lot faster? The key here is to make sure you don’t blit TO a managed image (Image or BufferedImage) since it invalidates the cached content in video memory each time. Using VolatileImage instead of managed images might be a bit faster if you skip some cache management operations done by a managed image but anyway you’ll have to check for content lost each time you access the image data.
Maybe I don’t see the whole point here?
Are you using a BufferStrategy?
What’s probably happening here is that the BufferedImages are actually in a non-native format, ie. different from the screen’s format. What you want to do is load your RGBA8 images in as BufferedImages first, then createCompatibleImage from the screen’s buffer strategy graphics and blit into there. This will give you a load of tiles which are in precisely the right format for the screen. You can discard the original BufferedImage you loaded after you’ve stashed the compatible images. I came across this exact same problem while trying to figure things out a year or two ago.
Cas
Maybe, but i have had some bad experiences with volatileimages and i’m quite happy with bufferedimages now.
That’s because images created with getSubImage aren’t a copy of the image data, just a small object which references a subsection in the original image data. I can only assume that this much larger actual image data makes the managed image’s caching less efficient.
I should of said i was thinking of swing or bufferstrategy, both of which use a volatile image as a backbuffer(according to a sun dev blog ) , not rendering to a bufferedimage.