In the tile based game I am making I sometimes need to update several tiles at once. Since I keep my world in a 2D tile array, I can't seem to find a good way to update the specific tiles I want updated.

An example:

When grass grows, I periodically need to check if it is time for it to grow. Since there are a lot of dirt tiles, there will be a lot of dirt tiles to go through. When searching for dirt tiles that needs to be updated, I search from top to bottom, until I hit a dirt tile, which needs to be updated. The part that gets taxing, is that since I don't necessarily know which tiles need updating, I have to iterate through a lot of them (Or at least all withing my Update Radius). Since the player can change the world, the tiles to be updated can change very quickly. I have considered adding the reference variables to a list, and then update the tiles on the list. But since the list can become quite long fast, I'm worried that I might be spending too many resources.

Solutions I've thought about:

- The first one is more or less just brute force. Periodically I iterate through the tiles within my Update radius, and update them. I've done this and sometimes this causes a lag for a second or so when the updates are applied- So this is not a good solution.

- Every time I draw my world, I iterate through a lot of tiles (those within my Draw radius). I was thinking about simply doing the tile updates there, since I already have an iteration going. I am pretty sure this is bad practice, and I know that Draw is potentially called fewer times than update, so I dropped the idea.

- The list idea I mentioned earlier, where I add tiles that needs to be updated to a list, and iterate through that list periodically. The problems I see with this method is that I still need to figure out which tiles to put on the list, which means I need to check for that every time the world changes somewhere. Another problem I see is if the list is getting too big. I don't think memory will be a big issue, but updating potentially thousands of tiles at once, will cause huge slowdowns. A fix could be to look at the list more often, and only update small parts of it- Like a queue system.

So my question is: What would be a good way to update "random" tiles in a 2D array?

Thanks for reading

Add more dynamic things - water, ice, fire, crawling goo of dynamicismism - so you dont feel bad for looping through everything

Lets say by average grass needs to be updated every 4 mins.

You could do this:

Have different containers for grass tiles, 4 mins, 2 mins, 1 min, 30 sec... and so on (stop at some point)

After update of a tile, it goes to 4 min container with (4 + time since 4 min container was last updated) minutes of time.

When you update a container (tiles only updated when they reach 0 time!), you reduce the time of the below container (2 mins for 4 min container) from each tile in it, and move it to the container below.

4 min container could be the world. Everything else could be a list of tiles. That means you loop thru the world every 2 mins.

The last container needs to be checked at whatever update resolution you want (every 1 second, every 15 second...)

something like

a) World (4 min) (half of all tiles here)

b) List (2 min) (fourth of all tiles here)

c) List (1 min) (eighth of all tiles here)

d) List (30 secs) (eighth of all tiles here) --check this lets say every 5 secs, reducing 5 sec from everything. If something goes below 0, (lets say -3), you add it to the 4 min container with time (4 minutes - that 3 seconds + time since last time the 4 min container was updated)

*might contain logical errors*

That seems somewhat reasonable at least. You can vary the amount of the containers. I would keep times half of the above time, seems optimal. Now, if you have a resolution of 5 secs, instead of updating ALL tiles by looping thru the whole world every 5 secs, you can loop thru the world every 2 minutes, and loop thru only a small part of the tiles every 5 secs.

If someone understand this, please come up with an O() thingy because it looks like it contains a log or something else cool.

EDIT:

Wait this doesnt make any sense. Forget all about moving tiles back to the 4 min container, unless they happen to die and start growing again :P

Several points may help you to cope with your problem.

1. divide your map in several cluster/quadtrees, and process one or a few cluster at a time
2. have a queue for each processing, to hopefully avoid scanning each of your tile. Remove the processed tile from the queue. If a tile need constant processing, it should reapply to the queue
3. Avoid having to change lots of tile at the same time. In your case of the grass, shift the growth cycle for each tile so that if you have N tiles for grass, you have to update, say, N/8 tiles at each run of the loop

To sum up, divide and conquer...

Or you could simply store the time when the grass was created, and deduce the growth/age from that using the current time.

If you do some action on the tile that affects its growth you might want to reset its age and set its growth to what it was + the effect.

So:

T (age=5, lastGrowth=0)

*hit grass*

T (age=0, lastGrowth=5) //what the growth would be after age 5

T (age=0, lastGrowth=4) //reduce effect of hit

*time passes*

T (age=1, lastGrowth=4)

EDIT:

nowait, age should be "created", holding the game time at the time of the last update of the grass tile.

Thanks a lot for all the replies

