Это я уже сделал, кстати, тем же методом, что предложили и вы(просматривать окрестности только живых клеток). Поэтому я прописываю остальной функционал.
В общем, я реализовал «бесконечное» поле для игры «Жизнь». Но как проверить работоспособность, я не знаю, поле слишком большое, клетки попросту не получается найти :) Здесь архив.
(1) Я тебе писал, что лучше использовать знаковый тип для координат. Тогда бы проблем было меньше: обычным rand() можно было бы нагенерить клеток в районе (0, 0) и смотреть за тем, как они расползаются по бесконечному полю.
(2) Генерить клетки по всему «бесконечному» полю — плохая идея. Лучше зародить жизнь в достаточно компактной области, скажем, 20х20 ячеек. Тут опять см. (1)
(3) Даже в твоей реализации оттестировать правильность работы алгоритма можно достаточно просто. В методе GameMan::randomize() убрать случайную генерацию клеток и вставить фрагмент с расстановкой клеток. Например так:
Прошу прощения за долгий ответ, бубунта на ноутбуке поломалась, пока переустанавливал и прочей восстановительной фигнёй занимался...
лучше использовать знаковый тип для координат
Наверное, я тупой, но я не могу понять, почему использовать знаковый тип лучше. По идее, если генерировать, случайную расстановку в районе (0;0), то нет разницы знаковый тип или нет.
можно достаточно просто
Чёрт, почему я до этого не додумался? :\
Генерация нового поколения происходит неправильно
Да, действительно, но я не могу найти ошибку.
Единственные места, где она может быть это calculate(), getLifeNeib(), getCell() и setCell() но я не вижу здесь ни каких ошибок. :(
Наверное, я тупой, но я не могу понять, почему использовать знаковый тип лучше.
Скорее не «лучше», а «удобнее». При знаковом типе начало координат (0, 0) совпадает с серединой диапазона. При беззнаковом — улетает в угол. Но по большому счёту — вопрос религии ))
Обнаружил ещё одну багу: у тебя некачественная хэш-функция. Если (в целях отладки) написать так:
То твоя хэш-функция на это 0-поколение и на следующее поколение выдаёт одинаковое значение 3. После чего всякая жизнь в программе прекращается с диагнозом «повтор позиции». Что есть неправильно. При расчёте по твоему алгоритму все должны умереть только на следующем поколении. Т.е. должно быть показано 3 картинки: начальное, 2 одиноких микроба и «все умерли».
Кстати, тут у тебя ещё и баг в показе. Из-за выхода из функции GameMan::nextGeneration() по исключению не отображается последняя позиция, которая вызвала это исключение. (А я тебе ещё давно говорил, что исключения не надо использовать для управления потоком выполнения программы!)
Для хэша я бы посоветовал, например, использовать crc32, как простой, быстрый и легкий алгоритм. Вот вариант заточенный под твою специфику:
У тебя LifeMap::getLifeNeib() неправильно считает. Саму клетку не надо учитывать как «соседа».
//Получить количество живых соседей у клетки
int LifeMap::getLifeNeib( lsize_t x, lsize_t y ) const
{
int count = 0;
for ( int i = -1; i < 2; i++ )
for ( int j = -1; j < 2; j++ )
{
if ( isValidCoord( x + i, y + j ) && !(i == 0 && j == 0)) // <-- !
if ( getCell( x + i, y + j ) )
count++;
}
return count;
}
И список надо бы очищать перед новым поколением:
//Расчитать поле, исходя из предыдущего поколения, которое передаётся в метод
void LifeMap::calculate( const LifeMap &prev )
{
//Если размеры карт не совпадают, ничего не делаем
if ( nSize != prev.nSize || mSize != prev.mSize )
return;
map.clear(); // <-----
int n;
//Пробегаться будем по живым клеткам предыдущего поля
for ( std::list<coord>::const_iterator it = prev.map.begin(); it != prev.map.end(); it++ )
{
И ты решил, что с этой задачей покончено? А как же оптимизация? Отлов багов? Рефакторинг?
Кстати, тему ты поднял «Оценка( критика ) кода». А код твой пока далёк от совершенства.
Даже вот чисто технически:
void LifeMap::calculate( const LifeMap &prev )
{
//Если размеры карт не совпадают, ничего не делаем
if ( nSize != prev.nSize || mSize != prev.mSize )
return;
map.clear();
int n;
//Пробегаться будем по живым клеткам предыдущего поля
for ( std::list<coord>::const_iterator it = prev.map.begin(); it != prev.map.end(); it++ )
{
//Пробегаемся по всем соседям живой клетки
for ( int i = -1; i < 2; i++ )
for ( int j = -1; j < 2; j++ )
{
if ( isValidCoord( it->x + i, it->y + j ) )
{
n = prev.getLifeNeib( it->x + i, it->y + j );
if ( prev.getCell( it->x + i, it->y + j ) )
{
//Если у клетки есть два или три живых соседа, сделать клетку на формируемом поле живой
if ( n == 2 || n == 3 )
setCell( it->x + i, it->y + j, true );
else setCell( it->x + i, it->y + j, false );
}
else
{
//В мертвой клетке, рядом с которой ровно 3 живых клетки, зарождается жизнь
if ( n == 3 )
setCell( it->x + i, it->y + j, true );
else setCell( it->x + i, it->y + j, false );
}
}
}
}
}
Выражения типа it->x + i вычисляются многократно. А если ещё учесть, что it — это не простой указатель, а итератор...
Многочисленные повторные вызовы isValidCoord(). Оно хоть и инлайновое, но проверки-то всё равно происходят.
Кроме того, я не уверен, что твоя реализация алгоритма оптимальна. Но про это я пока не буду говорить. Если у меня будет время, я напишу свою реализацию, или хотя бы проанализирую досконально твой код, вот тогда я смогу аргументированно побеседовать на данную тему.
И ты решил, что с этой задачей покончено? А как же оптимизация? Отлов багов? Рефакторинг?
Если честно, да. (всё-таки пару багов я отловил, но на этом и остановился)
На счёт оптимизации. Единственное что я могу придумать, это заменить std::find в setCell и getCell на что-нибудь более интеллектуальное, например, бинарный поиск.
На счёт постоянных проверок координат. А как от них избавиться?
Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.
Это я уже сделал, кстати, тем же методом, что предложили и вы(просматривать окрестности только живых клеток). Поэтому я прописываю остальной функционал.
В общем, я реализовал «бесконечное» поле для игры «Жизнь». Но как проверить работоспособность, я не знаю, поле слишком большое, клетки попросту не получается найти :)
Здесь архив.
(1) Я тебе писал, что лучше использовать знаковый тип для координат. Тогда бы проблем было меньше: обычным
rand()можно было бы нагенерить клеток в районе (0, 0) и смотреть за тем, как они расползаются по бесконечному полю.(2) Генерить клетки по всему «бесконечному» полю — плохая идея. Лучше зародить жизнь в достаточно компактной области, скажем, 20х20 ячеек. Тут опять см. (1)
(3) Даже в твоей реализации оттестировать правильность работы алгоритма можно достаточно просто. В методе
GameMan::randomize()убрать случайную генерацию клеток и вставить фрагмент с расстановкой клеток. Например так:Или сделать несколько отладочных методов с фиксированной расстановкой и вызывать один из них вместо
GameMan::randomize().(4) Генерация нового поколения происходит неправильно. Используя вышеприведённый фрагмент для начальной расстановки, должны получить следующее:
У тебя получается другая позиция.
Прошу прощения за долгий ответ, бубунта на ноутбуке поломалась, пока переустанавливал и прочей восстановительной фигнёй занимался...
Наверное, я тупой, но я не могу понять, почему использовать знаковый тип лучше. По идее, если генерировать, случайную расстановку в районе (0;0), то нет разницы знаковый тип или нет.
Чёрт, почему я до этого не додумался? :\
Да, действительно, но я не могу найти ошибку.
Единственные места, где она может быть это
calculate(),getLifeNeib(),getCell()иsetCell()но я не вижу здесь ни каких ошибок. :(Скорее не «лучше», а «удобнее». При знаковом типе начало координат (0, 0) совпадает с серединой диапазона. При беззнаковом — улетает в угол. Но по большому счёту — вопрос религии ))
Обнаружил ещё одну багу: у тебя некачественная хэш-функция. Если (в целях отладки) написать так:
То твоя хэш-функция на это 0-поколение и на следующее поколение выдаёт одинаковое значение 3. После чего всякая жизнь в программе прекращается с диагнозом «повтор позиции». Что есть неправильно. При расчёте по твоему алгоритму все должны умереть только на следующем поколении. Т.е. должно быть показано 3 картинки: начальное, 2 одиноких микроба и «все умерли».
Кстати, тут у тебя ещё и баг в показе. Из-за выхода из функции
GameMan::nextGeneration()по исключению не отображается последняя позиция, которая вызвала это исключение. (А я тебе ещё давно говорил, что исключения не надо использовать для управления потоком выполнения программы!)Для хэша я бы посоветовал, например, использовать crc32, как простой, быстрый и легкий алгоритм. Вот вариант заточенный под твою специфику:
А вот так оно применяется с минимальными изменениями твоего кода:
Где конкретно ошибка я не разбирался, но судя по всему, у тебя не зарождается новая жизнь в мёртвых клетках. Скорее всего, это в
LifeMap::calculate().UPD. Хотя нет, зарождается. Ошибся. Зато старые клетки вымирают как от эпидемии ((
У тебя
LifeMap::getLifeNeib()неправильно считает. Саму клетку не надо учитывать как «соседа».И список надо бы очищать перед новым поколением:
Спасибо большое, теперь код работает исправно.
И ты решил, что с этой задачей покончено? А как же оптимизация? Отлов багов? Рефакторинг?
Кстати, тему ты поднял «Оценка( критика ) кода». А код твой пока далёк от совершенства.
Даже вот чисто технически:
Выражения типа
it->x + iвычисляются многократно. А если ещё учесть, чтоit— это не простой указатель, а итератор...Многочисленные повторные вызовы
isValidCoord(). Оно хоть и инлайновое, но проверки-то всё равно происходят.Кроме того, я не уверен, что твоя реализация алгоритма оптимальна. Но про это я пока не буду говорить. Если у меня будет время, я напишу свою реализацию, или хотя бы проанализирую досконально твой код, вот тогда я смогу аргументированно побеседовать на данную тему.
Если честно, да. (всё-таки пару багов я отловил, но на этом и остановился)
На счёт оптимизации. Единственное что я могу придумать, это заменить
std::findвsetCellиgetCellна что-нибудь более интеллектуальное, например, бинарный поиск.На счёт постоянных проверок координат. А как от них избавиться?
Отщеплен новый топик «Сумма покупки нескольких товаров».