LibGDX Only rendering part of map that's on screen not working

Newbie & Debugging Questions
#1

Hi guys,

So i’m trying to implement a really big, randomly generated tile map which supports negative coordinates in my game.
I’ve decided to use a hashmap for this.

private HashMap<Vector2, TiledMapTileLayer.Cell> worldHashMap;

The Vector stores the x and y coordinate of the tile, and the cell stores the tile.
This all works fine.

Drawing the world also works well

public void drawWorld(Batch batch){
        batch.begin();

        for(Map.Entry<Vector2, TiledMapTileLayer.Cell> entry: worldHashMap.entrySet()){
            Vector2 v2World = entry.getKey();
            TiledMapTileLayer.Cell cellWorld = entry.getValue();
            
            batch.draw(cellWorld.getTile().getTextureRegion(), v2World.x * cellWorld.getTile().getTextureRegion().getRegionWidth(), v2World.y * cellWorld.getTile().getTextureRegion().getRegionHeight());
        }
        batch.end();
    }

The problem is that the bigger the world gets, the more tiles it’s trying to render at once. With only 2500 Tiled this works fine, but with 250000 I’m down to 5 FPS. I think the problem is it’s also trying to render all the tiles that aren’t on screen.

So I’ve been trying to get it to only draw the tiles which are visible.

This is the best code I’ve come up with

    public void drawWorld(Batch batch){
        batch.begin();

        for(Map.Entry<Vector2, TiledMapTileLayer.Cell> entry: worldHashMap.entrySet()){
            Vector2 v2World = entry.getKey();
            TiledMapTileLayer.Cell cellWorld = entry.getValue();

            //Check if the bottom left corner of the tile is to the right of the left most part of the screen plus an additional length of the tile & if it's past the right edge of the screen
            if((v2World.x > camera.position.x - camera.viewportWidth / 2 - cellWorld.getTile().getTextureRegion().getRegionWidth()) && (v2World.x < camera.position.x + camera.viewportWidth / 2)) {
                //Same for top and bottom of the screen.
                if (v2World.y > camera.position.y - camera.viewportHeight / 2 - cellWorld.getTile().getTextureRegion().getRegionHeight() && (v2World.y < camera.position.y + camera.viewportHeight / 2)) {
                    batch.draw(cellWorld.getTile().getTextureRegion(), v2World.x * cellWorld.getTile().getTextureRegion().getRegionWidth(), v2World.y * cellWorld.getTile().getTextureRegion().getRegionHeight());
                }
            }

        }
        batch.end();
    }

First of all, the code doesn’t really work. When I spawn my player at (0|0) of the world (the camera follows the player), everything around him is rendered properly. But as soon as I move a bit in any direction, the tiles stop rendering.

The second problem is that as soon as I increase the amount of tiles in the world the FPS drops dramaticlly, even though (i think) the tiles off screen arent’t rendered.

I’m assuming this has to to with the fact that I’m calling the drawWorld 60 times a second, and each times it’s call it iterates through 250000 entries in my Hashmap, which is way too much.

Can someone tell me what I’m doing wrong or maybe have an idea of how I can solve this issue in a better/more elegant way?

#2

I’m not going to try debug that code to see if anything is wrong, but here are some points you should consider.

  1. The overhead of using a HashMap for storing that many tiles, and iterating through them is going to be non-negligible. Positions and tiles have a 1:1 mapping, if you used a regular array, the look up would be done instantly. Depending on the capacity of your HashMap, you could be potentially doing thousands of iterations for each tile you want to find. You may want to look at how hash maps work.

  2. Checking if a tile is inside your view is expensive, it’s a lot of branching, extra variable look ups, and additional code to process, for so many iterations. Most importantly, it’s also redundant. Instead you store the range of tiles that you want to draw, which is a simple calculation from your camera position and size, and iterate over that range.

You might find some further information or understanding here: http://www.java-gaming.org/topics/strategies-for-handling-large-tile-maps/35525/msg/336652/view.html#msg336652, and also here: http://www.java-gaming.org/topics/2d-libgdx-drawing-only-what-camera-sees/35702/msg/338540/view.html#msg338540.

There are plenty of additional optimizations you can do, but the above two are big and easily fixable ones. :slight_smile:

#3

You have to, of course, only draw what is in sight.

For instance, if you want to draw 20x20 tiles, centered on player, and player position is tile x,y, you have to make two nested for-loops, and draw tiles from x-10,y-10 to x+10,y+10.

Once I’m home and have access to keyboard, I’ll give you some sample code.

#4

