Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Проверка на совпадение одинаковых шариков, в игре Lines. помогите с оптимизацией 
:(
    Опции темы
Sergio
  Дата 18.12.2008, 16:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: нет
Всего: 1
Всем привет. Следующий код находит совпадения подряд шариков (как в игре Lines) в двомерном массиве.
Код

    for (int a=0; a<PLAY_FIELD_WIDTH; a++) 
        for (int b=0; b<PLAY_FIELD_HEIGHT; b++)
        {
            if (gBallField[a][b].BALL_TYPE == gBallField[a+1][b].BALL_TYPE == gBallField[a+2][b].BALL_TYPE == gBallField[a+3][b].BALL_TYPE == BALL_1_TYPE)
            {
                gBallField[a][b].BALL_TYPE = gBallField[a+1][b].BALL_TYPE = gBallField[a+2][b].BALL_TYPE = gBallField[a+3][b].BALL_TYPE = BALL_EMPTY_TYPE;
                return 4;
            }
            else if (gBallField[a][b].BALL_TYPE == gBallField[a-1][b].BALL_TYPE == gBallField[a-2][b].BALL_TYPE == gBallField[a-3][b].BALL_TYPE == BALL_1_TYPE)
            {
                gBallField[a][b].BALL_TYPE = gBallField[a-1][b].BALL_TYPE = gBallField[a-2][b].BALL_TYPE = gBallField[a-3][b].BALL_TYPE = BALL_EMPTY_TYPE;
                return 4;
            }
            else if (gBallField[a][b].BALL_TYPE == gBallField[a][b+1].BALL_TYPE == gBallField[a][b+2].BALL_TYPE == gBallField[a][b+3].BALL_TYPE == BALL_1_TYPE)
            {
                gBallField[a][b].BALL_TYPE = gBallField[a][b+1].BALL_TYPE = gBallField[a][b+2].BALL_TYPE = gBallField[a][b+3].BALL_TYPE = BALL_EMPTY_TYPE;
                return 4;
            }
        }

И это только для одного типа шарика. Всего их 4 (BALL_1_TYPE, BALL_2_TYPE, BALL_3_TYPE, BALL_4_TYPE). BALL_EMPTY_TYPE делает клетку пустой. 
Функуия возращает количество заработаных очков .
Как видите алгоритм очень плохой для читабельности и т д. Как можно оптимизировать?
Спасибо.

Это сообщение отредактировал(а) Sergio - 18.12.2008, 16:51
PM MAIL ICQ   Вверх
maxdiver
Дата 18.12.2008, 17:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18
Код
for (int type=BALL_1_TYPE; type<=BALL_4_TYPE; ++type)
    for (int a=0; a<PLAY_FIELD_WIDTH; a++)
        for (int b=0; b<PLAY_FIELD_HEIGHT; b++) {
            const int dxy[3][2] = { {1,0}, {-1,0}, {0,1} };
            for (int d=0; d<3; ++d) {
                bool ok = true;
                for (int x=a, y=b, i=0; i<4; ++i, x+=dxy[d][0], y+=dxy[d][1])
                    ok &= gBallField[x][y] == type;
                if (ok) {
                    for (int x=a, y=b, i=0; i<4; ++i, x+=dxy[d][0], y+=dxy[d][1])
                        gBallField[x][y] = BALL_EMPTY_TYPE;
                    return 4;
                }
            }
        }
return 0;

примерно так, не компилил.

Добавлено через 3 минуты и 38 секунд
И, кстати, не понял у вас такого оборота:
Код
if (a == b == c == d == some_value)

Вообще-то, operator== возвращает только true/false, а не само значение. Вот для присвоения это будет работать нормально, а для проверки на равенство - нет.
PM MAIL WWW ICQ   Вверх
maxim1000
Дата 18.12.2008, 18:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110
какие направления возможны? только горизонтальные/вертикальные? или диагональные?
в целом, можно так:
проходимся по всему полю
для каждой клеточки предполагаем, что шарик является крайним в линии
проверяем в каждом из 8 направлений количество шариков
если больше порога - помечаем их удалёнными, удалять сразу не стоит, т.к. один шарик может участвовать в нескольких линиях

на самом деле, можно проверять только половину направлений
например необязательно проверять направление вниз, если мы и так отлавливаем все направления вверх - мы обнаружим эту линию позже, при анализе нижнего шарика

т.е. получается что-то вроде такого:
Код

void CheckLine(TField &field,int x,int y,int dx,int dy)
{
    int count=0;
    for(int c=1;c<std::max(width,height);++c)
    {
        if(field[x+c*dx][y+c*dy]!=field[x][y])
            break;
        ++count;
    }
    if(count<threshold)
        return;
    for(int c=0;c<count;++c)
        MarkAsDeleted(field,x+c*dx,y+c*dy);
}
...
for(int x=0;x<width;++x)
{
    for(int y=0;y<height;++y)
    {
        if(NotEmpty(field,x,y))
            continue;
        CheckLine(field,x,y,1,0);
        CheckLine(field,x,y,0,1);
        CheckLine(field,x,y,1,1);
        CheckLine(field,x,y,1,-1);
    }
}



--------------------
qqq
PM WWW   Вверх
Sergio
Дата 18.12.2008, 19:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: нет
Всего: 1
Цитата

какие направления возможны? только горизонтальные/вертикальные? или диагональные?

maxim1000, диагональные тоже нужны. Можно ещё описать выше написаный код?
Не очень понятен этот кусок
Код

    if(count<threshold)
        return;


Это сообщение отредактировал(а) Sergio - 18.12.2008, 19:54
PM MAIL ICQ   Вверх
maxim1000
Дата 18.12.2008, 21:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110
Цитата(Sergio @  18.12.2008,  19:00 Найти цитируемый пост)
Не очень понятен этот кусок

для простоты предположим, что нас интересуют только горизонтальные направления
тогда функция CheckLine делает две вещи:
1. смотрит, сколько шариков такого же цвета справа от выбранного (x,y)
2. если их количество больше какого-то порога, то помечает их удалёнными
можно переписать её по-другому:
Код

void CheckLine(TField &field,int x,int y,int dx,int dy)
{
    int count=0;
    for(int c=1;c<std::max(width,height);++c)
    {
        if(field[x+c*dx][y+c*dy]!=field[x][y])
            break;
        ++count;
    }
    if(count>=threshold)
    {
        for(int c=0;c<count;++c)
            MarkAsDeleted(field,x+c*dx,y+c*dy);
    }
}

порог - это то минимальное количество шариков в линии, чтобы она удалилась
в данном случае - 4


--------------------
qqq
PM WWW   Вверх
Sergio
  Дата 19.12.2008, 14:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: нет
Всего: 1
теперь понял. smile спасибо. 
Ещё вопросик: зачем вичислать максимум из этих переменных?
Код

...
 for(int c=1;c<std::max(width,height);++c)
...



Это сообщение отредактировал(а) Sergio - 19.12.2008, 14:53
PM MAIL ICQ   Вверх
Mayk
Дата 19.12.2008, 14:44 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


^аВаТаР^ сообщение>>
****


Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134
Если это реализация lines, то нужно не так. В lines есть удобный инвариант: прямо перед ходом игрока на поле никогда нет линии из 4 и более шариков одинакового цвета. Данный инвариант может быть нарушен  только в момент добавления шарика или перемещения шарика игроком. 

То есть проверку надо делать только при добавлении шарика или только при переносе шарика в новую позицию. А дальше уже просто - проверяем на образование линий и вуаля.
 примерно так:

Код

def lineLength(color, x,y, dx,dy):
    return длина линии из шариков цвета color, первая точка линии в (x+dx, y+dy), вторая точка линии в (x+dx+dx, y+dy+dy) и тд

def checkForNewLine(x,y):
  color = colorAt(x,y)
  lengthN = lineLength(color, x,y, 0,-1) 
  lengthS = lineLength(color, x,y, 0, 1) 

  lengthW = lineLength(color, x,y, -1,0) 
  lengthE = lineLength(color, x,y, 1, 0) 

  if lengthN+lengthS > 4:
      deleteLine(x,y,0,-1, lengthN) 
      deleteLine(x,y,0, 1, lengthS) 
  if lengthW+lengthE > 4:
      deleteLine(x,y,0,-1, lengthW)
      deleteLine(x,y,0, 1, lengthE) 



Это сообщение отредактировал(а) Mayk - 19.12.2008, 14:51


--------------------
 Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.
PM MAIL WWW ICQ   Вверх
maxim1000
Дата 19.12.2008, 21:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110
Цитата(Sergio @  19.12.2008,  14:34 Найти цитируемый пост)
Ещё вопросик: зачем вичислать максимум из этих переменных?

ну это что-то типа максимально возможной длины
хотя. конечно, field должен выдавать "пусто" на клетках снаружи поля




--------------------
qqq
PM WWW   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0562 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.