Отправляет email-рассылки с помощью сервиса Sendsay

Программирование игр в Linux

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "LinuxCenter News Channel: новости Linux" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Январь 2004   →
 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
Автор
Evgeny

Статистика

2.028 подписчиков
-1 за неделю
←   Все выпуски   →

Programming Linux Games 03


Информационный Канал Subscribe.Ru

Programming Linux Games

Выпуск 3 (18.01.2004)

Вступительное слово.

Здравтствуйте, уважаемые подписчики! Я очень вам признателен, за то, что вы остаетесь с нами и прошу прощения за задержку выхода этого выпуска. Этот номер будет коротким. Рассмотрен всего один вопрос. По большей части это от недостатка времени. Но также, эта статья не вписывается в рамки традиционной рассылки. Прежде чем начать, у меня есть небольшая просьба к тем, кто владеет web-технологиями (PHP и MySQL). Нужно проапгрейдить замечательный ресурс Linuxgames.RU. Нужно немного помощи. Идея - сделать нормальный каталог игр. Вся информация должна храниться в базе. Для каждой игры будут поля:

  • Название
  • Краткое описание
  • Полное описание (можно объединить с предыдущим)
  • URL
  • URL на архив для скачивания
  • Открытость (Open Source, Коммерческая)
  • Жанр
  • Рейтинг (оценка посетителей)
  • Количество просмотров описания игры
  • Есть ли сетевая игра
  • Пользовательские комментарии
Возможно что-то еще. Работа несложная и если делать вместе, то можно горы свернуть. Ребята из Linuxgames.RU - очень хорошие друзья нашего проекта. Я буду очень признателен за посильную помощь. Думаю, она не останется незамеченной.
В следующей рассылке я хотел бы поразмышлять о портировании игр в Linux с философской точки зрения. Очень хочу разместить интересную статью о легендарной компании Loki Entertainment Software, а также о смысле и необходимости портирования. Думаю вам будет интересно и с удовольствием услышал бы ваши мнения на этот счет.
Искренне ваш,
E$h

Обработка столкновений 2D спрайтов.

В этой колонке я попытаюсь пролить свет на проблему обработки столкновений, или как ее еще называют пошлым словом - "коллизий". Причиной послужил вопрос одного из участников нашего форума. Простейший способ - представить спрайт прямоугольником. К сожалению этот способ очень нехороший, но вполне применим при высоких разрешениях и мелких спрайтах. Действительно, кого будет смущать дефект наложения 4-х пикселей при 1024х768?

Суровая действительность такова, что спрайт содержит некоторые неиспользуемые части, которые кодируются специальным color key или альфа-каналом. Зачастую представить спрайт прямоугольником без ущерба для качества не представляется возможным. Один из методов, о котором я расскажу, заключается в следующем: мы должны проанализировать каждый из двух столкнувшихся спрайтов и выявить пересекающиеся области. Для каждого спрайта нам понадобятся две вещи - координаты (x,y) и битовая маска. Подробней об этом.

По сути, битовая маска (bitmask) - это ни что иное, как 1bpp-изображение нашего спрайта (изображение где каждый пиксель занимает 1 бит). Никаких заголовков, как например в BMP, нам соответственно не нужно. Вот так может выглядить примерная структура битовой маски: 
struct bitmask
{
  int width;
  int height;
  unsigned int *bits;
};
Поле bits - указатель на массив с маской. Идея в том, что мы записываем 1 для занятого бита спрайта или 0 для незанятого. Впоследствие мы легко можем изменять значения бинарными операторами AND или OR, которые выполняются очень быстро. Теперь самая прелесть: при проверке столкновения мы просто накладываем две маски друг на друга оператором OR, а результат теста записываем в новый массив. Даже если фактически две картинки пересеклись, столкновения может не быть, т.к. пересеклись только невидимые и неиспользуемые части спрайта (те, которые отсекаются цветовым ключом или альфа-каналом). 0 OR 0, как известно, будет ноль. Далее мы просто проверяем массив результата теста на наличие единичек - наложение видимых частей спрайтов. Более того, можно без проблем проверять таким вот образом спрайты различного размера. Маска гораздо экономичней чем обычное изображение (с глубиной 16, 24 или 32 бита).

Во время перекура меня посетила не менее замечательная идея: а что если в массиве маски (поле bits нашей структуры) не хранить каждый пиксель в одном элементе, а развить идею, что у нас всего 1 бит на пиксель? Другими словами хранить в одном элементе массива сразу множество пикселей (в частности 32 для 32-х битных систем). Работать побитно с помощью операторов AND и SHIFT* (для Си << и >>) чрезвычайно просто, а память экономится просто в гигантских масштабах! Например, для маски спрайта 192х192 пикселя нам нужно всего 6х6 (36) элементов массива маски при 32 битах для переменной типа unsigned int! Экономим память ровно в 32 раза, а это существенно!

Примерный план действий таков:

  • Загружаем (или создаем) маски спрайтов. Об этом позже.
  • Проверяем факт коллизии побитовым наложением масок (с помощью OR): если в результирующем массиве есть единицы, то столкновение было.
  • Определяем точно точки пересечения спрайтов (их координаты) при помощи оператора AND и возможно побитных сдвигов в случае упаковки битов в одной переменной. Это займет какое-то время, но скорость не должна сильно пострадать.
  • Можно определить площадь столкновения путем подсчитывания числа "общих" битов - пересеченных пикселей. Думаю нет необходимости вдаваться в метематические рассуждения, потому как реализовать это достаточно несложно.
  • Нахождение угла столкновения. Это достаточно ресурсоемкая часть. Следует использовать эти вычисления в случае крайней необходимости. Для нахождения угла нам нужно рассчитать градиент (уклон) пересеченной части. Это по сути вектор, указывающий в направлении столкновения, или нормаль коллизии.
    f(x, y) = ( f(x+1, y) - f(x-1, y), f(x, y+1) - f(x, y-1) )
    Как видим, требуется 4 обращения к области пересечения, что несколько накладно.

Теперь пару слов об оптимизации. Маска не обязана повторять форму изображения! Вы можете задать примерную маску, как бы плавный силуэт спрайта. Далее, можно разделить спрайты на динамические (движущиеся) и статические (спрайты карты - камни и т.п.). Естественно, что проверять столкновения двух статических спрайтов совершенно не нужно. Можно сортировать спрайты по расположению на карте используя алгоритмы семейства qsort, которые отлично работают при нескольких сотнях спрайтов. Потом отбираем спрайты, чьи координаты наиболее близки и проверяем их на столкновение. Вот простой пример:
[unsorted] --> [L; M; R]
Совершенно очевидно, что спрайты из группы L (левая часть) никогда не сталкиваются со спрайтами из группы R (правая часть).

И наконец,разберемся с созданием битовых масок. Вот пример функции, возвращающая пиксель из SDL_Surface. 
Uint32 GetPixel(SDL_Surface *m_pISurface, int x, int y)
{
    /* Код взят из документации по SDL */
    SDL_LockSurface(m_pISurface);
    int bpp = m_pISurface->format->BytesPerPixel;
    /* p - адрес пикселя, который мы хотим получить */
    Uint8 *p = (Uint8 *)m_pISurface->pixels + y * m_pISurface->pitch + x * bpp;
    SDL_UnlockSurface(m_pISurface);

    switch(bpp) {
    case 1:
        return *p;

    case 2:
        return *(Uint16 *)p;

    case 3:
        if(SDL_BYTEORDER == SDL_BIG_ENDIAN)
            return p[0] << 16 | p[1] << 8 | p[2];
        else
            return p[0] | p[1] << 8 | p[2] << 16;

    case 4:
        return *(Uint32 *)p;

    default:
        return 0; /* не должно случится, но уберет предупреждения компилятора :-) */
    }
}
Далее при помощи несложных действий проверяем является ли он прозрачным (т.е. равен цвету установленного Color Key). 
    Uint32 pixel = GetPixel(Surface, x, y);   // получить пиксель
    SDL_PixelFormat *fmt = Surface->format;          // получить формат сурфейса
    Uint8 r, g, b;                            // будут хранить цвет пикселя
    SDL_GetRGB(pixel, fmt, &r, &g, &b);  // получить цвет пикселя
    
    // далее простой тест на совпадение с прозрачным цветом:
    if(r == ColorKey.r && g == ColorKey.g && b == ColorKey.b)
               // Ставим соответственно ноль в маску, иначе - единичку.
Для данной операции лучше написать отдельную программу. С помощью этой программы затем создать маски для спрайтов и подгружать эти маски вместе с картинками спрайтов. Реализация упаковки битов маски в переменную и запись в файл достаточно простые и описание этих процедур не является целью моего рассказа. Данные размышления не были проверены на практике. Поэтому, если у вас есть комментарии, то я очень прошу присылать их мне или оставлять на форуме! Это очень важно, т.к. я мог что-то упустить и очень интересно как вы меня оцениваете.

Рассылку выпускал E$h (bbroth@plg.lrn.ru); Сайт рассылки: http://plg.lrn.ru; Периодичность: не менее 2-х раз в месяц.
 

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное