stuck : conways game of life (lots of code)

I have been trying to program conways game of life. I have to implement some functions including evolve and rotate to make it work... and it has to work with dmalloc.

I had this when I started out

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "life.h"
#include "load.h"
#include "rotate.h"
#include "evolve.h"

#define MAX_CYCLES 100
#define ROTATE        20

static void
show(char **arena, int width, int height)
{
        int x, y;

        printf("\033[2J");

        for (x = 0; x < width; x++)
                if (arena[x] != NULL)
                        for (y = 0; y < height; y++) {
                                if (arena[x][y] & 1)
                                        printf("\033[%d;%dH*", y, x);
        }
        printf("\033[H");
        fflush(stdout);
}

int main(int argc, char **argv)
{
        char **arena;
        int width = WIDTH, height = HEIGHT;
        int cycle;

        if (argc != 2 && argc != 4) {
                fprintf(stderr,"usage is %s filename [ width height ]\n",argv[0]);
                exit(1);
        }
        if (argc == 4) {
                width = atoi(argv[2]);
                height = atoi(argv[3]);
                if (width < MINSIZE || width > MAXSIZE || height < MINSIZE || height > MAXSIZE) {
                        fprintf(stderr, "%s: width and height must be in the range %d to %d\n",
                                        argv[0], MINSIZE, MAXSIZE);
                        exit(1);
                }
        }
        if ((arena = load(argv[1], width, height)) == NULL) {
                fprintf(stderr,"%s: Cannot open %s\n",argv[0],argv[1]);
                exit(1);
        }
        for (cycle = 1; cycle <= MAX_CYCLES; cycle++) {
                show(arena, width, height);
                evolve(arena, width, height);
                if (cycle % ROTATE == 0)
                        arena = rotate(arena, &width, &height);
                                usleep(100000); //delay
        }
        int x;
        for (x = 0; x < width; x++)
                if (arena[x] != NULL)
                        free(arena[x]);
        free(arena);
        return 0;
}

---

And for the evolve function I've done the following

Code:

---

#include <stdlib.h>
#include "evolve.h"
#define IN_ARENA(x,y) ((x) >= 0 && (x < width && (y) >= 0 && (y) < height))

// Return 1 if cell x,y is occupied and 0 otherwise.
#define IS_OCCUPIED(a, x, y) (a[x][y] & 1)

// Return 1 if cell x,y was occupied in the previous generation and 0 otherwise.
// Assumes that x,y is within the arena.
#define WAS_OCCUPIED(a, x, y) (a[x][y] >> 1 & 1)

// Return 1 if cell x,y was occupied in the previous generation and 0 otherwise.
// Works for any value of x and y.
#define WAS_OCCUPIED_ANY(a, x, y) (IN_ARENA(x,y) ? WAS_OCCUPIED(a, x, y) : 0)

void
evolve(char **arena, int width, int height)
{
       
        int x, y;
       
        // First shift each cell to the left so its occupied status
        // is in bit 1 rather than bit 0
        for (x = 0; x < width; x++)
                for (y = 0; y < height; y++)
                        arena[x][y] <<= 1;

        // Decide whether each cell should be occupied based on the
        // number of previously occupied neighbours etc.
        for (x = 0; x < height; x++)
                for (y = 0; y < height; y++) {
                        int neighbours = 0;

                        neighbours += WAS_OCCUPIED_ANY(arena, x - 1, y - 1);
                        neighbours += WAS_OCCUPIED_ANY(arena, x - 1, y);
                        neighbours += WAS_OCCUPIED_ANY(arena, x - 1, y + 1);
                        neighbours += WAS_OCCUPIED_ANY(arena, x, y - 1);
                        neighbours += WAS_OCCUPIED_ANY(arena, x, y + 1);
                        neighbours += WAS_OCCUPIED_ANY(arena, x + 1, y - 1);
                        neighbours += WAS_OCCUPIED_ANY(arena, x + 1, y);
                        neighbours += WAS_OCCUPIED_ANY(arena, x + 1, y + 1);
                        if (neighbours == 3 || (neighbours == 2 && WAS_OCCUPIED_ANY(arena,x,y)))
                                arena[x][y] |= 1;
                }

}

---

In evolve (above) need set column to null if a column is unoccupied by anything, but if it isn't I need to do a malloc for the size of the column.. so.. no of rows I guesss. I'm not sure how to check for this (well, I have an IS_OCCUPIED check)but where to check for it, and the loop to use. I think after I shift each cell to the left?
thinking of doing
for (y=0; y < height; y++)
{ for (x=0; x < height; x ++)
sorta thing?
then, can I assign null to an entire column easily ? without a loop?

I haven't programmed the rotate function (rotate the arena 90 degrees) and as usual any empty columns should be null pointers, and I'm unsure how to go about it so any ideas there as well would be appreciated.. totally drawing a blank on it. I'm not hugely awful with 2d arrays although pointers I am still mastering, it is mainly malloc and free I have a problem with..

Any help would be REALLY appreciated.. I'm really struggling with this exercise, I think all the code we were given was a bit overwhelming but I've given it a go and now I need help.

Thanks in advance :)

EDIT: Had an idea for rotate, and here is what I have so far

Code:

---

#include <stdlib.h>
#include "rotate.h"

/* Rorate the arena by 90 degrees clockwise. The pwidth and pheight
 * parameters should be pointers to the width and height of the arena
 * and these are changed by the function to the new width and height.
 * The new arena is returned and the old arena is freed. Any empty
 * columns in the new arena are represented by NULL pointers.
 */
char **rotate(char **arena, int *pwidth, int *pheight)
{
        int x, y;
        char ** newarena;
       
        for(x = 0; x < *pwidth; x++)
        {
                for(y =0; y < *pheight; y++)
                {
                        (*(*(newarena+x)+y)) = (*(*(arena+y)+x));
                                                // possibly newarena[y][x] = arena[*pheight-x][*pwidth-y]; might be better?


                }
        }
       
        free(arena);
       
        return newarena;
}

---

Thinking I need to malloc memory for the newarena? Maybe?

I would suggest you start with a separate program with which to test rotate()
Start simple, draw some diagrams on paper and work through it.

Code:

---

void print ( char **arena, int width, int height );
char **rotate( char **arena, int width, int height );
int main ( ) {
  char test[2][2] = { { 'A', 'B' }, { 'C', 'D' } };
  char *a1[] = { test[0], test[1] };
  char **a2 = rotate( a1, 2, 2 );
  print( a2, 2, 2 );
}

---

When you have a solid function, then drop it into your main program.


BTW, I didn't think Conway had a rotate in it, is that something just thrown in to spice it up a bit?

It doesn't have a rotate in it no so.. I guess it is just to spice it up lol.


Good idea though, thanks I'll have a play with that code..

Ok I tried and failed miserably at creating a test program. :'(
I got loads of errors, stuff like undefined symbol in rotate etc.

I'm getting segmentation faults

on the lines indicated in comments

Code:

---

char **rotate(char **arena, int *pwidth, int *pheight)
{
        int x, y;
        char ** newarena;
        *newarena = malloc((*pwidth)*(*pheight)); // here
        for(x = 0; x < *pwidth; x++)
        {
                for(y =0; y < *pheight; y++)
                {
                        (*(*(newarena+x)+y)) = (*(*(arena+y)+x)); //here
                //        newarena[y][x] = arena[*pheight-x][*pwidth-y];  //and here if i run it
                }
        }
       
        free(arena);
       
        return newarena;
}

---

Can't figure out how to fix it... any ideas?

Code:

---

char ** newarena;
        *newarena = malloc((*pwidth)*(*pheight)); // here

---

You can't dereference a ** that doesn't point to anything. Well you can, but then you segfault.


Quzah.

Quote:

---

Originally Posted by quzah

Code:

---

char ** newarena;
        *newarena = malloc((*pwidth)*(*pheight)); // here

---

You can't dereference a ** that doesn't point to anything. Well you can, but then you segfault.


Quzah.

---

OK
So now I don't get gdb telling me that the fault is with that line if I do the below.. but now it is on the line newarena [x][y] = ...

Code:

---

* parameters should be pointers to the width and height of the arena
 * and these are changed by the function to the new width and height.
 * The new arena is returned and the old arena is freed. Any empty
 * columns in the new arena are represented by NULL pointers.
 */
