Sign in to follow this  
freeworld

How toavoid overlapping when processing a grid?

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 this post


Link to post
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 this post


Link to post
Share on other sites
[quote name='NickGomes' timestamp='1311022785' post='4837025']
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.
[/quote]

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]
[code]
struct TILE_FW {
... tile data and interface to interact with the tile...
};

struct TILE {
TILE_FW t1;
TILE_FW t2;

*prevTile;
*currentTile;
};
[/code]

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.

[quote name='NickGomes' timestamp='1311022785' post='4837025']...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.
[/quote]

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this