/* hpplattice.c This application solves for the behavior of a lattice gas, using cellular automata in a square lattice (HPP) J. Watlington, 10/25/95 Usage: hpplattice [ block | random | test ] [ -s ] Modified: */ #include #include #include "display.h" #define DEFAULT_MAX_ITERATIONS 2000 #define MAX_ARRAY_SIZE 2048 #define DEFAULT_ARRAY_SIZE 256 /* The following define how the array is seeded */ #define SEED_BLOCK_SIZE ((array_size) / 4) #define SEED_BLOCK_START ((3 *(array_size)) / 8) #define SEED_RAND_SEED 0xFF67533 #define SEED_RAND_THRESHOLD 22000 #define SEED_BLOCK 0 #define SEED_BLOCK_AND_RND 1 #define SEED_TEST 2 #define DEFAULT_ARRAY_SEED SEED_BLOCK_AND_RND /* The following global variables are used for command line parameters */ int array_size = DEFAULT_ARRAY_SIZE; int array_seed = DEFAULT_ARRAY_SEED; int max_iterations = DEFAULT_MAX_ITERATIONS; /* This is the structure that will represent the lattice of nodes */ #define DEGREE_OF_INTERCONNECT 4 #define NUM_RULES 16 /* 2^DEGREE_OF_INTERCONNECT */ #define MAX_PARTICLES 4 #ifndef USE_BIT_STORAGE typedef struct { char north; char east; char west; char south; } lattice_node; #else typedef struct { char north:1, east:1, west:1, south:1, reserved:4; } lattice_node; #endif typedef struct { int size; /* Assume square array ! */ lattice_node *d[ MAX_ARRAY_SIZE ]; } lattice; /* These are the rules the determine the behavior of this lattice gas */ lattice_node rules[ NUM_RULES ] = { /* { N, E, W, S } */ { 0, 0, 0, 0 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 1, 1, 0, 0 }, { 0, 0, 1, 0 }, { 1, 0, 1, 0 }, { 1, 0, 0, 1 }, { 1, 1, 1, 0 }, { 0, 0, 0, 1 }, { 0, 1, 1, 0 }, { 0, 1, 0, 1 }, { 1, 1, 0, 1 }, { 0, 0, 1, 1 }, { 1, 0, 1, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, }; /* These are prototypes of functions internal to this code module */ void parse_arguments( int argc, char **argv ); lattice *alloc_lattice( int size ); void seed_lattice( lattice *l, int seed ); void calc_collisions( lattice *l, lattice *temp ); void calc_collision_row( lattice *in, lattice *out, int prev_row_index, int cur_row_index, int next_row_index ); void display_lattice( window_tag wt, lattice *l ); /* This is the top level of the program */ void main( int argc, char **argv ) { lattice *nodes[ 2 ]; int next_buf = 1; int cur_buf = 0; int num_iters = 0; window_tag w; parse_arguments( argc, argv ); nodes[ cur_buf ] = alloc_lattice( array_size ); nodes[ next_buf ] = alloc_lattice( array_size ); seed_lattice( nodes[ cur_buf ], array_seed ); if( (w = display_init_window( "HPP", array_size, array_size, MAX_PARTICLES + 1 )) < 0 ) { printf( "Unable to open display window.\n" ); exit( -1 ); } display_lattice( w, nodes[ cur_buf ] ); while( num_iters++ < max_iterations ) { calc_collisions( nodes[ cur_buf ], nodes[ next_buf ] ); display_lattice( w, nodes[ next_buf ] ); cur_buf = next_buf; next_buf = 1 - next_buf; } } void calc_collisions( lattice *in, lattice *out ) { int size = in->size - 1; int row; calc_collision_row( in, out, size, 0, 1 ); for( row = 1; row < size; row++ ) calc_collision_row( in, out, row - 1, row, row + 1 ); calc_collision_row( in, out, size - 1, size, 0 ); } void calc_collision_row( lattice *in, lattice *out, int prev_row_index, int cur_row_index, int next_row_index ) { int adr; int col; int size = in->size - 1; lattice_node *outcome; lattice_node *cur_row_in = in->d[ cur_row_index ]; lattice_node *prev_row_out = out->d[ prev_row_index ]; lattice_node *cur_row_out = out->d[ cur_row_index ]; lattice_node *next_row_out = out->d[ next_row_index ]; /* Special case the first node in a row */ adr = 0; if( cur_row_in->north != 0 ) adr |= 8; if( cur_row_in->east != 0 ) adr |= 4; if( cur_row_in->west != 0 ) adr |= 2; if( cur_row_in->south != 0 ) adr |= 1; outcome = rules + adr; prev_row_out[ 0 ].south = outcome->north; cur_row_out[ 1 ].west = outcome->east; cur_row_out[ size ].east = outcome->west; /* periodic boundary ! */ next_row_out[ 0 ].north = outcome->south; /* Now process the inner nodes */ for( col = 1; col < size; col++ ) { cur_row_in++; adr = 0; if( cur_row_in->north != 0 ) adr |= 8; if( cur_row_in->east != 0 ) adr |= 4; if( cur_row_in->west != 0 ) adr |= 2; if( cur_row_in->south != 0 ) adr |= 1; outcome = rules + adr; prev_row_out[ col ].south = outcome->north; cur_row_out[ col + 1 ].west = outcome->east; cur_row_out[ col - 1 ].east = outcome->west; next_row_out[ col ].north = outcome->south; } /* Special case the last node in a row */ cur_row_in++; adr = 0; if( cur_row_in->north != 0 ) adr |= 8; if( cur_row_in->east != 0 ) adr |= 4; if( cur_row_in->west != 0 ) adr |= 2; if( cur_row_in->south != 0 ) adr |= 1; outcome = rules + adr; prev_row_out[ size ].south = outcome->north; cur_row_out[ 0 ].west = outcome->east; /* periodic boundary ! */ cur_row_out[ size - 1 ].east = outcome->west; next_row_out[ size ].north = outcome->south; } void parse_arguments( int argc, char **argv ) { int index; if( argc > 1 ) { index = 1; while( index < argc ) { if( argv[ index ][0] == '-' ) { /* - option, only -size defined right now */ if( index + 1 >= argc ) { printf( "%s option requires an argument !\n", argv[ index ] ); exit( -1 ); } array_size = atoi( argv[ ++index ] ); printf( "Simulating a %d x %d array\n", array_size, array_size ); } else { /* must be array seed - block, rand, or test */ switch( argv[ index ][0] ) { case 'b': array_seed = SEED_BLOCK; break; case 'r': array_seed = SEED_BLOCK_AND_RND; break; case 't': array_seed = SEED_TEST; break; default: printf( "I don't understand %s as a seed pattern !\n", argv[ index ] ); exit( -1 ); } } index++; } } srand( SEED_RAND_SEED ); } void seed_lattice( lattice *l, int seed ) { int row, col; int lattice_size = l->size; lattice_node *n; /* Now seed the lattice structure. It has already been cleared to all zeroes. */ if( seed == SEED_BLOCK_AND_RND ) for( row = 0; row < lattice_size; row++ ) { for( n = l->d[ row ], col = 0; col < lattice_size; col++, n++ ) { if((rand() >> SEED_RAND_SCALE_FACTOR) > SEED_RAND_THRESHOLD) n->north = 1; if((rand() >> SEED_RAND_SCALE_FACTOR) > SEED_RAND_THRESHOLD) n->south = 1; if((rand() >> SEED_RAND_SCALE_FACTOR) > SEED_RAND_THRESHOLD) n->east = 1; if((rand() >> SEED_RAND_SCALE_FACTOR) > SEED_RAND_THRESHOLD) n->west = 1; } } if( (seed == SEED_BLOCK) || (seed == SEED_BLOCK_AND_RND) ) for( row = SEED_BLOCK_START; row < (SEED_BLOCK_START + SEED_BLOCK_SIZE); row++ ) { n = l->d[ row ] + SEED_BLOCK_START; for( col = SEED_BLOCK_START; col < (SEED_BLOCK_START + SEED_BLOCK_SIZE); col++, n++ ) { n->north = 1; n->east = 1; n->west = 1; n->south = 1; } } if( seed == SEED_TEST ) { for( n = l->d[ 0 ], col = 0; col < l->size; col++, n++ ) { n->north = 0; n->east = 0; n->west = 1; n->south = 1; } for( row = 2; row < (array_size - 1); row++ ) { n = l->d[ row ] + 4; n->north = 1; n->east = 1; n->west = 0; n->south = 0; } } } /* alloc_lattice This lattice is stored as an array of lattice_nodes, where each row is pointed to independently (although in this case the lines are actually stored consecutively.) */ lattice *alloc_lattice( int lattice_size ) { int row, col; long total_array_size; lattice_node *n; lattice_node *row_start; lattice *l; /* malloc the memory */ total_array_size = (lattice_size * lattice_size * sizeof(lattice_node)) + sizeof( lattice ); if( (l = (lattice *)malloc( total_array_size )) == NULL ) { printf( "unable to alloc %d bytes of memory for lattice\n", total_array_size ); exit( -1 ); } /* Now init the lattice structure. */ l->size = lattice_size; row_start = (lattice_node *)((long)l + sizeof( lattice )); for( row = 0; row < lattice_size; row++ ) { l->d[ row ] = row_start; for( n = row_start, col = 0; col < lattice_size; col++, n++ ) { n->north = 0; n->east = 0; n->west = 0; n->south = 0; } row_start += lattice_size; } return( l ); } void display_lattice( window_tag wt, lattice *l ) { int x, y; int size = l->size; int num_particles; lattice_node *n; for( y = 0; y < size; y++ ) { n = l->d[ y ]; for( x = 0; x < size; x++, n++ ) { num_particles = n->north; num_particles += n->east; num_particles += n->west; num_particles += n->south; display_set_pixel( wt, x, y, num_particles ); } } display_update( wt ); }