Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (601)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Efficient 2d tile rendering  (Read 4925 times)
0 Members and 1 Guest are viewing this topic.
Offline kaffiene
« Posted 2005-09-06 10:48:48 »

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  Wink

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  Smiley  I'm happy using java 1.5 only features, if that's important.

Offline Soulfly32

Senior Newbie





« Reply #1 - Posted 2005-09-06 15:21:13 »

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 5000*5000 tilemap and cut it to a 100*100 AreaMap (500*500 Tiles per Area)
(four areas visible on screen!)
= 500*500*4 = 10000

So! What do you Think!


_____________________________________
www.soulfly-design.de
www.soulflyhome.com
Offline darkprophet

Senior Devvie




Go Go Gadget Arms


« Reply #2 - Posted 2005-09-06 16:35:15 »

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

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

« JGO Spiffy Duke »


Medals: 434
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #3 - Posted 2005-09-06 18:47:57 »

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 Smiley

Offline g666

Junior Devvie





« Reply #4 - Posted 2005-09-06 20:12:16 »

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.

desperately seeking sanity
Offline f.l.x

Senior Devvie


Projects: 3


there is no place like 127.0.0.1


« Reply #5 - Posted 2005-09-06 21:25:24 »

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 Smiley . If you want it faster, try adding to the command line -Dsun.java2d.opengl=True, it's impressive, at least on a linux box  Tongue

Litterarum radices amaras, fructus dulces
http://flx.proyectoanonimo.com
figth spam!
Offline kaffiene
« Reply #6 - Posted 2005-09-06 22:29:21 »

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)
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #7 - Posted 2005-09-06 22:51:54 »

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?

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).

Offline darkprophet

Senior Devvie




Go Go Gadget Arms


« Reply #8 - Posted 2005-09-06 23:25:19 »

Quote
A quadtree is completely the wrong way to go about this.

So you say, but you haven't said why, and am i supposed to take your word for it?!

Quote
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

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


Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline kaffiene
« Reply #9 - Posted 2005-09-06 23:34:04 »

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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #10 - Posted 2005-09-06 23:46:18 »

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).
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
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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Abuse

JGO Knight


Medals: 14


falling into the abyss of reality


« Reply #11 - Posted 2005-09-06 23:52:59 »

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.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #12 - Posted 2005-09-07 00:00:39 »

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. Grin

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline kaffiene
« Reply #13 - Posted 2005-09-07 00:16:31 »

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.
Offline g666

Junior Devvie





« Reply #14 - Posted 2005-09-07 20:51:35 »

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 Smiley . If you want it faster, try adding to the command line -Dsun.java2d.opengl=True, it's impressive, at least on a linux box  Tongue

I have to disagree, I just upgraded my tile based game drawing a grid of (64*64)+ 16*16px 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

desperately seeking sanity
Offline TheAnalogKid

JGO Coder


Projects: 2



« Reply #15 - Posted 2005-09-07 21:13:18 »

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?

Offline princec

« JGO Spiffy Duke »


Medals: 434
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #16 - Posted 2005-09-07 23:11:40 »

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 Smiley

Offline f.l.x

Senior Devvie


Projects: 3


there is no place like 127.0.0.1


« Reply #17 - Posted 2005-09-08 09:27:53 »

I have to disagree, I just upgraded my tile based game drawing a grid of (64*64)+ 16*16px 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.

Maybe, but i have had some bad experiences with volatileimages and i'm quite happy with bufferedimages now.

Litterarum radices amaras, fructus dulces
http://flx.proyectoanonimo.com
figth spam!
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #18 - Posted 2005-09-08 09:35:42 »

Also i would recommend you steer clear of bufferedimage.getSubimage(...), due to my exerience of much slowness

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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline g666

Junior Devvie





« Reply #19 - Posted 2005-09-08 19:22:06 »

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?

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.

desperately seeking sanity
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (30 views)
2014-12-15 09:26:44

Mr.CodeIt (20 views)
2014-12-14 19:50:38

BurntPizza (42 views)
2014-12-09 22:41:13

BurntPizza (76 views)
2014-12-08 04:46:31

JscottyBieshaar (37 views)
2014-12-05 12:39:02

SHC (51 views)
2014-12-03 16:27:13

CopyableCougar4 (48 views)
2014-11-29 21:32:03

toopeicgaming1999 (115 views)
2014-11-26 15:22:04

toopeicgaming1999 (103 views)
2014-11-26 15:20:36

toopeicgaming1999 (31 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!