I would advise you to not use a datastructure like an hashmap, it is great for things that are not sorted or do not have sortable keys.

Instead, you could split your world in chunks, of which each holds an array of elements, this allows you to access the tiles without overhead, just by using the tiles coordinate to retrieve it from the array.

You can load and unload these chunks while playing and also you can just pick the tiles you need from the arrays inside the chunks.

This should make your game a lot faster.

Ps: to slow, already two answers :smiley:

#5

Thank you guys for your answers! :slight_smile:

@Husk:
Your’re right, I barely know anything about HashMaps as I’ve never used them before, but from the reading I’ve done on them they seem to be a pretty good option. The problem with a rectangular array would be the for one, I couldn’t have negative coordinates in them. Storing the range seems like a very good idea, thank you :slight_smile:

@DavidBVal:
This is kind of what I was trying to do :clue:. But instead of only iterating through the tiles from (like in your example) x-10,y-10 to x+10,y+10, I was iterating through all the tiles and checking if they are in that range. Is there a way to directly get the entries from the map at a given postition, or would I need to convert this to an array to do this?

@VaTTeRGeR:
Thank you for this approach, it sound very good :slight_smile:
How would you go about storing the chucks then? Say i want to procedurally add new chunks if the player reaches an area where no chuncks have been generated. What would I add them to? An ArrayList?

#6

[quote=“TheLopais,post:5,topic:54443”]
Not at all. :wink:

Say your map goes from coordinates (-25, -25) to (25, 25), we simply need to have an array of [51][51] (50, +1 because of 0). When we want to get a tile out of our array, we simply do array[x + 25][y + 25], which will get the value at a positive index, and the correct value.

#7

[quote=“Husk,post:6,topic:54443”]

I see. But would this also work if I don’t know how big the map is going to be yet? I’d like to have the map expand dynamicly, sort of like in minecraft.

#8

Yep, it’ll work great. You don’t even have to resize the array if you’re worried about that. You simply want your array to be big enough to store all the tiles that the player can see, and all the surrounding tiles if he were to move one screen left, or up, etc. You could do this by implementing a chunk system like VaTTeRGeR suggested, or by calculating what tiles are, and would be visible. When the player moves over right one screen for example, you move all the data left (or preferably use a circular buffer), and load in the new data to the right.

#9

This sound like a very good solution, thank you :slight_smile:

The only thing I’m unclear about is how I would store the tiles(or chunks) that are not stored in the buffer at the moment, so I can retrieve them easily when the player moves to a location which is not in the buffer, but has already been generated already.

#10

Well I was going to let VaTTeRGeR get to that, but he’s not here now, so I’m up. :stuck_out_tongue:

Ultimately, if you have data that is not in memory, then it will have to be loaded from disk (or some non memory location), or generated at runtime.

In the case of a tilemap, if you intend to keep everything in memory, then you only need to perform your operations on the buffer containing all your tiles. You don’t need a separate buffer for what the nearby visible tiles are.

If you want to store data on disk until it’s needed, which I’d suggest if you’re data is going to be millions of blocks big, then it’s just a matter of loading that data from disk and writing it in to the buffer containing the tiles you can see, when needed. This applies if you want to generate data at run time too.

#11

Thank you very much for your help! :point:

I’ve learnt alot :slight_smile:

I know this is getting very off topic, but do you have any suggestions on how I should organize the chunks on disk?

Would an approach like the following be a good way to go?

X row 3:
   Y row -3
   Y row -2
   Y row -1
   Y row 0
   Y row 1
   Y row 2
   Y row 3
X row 2:
   Y row -3
   Y row -2
   Y row -1
   Y row 0
   Y row 1
   Y row 2
   Y row 3
X row 1:
   Y row -3
   Y row -2
   Y row -1
   Y row 0
   Y row 1
   Y row 2
   Y row 3
...

With each row being its own folder that stores the serialized chunk?

#12

That would be sufficient, it will allow you to index directly to the bytes you need. There’s certainly different ways you could go about it of course. Personally I’d probably make sure than any chunk would be contiguous in the file so I can read it in one hit.

File structure would be like:

ChunkX1Y1->ChunkX2Y1->
ChunkX1Y2->ChunkX2Y2

Each chunk would then store it’s column and rows like you shown above.

It’s also feasible to break your data up in to multiple files. Optimization is largely a big game of compromises, and only by knowing how your application will be used can you make the appropriate, or best, compromises. I’d suggest just doing whatever you can make work for now, and abstract that away in to some method. When you want to improve it, you only have to change that one method. :slight_smile: