[SOLVED] Drawing isometric tiles inside a screen ??

[jonjava]

Here’s a link to an Applet ( source included ) so you can see the stuff discussed in action:

http://i.imgur.com/QOGWC.png

SOURCE: http://jonjavaweb.orgfree.com/IsoWorldSource.zip

In Normal tiled games, maps/rooms/worlds are saved and portrayed through a 2d Array like this:

Isometric games are practically no different in how these maps/rooms/worlds are stored. The most notable difference is, of course, how these maps/worlds appear on screen. This is achieved through different projection. I.e, the same 2d Array, just viewed differently. This is mostly done by turning the tiled map 45 degrees in either direction and substituting the tile with a new isometric tile image.

There are different ways and styles on how you can draw isometric tiles. However, this doesn’t matter in calculations. What matters is the width and height of the isometric tile. NOTE: Not always the same as the Images width or height.

Here we have a Sprite/Image of a pink isometric tile that is 34 pixels wide and 17 pixels high. However, this tile’s intended Width and Height are 32 and 16 respectively. Notice the jagged lines that are produced when using the Images Width/Height instead of the intended Isometric Tile Width/Height.

A 2d Array projected Isometrically

(reference:

)

Let’s start by going through the array and figuring out the isometric coordinates. We will calculate the isometric position of the blue (Top Left) corner for each tile.

Let’s insert the isometric projection into a coordinate system and see what conclusions we can draw from it.

[EDIT]: Added Formula to convert Isometric positions back to 2D-Array positions.

In this case we have a screen whose Top Left corner points to a tile (pink!). Now even if the screen moves around a bit, the Top Left corner still points to the exact same tile!

Now that we can find out where to draw the isometric tiles based on the 2d Array, let’s try it out:

Half the tiles are off-screen! To fix this issue we need to add a Horizontall Offset and Vertical Offset Variable. The hOffset makes sure no tile is draw behind the screen to the left, and the vOffset drags all the tiles down so it’s easier on the eyes:

Now here’s my question! Consider a large map

How do I make sure to draw only the tiles within the screen as to not waste memory cpu (less iterations)? The map is stored in a 2D Array.

I’ve fiddled around with my own solution for days now and it just doesn’t work. I need some fresh ideas.

public void paintDiamond(Graphics g, int x, int y, int w, int h) {
		// Paint a diamond shape taken from the 2D surface array
		// shows up as a rectangle in isometric view
		/* [ i ]
		 *   x   *
		 *  x x  *
		 * x x x * [ j ]
		 *  x x  *
		 *   x   *
		 */
		 int px = x/Tile_W; // position x
		 int py = y/Tile_H; // position y
		 int dpw = (w - x) / Tile_W; // delta position width
		 int dph = (h - y) / Tile_H; // delta position height
		 
		 for(int i=px; i<dpw; i++) {
			for(int j=px; j<i; j++) {
				//TODO
				colArray[i][j].paintAll(g);
			}
		 }
	}

Basically only the highlighted tiles should be drawn

[loom_weaver]

You will need to iterate over an axis-aligned rectangle overlaying your original 2D-array.

Then for each tile in the axis-aligned rectangle you will need to check to see if it is on-screen or not. The number of visible tiles will be less as they are a diamond within your axis-aligned rectangle.

Both the iteration and the on-screen check is easy to do and speedy. I don’t understand how and where you think you’ll be able to save memory.

[jonjava]

Thanks for replying to my question. I was wondering if you could clarify what you mean by

[quote]“You will need to iterate over an axis-aligned rectangle overlaying your original 2D-array.”
[/quote]
Here’s what I gather from your post:

Pick an “estimate” box of values (small array) from the BIG 2D-Array. Iterate through this “estimate” smaller 2D-Array and check each iteration if this element is inside or outside of the Screen.

[theagentd]

Find the tile position of the tiles in the corners of the screen, then draw the map line by line between these positions?

int startX = topLeftCornerX(), startY = topLeftCornerY();
int minX = botLeftCornerX();
int maxX = topRightCornerX() + 1;
int maxY = botRightCornerY() + 1;

int currentMinX = startX, currentMaxX = startX+1;
boolean bouncedRight = false, bouncedLeft = false;
for(int y = startY; y < endY; y++){
    for(int x = currentMinX; x < currentMaxX; x++){
        tiles[y][x].draw();
    }
    if(!bouncedLeft){
        currentMinX--;
        if(currentMinX == minX){
            bouncedLeft = true;
        }
    }else{
        currentMinX++;
    }
    if(!bouncedRight){
        currentMaxX++;
        if(currentMaxX == maxX){
            bouncedRight = true;
        }
    }else{
        currentMinX--;
    }
}

Warning: I wrote that when posting. Not tested at all.

[jonjava]

I’ve tried implementing your method, here’s the general idea:

In my code I also use a Buffer variable when they reach the min and max points in the j position. So that it doesn’t immediately start decreasing, only until the buffer is gone. I’ve tried commentating as well as possible.

	private int isoToI(int x, int y) {
                // converts world isometric coordinates into the i position of the 2D-Array
		return (((y/Tile_HH) + (x/Tile_HW)) /2);
	}
	private int isoToJ(int x, int y) {
                // converts world isometric coordinates into the j position of the 2D-Array
		return (((y/Tile_HH) - (x/Tile_HW)) /2);
	}
	
	public void paintScreen(Graphics g, Screen scr) {
		// Screen is a class that holds data
		// start position of the screen, and its width and height
		// paint only the isometric tiles within the canvas
		int iStart = isoToI(scr.x(), scr.y());
		int jStart = isoToJ(scr.x(), scr.y());
		int iMax = isoToI(scr.x()+scr.width(), scr.y()+scr.height()) +1;
		int jMax = isoToJ(scr.x(), scr.y()+scr.height()) +1;
		int jMin = isoToJ(scr.x()+scr.width(), scr.y());
		
		boolean nBump = false, mBump = false;
		int n = 1, nStart = 1, nBuffer = 1;
		int m = 1, mStart = 1, mBuffer = 1;
		
		for(int i=iStart; i < iMax; i++) {
		
		// Testing Purposes
		// Sleep 1 second each i iteration and paint the screen
			// TODO
		// .......
		
		
			for(int j=jStart-n; j < jStart+m; j++) {
				// paint the column
				colArray[ hWrap(i) ][ vWrap(j) ].paintAll(g);
				
				// adjust m and n to keep us within the screen
				
				// adjust n
				if(!nBump) {
					//we have not yet reached the lowest j point
					// increment n to go even lower next iteration
					n++;
					// Check if we have reached the lowest j point
					if( (jStart-n) == jMin) {
						nBump = true;
							//System.out.println("Bump N");
					}
				} else {
						// we have reached the deepest j and are now going back
						// start decreasing after the buffer is gone
						if(nBuffer>0) {
							nBuffer--;
						} else {
							// The buffer is gone, start decreasing n each iteration
							n--;
							// check that n never exceeds its starting point
							if(n<nStart) n = nStart;
						}
					}
				
				// adjust m
				if(!mBump) {
					// we have not yet reached the HIGHEST j point
					// increasee m to go even higher next iteration
					m++;
					// Check if we have reached the highest j point
					if( (jStart+m) == jMax) {
						mBump = true;
							//System.out.println("Bump M");
					}
				} else {
						// we have reached the maximum j point
						// and are now moving back.
						// start decreasing m after the buffer is gone
						if(mBuffer>0) {
							mBuffer--;
						} else {
							// The Buffer is gone
							// decrease m each iteration
							m--;
							// check that m never exceeds its starting point
							if(m<mStart) m = mStart;
						}
					}
			}
		}
		
	}

Results in:

[theagentd]

