Culling offscreen tiles in an Isometric engine

Question

For a university term project, I'm working on a graphical roguelike (I'm aware of the contradiction in terms :P) that uses an isometric display. What I'm trying to figure out is, since drawing all the tiles is stupidly expensive and unnecessary, I'm wanting to figure out a relatively fast algorithm to determine which tiles should be drawn to fit within an NxMpx window, given that the tile graphics are XxYpx.

I'm not doing smooth scrolling for this, so that's not an issue. I'm also not worried about being perfect - a little unnecessary draw is fine, I just don't want to draw a huge amount of unnecessary tiles that won't show up in-game.

Answer 1

You need to think about two concepts: Screen space and world space. These are very important in 3d engines, but they apply to all but the very simplest games. In the isometric engine your world-space is a 2d array of tiles.

So you are looking first of all at a way to covert between these two co-ordinate spaces. Once you've done that, it'll be obvious that screen space maps onto the world as a rectange that's turned at 45 degrees. You can determine a formula for that, but it's only important if you are trying to determine which part of the world space is visible so you only simulate monsters in that area (an efficiency necessary on 8 bit consoles, probably not on a modern PC!). When it comes to actual rendering you don't really need to determine this visible region of the world, because it's implicit in the way you render the tiles onto the screen:-

1. You work out which tile location is at the top-left of the screen, call this O (for origin) - that's going to be a fixed offset from your point of interest, usually the player, that you want to keep in the centre of the screen.
2. Once you have that you paint the tiles in the top row of the screen, stepping +1X and -1Y in world space for each tile (if you are looking north-east).
3. Then you paint the row below. That is offset minus one half a tile width in screen space and starts at O -1X in world space.
4. You repeat steps 2 and 3, modifying your starting position in world space by -1 in X and Y from what you used in the previous stage 2 until you reach the top of the screen.

Other tips:-

• Obviously you don't draw any tiles that are outside the map. You might also, depending on game design, not draw any tiles outside a particular room the player is in.
• There's not just floor tiles to draw, theres also players, monsters, scenary, etc. The rule is you draw everything in a paricular world location in the same pass. That way objects closest to the 'camera' will obscure stuff behind them (which is why you start drawing at the top of the screen).
• Also, you don't just have floor tiles in most iso engines, you would also have furniture and wall segments. You might designate areas of the map as belonging to a particular room, when the focus is on that room (because the player is in it for example), you don't draw the wall segments for the side of the room closest to the camera.

Anyway, that's enough to be getting on with, hope it's helpful and your project goes well.