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

Создание компьютерных игр. Школа Демиургов

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 11.229 RSS
←   Август 2003   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://community.livejournal.com/way_to_homounus/14755.html
Открыта: 17-03-2003

Автор
ucmok_peku

Статистика

11.229 подписчиков
0 за неделю
←   Все выпуски   →

Создание компьютерных игр


Информационный Канал Subscribe.Ru
Cоздание компьютерных игр.
Выпускается еженедельно по пятницам.
Автор рассылки - Евгений Казеко.

Выпуск 13. (от 29 августа 2003 года)
Алгоритмы.

--------------------------------------------------------------

Доброго времени суток, дорогие читатели!

Скоро начинается учебный год, в какой-то степени он начинается и в нашей рассылке. Да, вы не ошиблись, опять все только начинается. И это нормальный процесс обучения - за завершением очередного этапа следует начало нового, еще более сложного и захватывающего. И сейчас как раз наступает тот этап, к которому мы все это время готовились. Мы наконец-то начнем создавать нашу первую игру - тетрис. Вы же не ждали, что мы за несколько выпусков напишем трехмерную игру уровня Half-Life? Я уже говорил об этом неоднократно и повторю еще раз - начинать надо с малого.

Подведем небольшой итог нашим знаниям. Мы знаем общие принципы языка С, знаем, что такое переменные, функции, структуры, указатели, циклы и как со всем этим работать. Кроме того мы познакомились с принципами создания Windows приложений, мы можем создать окно и вывести в него графику. Все - этого уже достаточно для создания более-менее работоспособной игры. Пускай мы чего-то не знаем, это не страшно. Все познается в процессе работы.

Итак, начинаем мы как всегда с основополагающих вещей. Алгоритмы - не это ли самое главное? Нет, не это :) Главное - это идея игры, ее "дизайн". Алгоритм является следствием продуманной идеи, а программный код это всего лишь его реализация, не больше не меньше. Поэтому мы начнем с алгоритма, так как с идеей тетриса обычно сложностей не возникает - все видели тетрис и хорошо знают, что это такое.

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

Прежде всего, мы имеем дело с набором фигур, состоящих из четырех "кубиков" (нарисуйте их все):
1) квадрат
2) прямая
3) т-образная фигура (подобие креста)
4) L-образная фигура и ее зеркальное отражение
5) z-образная фигура и ее зеркальное отражение
Таким образом, всего мы имеем 7 видов фигур (вместе с отражениями).

Каждая фигура состоит из 4 элементов-кубиков (надеюсь, все знают, что именно поэтому игра и называется тетрис?) и может вращаться по часовой стрелке (для упрощения не будем делать вращение против часовой стрелки), принимая при этом 4 "разновидности" (зарисуйте, пригодится).

Кроме того, существует "стакан", в котором движутся фигуры. У стакана есть дно и стенки.

Фигура может двигаться вниз и в стороны, продвигаясь за один раз на одну позицию, размер которой определяется размером кубика (нет смысла делать попиксельное движение).

Фигура движется вниз до тех пор, пока не соприкоснется с дном стакана или другой неподвижной фигурой.

Внимание, важный момент. Фигура может двигаться в стороны, сталкиваясь с другими фигурами, при этом движение вниз не прекращается.

Когда движение фигуры прекращается, в верхней части стакана появляется новая фигура, которая двигается согласно приведенным выше принципам.

Когда происходит "заполнение ряда" из кубиков, он исчезает и все элементы стакана смещаются вниз.

Игра завершается, когда невозможно движение очередной новой фигуры (происходит заполнение стакана).

То, что мы написали, это еще не алгоритм, это пожалуй как раз и есть идея или дизайн игры. Когда у нас есть четкая, подробно изложенная идея, нам будет гораздо легче писать и алгоритм, и программу. Конечно, вы можете сказать, зачем писать то, что и так ясно? Может для тетриса и действительно все ясно, но вот для более сложных игр проработка дизайна просто необходима. Гораздо проще и эффективнее продумать все в самом начале, чем переделывать что-то по ходу игры. Поэтому не ленитесь, всегда делайте проектную документацию. Подробно описывайте все, что только можно описать.

А теперь приступим непосредственно к алгоритму, для этого опишем пошагово, как должен работать тетрис.

1) Рисуется игровое поле - стакан.
2) Создается фигура, которая выбирается случайным образом, но пока еще не рисуется.
3) Сперва нужно проверить, есть ли в стакане место для ее вывода (не перекрывает ли она уже имеющиеся фигуры).
4) Если есть место - рисуем фигуру. Если нет - игра окончена (стакан заполнен).
5) Проверяем, можем ли мы двигать фигуру вниз. Если да, то двигаем на одну позицию, плюс см.пункт 7. Если нет - выводим новую фигуру (возвращаемся к пункту 2).
6) Проверяем, не нажаты ли клавиши вращения фигуры или движения в стороны. Если нажаты, то:
- двигаем фигуру влево или вправо на одну позицию;
- или вращаем фигуру;
Разумеется, нужно проверять, возможно ли такое движение. Что подразумевается под такими проверками? Мы проверяем, не сталкивается ли фигура с другими фигурами или со стенками стакана. Если есть такие столкновения, мы не двигаем фигуру. Если есть столкновение с дном или фигурами при движении вниз, фигура останавливается и появляется новая фигура.
7) После каждого останова фигуры проверяем, нет ли у нас заполненных рядов, и если они есть, то удаляем их, смещая все элементы стакана вниз.

