Релазиация игры Жизнь на С++, OpenMP

      Комментарии к записи Релазиация игры Жизнь на С++, OpenMP отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 неделя, 4 дн. назад.

  • Автор
    Сообщения
  • #4105

    Выложена лабораторная работа студентов В.Л. Филинов и С.Л. Лещенко.

    Задание:

    Написать клеточный автомат на ограниченном двумерном поле (за границей поля все клетки имеют состояние 0). Выход из программы осуществляется, если система пришла в стационарное состояние, либо достигнуто заданное число итераций.

    Анализ программы:

    Для реализации алгоритма работы клеточного автомата, необходимо определить как он должен вести себя, и при каких условиях. Клеточный автомат — математический объект с дискретным пространством и временем. Каждое положение в пространстве представлено отдельной клеткой матрицы.
    Начальное состояние каждой клетки может быть либо 1 (считается, что в клетке «есть жизнь»), либо 0 (клетка свободна). Также у каждой клетки есть «соседи», в соответствии с количеством которых и определяется, будет ли жить клетка в следующий такт времени.
    Поэтому выводим условия:
    1) Если у клетки больше 3 «соседей», она погибает.
    2) Если у клетки ровно 3 «соседа», клетка оживает (если была пуста), либо продолжает жить.
    3) Если у клетки ровно 2 «соседа», клетка статична.
    4) Если у клетки меньше 2 «соседей», клетка становится пустой (если в клетке была «жизнь»), либо остается пустой (если клетка была изначально пустой).

    Описание алгоритма программы:
    1. Считываются данные с файла – высота поля n, ширина поля m, минимальная задержка между отображением поколений delay, максимальное количество итераций max_iterations, необходимость вывода output, первое поколение arr.
    2. Если есть необходимость вывода, после расчёта каждого поколения оно выводится на экран. Программа останавливается на delay, затем рассчитывается следующее поколение.
    3. Если необходимости вывода нет, вывод на экран не осуществляется и программа не останавливается, а сразу же начинает расчёт следующего поколения.
    4. Засекается время выполнения программы и результат выводится в файл.
    5. Расчёт поколения g+1 производится следующим образом: Для каждой клетки поля рассчитывается количество «соседей» этой клетки, состояние клетки в поколении g+1 определяется правилами игры – если соседей больше 3 или меньше 2, клетка будет пустой. Если их 2, то состояние клетки не меняется. Если их 3, клетка будет живой.
    6. Программа останавливается, если выполняется хотя бы одно из двух условий: достигнуто максимальное количество итераций max_iterations (притом считается, что если max_iterations = 0, ограничение на количество итераций отсутствует), система пришла в стационарное состояние, то есть, g=g+1.
    7. Определение стационарного состояния осуществляется поклеточным сравнением поколений g и g+1.
    8. В программе используются параллельные секции. Например в функциях (void process_output(…) и void process_no_output) параллельные потоки используются в качестве ускорения процесса обработки. Так в обеих функциях используется директива #pragma omp parallel for, которая позволяет распределить вычисление между потоками.

    Для визуального представления программы на рисунке 1 представлен результат выполнения программы. А на рисунке 2 загрузка ядер при выполнении программы:

    Начальная фигура

    Gosper glider gun

    Beacon

    Случайные числа

    Время выполнения, мс

    Размер поля

    100×100

    50x50

    100×100

    4×4

    200×200

    Ограничение количества итераций

    20 000

    915

    336

    909

    59

    3253

    40 000

    1764

    533

    1821

    112

    6385

    80 000

    3454

    1270

    3549

    227

    12776

    160 000

    7114

    2015

    8224

    429

    24561

    640 000

    27365

    7915

    27255

    1335

    115765

    Исходный код программы:

    #include <iostream>
    #include <fstream>
    #include <thread>
    
    using namespace std;
    
    #define FILL_CHAR 219
    #define EMPTY_CHAR 255
    
    void print(unsigned int generation, char *print_arr) {
    	printf("Generation:%i\n%s\n", generation, print_arr);
    }
    
    bool equals(bool *array1, bool *array2, unsigned int n, unsigned int m) {
    	for (unsigned int i = 0; i < n; i++) //
    		for (unsigned int j = 0; j < m; j++)
    			if (array1[i * m + j] != array2[i * m + j])
    				return false;
    	return true;
    }
    unsigned short inline get(bool *array, unsigned int n, unsigned int m, unsigned int x, unsigned int y) { 
    														if (x < 1 || y < 1 || x > m || y > n) return 0; 
    	return array[(y - 1) * m + (x - 1)];
    }
    
    void process_output(bool *array1, bool *array2, char *print_arr, unsigned int n, unsigned int m) {
    #pragma omp parallel for
    	for (__int64 i = 0; i < (__int64)n; i++)
    	{
    		for (unsigned int j = 0; j < m; j++) {
    			unsigned short alive_near = get(array1, n, m, j, i) +
    				get(array1, n, m, j, i + 1) +
    				get(array1, n, m, j, i + 2) +
    				get(array1, n, m, j + 1, i) +
    				get(array1, n, m, j + 1, i + 2) +
    				get(array1, n, m, j + 2, i) +
    				get(array1, n, m, j + 2, i + 1) +
    				get(array1, n, m, j + 2, i + 2);
    			
    			if (alive_near > 3)
    			{
    				array2[i * m + j] = false;
    				print_arr[i*(m + 1) + j] = EMPTY_CHAR;
    			}
    			else if (alive_near > 2)
    			{
    				array2[i * m + j] = true;
    				print_arr[i*(m + 1) + j] = FILL_CHAR;
    			}
    			else if (alive_near > 1)
    			{
    				array2[i * m + j] = array1[i * m + j];
    				print_arr[i*(m + 1) + j] = array1[i*m + j] ? FILL_CHAR : EMPTY_CHAR;
    			}
    			else			{
    				array2[i * m + j] = false;
    				print_arr[i*(m + 1) + j] = EMPTY_CHAR;
    			}
    		}
    		print_arr[m + i*(m + 1)] = '\n';
    	}
    	print_arr[n*(m + 1) - 1] = '\0';
    }
    
    void process_no_output(bool *array1, bool *array2, unsigned int n, unsigned int m) {
    #pragma omp parallel for
    	for (__int64 i = 0; i < (__int64)n; i++)
    	{
    		for (unsigned int j = 0; j < m; j++) {
    			unsigned short alive_near = get(array1, n, m, j, i) +
    				get(array1, n, m, j, i + 1) +
    				get(array1, n, m, j, i + 2) +
    				get(array1, n, m, j + 1, i) +
    				get(array1, n, m, j + 1, i + 2) +
    				get(array1, n, m, j + 2, i) +
    				get(array1, n, m, j + 2, i + 1) +
    				get(array1, n, m, j + 2, i + 2);
    			
    			if (alive_near > 3
    			{
    				array2[i * m + j] = false;
    			}
    			else if (alive_near > 2)
    			{
    				array2[i * m + j] = true;
    			}
    			else if (alive_near > 1)
    			{
    				array2[i * m + j] = array1[i * m + j];
    			}
    			else			{
    				array2[i * m + j] = false;
    			}
    		}
    	}
    }
    
    int main(int argc, char *argv[]) {
    	ifstream in("in.txt");
    	unsigned int n;
    	unsigned int m; 
    	unsigned int delay; 
    	unsigned int max_iterations; 
    	bool output; 
    	in >> n >> m >> delay >> max_iterations >> output; 
    
    	
    bool *array1 = new bool[n * m];
    	bool *array2 = new bool[n * m];
    	
    
    	if (output) 
    	{
    		char *print_arr = new char[n*(m + 1)]; 
    for (unsigned int i = 0; i < n; i++)
    		{
    			for (unsigned int j = 0; j < m; j++)
    			{
    				in >> array1[i * m + j];
    				print_arr[i*(m + 1) + j] = array1[i*m + j] ? FILL_CHAR : EMPTY_CHAR;
    			}
    			print_arr[m + i*(m + 1)] = '\n';
    		}
    		printf_s("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
    		print_arr[n*(m + 1) - 1] = '\0';
    		
    print(0, print_arr);
    		this_thread::sleep_for(chrono::milliseconds(delay));
    
    		unsigned int generation = 0;
    
    		while (true) {
    			
    			chrono::steady_clock::time_point start, end;
    			start = chrono::steady_clock::now();
    
    			process_output(array1, array2, print_arr, n, m);
    			print(++generation, print_arr);
    
    			if (equals(array1, array2, n, m) || max_iterations != 0 && generation >= max_iterations)
    				break;
    			
    			end = chrono::steady_clock::now();
    
    			__int64 time = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    			if (time < delay) 
    			{
    				this_thread::sleep_for(
    					chrono::milliseconds(delay - time)); 
    			}
    			bool *temp = array1;
    			array1 = array2;
    			array2 = temp;
    		}
    	}
    
    
    	else	{
    		chrono::steady_clock::time_point start, end;
    		start = chrono::steady_clock::now();
    		for (unsigned int i = 0; i < n; i++)
    		{
    			for (unsigned int j = 0; j < m; j++)
    			{
    				in >> array1[i * m + j];
    			}
    		}
    		unsigned int generation = 0;
    		while (true) {
    		process_no_output(array1, array2, n, m);
    			generation++;
    			if (equals(array1, array2, n, m) || max_iterations != 0 && generation >= max_iterations)
    				break;
    			
    			bool *temp = array1;
    			array1 = array2;
    			array2 = temp;
    		}
    		end = chrono::steady_clock::now();
    		__int64 time = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    		ofstream out("out.txt");
    		out << "Time, milliseconds: " << time;
    	}
    	return 0;
    }

Для ответа в этой теме необходимо авторизоваться.