I have a hard time debugging code for you in my head. Either do the debugging yourself or post something I can run.
EDIT: You should only have the paintAll calls in the inner loop. That is most likely your problem. You want to check for bouncing every y, not for every x.
EDIT2: To clarify:

    private int isoToI(int x, int y) {
        // converts world isometric coordinates into the i position of the 2D-Array
        return (((y / Tile_HH) + (x / Tile_HW)) / 2);
    }

    private int isoToJ(int x, int y) {
        // converts world isometric coordinates into the j position of the 2D-Array
        return (((y / Tile_HH) - (x / Tile_HW)) / 2);
    }

    public void paintScreen() {
        // Screen is a class that holds data
        // start position of the screen, and its width and height
        // paint only the isometric tiles within the canvas
        int iStart = isoToI(scr.x(), scr.y());
        int jStart = isoToJ(scr.x(), scr.y());
        int iMax = isoToI(scr.x() + scr.width(), scr.y() + scr.height()) + 1;
        int jMax = isoToJ(scr.x(), scr.y() + scr.height()) + 1;
        int jMin = isoToJ(scr.x() + scr.width(), scr.y());

        boolean nBump = false, mBump = false;
        int n = 1, nStart = 1, nBuffer = 1;
        int m = 1, mStart = 1, mBuffer = 1;

        for (int i = iStart; i < iMax; i++) {

            // Testing Purposes
            // Sleep 1 second each i iteration and paint the screen
            // TODO
            // .......


            for (int j = jStart - n; j < jStart + m; j++) {
                // paint the column
                colArray[ hWrap(i)][ vWrap(j)].paintAll(g);
            }
            // adjust m and n to keep us within the screen

            // adjust n
            if (!nBump) {
                //we have not yet reached the lowest j point
                // increment n to go even lower next iteration
                n++;
                // Check if we have reached the lowest j point
                if ((jStart - n) == jMin) {
                    nBump = true;
                    //System.out.println("Bump N");
                }
            } else {
                // we have reached the deepest j and are now going back
                // start decreasing after the buffer is gone
                if (nBuffer > 0) {
                    nBuffer--;
                } else {
                    // The buffer is gone, start decreasing n each iteration
                    n--;
                    // check that n never exceeds its starting point
                    if (n < nStart) {
                        n = nStart;
                    }
                }
            }

            // adjust m
            if (!mBump) {
                // we have not yet reached the HIGHEST j point
                // increasee m to go even higher next iteration
                m++;
                // Check if we have reached the highest j point
                if ((jStart + m) == jMax) {
                    mBump = true;
                    //System.out.println("Bump M");
                }
            } else {
                // we have reached the maximum j point
                // and are now moving back.
                // start decreasing m after the buffer is gone
                if (mBuffer > 0) {
                    mBuffer--;
                } else {
                    // The Buffer is gone
                    // decrease m each iteration
                    m--;
                    // check that m never exceeds its starting point
                    if (m < mStart) {
                        m = mStart;
                    }
                }
            }
        }
    }
}

[jonjava]

Duhh, of course! I even had the adjustments schedules for the outer loop in my picture, and even so I went head and included it inside the inner loop. Thanks! Your method works perfectly!

[EDIT]: I’ve no time now to clarify but it works quite flawlessy with a few tweaks - I’ll the solution more in depth tomorrow.

[theagentd]

Great that it works! I’m a little suspicious about the if(n < nStart) and the same for m, as that would possibly make it cut into to screen when you the screen scrolls to the edge of the map, but maybe I’m just being paranoid. If it proves to be a problem, move the bounds checking to the for(int j = …) loop and only loop through the tiles that actually exist. xD
I’m pretty sure that the direct algorithm I posted actually culls too much, so that you can see through the tiles near the screen edges. Either increase the screen size in all direction by half a tile or increase the size of the cull region when calculating iStart, jStart, e.t.c. Basically just decrease the minimums by 1 and increase the maximums by 1 (or 2 if it’s a length depending on the minimum).
Glad I could help! =D

[jonjava]

@theagentd

Great that it works! I’m a little suspicious about the if(n < nStart) and the same for m, as that would possibly make it cut into to screen when you the screen scrolls to the edge of the map, but maybe I’m just being paranoid. If it proves to be a problem, move the bounds checking to the for(int j = …) loop and only loop through the tiles that actually exist. xD
I’m pretty sure that the direct algorithm I posted actually culls too much, so that you can see through the tiles near the screen edges. Either increase the screen size in all direction by half a tile or increase the size of the cull region when calculating iStart, jStart, e.t.c. Basically just decrease the minimums by 1 and increase the maximums by 1 (or 2 if it’s a length depending on the minimum).
Glad I could help! =D

You have a good eye. What you point out is absolutely correct. Limiting n and m to not go below their starting point is stupid (as I learned through testing). It prevents the algorithm to work as inteded.

About culling too much, you’re correct, sort of. The algorithm works fine but as you said it culls a bit too much for the block to perfectly surround the screen. These are fixed by simple adjustments to the screen size or jStart,iStart, mBuffer, nBuffer values like you said.

