Fast way of rendering Tiles.

Newbie & Debugging Questions
#1

Hello there again JGO,

Currently I am working on an infinite map-generator, or atleast trying to. But evrytime I want to test/try something it will take a BIG, I mean a very BIG part of the CPU :/. I am without my code running on 60 ticks, 200 frames, but with the infinite Tile-rendering codes it is going to be 60ticks, 39frames (And this is with almost no tiles, around 200, while I was running the old code 50*50 tiles = 2500tiles…) My rendering code is just a simple arrayList with some if’s and looping throught all the tiles :confused: not the greates… while my other code was just searching for that tile and not looping over the arrayList like 1000times more then is needed…

    	for (LevelTile t : tiles) {
	     	if(t.y >=  (yOffset >> 3) && t.y  <= (yOffset + screen.height >> 3) + 1){
	     		if(t.x >= (xOffset >> 3) && t.x <=  (xOffset + screen.width >> 3) + 1){
	     			t.render(screen, this);
	        	}
	        }
    	}

Is there a way for searching x’s and y’s better then this? Like:

    	for (int y = (yOffset >> 3); y < (yOffset + screen.height >> 3) + 1; y++) {
        	for (int x = (xOffset >> 3); x < (xOffset + screen.width >> 3) + 1; y++) {
        		//Searching in the ArrayList tiles to x and y and then just .render(); it
        	}
    	}

Is the example possible? Or another solution? Just say it!
-RoseSlayer, and yes I didn’t found anthing on java.docs

#2

If you are doing tile-based rendering I would suggest using an Array instead of an ArrayList. That way you can access the tiles via an index and do not have to loop through every single one of them, Just the ones that are currently visible on the screen.

#3

I suggest while you are working on the map generator you immediately set it up to seperate your map into chunks/rooms.


Chunk[][] chunks; // Your World / Level / Map
Tile[][] tiles; // One Room/Chunk of the Map

First you would need to check in which chunk you are:


int currentChunkLeftX = (int) playerPositionInWorld / MAP.CHUNK_WIDTH // Do this for all 4 edges of your camera. You might be in 2 chunks at the same time.

For each chunk you are in you calculate the 4 edges again (yTop, yBottom, xLeft, xRight) and only render the part visible for the user


