CyberForum.ru - Форум программистов и сисадминов
Вернуться   Форум программистов и сисадминов CyberForum.ru > Форум программистов > Форум C++

Ответ Создать новую тему
 
Старый 17.07.2011, 17:42   #1
BadBaddak
Новичок
 
Регистрация: 09.06.2010
Сообщений: 85
Репутация: 59 (2)
По умолчанию Решение игры "вирус"?

В инете есть много флеш игр на тему вирусов. Поле поделено на квадраты из нескольких цветов и нужно всё заразить на наименьшее число ходов.
Хочу потренироваться находить решения таких задач.
Для примера возьмём "Перекрась поле!". Поле 14*14 клеток, 6 разных цветов, главная клетка - верхняя левая, дают 30 ходов. Поле в программу вбивать пока придётся в ручную. С чего начать создание решалки? Алгоритм дума сделать полным перебором, как просчитываются перекрашивания? Наверное придётся вводить 6 чисел для обычных клеток + 6 для вирусных. Поле лучше делать в виде чисел в массиве, или символов в строках?
BadBaddak вне форума
Другие темы раздела
C++ Multyplayer Game Server
Здравствуйте, захотелось для общего развития написать игрушку реального времени, но для этого надо иметь сервер. Можно написать все это самому, но охота узнать есть ли какие готовые продукты какими все пользуются, что-бы можно было использовать выбранную платформу в дальнейшем а не каждый раз.... Multyplayer Game Server
Критика архитектуры набора планов C++
Требуется создать систему похожую на Hierarchical task network то есть некоторая библиотека планов и каждый план может содержать подпланы, получать результаты выполнения подпланов и передавать их в другие подпланы используется в системе управления ботами в командной реалтайм игре. пока мои.... Критика архитектуры набора планов
Старый 23.07.2011, 01:14   #11
voral
Форумчанин
 
Регистрация: 16.03.2008
Адрес: Иваново
Сообщений: 594
Репутация: 113 (101)
По умолчанию Re: Решение игры "вирус"?

Цитата Сообщение от BadBaddak Посмотреть сообщение
Пока такой кусок. Подскажите, как лучше из отдельных строк делать один массив байт?
У тебя файл содержит все поле. Т.е. выглядит как массив (один символ на ячйку). Н у так все просто:
Код C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
freopen("game.dat", "r", stdin);
char c;
int i=0;
int j=0;
while (c=getchar())!=EOF)
{
    if (c=="\n")
   {
     ++i;
     j=0;
   }
   else 
  {
    A[i][j]=c;
    ++j;
  }
}
 
Вот такая заготовка. Только обязательно нужно:
1 обработать ситуацию когда символов в строке или количество строк отличается от размеров массива.
2 обработать ситуацию, когда среди всех окажется "чужеродный сивол" (например испоьзуете только три цвета R, G и B..... Массив должен содержать только их, но вдруг там еще Х)
voral вне форума
Старый 24.07.2011, 18:38  [ТС]   #12
BadBaddak
Новичок
 
Регистрация: 09.06.2010
Сообщений: 85
Репутация: 59 (2)
По умолчанию Re: Решение игры "вирус"?

Разобрался немного. (Про getchar() не знал, в учебнике по строкам работают)
До 29 строки не дойдёт, потому что у меня из цикла выход через ретурн стоит. Файл надо переоткрыть, чтоб строки читались с начала. Процедура будет заполнять массив A и сразу показывает исходное положение на поле:
Код C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ShowPole()
{
    fp = fopen ( "pole.txt", "r" );
    // из файла заполняем массив по буквенно
    for (i=0; i<Strok; i++) {
        fgets ( s, 80, fp ); 
        for (j=0; j<Stolb; j++){
            A[i][j]=s[j]; // побуквенно заполняем массив
        }
    }
 
    //вывод массива в консоль
    for ( i = 0; i < Stolb; i ++ ){
        for ( j = 0; j < Strok; j ++ ){
            printf ( "%2c", A[i][j] );
        }
        printf("\n");
    }
 
    fclose ( fp );
}
Добавлено через 18 часов 34 минуты
Сделаю ещё один массив для букв-цветов. Полный перебор по полю поможет определить сколько и какие буквы там есть. Это сделаю. Думаю как лучше организовать перебор всех вариантов? Есть может у кого пример? Если 6 цветов, попробуем перебрать 10 ходов, то всего 6*5*5*5*5*5*5*5*5*5=50.4 миллиона вариантов многа...

Добавлено через 22 часа 49 минут
Эта процедура смотрит какие цвета есть на поле, и делает их них массив. Кроме того показывает их на консоли. Вроде работает правильно.
Код C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void SetColor()
{
    //перебор массива и заполнение цветов
    for (k=0; k<10; k++) color[k]=0; // обнуляем
 
    for ( i = 0; i < Stolb; i ++ ){
        for ( j = 0; j < Strok; j ++ ){
            for (k=0; k<10; k++){ // перебор массива цветов
                if (color[k]==0) { // если ноль, пишем новый цвет
                    color[k]=A[i][j];
                    break; // выход на след клетку поля
                }
                if (color[k]==A[i][j]) { // если та же буква, то след буква
                    break;
                }
            }
        }
     }
     // сколько цветов
    for (k=0; k<10; k++){
        if (color[k]!=0) numcolor++;
    }
    printf ("vsego tsvetov: %d \n",numcolor);
 
    // вывод массива цветов
    for (k=0; k<numcolor; k++){
        printf ("%d %c \n",k+1,color[k]);
    }
}

Последний раз редактировалось BadBaddak; 23.07.2011 в 01:18. Причина: getchar()
BadBaddak вне форума
Старый 03.02.2012, 13:38  [ТС]   #13
BadBaddak
Новичок
 
Регистрация: 09.06.2010
Сообщений: 85
Репутация: 59 (2)
По умолчанию Re: Решение игры "вирус"?

Код C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int zaragenie(char ColorVir)
{
    // перебор поля, чтобы определить сколько клеток можно заразить
    // дублируем с массива A на изменяемый B
    for ( i = 0; i < Strok; i ++ ){
        for ( j = 0; j < Stolb; j ++ ){
            B[i][j]=A[i][j];
        }
     }
 
     int flag=0;
     skolkozarazaem=0;
     while (flag==0) // хотя бы одна заразилась
     {
         for ( i = 0; i < Strok; i ++ )
         {
            for ( j = 0; j < Stolb; j ++ )
            {
                // заражаем соседние клетки
                if (B[i][j]=='.') {
                   
                    // заражаем клетку СНИЗУ
                    if (i<Strok && B[i+1][j]==ColorVir){
                        B[i+1][j]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
 
                    // заражаем клетку СВЕРХУ
                    if (i>0 && B[i-1][j]==ColorVir){
                        B[i-1][j]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
 
                    // заражаем клетку СПРАВА
                    if (j<Stolb && B[i][j+1]==ColorVir){
                        B[i][j+1]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
 
                    // заражаем клетку СЛЕВА
                    if (j>0 && B[i][j-1]==ColorVir){
                        B[i][j-1]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
                }
            }
         }
         if (flag==0) return skolkozarazaem;
         flag=0;
     }
}
 
Вот функция заражения. В неё передаётся цвет вируса, возвращается количество заражаемых клеток. Глядя на экран человек выбирает какой именно цвет надо заразить, происходит заражение и массив B переписывается в массив А. Всё повторяется.
Но это ручное заражение на основании ближайших клеток. Может сделать не "больше клеток заразить" а какое-нибудь другое условие?
Миниатюры
Нажмите на изображение для увеличения
Название: 2012-02-03_141254.png
Просмотров: 15
Размер:	9.3 Кб
ID:	124855  
BadBaddak вне форума
Старый 07.02.2012, 10:02   #14
taras atavin
Нарушитель
 
Регистрация: 24.11.2009
Адрес: Где то в сетке
Сообщений: 11,931
Репутация: 1080 (736)
По умолчанию Re: Решение игры "вирус"?

Я предлагаю перебор на всю глубину в 30 ходов.
taras atavin вне форума
Старый 08.02.2012, 12:38   #15
iama
Серая масса
Эксперт C++
 
Аватар для iama
 
Регистрация: 30.07.2010
Адрес: 0xDEADBEEF
Сообщений: 3,444
Репутация: 1008 (757)
По умолчанию Re: Решение игры "вирус"?

taras atavin, асимптотика решения - O(C^M), где C - колличество цветов, M - колличество ходов. Для 6 цветов и 30 ходов будет работать около недели, если красивое решение будет, с малыми константами, скрытыми в асимптотике. У вас в статусе все верно написано.
iama вне форума
Старый 17.02.2012, 03:12  [ТС]   #16
BadBaddak
Новичок
 
Регистрация: 09.06.2010
Сообщений: 85
Репутация: 59 (2)
По умолчанию Re: Решение игры "вирус"?

ухх... пошел по пути лёгкого кода
Простой генератор случайных чисел RandCol=rand()%numcolor;, выбирается один из цветов. Если заражения не происходит, то цвет перевыбирается. Успешно заражаемые цвета постепенно скидываются в массив ходов, счётчик++, цикл повторяется пока всё не заразим.
Если текущий проход завершился за меньшее количество ходов, чем предыдущие, то выводим массив последовательности на консоль.
Пока мыл посуду, комп нашел вариант с 20 ходами. Обратите внимание, что цвет Y заражает одним разом 27 клеток. (не говорите про HODOV, сам знаю )
Миниатюры
Нажмите на изображение для увеличения
Название: F7Ue2Um6.png
Просмотров: 17
Размер:	37.0 Кб
ID:	127790   Нажмите на изображение для увеличения
Название: VfWX6678.png
Просмотров: 15
Размер:	10.6 Кб
ID:	127791  
BadBaddak вне форума
Старый 24.02.2012, 02:56  [ТС]   #17
BadBaddak
Новичок
 
Регистрация: 09.06.2010
Сообщений: 85
Репутация: 59 (2)
По умолчанию Re: Решение игры "вирус"?

Сделал оптимизацию: если при переборе найдено минимальное число ходов, оно запоминается. Если следующее заражение идёт за бОльшее число ходов, оно не просчитывается до конца, а пропускается. На скрине видно, что за 9 секунд просчитало 66 тысяч вариантов.
Прога сканирует цвета на экране, заносит поле в массив, просчитывает на минимально возможное число ходов рандомным перебором, каждое найденное решение пишется поверх старого. Вручную заражаю тот цвет, который первый в строке, поле перекрашивается, перезапускаю скнирование и т.д.
После решения последнего десятого уровня у меня стало больше 10 миллионов очков. Игра решена и пройдена!
Миниатюры
Нажмите на изображение для увеличения
Название: 2012-02-24_034401.png
Просмотров: 16
Размер:	47.0 Кб
ID:	129459  
BadBaddak вне форума
После регистрации реклама в сообщениях будет скрыта
Старый 27.03.2012, 10:16   #18
talis
Форумчанин
 
Аватар для talis
 
Регистрация: 11.05.2010
Адрес: talis_t * ptr = &talis;
Сообщений: 1,186
Репутация: 675 (482)
По умолчанию Re: Решение игры "вирус"?

BadBaddak, в качестве оптимизации: если проц многоядерный, посмотрите в сторону поиска решения в нескольких параллельных потоках.

Да, и вместо копирования массива в цикле поэлементно, попробуйте через memcpy() :-)
talis вне форума
Ответ Создать новую тему

Похожие темы
Тема Автор
C# для начинающих Реализация Игры "Жизнь" из книги Уэзерелл Ч. "Этюды для программистов"
Кто нибудь встречал ее нга с#??? Если у кого-то есть, вы не могли бы выложить исходник?
demon_666_902
C# для начинающих Игра "Змейка", ошибка "Globals.Close не объявлен", неправильная логика игры
Нашёл в интернете код игры "змейка" и саму скомпилированную игру. Но есть загвоздка. А точнее две using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using...
Ney4
Pascal (Паскаль) Решение заданий типа "Array","Matrix","String","File","Text"""
большая просьба помочь решить где-то около 35-40 (из 100) задач (мне не понятных) типа массив и матрица я буду рад (да и если у кого будет желание) если кто нибудь будет давать еще пояснения к задача необязательно но желательно. сам я уже перегрузился от этих задач уже торможу (Меня девушка уже...
tork113
Turbo Pascal из слова "вирус" путем замены его букв получить слово "фокус"
из слова "вирус" путем замены его букв получить слово "фокус"
Возбуждающая
C++ Builder Создание игры "монополия" или по-другому "менеджер"
Доброго всем дня, задача ставится, написать игру с возможностями OpenGL, дабы создать красочное меню и анимацию, игра подразумевает работа с сетью(но это решабельный вопрос, будут использоваться компоненты TServerSocket и TClientSocket, с ними все понятно), игра будет по сети. Чтобы я хотел узнать...
GaFBich
Опции темы

Текущее время: 00:58. Часовой пояс GMT +4.

Компьютерный форум программистов и сисадминов
Powered by vBulletin® Version 3.8.7 PL2
Copyright ©2000 - 2012, vBulletin Solutions, Inc.
Рейтинг@Mail.ru Яндекс.Метрика