• 15
• 15
• 11
• 9
• 10

# How toavoid overlapping when processing a grid?

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

## Recommended Posts

Imagine a 2D grid full of information, I'm iterating over the grid processing each chunk one at a time. The problem is that for each chunk, it's being compared to each of e it's neighbor and sometimes effecting those neighbors. Then when it comes to processing the neighbor, it's already been altered from the previous chunk. This causes all the calculations to be bias'd towards one side, because they get processed repeatedly when they shouldn't.

What would be a clean way to process the grid without altering the current state of the grid... do I have to store basically a copy of the chunk in the chunk. I would just alter the copy, while using the original for calculations. and when everything is said and done swap the two?

##### Share on other sites
You could store the changes that need to be made at the end of your iteration separately from the main grid. Then once your done processing the grid apply all the changes. The copy and swap method is also viable although if a grid spot is left unchanged you might waste memory. Now with the copy and swap you would want to make an EMPTY copy and just put the results in that empty copy, leaving the original intact. Then at the end you switch your original with your new copy.

Now to compare both methods:

1) Store changes then update grid - Lower memory footprint, but will probably need another loop to update the values.

2) Copy grid then swap original - Higher memory footprint, but to update you just need to swap a reference which would avoid a loop.

Now there might be cases where 1 will be faster than 2 or vice versa. Say you have a massive grid that only changes one chunk, option 1 is probably better then copying the whole grid in. But now say you have a massive grid and all of the values change. option 2 would definitely be better since you are only looping through the massive grid once.

##### Share on other sites

You could store the changes that need to be made at the end of your iteration separately from the main grid. Then once your done processing the grid apply all the changes. The copy and swap method is also viable although if a grid spot is left unchanged you might waste memory. Now with the copy and swap you would want to make an EMPTY copy and just put the results in that empty copy, leaving the original intact. Then at the end you switch your original with your new copy.

Now to compare both methods:

1) Store changes then update grid - Lower memory footprint, but will probably need another loop to update the values.

2) Copy grid then swap original - Higher memory footprint, but to update you just need to swap a reference which would avoid a loop.

Now there might be cases where 1 will be faster than 2 or vice a versa. Say you have a massive grid that only changes one chunk, option 1 is probably better then copying the whole grid in. But now say you have a massive grid and all of the values change. option 2 would definitely be better since you are only looping through the massive grid once.

I quickly put together, the swap method, just by making a new structure that has 2 of my grid chunk and internally switches them but I'm getting a weird error... or bug.

I have two structures like so [psuedo]
 struct TILE_FW { ... tile data and interface to interact with the tile... }; struct TILE { TILE_FW t1; TILE_FW t2; *prevTile; *currentTile; }; 

In tiles constructors, it zeros out the two tiles, then sets the prevTile pointer to point to the first one and current to point o the second one. The constructor gets called, but as soon as it exits the constructor, all of a sudden the tiles aren't in the same space in memory? and the pointers are pointing to garbage. I figured this had to do with using the constructor to push the tiles into a vector. So i made a function RESET() to call after I'm done filling the vector to set the pointers, but still the same result.

guess I'll have to store changes and pretty much duplicate everything... so tedious.

...But now say you have a massive grid and all of the values change. option 2 would definitely be better since you are only looping through the massive grid once.

It's not really a massive grid, atleast I wouldn't consider it massive. ~id like it to operate up to 300x300 grid, but there's alot of data per tile, and each tile can effect or be effected by up to a radius of 7 around it.