It may not be obvious, but increasing the nBuffer by 1, adds a row of Tiles to the RIGHT side of the screen, and mBuffer similarly adds a row of Tiles BELOW the screen:

So the way I “got it just right” was by tweaking the iStart, jStart and n,m, mBuffer etc values:

		int iStart = isoToI(sx, sy) -1;
		int jStart = isoToJ(sx, sy);
		int iMax = isoToI(sx+sw, sy+sh) +1;
		int jMax = isoToJ(sx, sy+sh) +2;
		int jMin = isoToJ(sx+sw, sy);
		
		boolean nBump = false, mBump = false;
		int n = 0, nStart = 0, nBuffer = 1;
		int m = 1, mStart = 0, mBuffer = 0;

Now this is all fine and good. And we have now answered my original question. The correct Tiles are picked up from the 2D-Array to represent a screen in the isometric world.

Now that we know which tiles from the 2D-Array to use, we can paint them! This works fine if our screen x and y positions are 0. But when we start moving the screen around this happens:

1). The tiles move WITH the screen. It does what it’s supposed to do, because the screen position changes, so should the tiles used to represent the new position of the screen:

[SOLUTION]: If we want the visible screen/canvas to stay in place, we simply alter the horizontal and vertical offsets to cancel out the screens x and y position.( that we’re already familiar with from the OP ). I.e: horOffset = -screen.xPosition(); verOffset = -screen.yPosition();

So our paint method would look something like this

int horOff = screen.xPosition();
int verOff = screen.yPosition();
drawImage(sprite, isoX() - horOff, 
                            isoY() - verOff, null);

Here’s my finished code, the differences to the previous code are simple:

1. Close the inner loop before adjusting n and m;
2. remove the limitation of n and m going below their starting points
3. adjusting the starting position

	public void paintScreen(Graphics g, Screen scr) {
		// Screen is a class that holds data
		// start position of the screen, and its width and height
		// paint only the isometric tiles within the canvas
		
		// We need to even out the screen size to fit each isometric tile
		// to avoid small gaps
		int sx = scr.x();
		int sy = scr.y();
		int sw = scr.width();
		int sh = scr.height();
		
		int iStart = isoToI(sx, sy) -1;
		int jStart = isoToJ(sx, sy);
		int iMax = isoToI(sx+sw, sy+sh) +1;
		int jMax = isoToJ(sx, sy+sh) +2;
		int jMin = isoToJ(sx+sw, sy);
		
		boolean nBump = false, mBump = false;
		int n = 0, nStart = 0, nBuffer = 1;
		int m = 1, mStart = 0, mBuffer = 0;
		
		for(int i=iStart; i < iMax; i++) {
			for(int j=jStart-n; j < jStart+m; j++) {
				// paint the column
				colArray[ hWrap(i) ][ vWrap(j) ].paintAll(g);
			}
				// adjust m and n to keep us within the screen
				
				// adjust n
				if(!nBump) {
					//we have not yet reached the lowest j point
					// increment n to go even lower next iteration
					n++;
					// Check if we have reached the lowest j point
					if( (jStart-n) == jMin) {
						nBump = true;
							//System.out.println("Bump N");
					}
				} else {
						// we have reached the deepest j and are now going back
						// start decreasing after the buffer is gone
						if(nBuffer>0) {
							nBuffer--;
						} else {
							// The buffer is gone, start decreasing n each iteration
							n--;
						}
					}
				
				// adjust m
				if(!mBump) {
					// we have not yet reached the HIGHEST j point
					// increasee m to go even higher next iteration
					m++;
					// Check if we have reached the highest j point
					if( (jStart+m) == jMax) {
						mBump = true;
							//System.out.println("Bump M");
					}
				} else {
						// we have reached the maximum j point
						// and are now moving back.
						// start decreasing m after the buffer is gone
						if(mBuffer>0) {
							mBuffer--;
						} else {
							// The Buffer is gone
							// decrease m each iteration
							m--;
						}
					}
		} // for loop ends
		
	}// paintScreen() Method ends

[Demonpants]

Maybe it’s slower, but I’ve always just looped through the vertices of each space and any are onscreen then draw the whole diamond. Works fine.

[jonjava]

@Eli Delventhal

Maybe it’s slower, but I’ve always just looped through the vertices of each space and any are onscreen then draw the whole diamond. Works fine.

The vertices of each space… I’ve little to no clue what that means - English is my third language:(. Could you clarify what you mean? I’m very much interested in hearing about your method! Regardless if it’s slower, but especially if it turns out to be faster

[Demonpants]

Well, all my logic is stored as if there is a non-isometric grid, i.e. isometric transformations are only applied to what is drawn to the screen. To do so, you can loop through all points in your grid, and do the isometric transformation on each point. Then draw anything that is onscreen.

for (int i = 0; i < grid.length; i++)
{
    int x = i * GRID_SIZE;
    for (int j = 0; j < grid[0].length; j++)
    {
        int y = j * GRID_SIZE;
        Vector2 isometricTopLeft = translateToIsometric(x,y);
        Vector2 isometricTopRight = translateToIsometric(x + GRID_SIZE, y);
        Vector2 isometricBottomRight = translateToIsometric(x + GRID_SIZE, y + GRID_SIZE);
        Vector2 isometricBottomLeft = translateToIsometric(x, y + GRID_SIZE);

        if (pointIsOnScreen(isometricTopLeft) || pointIsOnScreen(isometricTopRight) || pointIsOnScreen(isometricBottomRight) || pointIsOnScreen(isometricBottomLeft))
        {
            drawQuad(isometricTopLeft, isometricTopRight, isometricBottomRight, isometricBottomLeft);
        }
    }
}

Granted that’s not exactly how I do it, but you should get the idea.

[theagentd]

That is really ineffective. The number of checks is equal to the number of tiles on the whole map. The algorithm I proposed only draws the visible tiles in constant time no matter how big the map is.

[Demonpants]

@theagentd

That is really ineffective. The number of checks is equal to the number of tiles on the whole map. The algorithm I proposed only draws the visible tiles in constant time no matter how big the map is.

Yes, I said it was less efficient. I do stuff like caching the isometric transformations and the like, and you just end up with a few cheap comparisons each render. It’s certainly simpler.

Come to think of it what makes more sense than that is just translating the screen corners from isometric space into grid space, then you exactly have the indices you need to draw. Maybe that’s what you guys are doing - I didn’t really look at the code.

[theagentd]

@Eli Delventhal

@theagentd

That is really ineffective. The number of checks is equal to the number of tiles on the whole map. The algorithm I proposed only draws the visible tiles in constant time no matter how big the map is.

Yes, I said it was less efficient. I do stuff like caching the isometric transformations and the like, and you just end up with a few cheap comparisons each render. It’s certainly simpler.

Come to think of it what makes more sense than that is just translating the screen corners from isometric space into grid space, then you exactly have the indices you need to draw. Maybe that’s what you guys are doing - I didn’t really look at the code.

That is exactly what we’re doing. POKE :yawn: :point:

[Demonpants]

@theagentd

@Eli Delventhal

@theagentd

That is really ineffective. The number of checks is equal to the number of tiles on the whole map. The algorithm I proposed only draws the visible tiles in constant time no matter how big the map is.

Yes, I said it was less efficient. I do stuff like caching the isometric transformations and the like, and you just end up with a few cheap comparisons each render. It’s certainly simpler.

Come to think of it what makes more sense than that is just translating the screen corners from isometric space into grid space, then you exactly have the indices you need to draw. Maybe that’s what you guys are doing - I didn’t really look at the code.

That is exactly what we’re doing. POKE :yawn: :point:

Lawl well good on you.

[jonjava]

[quote=“Eli Delventhal,post:14,topic:37375”]
Hmmm. I use a method to calculate the Isometric X and Y position based on the 2D-Array every single time each tile is painted on the screen. Saves loads of computational power to simply have 2 additional values to store the Isometric x and y positions and only recalculate if it changes/movement occurs.

Seems so trivial and yet I’d overlooked it, thanks for pointing that out

And what you said about about only “painting” the tiles so they look isometric and in reality they’re stored in a 2D-Array is precisely what I was trying to convey in the pictures and explanation in the beginning of my OP. I do realise, however, that this topic is a huge pile of TL;DR wall of texty mess. But I learned a lot trying to explain my thoughts in these posts so I don’t mind.^^

[Demonpants]

Cool, glad I helped a little bit, at least.

Also glad that laying your thoughts out here (seriously, this is the most detailed thought laying I have ever seen on JGO :)) helped you figure things out.