Pull to refresh

Как я писал Pacman'a, и что из этого получилось. Часть 1

Reading time 7 min
Views 61K
Здравствуйте, уважаемые хабралюди!
Последние несколько месяцев, в свободное время, я занимался разработкой клона знаменитой игры Pacman для ОС Android. Как это было, и что из этого вышло я хочу рассказать.


Почему Pacman?

Ответ на этот вопрос достаточно прост, и, возможно, уже мелькнул в мыслях кого-то из читателей. Да, совершенно верно, это было тестовое задание для компании ZeptoLab. Из требований этого задания понятны и инструменты, использованные при разработке: Android NDK, C++, OpenGL.

Pacman: начало

Итак, решение принято, инструменты выбраны. Что дальше? Опыта работы с Android NDK нет, опыт работы с OpenGL ограничивается теорией и лабораторными работами из курса компьютерной графики 2011 года. Опыт разработки на С++ есть, но не в геймдеве. Что ж, приступим.

Первое, что я сделал, это установил Android NDK (установка подробно расписана на множестве ресурсов, как иностранных, так и рунета) и запустил несколько примеров из его поставки: во-первых пример GL2JNI, во-вторых SanAngeles. Первый выводит треугольник при помощи OpenGL ES 2.0, второй показывает 3D-ролик, собранный из примитивов, используя OpenGL ES. Код выглядит на первый взгляд жутковато. Да и на второй тоже. Собственно, отправной точкой для меня стал файл gl_code.cpp из проекта GL2JNI.

Почему OpenGL ES 2.0?

Конечно, для простой 2D-игры вполне достаточно статического конвейера OpenGL ES, никаких шейдеров не надо, зачем все это? Ответ: хотелось попробовать. В лабораторных работах по компьютерной графике пощупать шейдеры не удалось, так почему бы не наверстать упущенное?

Изучение OpenGL ES 2.0 начал отсюда, с хабрахабра, с перевода статьи All about OpenGL ES 2.x – (part 1/3). К сожалению, сейчас найти перевод не могу, возможно, автор убрал его в черновики. Автор статьи говорит об OpenGL ES 2.x применительно к iOS, но практически все то же самое верно и для Android. Дочитав первую часть на русском и поняв, что этого мало, я устремился на англоязычные ресурсы (в основном — часть 2 и 3 приведенной выше статьи, но и другие источники тоже использовал), где и почерпнул все знания по OpenGL ES 2.0, которые использовал впоследствии.

Настало время для скриншота

Это один из самых первых скриншотов моей будущей игры. Самыми-самыми первыми были всякие экраны, замощенные треугольниками и растаманские треугольники, причудливо меняющие цвет.
Что можно увидеть на этом, казалось бы, примитивном скриншоте? Достаточно многое:
  1. Загрузка текстур. Да, это важно, это был большой шаг;
  2. Карта. Она есть, на ней различаются стены, еда и пустые места;
  3. GUI. В левом нижнем углу видна кнопка. Да, это была самая первая кнопка.

Подробнее о каждом пункте:

Загрузка текстур

Загрузка текстур в Android NDK возможна несколькими способами:
  • Использовать libpng и libzip для доступа к файлам ресурсов apk напрямую;
  • Использовать AAssetManager, читать файл и интерпретировать его содержимое как картинку вручную;
  • Использовать jni для доступа к android.graphics.Bitmap.

Возможно, существуют еще способы, но я их не нашел. Наиболее приемлемым показался третий вариант, его я и реализовал.

Немного кода на Java
import android.content.res.AssetManager;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;

/*Обертка над стандартным Bitmap, с которой впоследствии будем работать через jni*/
public class PngManager
{
    private AssetManager amgr;
    
    public PngManager(AssetManager manager){
    	amgr = manager;
    }

    public Bitmap open(String path){
        try{
            return BitmapFactory.decodeStream(amgr.open(path));
        }catch (Exception e) { }
        return null;
    }

    public int getWidth(Bitmap bmp) {
    	return bmp.getWidth(); 
    }
    
    public int getHeight(Bitmap bmp) {
    	return bmp.getHeight(); 
    }

    public void getPixels(Bitmap bmp, int[] pixels){
        int w = bmp.getWidth();
        int h = bmp.getHeight();
        bmp.getPixels(pixels, 0, w, 0, 0, w, h);
    }

    public void close(Bitmap bmp){
        bmp.recycle();
    }
}



Немного кода на С++
/*Контейнер для бинарных данных текстуры*/
struct Texture{
	char* pixels; /*should be allocated with new[width*height*4]; RGBA*/
	int width;
	int height;
	Texture(): pixels(NULL), width(0), height(0){}
	Texture(char* p, int w, int h): pixels(p), width(w), height(h){};
	~Texture(){
		if(pixels){
			delete[] pixels;
			pixels = NULL;
		}
	}
};

/*Статический метод, вызываемый при инициализации нативной библиотеки. Параметры передаются через jni из Java */
void Art::init(JNIEnv* env, jint _screenWidth, jint _screenHeight, jobject _pngManager, jobject javaAssetManager){
	LOGI("Art::init");
	free(env);

        /*Все члены - статические*/
	pngManager = env->NewGlobalRef(_pngManager);
	pmEnv = env;

	pmClass = env->GetObjectClass(pngManager);
	pmOpenId = env->GetMethodID(pmClass, "open", "(Ljava/lang/String;)Landroid/graphics/Bitmap;");
	pmCloseId = env->GetMethodID(pmClass, "close", "(Landroid/graphics/Bitmap;)V");
	pmGetWidthId = env->GetMethodID(pmClass, "getWidth", "(Landroid/graphics/Bitmap;)I");
	pmGetHeightId = env->GetMethodID(pmClass, "getHeight", "(Landroid/graphics/Bitmap;)I");
	pmGetPixelsId = env->GetMethodID(pmClass, "getPixels", "(Landroid/graphics/Bitmap;[I)V");
        /*...*/
}

/*Используем jni для доступа к нашей обертке*/
Texture* Art::loadPng(const char* filename){
	LOGI("Art::loadPng(%s)", filename);

	Texture* result = new Texture();

	jstring name = pmEnv->NewStringUTF(filename);
	jobject png = pmEnv->CallObjectMethod(pngManager, pmOpenId, name);
	pmEnv->DeleteLocalRef(name);
	pmEnv->NewGlobalRef(png);

	jint width = pmEnv->CallIntMethod(pngManager, pmGetWidthId, png);
	jint height = pmEnv->CallIntMethod(pngManager, pmGetHeightId, png);

	jintArray array = pmEnv->NewIntArray(width * height);
	pmEnv->NewGlobalRef(array);
	pmEnv->CallVoidMethod(pngManager, pmGetPixelsId, png, array);

	jint *pixels = pmEnv->GetIntArrayElements(array, 0);

	result->pixels = argb2rgba((unsigned int*)pixels, width, height);
	result->width = width;
	result->height = height;

	pmEnv->ReleaseIntArrayElements(array, pixels, 0);
	pmEnv->CallVoidMethod(pngManager, pmCloseId, png);

	return result;
} 


Тут стоит немного остановиться на классе Art. Идея этого класса со статическими методами и членами взята у Нотча (из одной из его игр с открытым исходным кодом), так же как и само имя класса. В нем хранится все, связанное с артом: текстуры, музыка, звуки и т.д. В классе есть статические методы init(), free(), getTexture(int id) и еще пачка всяких полезностей.

Карта

С самого начала разработки я думал о том, каким сделать механизм загрузки уровней. Сходу на ум приходят варианты «захардкодить» и «читать из текстового файла». Это, конечно можно, но тогда ни о какой легкой правке карт говорить не приходится. В голову приходят мысли о редакторе уровней, тем более недавно видел вкусную статью… Нет! Так за деревьями леса не видно будет. Напоминаю себе, что цель – рабочий Pacman и как можно быстрее.
Но ведь только что я научился загружать png! Пикселами разных цветов обозначим клетки стен, еды, пустого пространства, Pacman'а и т.д. А Paint вполне подойдет в качестве редактора уровней. Размер карты может варьироваться, вплоть до 32х32.
Этот подход оправдал себя на 100%. Я получил очень легко редактируемые уровни практически бесплатно.

GUI

Еще одной проблемой для меня был графический интерфейс пользователя. Как дать пользователю возможность нажать кнопку или сделать swipe? Как среагировать на это? Как удобно организовать программную часть? Для себя я ответил на эти вопросы самостоятельно. На диаграмме классов мой ответ выглядит примерно так:

Есть базовый абстрактный класс IRenderable, от которого наследуется Control, от которого наследуется Label, Button, CheckBox и Menu (Содержащий список Control'ов). Все остальные меню (Pause/Game/GameOver и т.д.) наследуются от Menu. Все что им нужно сделать – при создании определить список Control’ов (Button, Label и т.д.), которые появятся при активизации меню. Кроме того, они могут определить свои реакции на события (например, GameMenu отслеживает swipe). Метод render() каждый следующий класс вызывает у предыдущего.
Кроме того, есть класс Engine, который отвечает за глобальную логику игры. Загрузка, переключение между меню, получение сообщений о действиях пользователя и т.д. В нем есть поле Menu* currentMenu, которое он и запрашивает о реакции на действие пользователя. Engine также вызывает Menu::onShow().

Логика игровых персонажей


В игре помимо Pacman'a присутствуют монстры-противники. Каждый из них должен уметь двигаться по лабиринту, сталкиваться со стенами, есть друг друга, в конце концов. Их логика реализована в виде конечных автоматов (StateMachine). Для унификации была выстроена иерархия:

StupidMonster и CleverMonster отличаются своим поведением, задаваемым методом newDirectionEvent(): StupidMonster ходит по лабиринту случайным образом, не обращая внимания на Pacman’a. CleverMonster гонится за Pacman’ом по самому оптимальному маршруту. В этом месте я фактически реализовал велосипед, который по-научному называется шаблоном проектирования «Стратегия»

Поиск оптимального пути.

Поскольку карта представлена массивом, сделать поиск пути несложно. Я реализовал слегка модифицированный волновой алгоритм с сохранением фронта волны. Поскольку двигаться по лабиринту можно лишь по 4, а не направлениям, реализация достаточно тривиальна.
В классе CleverMonster есть статичное поле maps, которое является массивом (размер равен размеру карты) карт. При создании первого экземпляра CleverMonster выделяется память под этот массив. При разрушении последнего экземпляра память очищается. Реализовано это путем подсчета количества созданных объектов.

Алгоритм поиска пути в каждый момент времени:
  1. Узнать координаты Pacman’a (pX, pY);
  2. Заглянуть в массив maps по координатам: maps[pX, pY];
    • Если соответствующая карта еще не построена (NULL), то перейти к пункту 3;
    • Иначе перейти к пункту 5

  3. Создать карту такого же размера, как исходная, сохранить в maps[pX, pY];
  4. С помощью волнового алгоритма заполнить созданную карту полностью, начиная с клетки (pX, pY);
  5. Строить путь, исходя из карты maps[pX, pY];

Эти ухищрения нужны для того, чтобы не считать многократно одни и те же маршруты. Одними и теми же картами пользуются все умные монстры. Каждая карта строится не более одного раза. Достаточно большая часть карт не строится никогда(так как Pacman не может ходить сквозь стены).
Для карты без стен размером 20x20 клеток в худшем случае будет израсходовано 20*20*20*20*4 = 640 000 байт или 625 килобайт памяти. Реально это число гораздо меньше из-за наличия стен.


Итог первой части

Таким был итог почти трех недель разработки. Монстры бегают за Pacman'ом, Pacman ест еду и умеет умирать три раза. Пользователь может поставить игру на паузу, перейти на следующий уровень при победе, или вернуться в меню и выбрать другой уровень. Pacman' анимирован, монстры – нет. Об анимации Pacman'а я подробнее напишу в следующей части.
В таком виде задание было отправлено на проверку в ZeptoLab, после чего меня пригласили на собеседование. Скажу честно – ни до, ни после этого я так не волновался и не тупил на самых простейших вопросах. По моим ощущениям, это был epic fail. Мне посоветовали прочитать несколько книг по алгоритмам и С++, предложили встретиться еще раз в феврале. Об игре был отзыв HR: «Одна из лучших присланных работ». И, кстати, я все еще ищу работу.

Проект в открытом доступе на github.
И в Google Play Market Ссылка убрана, чтобы не было рекламы в профильных хабах.

Ссылка на вторую часть.
Tags:
Hubs:
+20
Comments 20
Comments Comments 20

Articles