Вот и все. Мы только что составили примерный алгоритм работы тетриса. Но для того, чтобы мы смогли проще написать программу (реализовать алгоритм), нужно воспользоваться так называемой нисходящей пошаговой детализацией. Для этого мы каждое конкретное действие расписываем еще подробнее, т.е. раскладываем на составные элементы. Например, рисование стакана может быть разложено на рисование его стенок и дна. Впрочем, мы поступим по другому. Представим стакан в виде набора клеток. И тогда каждая клетка будет своеобразным "знакоместом", возможным элементом фигуры. (Экран монитора тоже состоит из подобных клеток-знакомест очень маленького размера, я имею в виду пиксели).

Давайте распишем наш алгоритм более подробно, а заодно наметим набор функций, которые можно реализовать в программе:

1) Создаем стакан в памяти. Стакан представляет собой набор квадратов-клеток. Удобнее всего этот набор представить в виде двумерного массива. Записываем в каждую клетку "флаг", указывающий, что в клетке нет элементов фигур. (например 0).

2) Выводим стакан на экран.

3) Создаем фигуру в памяти. Используем для этого случайный выбор из набора фигур.

4) Проверяем, свободны ли клетки, в которых будет размещаться фигура. Если нет, то игра заканчивается.

5) Если клетки свободны, записываем фигуру в стакан (к примеру, записываем значение 1 в соответствующие клетки).

6) Рисуем стакан с фигурами на экран.

7) Опрашиваем клавиатуру, не нажаты ли клавиши для движения или поворота.

8) Если нажаты клавиши, то определяем, куда будет двигаться фигура и проверяем, свободны ли клетки для нового положения. Если да, то записываем фигуру в стакан в новой позиции и перерисовываем стакан.

9) Проверяем, возможно ли передвижение вниз. Если да, то двигаем фигуру, если нет, то останавливаем фигуру. Перерисовываем стакан.

10) Проверяем, нет ли заполненных рядов (делаем это снизу вверх). Если есть, то сдвигаем вышестоящий ряд вниз.

11) Переходим к пункту 2.

Вот он, наш алгоритм... Как видите, ничего сложного, но на его основе уже можно написать тетрис. Осталось только применяя несколько уровней детализации расписать алгоритм еще подробнее, а также изобразить его в виде блок-схемы. Мы же ограничимся еще одним уровнем детализации, описав алгоритм в виде функций.

 Инициализировать массив-стакан;
 Перерисовать стакан;
 
 Пока (Генерировать фигуру(); != 0)
 {
  Записать фигуру в стакан;
  Перерисовать стакан;
  Опросить клавиатуру;
     {
   Определить направление движения и вызвать соответствующие функции:
   Движение влево() или Движение вправо() или Поворот();
   Если (возможно передвижение)
      Передвинуть фигуру, записав в стакан;
     }
  Передвинуть фигуру вниз;
  Перерисовать стакан;
  Проверить, есть ли заполненные ряды;
  Перерисовать стакан;  
   

        }
Итак, нам будут нужны функции: генерация фигуры, занесение фигуры в массив, вывод массива на экран, движение влево, движение вправо, движение вниз, поворот, проверки столкновений, проверка на заполнение рядов. Теперь осталось только реализовать эти функции в виде программного кода. Я не претендую на то, что мой алгоритм является совершенным. Попробуйте, возможно вы сможете написать более простой и эффективный алгоритм.

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

До следующего выпуска!

----------------------------

Что почитать:

Алгоритмы: построение и анализ
Авторы: Т. Кормен, Ч. Лейзерсон, Р. Ривест

Книга представляет собой перевод учебника по курсу построение и анализ эффективных алгоритмов, написанного в Массачусетском техническом университете; в ней разрабатываются важнейшие классы быстрых алгоритмов и прием их построения. Изложение подробное и математически строгое. Книгу можно использовать в качестве учебника и справочника; она будет полезна как студентам, так и профессионалам в области computer science и программирования.

Искусство программирования. Том 1. Основные алгоритмы.
Искусство программирования. Том 2. Получисленные алгоритмы.
Искусство программирования. Том 3. Сортировка и поиск.
Автор: Дональд Е. Кнут

Серия книг Искусство программирования начинается описанием основных алгоритмов вычислительной математики и технологии программирования. Затем автор переходит к описанию информационных структур, а также способов представления данных в компьютере. Все алгоритмы сопровождаются примерами приложений, написанных в псевдокодах для машины Кнута. По сравнению с предыдущим изданием, в первый том было добавлено описание множества новых алгоритмов. Кроме того, существенно переработан раздел, посвященный вычислительной математике, в котором автор отразил последние достижения в этой области.

--------------------------------------------------------------

Архив рассылки вы найдете по адресам http://subscribe.ru/catalog/comp.games.gamecoder и http://www.gamecoder.nm.ru/subscribe.htm.

Евгений Казеко.
kazeko@list.ru
www.gamecoder.nm.ru
-----------------------------
Рассылка "Создание компьютерных игр", выпуск 13.
Выпускается еженедельно по пятницам.

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