J2ME - big image scrolling

[roudek]

Hi,
on this forum:
forum.java.sun.com/thread.jspa?threadID=5191183&messageID=9760475
you described a simple way to implement scrolling of a big image:

1) Start with a 2-D array of Image Objects, that is the size of your entire tile set: 50x50, set them all to null(default)
2) When you draw a tile, check if the image in the 'image' array is null, if so: load it.
3) If at any time you have too many images loaded, just set the reference to null for one of the image tiles that is currently off screen. This is easy, just find the lowest/higest row or column currently on screen, and nullify everything beyond it.
4) Remember to call the garbage collector after a session of nullifying images. "Runtime.getRuntime().gc();"
5) This will have very poor performance, but will solve the memory issue. The larger the tile size you use, the fewer calls to 'drawImage' you will need, and the performance will be much better, but take more memory. For your app, you'd probably be best off with something like 64x64 sized tiles.


I've implemented this, but it is waaay to slow. Could you please give me any advice on improving this algorithm? You also mentioned that there is some other way to implement smooth scrolling using a single off screen buffer.. maybe you could explain it?

thanks, roudek

[Adam Schmelzle]

Before I ramble incoherantly, I'd like to re-issue my disclaimer from that previous post....

Please nobody post telling me that this is horridly inneficient, and slow. I know, but am just trying to explain a simple way to get the image on screen without blowing up.

There are ways to implement smooth scrolling using a single off screen buffer, while also being able to arbitrarily scroll in both x and y directions. It's 100% non trivial though, and I wouldn't be able to explain it if my life depended on it.

Despite that, let me risk my life... This consumed my life for about a month. A solid month on this class I use to scroll smoothly now in all my games. This class is used in 'Attack Cannon', and some other games that are so far un-released, but has worked out famously for me. Let me try to explain my technique....

1) Picture an overall scene that is larger than the size on any one device-screen, lets say as large as 10 x 10 screens. Use a blank piece of paper.

2) Now imagine you want to draw the top-left corner of the scene onto the device-screen, so you draw a screen-sized frame(lets make it blue) around the top-left portion of the scene, and that is what will be contained within your image if you draw it on screen.

3) Now imagine drawing the contents of the scene to your screen, only it's exactly 1 screen over to the right of the first one, and draw a frame around that. Also make it red.

4) Continue drawing screen-sized frames onto the scene in this fashion, and you'll end up with a grid pattern on the scene all coloured blue. These frames show what is displayed on the device if you scrolled over exactly one screen size at a time and re-drew the scene to the screen.

5) Now it gets tricky to explain. Draw a red device-sized frame that overlaps the 2nd and 3rd colums, as well as the 4th and 5th row.

6) Looking at the new frame, imagine we want to display this portion of the scene on the device. The TOP-LEFT quadrant of the red frame(device screen) as divided by the blue grid is actually a slice at the bottom-right of the scene at grid (column 2, row 4). TOP-RIGHT of device is the bottom-left of scene(3,4), etc.

7) Now what you want to store in the magic buffer is data stored in the orientation of the blue grid. So in our initial setup of the blue frame, the buffer is re-arranged, so that the scene portion(2,4) is in the bottom-right of the magic buffer, as opposed to the top-left of the device-screen. It's as if we imagine the initial blue grid as having a bunch of side-by-side device-screens, and therefore the top-left of our red frame is only displaying the lower-right of the imaginary device located at position (2,4). So we store all the data in our magic buffer in the same portion of the screen as the virtual device has it. This goes for all overlapping imaginary device screens.

8)If we've managed to get this far, and I'm not sure if I still make sense, we'll continue by drawing a new device-sized frame in green that is shifted slightly to the bottom-right of the red frame. To keep life simple, don't overlap any new virtual device screens.

9)What we have now in the green frame is the second position of the game screen. As if we scrolled down-right since the last frame. What you may now notice, is that there are significant portions that overlap between the two frames. These overlapping areas do NOT need to be re-drawn to the magic buffer! Even though we just moved the screen in BOTH the x and y directions, the screen only ever needs the NEW areas to be drawn over top of the old sections that are now off-screen. You should also notice that the new segments will exactly overlay ontop of the now off-screen segments in the magic buffer.

10) To draw the magic buffer to the device screen, it takes 4 separate calls to clip and draw-image. One clip and draw for each quadrant defined by the overlapped imaginary device screens.

11) By now I'm sure this has totally confused any reader, since I havn't provided any diagrams to back up my explanation. This is why I said I wouldn't be able to explain it very well. It took me quite some time to get my own head wrapped around it, and I came up with it! I went through a couple notebooks worth of paper trying to work out all the diagrams to convince myself it would work while I was trying to implement it.

12) I'm terribly sorry for exploding any brains. I just did this straight from memory, visualizing it in my head.

[Adam Schmelzle]

I'm much better at explaining things in person using a white-board and erasable markers. If I was keen I'd make a video explaining it, but I feel a little bit protective of this since It gave me headaches for a month.

[Adam Schmelzle]

As for the original algorithm, improvements depend on what the slowest part of your implementation is. Any chance of seeing some code? I can't think of why it would be all that slow.

[roudek]

Thank you very much for your reply.
I think I understand how you do the thing with the buffer but I'm not sure if it is the best solution for me. I played Attack Cannon and it scrolls really very nicely. But you obviously do not store the levels in images, do you? I think you have the levels stored in some way so that you can easily get value of "pixel" at any position. What I need to do is to scroll a world map stored in images. So if I wanted to use your algorithm, I probably would have to have one screen-sized buffer and whenever user scrolls the map I would have to load 3 (in the worst case) screen-sized images into memory to draw parts of it into buffer, and that would be memory and time consuming. Or have I misunderstood something?

In the originial algorithm the slowest part is when I call createImage... I have divided the map into 64x48 tiles but loading of images is too slow (I load 3 or 4 images at once)

[Adam Schmelzle]

With my confusing algorigthm it would simply cut down on the space you re-draw which should cut back on the images that need to be in memory at any one time. You would never need to have 3 full-screen sized images to load. Forget it, it's too hard for me to actually explain properly

As for the first method, while you are scrolling you shouldn't need to load new images every frame, only when you cross a boundary between map chunks. There's nothing you can do about createImage(). If you need to load images, it's gonna slow you down. The best solution really only depends on the situation.

Maybe it wouldn't be as noticable if you offset the loading between frames. So if you are scrolling to the right, maybe pre-emptively load the images you expect to need, but do one every 10th frame. This wors best with smaller images, since the hit to your framerate for each image is the slow part of your program not the re-drawing to the screen. In combination with my complicated algorithm, this would likely be the smoothest option. The slower you scroll, the easier to predict what needs to be loaded ahead of time.

If it doesn't need to show the images all the time, you could simply wait until the user stops scrolling, and then re-draw everything on screen.

If you have lots of free memory, you can have many more images pre-loaded at a time, and thus need to load less often.

So this is an image editor right? In that case, are you actually saving the image parts when you scroll off-screen as well? That's gonna kill your framerate more than loading I imagine. Both however are killers to performance.

[roudek]

Nope, it's not an image editor. It's just a map of the world, the player will choose missions on the map. Of course I load images only when I cross boundaries between chunks. I will probably try to offset the loading as you propose, it should help. Redrawing the map only when the user stops scrolling is also an option, but it would be nicer if the map was visible all the time.

Or maybe I will try your algorithm.. Finally I really do understand it. The only thing that was confusing me was that I thought (for no reason) that the image must be divided in screen-sized tiles.. and that made no sense

[Adam Schmelzle]

Doh! Sorry about that. I was looking back at the original thread on the Sun forums about an image editor when I first posted this stuff.

So it's safe to assume that the world map won't fit into memory at runtime right? Another thing you can do is try to 'hide' the loading in the background. Like maybe have some really low-detail version of the game map that can be drawn in place of any tiles that are still loading. Or the low-detail can be displayed while you scroll, and then re-draw when scrolling is done.

It really is a tough nut to crack when you have an image set that won't fit into memory. Maybe loading in a separate thread would help smooth things over a little as well, since it may not add any large pauses to the gameplay when scrolling.

[Adam Schmelzle]

Maybe as a side project, I'll try to implement something that works well under these circumstances. Hell, if I can get it done right, maybe I'll just post the classes.

[roudek]

For now I changed the program acording to your hint - now I load images between frames. It works well. Scrolling is now much smoother. I will experiment with various tile sizes etc and I'll also try to use a separate thread, I'll see what will come out of it.

I also like your idea about low-detail version displayed while loading tiles.

admin said:

Maybe as a side project, I'll try to implement something that works well under these circumstances. Hell, if I can get it done right, maybe I'll just post the classes.

That would be great

[Adam Schmelzle]

Cool. I just haven't had to deal with this situation yet, since my games use minimal amounts of images. Maybe I should license my classes as middleware. I wonder if there's a market for this stuff.

Anyhoo, I may start to tackle this next week. I'll have a look if I want a break from my current stuff.

[roudek]

My final solution: I load the map into a byte array and use your 'magic buffer'. The parts that need to be redrawn I put into temporary int arrays and draw using drawRGB. It works really great!
Thank you very much for your help, your algorithm is cool

[Adam Schmelzle]

That's awsome.