char **rotate(char **arena, int *pwidth, int *pheight)
{
        int x, y;
        char ** newarena;
        newarena = malloc((*pwidth)*(*pheight));
        for(x = 0; x < *pwidth; x++)
        {
                for(y =0; y < *pheight; y++)
                {
                        newarena[x][y] = (*(*(arena+y)+x));
                //        newarena[y][x] = arena[*pheight-x][*pwidth-y];
                }
        }
       
        free(arena);
       
        return newarena;
}

---

I'm not sure how to assign the values from where arena x y is pointing to the new arena... pointers confuse me but double pointers are .. even more so... just when I thought I'd figured it out.. thanks for the tip though. :)

What do you think I should do? Can you see where I'm going with this though? I'm not even sure if I'm on the right track.

Just adding more stars doesn't automatically give you more dimensions. You have to allocate each type specifically (because each star gives you a new type).

Code:

---

type x; /* a variable named x of type type */
type *x; /* a variable named x of type pointer to type */
type **x; /* a variable named x of type pointer to pointer to type */

---

Thus, if you really want a two dimensional array, you have to allocate both rows and columns:

Code:

---

type **array;

array = malloc( rows * sizeof *array );
for( x = 0; x < rows; x++ )
    array[ x ] = malloc( cols * sizeof( **array) );

---

Note: Here I am not getting the value of array when I use it with sizeof, I'm actually getting the type of variable it is, and determining its size. sizeof is pretty much the only time you can ever get away with this:

Code:

---

type *p;
x = sizeof *p;

---

Oh, and when you're all done, you don't just call free once and be done with it. You have to call free for every malloc call you have made. Free each row's columns. Then free the main pointer.

Quzah.

Quote:

---

Originally Posted by quzah

Code:

---

type **x; /* a variable named x of type pointer to pointer to type */

---

---

You have to admit though, that is slightly confusing.

Quote:

---

Originally Posted by quzah

array = malloc( rows * sizeof *array );
for( x = 0; x < rows; x++ )
array[ x ] = malloc( cols * sizeof( **array) );[/code]Note: Here I am not getting the value of array when I use it with sizeof, I'm actually getting the type of variable it is, and determining its size. sizeof is pretty much the only time you can ever get away with this:

Code:

---

type *p;
x = sizeof *p;

---

Oh, and when you're all done, you don't just call free once and be done with it. You have to call free for every malloc call you have made. Free each row's columns. Then free the main pointer.

Quzah.

---

OK if I understand correctly then I've got

Code:

---

#include <stdlib.h>
#include "rotate.h"


char **rotate(char **arena, int *pwidth, int *pheight)
{
        int x, y;
        char ** newarena;
        newarena = malloc( *pwidth * sizeof(char *) );
        for(x = 0; x < *pwidth; x++)
        {
                newarena[x] = malloc(*pheight * sizeof(**newarena));
                for(y =0; y < *pheight; y++)
                {
                        (*(*(newarena+x)+y)) = (*(*(arena+y)+x));
                       
                //        *newarena = (*(*(arena+y)+x));
                //        newarena[y][x] = arena[*pheight-x][*pwidth-y];
                }
        }

        for(x = 0; x < *pwidth; x++)
                for(y = 0; y < *pheight; y++)
                        free(newarena[y]);

        free(arena);
       
        return newarena;
}

---

I'm still getting a seg fault on the (*(*(newarena.. but I don't even know what I'm trying to do there. Perhaps I should do separate statements for assigning new values from old values...

But, is the whole malloc free thing looking OK? Thanks by the way that makes a bit more sense now...

I don't know what you are trying to do here either. What are you trying to do there? How about putting in words what you want to do in the function, including what you plan on passing and returning, and then we'll have an idea of where to go from?


Quzah.

Any reason you're not addressing arena and newarena as arrays? It's usually much easier to spot errors that way. Try arena[y][x] and newarena[x][y] instead. Also, why are you passing in the address of pheight and pwidth. There's no need to, since you never change their values. Lastly, you're not actually rotating. Swapping the x and y values is reflecting it over the line y = x.

Quote:

---

Originally Posted by quzah

I don't know what you are trying to do here either. What are you trying to do there? How about putting in words what you want to do in the function, including what you plan on passing and returning, and then we'll have an idea of where to go from?


Quzah.

---

I think I was trying to do something similar to the new line I've got replacing it. Problem is though,

I think that there is an error with the allocating of the new height and width as they should be swapped... not sure where I'm overrunning or indexing out of bounds maybe.. because the whole point is to rotate the array 90 degrees.

Code:

---

#include <stdlib.h>
#include "rotate.h"

/* Rorate the arena by 90 degrees clockwise. The pwidth and pheight
 * parameters should be pointers to the width and height of the arena
 * and these are changed by the function to the new width and height.
 * The new arena is returned and the old arena is freed. Any empty
 * columns in the new arena are represented by NULL pointers.
 */
char **rotate(char **arena, int *pwidth, int *pheight)
{
        int x, y;
        char ** newarena;
        newarena = malloc(*pwidth * sizeof(char));
        for(x = 0; x < *pwidth; x++)
        {
                newarena[x] = malloc(*pheight * sizeof(char));
                for(y =0; y < *pheight; y++)
                {
                       
                        newarena[*pheight - (y+1)][x] = (arena[x] != NULL) ? arena[x][y] : 0;
                       
                //        *newarena = (*(*(arena+y)+x));
                //        newarena[y][x] = arena[*pheight-x][*pwidth-y];
                }
        }

        for(x = 0; x < *pwidth; x++)
                for(y = 0; y < *pheight; y++)
                        free(newarena[y]);

        free(arena);
       
        return newarena;
}

---

Code:

---

for each old row
    for each old col
        new[ /* normally rows */ col ][ /* normally col */ row ] = old[ row ][ col ]

---

You need to allocate col number of rows for your new one, and each one is row in length instead of col. But you need to be sure to allocate correctly as I showed you eaerlier.


Quzah.

Yes there is. newarena is a char **, but you allocate *pwidth * sizeof(char) bytes. Try the following:

Code:

---

newarena = malloc(*pwidth * sizeof(*newarena));
...
newarena[x] = malloc(*pheight * sizeof(*newarena[x]));

---

That way, whatever type newarena is, you allocate the right amount of space for each dimension.

I'm really sorry guys.. I've tried to understand sorry if I get it wrong..

Code:

---



char **rotate(char **arena, int *pwidth, int *pheight)
{
        int x, y;
        char **newarena;
        newarena = malloc(*pwidth * sizeof(*newarena));
        for(x = 0; x < *pwidth; x++)
        {
                newarena[x] = malloc(*pheight * sizeof(*newarena[x]));
                for(y =0; y < *pheight; y++)
                {
                       
                        newarena[*pheight - (y+1)][x] = (arena[x] != NULL) ? arena[x][y] : 0;
                }
        }

        for(x = 0; x < *pwidth; x++)
        {
                for(y = 0; y < *pheight; y++)
                {
                        free(newarena[y]);
                }
        }
       

        free(arena);
       
        return newarena;
}

---

What do you think now?

I keep swapping width and height around in various places hoping I'll find the overrun but it doesn't work I always get seg fault... :( My brain is turning to mush now after several hours of trying to get it to work. It is probably really obvious but I'm at that wall...

checking if row is not empty, if it isnt then copy the contents else set the column to null (because columns become rows in the newarena anyway..) so think the trying to get something that points to null might be the problem..

Code:

---


#include <stdlib.h>
#include "rotate.h"

/* Rorate the arena by 90 degrees clockwise. The pwidth and pheight
 * parameters should be pointers to the width and height of the arena
 * and these are changed by the function to the new width and height.
 * The new arena is returned and the old arena is freed. Any empty
 * columns in the new arena are represented by NULL pointers.
 */
char **rotate(char **arena, int *pwidth, int *pheight)
{
        int x, y;
        char **newarena;
       
                                       

        newarena = malloc(*pwidth * sizeof(*newarena));
        for(x = 0; x < *pwidth; x++)
        {
               
                if(arena[x] !=NULL)
                {
                        newarena[x] = malloc(*pheight * sizeof(*newarena[x]));
                       
                        for(y =0; y < *pheight; y++)
                        {
                       
                                newarena[*pheight - (y+1)][x] = (arena[x][y] != NULL) ? arena[x][y] : 0;
                        }
                }
                else
                {
                        newarena[y] = NULL;
                }
               
        }       

        for(x = 0; x < *pwidth; x++)
        {
                for(y = 0; y < *pheight; y++)
                {
                        free(newarena[y]);
                }
        }
       

        free(arena);
       
        return newarena;
}

---