foreach chunk you are in do:
    for(int x = leftEdgeX - 1; x < rightEdgeX + 1; x++{
        for(int y = bottomEdgeY; y < topEdgeY; y++ {
           tiles[x][y].render();
        }
    }
}

As Gjallar stated this will save you a lot of computation time ( O(n) versus O(x) where x = numberOfVisibleTilesToRender)

#4

The simple answer is to store the tiles in a data structure which enables you to query specific regions.

If you have a static World(fixed size) you could store the tiles in an array like Gjallar suggests. While rendering you could calculate the array indices which hold tiles which are in view.

In your case it seems that you have a dynamic world, means you stream the world content in some way. My suggestion would be to load the world into chunks which are hold in a simple data structure like an array. So for example you could have always nine chunks in memory, where the chunks are located like this:

x x x
x v x
x x x

When the view moves out of the center chunk deallocate the more far away chunks and load new chunks which are in the direction of where the view is going. With this system you only iterate over all active chunks and for each chunk you can quickly access the needed tiles.

->
d x x a
d v v a
d x x a

#5

I tried to make Chunks with fixed Tile Arrays, and so far so good. I’ve added alot of code that should work fine etc. but I can’t seem to make this part correct (if the chunk excist and must be loaded):

boolean loaded = false;
		try {
			FileInputStream loadFile = new FileInputStream(levelDirectory + "/chunks/chunk[" + x + "," + y + "].dat");
			ObjectInputStream load = new ObjectInputStream(loadFile);
			this.tiles = (LevelTile[][]) load.readObject();
			load.close();
			loaded = true;
		} catch (Exception e) {
			e.printStackTrace();
		}
		if(!loaded)
			generateChunk();

[edit]
It is now working correctly! The only thing I don’t know how to do is creating a new chunk if he is not in the ChunksList.

        if(currentViewedChunkX != viewedChunkX || currentViewedChunkY != viewedChunkY){
        	chunksOpen.clear();
        	for(Chunks c: chunksList){
        		if(c.x >= currentViewedChunkX - 1 && c.x <= currentViewedChunkX + 1){
            		if(c.y >= currentViewedChunkY - 1 && c.y <= currentViewedChunkY + 1){
            			chunksOpen.add(c); //So if this one doesn't excist it needs to create a new Chunk, but because it is a forloop the not-excisted coords won't come here....
            		}
        		}
        	}
        	viewedChunkX = currentViewedChunkX;
        	viewedChunkY = currentViewedChunkY;
        }

[edit]
Found a simple solution that doesn’t seems to work:

for(int x = cx - 1; x <= cx + 1; x++){
        	for(int y = cy - 1; y <= cy + 1; y++){
        		boolean opened = false;
        		for(Chunks c : chunksOpen){
        			if(c.x == x && c.y == y){
        				opened = true;
        				break;
        			}
        		}
        		if(!opened)
        			createChunk(x, y);
        	}
    	}

It is drawing more then 9 at the time, don’t know how that is even possible but yeah…

    	System.out.println(chunksOpen.size());
        screen.setOffset(xOffset, yOffset);
        int currentViewedChunkX = (((screen.xOffset + 4 + screen.width/2)>>3)>>4);
        int currentViewedChunkY = (((screen.yOffset + 4 + screen.height/2)>>3)>>4);
        if(currentViewedChunkX != viewedChunkX || currentViewedChunkY != viewedChunkY){
        	chunksOpen.clear();
        	for(Chunks c: chunksList){
        		if(c.x >= currentViewedChunkX - 1 && c.x <= currentViewedChunkX + 1){
            		if(c.y >= currentViewedChunkY - 1 && c.y <= currentViewedChunkY + 1){
            			chunksOpen.add(c);
            		}
        		}
        	}
        	if(chunksOpen.size() != 9)
        		generateNewChunks(currentViewedChunkX, currentViewedChunkY);
        	viewedChunkX = currentViewedChunkX;
        	viewedChunkY = currentViewedChunkY;
        }
        
        for(Chunks c: chunksOpen){
        	c.render(screen);
        }

[edit]
The only thing I needed to do was after creating new chunks, adding them to the chunksOpen ArrayList… Thanks for all the help!

-RoseSlayer

#6

I dont quite understand your problem. When you scroll and need a new chunk, look up your chunks that you stored in a file and load them from there, and if no chunk exists in the file, create a new chunk, fill it, add it to the open list and then hen it disappears off the screen, remove it from the list and write it to your hard drive.

#7

What about using a Grid for tiles?


Grid tiles = new Grid(TILE_SIZE * numTilesX, TILE_SIZE * numTilesY, TILE_SIZE);
tiles.insert(tilesList);

And to get the tiles visible, you need a screen rectangle.


Rectangle SCREEN = new Rectangle(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);

You need to update this rectangle every time the view changes. So when updating,


SCREEN.x = -offSetX;
SCREEN.y = -offSetY;

Now draw everything which are likely to be collided with the screen rectangle.


List<Tile> visible = tiles.retrieve(SCREEN);

for (Tile t: visible)
{
    t.render();
}

This is what I use. Hope it helps.

#8

But if there are entities outside a chunk, that I want to use all have the methode tick() in them. And if I don’t render that Chunk it will not “tick” correctly as there is nothing out there… Do I need to open that chunks aswell? and if I have a minimap, it needs to find also the chunks outside the rendered chunks?

    public Tile getTile(int x, int y) {
    	int chunkX = x >> 4;
	    int chunkY = y >> 4;
	    for(Chunks c : chunksOpen)
	    	if(c.x == chunkX && c.y == chunkY)
	    		return c.getTile(x - chunkX*16, y - chunkY*16);
	    for(Chunks c : chunksList)
	    	if(c.x == chunkX && c.y == chunkY)
	    		return c.getTile(x - chunkX*16, y - chunkY*16);
    	return Tile.VOID;
    }

That’s a very good idea! I honestly forgot about grids (I thaught grids are also fixes size?). and using a rectangle is a good idea, but I think I prefer the forloop to do it… I also don’t know what is faster.

public void render(Screen screen){
    	for(int y = 0; y < 16; y++){
    		if(y + this.y * 16 >= (screen.yOffset >> 3) && y + this.y * 16 <= (screen.yOffset + screen.height >> 3) + 1){
    	    	for(int x = 0; x < 16; x++){
    	    		if(x + this.x * 16 >= (screen.xOffset >> 3) && x + this.x * 16 <= (screen.xOffset + screen.width >> 3) + 1){
    	        		tiles[x][y].render(screen, level);
    	    		}
    	    	}
    		} 		
    	}
    }

Thanks for all the help!
-RoseSlayer