Treating a 1D array as a 2D array with wraparound

[Dan]

Hey hey,

I'm trying to code a program for generating cyclic cellular automaton
(http://en.wikipedia.org/wiki/Cyclic_cellular_automaton) and have
gotten it working well enough to generate pretty pictures but have run
into a problem with it wrapping around the array properly when wanting
to check cell values beyond the edge of the screen.

In the picture link it shows that the wrapping works correctly when
cells are checking the value over the bounds from east to west and
west to east (you can tell from the big diamond in the top left across
the left bound to the right bound and from the bottom right diamond
pulsing from the right bound to the left bound) and from north to
south (from the top left diamond pulsing to the top to the bottom).

The wrapping does not work correctly when trying to go from the bottom
bound to the top bound. This can be seen in the big diamond in the
bottom right pulsing into the bottom and having nothing appear on the
top.

http://img48.imageshack.us/my.php?image=screencaptureoe9.png

The diamonds grow over time as each 'step' is run.

I have the all the cells stored in a one dimensional array which I
treat as a two dimensional array but I think my logic is screwed up
when calculating the correct cell when it happens to be checking
across the bounds.

In the example below modelArray is considered a pointer to an array of
integers. It is the same size as previousModelArray.

previousModelArray is the array that is used to calculate the next
step. Once the calculation is done it is discarded.

Also the function name looks funny because it's implemented in
objective-c. Most of the code is C though so I thought I would post it
in this group.

-(void)step {

int *previousModelArray;
previousModelArray = malloc(sizeof(int) * arrayWidth *
arrayHeight);

for(int i = 0; i < arrayWidth * arrayHeight; i++) {
previousModelArray = modelArray;
}

for(int x = 0; x < arrayWidth; x++) {
for (int y = 0; y < arrayHeight; y++) {

int i = x + (y * arrayWidth);
int iRight = ((x + 1) % arrayWidth) + (y *
arrayWidth);
int iDown = x + (((y + 1) % arrayHeight) *
arrayWidth);
int iLeft = ((x - 1) % arrayWidth) + (y *
arrayWidth);
int iUp = x + (((y - 1) % arrayHeight) *
arrayWidth);

if(((modelArray + 1) % n) ==
previousModelArray[iRight]) {
modelArray = previousModelArray
[iRight];
}
else if (((modelArray + 1) % n) ==
previousModelArray[iDown]) {
modelArray = previousModelArray
[iDown];
}
else if (((modelArray + 1) % n) ==
previousModelArray[iLeft]) {
modelArray = previousModelArray
[iLeft];
}
else if (((modelArray + 1) % n) ==
previousModelArray[iUp]) {
modelArray = previousModelArray
[iUp];
}
}
}

free(previousModelArray);

}

Any help would be much appreciated.

Thanks,

Dan

 

[Dan]

Wow that looks terrible. Here is the code that's in the double for
loop in a hopefully more readable format.


int i = x + (y * arrayWidth);
int iRight = ((x + 1) % arrayWidth) + (y * arrayWidth);
int iDown = x + (((y + 1) % arrayHeight) * arrayWidth);
int iLeft = ((x - 1) % arrayWidth) + (y * arrayWidth);
int iUp = x + (((y - 1) % arrayHeight) * arrayWidth);

if(((modelArray + 1) % n) == previousModelArray[iRight]) {
modelArray = previousModelArray[iRight];
}
else if (((modelArray + 1) % n) == previousModelArray[iDown]) {
modelArray = previousModelArray[iDown];
}
else if (((modelArray + 1) % n) == previousModelArray[iLeft]) {
modelArray = previousModelArray[iLeft];
}
else if (((modelArray + 1) % n) == previousModelArray[iUp]) {
modelArray = previousModelArray[iUp];
}

 

[Ben Bacarisse]

I'm trying to code a program for generating cyclic cellular automaton
(http://en.wikipedia.org/wiki/Cyclic_cellular_automaton) and have
gotten it working well enough to generate pretty pictures but have run
into a problem with it wrapping around the array properly when wanting
to check cell values beyond the edge of the screen.

The wrapping does not work correctly when trying to go from the bottom
bound to the top bound. This can be seen in the big diamond in the
bottom right pulsing into the bottom and having nothing appear on the
top.

http://img48.imageshack.us/my.php?image=screencaptureoe9.png

The diamonds grow over time as each 'step' is run.

I have the all the cells stored in a one dimensional array which I
treat as a two dimensional array but I think my logic is screwed up
when calculating the correct cell when it happens to be checking
across the bounds.

What is the reason for a 1D array? If you can use some C99 features,
2D arrays are much simpler for this sort of thing.

In the example below modelArray is considered a pointer to an array of
integers. It is the same size as previousModelArray.

previousModelArray is the array that is used to calculate the next
step. Once the calculation is done it is discarded.

Also the function name looks funny because it's implemented in
objective-c. Most of the code is C though so I thought I would post it
in this group.

-(void)step {

int *previousModelArray;
previousModelArray = malloc(sizeof(int) * arrayWidth *
arrayHeight);

for(int i = 0; i < arrayWidth * arrayHeight; i++) {
previousModelArray = modelArray;
}

I'd use memcpy rather than a loop:

memcp(previousModelArray, modelArray,
arrayWidth * arrayHeight * sizeof *modelArray);

for(int x = 0; x < arrayWidth; x++) {
for (int y = 0; y < arrayHeight; y++) {

int i = x + (y * arrayWidth);
int iRight = ((x + 1) % arrayWidth) + (y *
arrayWidth);
int iDown = x + (((y + 1) % arrayHeight) *
arrayWidth);
int iLeft = ((x - 1) % arrayWidth) + (y *
arrayWidth);
int iUp = x + (((y - 1) % arrayHeight) *
arrayWidth);

if(((modelArray + 1) % n) ==
previousModelArray[iRight]) {
modelArray = previousModelArray
[iRight];
}
else if (((modelArray + 1) % n) ==
previousModelArray[iDown]) {
modelArray = previousModelArray
[iDown];
}
else if (((modelArray + 1) % n) ==
previousModelArray[iLeft]) {
modelArray = previousModelArray
[iLeft];
}
else if (((modelArray + 1) % n) ==
previousModelArray[iUp]) {
modelArray = previousModelArray
[iUp];
}

And now I must guess. Surely these rules should not be joined by
"else". The effect is that the iUp values only ever "kicks in" if
all of the other three have no effect.

 

[Dan]

What is the reason for a 1D array?  If you can use some C99 features,
2D arrays are much simpler for this sort of thing.

I wanted to avoid the array of pointers as I've had some trouble with
those in the past. It seems you can't have pointers to 2D arrays? I've
tried that but get compilation errors.

In the example below modelArray is considered a pointer to an array of
integers. It is the same size as previousModelArray.

previousModelArray is the array that is used to calculate the next
step. Once the calculation is done it is discarded.

Also the function name looks funny because it's implemented in
objective-c. Most of the code is C though so I thought I would post it
in this group.

-(void)step {

        int *previousModelArray;
        previousModelArray = malloc(sizeof(int) * arrayWidth *
arrayHeight);

        for(int i = 0; i < arrayWidth * arrayHeight; i++) {
                previousModelArray = modelArray;
        }

I'd use memcpy rather than a loop:

  memcp(previousModelArray, modelArray,
        arrayWidth * arrayHeight * sizeof *modelArray);

Yeah I was looking at that part of my code after I posted and I think
I could save even more time if I created a blank array and just looked
at modelArray to check the values and then put the correct value into
the new array and then just set the pointer to modelArray to the new
array. I would get to avoid any copying at all then.

I didn't know memcp existed though! It seems like it'll be handy.

        for(int x = 0; x < arrayWidth; x++) {
                for (int y = 0; y < arrayHeight; y++) {

                        int i = x + (y * arrayWidth);
                        int iRight = ((x + 1) % arrayWidth) + (y *
arrayWidth);
                        int iDown = x + (((y + 1) % arrayHeight) *
arrayWidth);
                        int iLeft = ((x - 1) % arrayWidth) + (y *
arrayWidth);
                        int iUp = x + (((y - 1) % arrayHeight) *
arrayWidth);

                        if(((modelArray + 1) % n) ==
previousModelArray[iRight]) {
                                modelArray = previousModelArray
[iRight];
                        }
                        else if (((modelArray + 1) % n) ==
previousModelArray[iDown]) {
                                modelArray = previousModelArray
[iDown];
                        }
                        else if (((modelArray + 1) % n) ==
previousModelArray[iLeft]) {
                                modelArray = previousModelArray
[iLeft];
                        }
                        else if (((modelArray + 1) % n) ==
previousModelArray[iUp]) {
                                modelArray = previousModelArray
[iUp];
                        }

And now I must guess.  Surely these rules should not be joined by
"else".  The effect is that the iUp values only ever "kicks in" if
all of the other three have no effect.

It only needs to have one of it's neighbours with a successor to it's
original value to switch to the higher value. And it can only do that
once per 'step'. If it did have the elses removed it could potentially
do that 4 times which wouldn't fit the right behaviour.

I tried it without the elses though and it looked pretty cool! I'll
have to add that as an option or something.

Thanks for responding!

 

[Nate Eldredge]

Hey hey,

I'm trying to code a program for generating cyclic cellular automaton
(http://en.wikipedia.org/wiki/Cyclic_cellular_automaton) and have
gotten it working well enough to generate pretty pictures but have run
into a problem with it wrapping around the array properly when wanting
to check cell values beyond the edge of the screen.

One thing that looks like a problem is when, say, x == 0. C's %
operator works such that (-1 % arrayWidth) is -1, not (arrayWidth - 1).

When fixing this, you might want to wrap your index computation in some
functions and/or macros, perhaps with some asserts to verify your
arithmetic.

/* c=posmod(a,b) is the unique integer with 0 <= c < b and a-c divides b */
inline int posmod(int a, int b) {
int m = a % b;
int c = (m < 0) ? (m + b) : m;
assert(c >= 0);
assert(c < b);
assert(((a-c) % b) == 0);
return c;
}

#define INDEX(x,y) (posmod((x),arrayWidth) + posmod((y),arrayHeight) * arrayWidth)

for (x = ...) {
for (y = ... ) {
if (modelArray[INDEX(x,y)] == previousModelArray[INDEX(x+1, y)])
...
}
}

et cetera.

 

[James Kuyper]

Dan wrote:
....

I wanted to avoid the array of pointers as I've had some trouble with
those in the past. It seems you can't have pointers to 2D arrays? I've
tried that but get compilation errors.

You can have pointers to 2D arrays:

int array[3][5];
int (*parray)[5] = array;

However, the C99 feature that is most likely to be useful for working
with 2-D arrays is VLAs. A simple example:

void mat_mul(int l, int m, int n, double out[l][n],
double left[l][m], double right[m][n])
{
for(int i=0; i<l; i++)
for(int j=0; j<n; j++)
{
out[j] = 0.0;
for(int k=0; k<m; k++)
out[j] += left[k] * right[k][j];
}
}

 

[Dan]

Ah yeah it was the % operator that was screwing me up. It works great
now. Thanks Nate!

Also James that 2D array with pointers blew my mind. Is there a way to
make that work with dynamic memory allocation?

I've got this working but it I'm wondering if there will be any
problems with it...

int *arrayOne;
arrayOne = malloc(sizeof(int) * arrayWidth * arrayHeight);
int (*arrayTwo)[arrayWidth] = arrayOne;

It seems like I can insert and retrieve elements from the 2d array but
I'm wondering if there is a better way to do it.

Thanks again!

Dan

 

[James Kuyper]

Ah yeah it was the % operator that was screwing me up. It works great
now. Thanks Nate!

Also James that 2D array with pointers blew my mind. Is there a way to
make that work with dynamic memory allocation?

A Variable Length Array (VLA) is an alternative to dynamic memory
allocation; they themselves cannot be dynamically allocated. However, a
VLA parameter in a function can refer to an argument which is a
conventional multi-dimensional array that has been dynamically allocated.

Note: VLAs are not restricted to function parameters, they can also be
declared with block scope (they cannot be used at file scope).

I've got this working but it I'm wondering if there will be any
problems with it...

int *arrayOne;
arrayOne = malloc(sizeof(int) * arrayWidth * arrayHeight);
int (*arrayTwo)[arrayWidth] = arrayOne;

It seems like I can insert and retrieve elements from the 2d array but
I'm wondering if there is a better way to do it.

That shouldn't work without a cast:

int (*arrayTwo)[arrayWidth] = (int (*)[arrayWidth])arrayOne;

There is a slightly better way to do it:

int (*arrayTwo)[arrayWidth] =
malloc(arrayHeight * sizeof *arrayTwo);
int *arrayOne = arrayTwo[0];

That is simpler, in part because it doesn't require any explicit casts.
Because it's simpler, it's also easier to get right. In effect, it makes
the compiler implicitly perform the sizeof(int)*arrayWidth calculation
for you, which avoids the possibility of you performing that calculation
incorrectly.

 

[Dan]

Awesome. Thank you.