Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


How to update a lot of random tiles in a 2D array?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 Mekuri   Members   -  Reputation: 300

Like
1Likes
Like

Posted 28 March 2013 - 03:20 AM

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 smile.png


Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


Sponsor:

#2 Ravnock   Members   -  Reputation: 289

Like
0Likes
Like

Posted 28 March 2013 - 03:55 AM

Hi Mekuri

 

I don't understand why do you want to update only some random tiles, but this could be what you want:

 

int numTilesToUpdate = ...;

 

for (int i=0; i < numTilesToUpdate; i++)

{

    m_Tiles[rand()%m_Tiles.size()].Update;

}



#3 dilyan_rusev   Members   -  Reputation: 1035

Like
1Likes
Like

Posted 28 March 2013 - 05:02 AM

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.



#4 Waterlimon   Crossbones+   -  Reputation: 2598

Like
1Likes
Like

Posted 28 March 2013 - 06:00 AM

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

 

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


Edited by Waterlimon, 28 March 2013 - 07:55 AM.

o3o


#5 Sporniket   Members   -  Reputation: 344

Like
2Likes
Like

Posted 28 March 2013 - 06:37 AM

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...


Space Zig-Zag, a casual game of skill for Android by Sporniket-Studio.com


#6 Waterlimon   Crossbones+   -  Reputation: 2598

Like
2Likes
Like

Posted 28 March 2013 - 07:54 AM

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.


Edited by Waterlimon, 29 March 2013 - 03:58 AM.

o3o


#7 Lightness1024   Members   -  Reputation: 737

Like
1Likes
Like

Posted 28 March 2013 - 09:27 AM

it is far from being natural that update some thousands stuffs takes that long.

In extreme carnage I'm updating the IA of 2000 to 3000 enemies that are stored in a linked list (not the fastest thing to iterate on...) and doing lots of ray casts in each of them, and it runs in real time (> 60 FPS).

Stronger even : Intel Ray Tracing Library, or many indie demos (on cpu) are able to cast millions of rays per second and 1 cast is much heavier than update a sprite id.

So definitely, you have a bug. what is the language ? do you not have a garbage collection issue rather than a looping issue ? can you run on MacOS ? if yes use the built in instruments profiler. Or valgrind + cachegrind on linux. Or Vtune, or AMD code analyst on windows.



#8 Mekuri   Members   -  Reputation: 300

Like
0Likes
Like

Posted 28 March 2013 - 12:25 PM

Thanks a lot for all the replies smile.png

 

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 smile.png

 

Computers are quite good at doing repetitive tasks smile.png 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 smile.png

 

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 smile.png

 

Thanks a lot!


Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri


#9 dilyan_rusev   Members   -  Reputation: 1035

Like
1Likes
Like

Posted 28 March 2013 - 03:54 PM

In C++, pointer is the same as reference, with some enforced-by-compiler restrictions. In C#/Java, references are pointeres again, with the added caveat that the VM can rearrange the memory (i.e. move your pointer to another location). The difference shouldn't matter for most programs. And you can use raw pointers in C#, and you can pin them so that the VM can't move them, but it's not recommended unless you're doing some interop. Hope that clarification was helpful :)

 



#10 Ravyne   GDNet+   -  Reputation: 7743

Like
1Likes
Like

Posted 28 March 2013 - 07:15 PM

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.



#11 snowmanZOMG   Members   -  Reputation: 889

Like
1Likes
Like

Posted 28 March 2013 - 11:55 PM

You haven't provided nearly enough detail about your problem to really get at the potential problems.  Based on what I've read you may have one or more of the following problems (among others which may not be listed here):

  1. Bad algorithm.
  2. Poor memory access patterns.
  3. Bad memory allocation and usage causing excess garbage collection pressure.

Updating only tiles within your "update radius" should be very fast unless your radius is so large, that it contains the entire map.  Even then, you'd have to have a colossal map to have it take enough time to notice a really long pause (~1 second or more).  How are you determining which tiles are in your "update radius"?

 

Maintaining homogeneous lists of each tile type could be advantageous, but you pay for it with memory.  Suppose you put each type of tile in its own list and each list element points directly to the actual tile in your grid.  This gives you the advantage of not having to search the entire grid for all elements of a certain type.  But you're paying for this advantage in speed (by not having to search) by spending memory to have all that information already computed.  I would say it's a worthy trade as long as your game requires you to perform many operations/queries on only subsets of your data, where your subsets typically match your tile types.  If you have operations that require iterating over the entire 2D grid anyways, then this may not be worth doing, since at each tile you visit, you could perform the operation right then and there.

 

Creating new tiles entirely for the update is probably a bad idea.  C# is garbage collected.  If you create tons of new tiles every frame and remove references to the old tiles, you could be creating enormous pressure on the garbage collector.  You should avoid orphaning data at all costs and just mutate existing memory if you want to avoid garbage collection hiccups.

 

Your description of "update" is woefully vague, but I suspect your update is performing something pathologically expensive or your overall algorithm for iteration is just far too excessive for what you want to accomplish.  Even for large 2D grids, you shouldn't have much of a problem updating the entire grid if you've carefully designed your algorithms and data structures.



#12 LorenzoGatti   Crossbones+   -  Reputation: 2735

Like
0Likes
Like

Posted 29 March 2013 - 03:42 AM

If grass is growing according to a certain schedule, I'd simply place tiles in a priority queue (efficiently answering only one query: which tiles are due for a special update at timesteps <=N?). You process tiles, swapping graphics, altering stats, and so on, and you put tiles back in the priority queue tagged with the appropriate future time of their next update. Obviously, tiles can be retired from the queue (e.g. grass reaches the growth limit), added to the queue (e.g. an inert dust tile gets seeded), rescheduled (e.g. grazing delays grass growth events), delayed if there are too many updates in a single frame (just process up to K events per timestep rather than all ripe ones, with K greater than the average number of events per timestep).
Produci, consuma, crepa

#13 EarthBanana   Members   -  Reputation: 941

Like
0Likes
Like

Posted 30 March 2013 - 03:34 AM

Are you sure your getting slow because of the update rather than the draw?

 

The game we are working on now is hex tile based and to avoid bottle neck in the draw we instance draw the tiles so that there is one draw call for each base tile. We also don't recreate the list of transforms for each tile every update.

 

If you have a base grass tile with say 100 instances of it in the world - perhaps you can simply update the base object mesh/texture/whatever your needing to update and have all of your instance tiles refer to the base. Only store essential information in the instances that must change per instance such as position and size and such.



#14 ankhd   Members   -  Reputation: 1320

Like
0Likes
Like

Posted 02 April 2013 - 05:27 AM

Make your game like a river. Never dam it.
Eg. Make your update run for say ten tile then return to your app and on the next process round start at the last tile and keep repeating.
Remember treat you app like a river always flowing.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS