# Most efficient way of looping trough a sprite grid

This topic is 947 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm currently making a game (or, trying to) that has a grid layout, pretty much like this :

Where each square represents a sprite.

The current way I'm doing it is to store the map inside of a std::vector, so I can modify values on each sprite, using it's index.

When I want to modify, or check collision on each sprite I loop trough every single one checking if the mouse is inside a sprite.

However, this results in really long delays when my mouse is on the bottom right corner sprite, since it has to loop trough every single sprite before reaching the one the mouse is actually on.

My final question is, how to make this task faster?

##### Share on other sites

As a side note to Sponji's excellent answer: you can easily create an inline function or method, or macro even to perform the index calculations for you. Rather than calculating an index all the time you can just call a method with the, usually, calculated x and y coordinates.

##### Share on other sites

If the grid is regular (each cell has the same size), you know the position of the top-left corner, and the position of the mouse, you can just compute the row and column:

column = int((mouse.x - topleft.x) / cell.xsize)
row    = int((mouse.y - topleft.y) / cell.ysize)

Compute how many pixels there are between the top-left and the mouse, in both positions, divide by the size of a grid cel, and round down to an integer value.

The index in your vector can be computed with the algorithm by Sponji

##### Share on other sites
A secondary approach I recommend is to break up your tile map into a grid of _chunks_, where each chunk is a 2d tile array similar to what you already have.

This has several benefits. Resizing your world is easier, baking tilemaps into cullable geometry is easier, memory locality tends to be greatly improved for many operations, etc.

Aside from that, take the mouse coordinate projection as far as you can. For instance, I often see code like this in rendering (presented in pseudo-code):

for y = 0 .. height
for x = 0 .. width
if x,y is visible
draw tile at x,y

That loops over every single tile to determine if it's visible. If you can only see a 20x15 area of the game but you have 1000x1000 map, you're going to be a very unhappy camper. Using projection, you can narrow down your search:

upper left = project camera -1,-1
bottom right = project camera +1,+1

for y = top .. bottom
for x = left .. right
draw tile at x,y

And now you're looping over just the visible tiles. You'll have to slightly tweak the loop bounds a bit to deal with partially-visible tiles if your game scrolls smoothly, but that's the gist of it.

With the previously-mentioned chunk approach, you'd do the same thing at the chunk level instead of the tile level. Each chunk can have its geometry and UV coordinates baked to give you a single draw call per chunk (so instead of a 20x15 viewport requiring 300 draw calls, with 10x10 chunks it might require at most 12, which is a pretty nice improvement and will very quickly become worth it if you do a lot of layering).

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633705
• Total Posts
3013463
×