Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (710)
Games in Android Showcase (212)
games submitted by our members
Games in WIP (784)
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  
  Tile-based games and Quadtrees  (Read 3846 times)
0 Members and 1 Guest are viewing this topic.
Offline GergisKhan

Junior Devvie

"C8 H10 N4 O2"

« Posted 2002-11-08 06:06:55 »

I think I may have found possible reasons for a slowdown, and I'd like your help in analyzing this as a possible solution.

My game is a 2D tile-based game.

The current world area is 128 by 128 tiles, each of which is 64 pixels.

The viewable area is 512x512 pixels, or 8 tiles on a side.

You should be able to move one tile in one second.  Most characters have 8 frames of animation to display in that time, so I'd like to achieve 32 fps.  (there are times in the game you should move faster, like on a speed potion).

Here is what I'm doing to paint the screen:

I have a thread that just draws the background.  This is done the moment you start a movement... it uses two buffers and switches the buffers when movement stops, so it can take up 1000 ms to draw.  I doubt this drawing is an issue.

To create the offScreenBuffer, which is FINALLY painted to the screen, I first blit the current BackgroundBuffer +/- the scrolling offsets.... this is one g.drawImage().

The foreground images must be interleaved with character images to achieve the depth illusion, so unfortunately they MUST be redrawn every frame.  I have drawing rules which state that top-right is furthest away, and bottom-left is closest, giving us a diagonal "perspective" so to speak.  In order to paint these images, I got the first thing I could think of to work: a nested loop that draws top-to-bottom, right-to-left.

This results in 192 checks to see if anything is there needing to be painted.  And I think it is slow to do this.

I am wondering whether I should load foreground tiles, those non-moving images in the game that interleave with characters (trees, fountains, etc), into a Quadtree.

I'm thinking of creating a Quadtree that holds an object called MapCell, which contains three variables: foreground, character, and flying.  If anything there needs to be painted, I'd just draw the image right then.  My reasoning is that although g.drawImage might be slow, the following loop is likely slower:

for ( int i = iRowOffset - 4; i < iRowOffset + 3; i++ )
 for (int j = iColOffset -4; j < iColOffset + 3; j++ )
   // Check if foreground tile exists at map[j]
   // draw it if there

  // Check if character exists at map[j]
  // draw it if there

 // Check if flying character exists at map[j]
 // draw it if there

Now, I don't know how long it takes to complete the checks, but I know for a fact this loop runs in O(n2) and is guaranteed to run at that rate.

At maximum this has 192 drawImage() calls, but that should never happen; the screen should never be that full.

Would it make more sense to get a range from a Quadtree, which may or may not have objects at the appropriate positions, and just iterate through that list?

Is my logic sound, or am I not looking at the fps problem the right way?


"Go.  Teach them not to mess with us."
          -- Cao Cao, Dynasty Warriors 3
Offline swpalmer

JGO Coder

Exp: 12 years

Where's the Kaboom?

« Reply #1 - Posted 2002-11-08 10:48:40 »

I can't imagine that those comparisons are taking a significant amount of time.

If you think they are, I would first profile or at least do some experiments.  You could for instance run a test where you have no comparisons in that loop.  maybe split the loop in two parts, so that the appropriate number of foreground blits happen so you can get a measure of drawing the average amount of foreground tiles without any per-tile comparison.

For this application it seems that a quadtree is overkill.

Offline GergisKhan

Junior Devvie

&quot;C8 H10 N4 O2&quot;

« Reply #2 - Posted 2002-11-08 21:08:14 »

My very next thing to test is going to be just how long it takes me to draw a frame.

Trying to achieve 32fps when it takes me 120 ms to draw a single frame isn't going to work.

At that point, though, I think I'm onto that other thread about FPS and 1.3.1, where there is NOTHING I can do as I have no acceleration of images right now.  That's assuming that either drawImage or Memory copies are that slow.

I thank you for the thoughts... I will let you know.


"Go.  Teach them not to mess with us."
          -- Cao Cao, Dynasty Warriors 3
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Orden

Senior Newbie

« Reply #3 - Posted 2002-11-08 22:33:34 »

Just as a comparison, i'm running java1.4.1

All images are accelerated.

Tile size is 48*48 pixels.
Screen size 800*600*16.
Number of objects placed on top of tiles 250 all image sizes.

On my AMD1.4 (gforce 64 meg)i get an fps of around 300.
On my p2 266  8meg matrox (old machine) i get an fps of around 58.

I'm using the if method plus an object sort and there is no slowdown.

Accelerated images are definitely the way to go.

All The Best
Offline GergisKhan

Junior Devvie

&quot;C8 H10 N4 O2&quot;

« Reply #4 - Posted 2002-11-09 01:01:18 »

Unfortunately I cannot yet convert to 1.4.  So I cannot accelerate any images yet.

But if you are using an if loop..... it might suggest this is a pretty decent way to go and I'm not going to enhance performance any better than this right now.


"Go.  Teach them not to mess with us."
          -- Cao Cao, Dynasty Warriors 3
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

numerical (56 views)
2017-02-21 07:32:16

numerical (55 views)
2017-02-21 07:31:46

theagentd (161 views)
2017-02-18 13:42:33

theagentd (164 views)
2017-02-18 13:35:16

h.pernpeintner (1327 views)
2017-01-24 22:39:11

h.pernpeintner (1315 views)
2017-01-24 22:38:32

Galdo (1875 views)
2017-01-12 13:44:09

Archive (1967 views)
2017-01-02 05:31:41

0AndrewShepherd0 (2506 views)
2016-12-16 03:58:39

0AndrewShepherd0 (2307 views)
2016-12-15 21:50:57
List of Learning Resources
by elect
2016-09-09 09:47:55

List of Learning Resources
by elect
2016-09-08 09:47:20

List of Learning Resources
by elect
2016-09-08 09:46:51

List of Learning Resources
by elect
2016-09-08 09:46:27

List of Learning Resources
by elect
2016-09-08 09:45:41

List of Learning Resources
by elect
2016-09-08 08:39:20

List of Learning Resources
by elect
2016-09-08 08:38:19

Rendering resources
by Roquen
2016-08-08 05:55:21 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‑
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!