I already noticed one flaw in the way I update things. Instead of just changing a value when the grass is growing, I am actually creating a whole new instance of that specific tile. There's absolutely no reason for that, and I am pretty sure creating loads of new instances in one update cycle causes problems.

You could do this:

Have different containers for grass tiles, 4 mins, 2 mins, 1 min, 30 sec... and so on (stop at some point)

After update of a tile, it goes to 4 min container with (4 + time since 4 min container was last updated) minutes of time.

When you update a container (tiles only updated when they reach 0 time!), you reduce the time of the below container (2 mins for 4 min container) from each tile in it, and move it to the container below.

4 min container could be the world. Everything else could be a list of tiles. That means you loop thru the world every 2 mins.

The last container needs to be checked at whatever update resolution you want (every 1 second, every 15 second...)

something like

a) World (4 min) (half of all tiles here)

b) List (2 min) (fourth of all tiles here)

c) List (1 min) (eighth of all tiles here)

d) List (30 secs) (eighth of all tiles here) --check this lets say every 5 secs, reducing 5 sec from everything. If something goes below 0, (lets say -3), you add it to the 4 min container with time (4 minutes - that 3 seconds + time since last time the 4 min container was updated)

I like the idea. I wasn't actually considering updating the entire world, only within my update radius. Doing this might very well make it possible though.

Thanks for the input

Computers are quite good at doing repetitive tasks In our game, we use a component system, and we can have a lot of components in a scene - updating usually takes negligible time, as long as you avoid doing stupid thigs (and do profile the code when you see it's slow). For compute-intesive tasks (like texture generation), parallelizing the code can dramataically speed it up.

What I'm saying is that you can simply go and update everything. Let every component know when it should and when it shouldn't update (either determining it interally, or by sending a message when it goes out of scope - e.g. Enabled/Visible properties). Alternatively, you can maintain a list of components that need to be updated. Don't worry - in C# references are more or less just pointers, so having lists of components that live in memory anyway won't take all that much memory... you'll end with lists of pointers, not duplicated objects.

You will have to have a list of components.. I'd rather use some sort of composition (component on top of component whose job is to randomly update its child component), as it is more flexible... and in time can allow you to do complex things with very little code.

I think I do obsess about performance lately. I haven't had the chance to test my game any other computers than my own, and a very old laptop. The laptop can't run the game very well, I do believe that it is because of my lighting, which is rather CPU intensive.

Currently the way I handle updates, is simply by iterating all the tiles within a certain distance from the player, and change the tiles accordingly. I am not happy with that approach though, since all dirt tiles within range will grow grass every time I run the update.

I always wondered what the difference is between references and pointers. I never did much C++, but I did learn that pointers was the force of C++, which had be wondered what the difference between those two were. It's nice to know that they're similar at least. - Thanks for your input

Several points may help you to cope with your problem.

1. divide your map in several cluster/quadtrees, and process one or a few cluster at a time
2. have a queue for each processing, to hopefully avoid scanning each of your tile. Remove the processed tile from the queue. If a tile need constant processing, it should reapply to the queue
3. Avoid having to change lots of tile at the same time. In your case of the grass, shift the growth cycle for each tile so that if you have N tiles for grass, you have to update, say, N/8 tiles at each run of the loop

To sum up, divide and conquer...

After reading all these posts, I think I've decided on a queue system, as you suggested. I was thinking of keeping it all in one big queue (List) and then at certain intervals (maybe random) I update a certain amounts of tiles on the list, and remove them, if no more updates are required, or move them to the bottom of the queue.

This will also be very useful for plants, and farm objects that I am adding to the game soon. Also when winter is over, I can use this to melt the snow over time.

I really appreciate all the input I got from you guys

Thanks a lot!

Its odd that you have such a performance hit for so few updates. I would say its likely that you're doing much more work per update than you should be, perhaps unintentionally, as you've already found, or that you're not iterating in a way that's cache friendly.

For the cache issue, its a common mistake to allocate an array like so: int tiles[x][y], which will completely blow out your cache if you then iterate over it with a nested loop where the outer loop moves in y. Make sure you're not doing that, instead allocate instead like so: int tiles[y][x], or swap the nesting order of the iteration, though that might be less natural to think about.

Out of curiosity, when you update these tiles, is that process entirely self-contained, or are you touching other memory to compute the change? Neighboring tiles, perhaps?

In general, though, the approach I'd take is to either do some kind of update/processing on the majority of tiles (so that touching each memory location through iteration is not wasted), or if tiles that need updates are sparse, maintain a list of them and run through the list to update them, rather than the array.