April 26, 2013 at 11:16As I wrote Pacman, and what came of it. Part 1
Hello, dear habralum!
The last few months, in my free time, I have been developing a clone of the famous Pacman game for Android OS. How it was, and what came of it, I want to tell.
The answer to this question is quite simple, and, perhaps, one of the readers has already flickered in the thoughts. Yes, that's right, it was a test case for ZeptoLab. From the requirements of this assignment, the tools used in the development are also clear: Android NDK, C ++, OpenGL.
So, the decision is made, the tools are selected. What's next? There is no experience with Android NDK, experience with OpenGL is limited to the theory and laboratory work from the 2011 course in computer graphics. There is experience in C ++ development, but not in game dev. Well, let's get started.
The first thing I did was install Android NDK (the installation is detailed on a variety of resources, both foreign and runet) and ran several examples from its delivery: first, the GL2JNI example, and secondly SanAngeles. The first draws a triangle using OpenGL ES 2.0, the second shows a 3D movie assembled from primitives using OpenGL ES. The code looks creepy at first glance. Yes, and the second too. Actually, the starting point for me was the gl_code.cpp file from the GL2JNI project.
Of course, for a simple 2D game, the OpenGL ES static pipeline is enough, no shaders are needed, why all this? Answer: I wanted to try. In the laboratory work on computer graphics, it was not possible to touch the shaders, so why not catch up?
The study of OpenGL ES 2.0 began from here, with habrahabr, with the translation of the article All about OpenGL ES 2.x - (part 1/3). Unfortunately, I can’t find the translation now, perhaps the author put it in draft copies. The author of the article talks about OpenGL ES 2.x in relation to iOS, but almost all the same is true for Android. After reading the first part in Russian and realizing that this is not enough, I rushed to the English-language resources (mainly part 2 and 3 of the above article, but also used other sources), where I gained all the knowledge on OpenGL ES 2.0, which I subsequently used .
This is one of the very first screenshots of my future game. The very first ones were all kinds of screens, paved with triangles and Rastaman triangles, fantastically changing colors.
What can be seen in this seemingly primitive screenshot? Enough is enough:
Details for each item:
Texture loading in Android NDK is possible in several ways:
Perhaps there are still ways, but I have not found them. The third option seemed the most acceptable; I implemented it.
Here it’s worth a little dwell on the class
From the very beginning of development, I was thinking about how to make a mechanism for loading levels. The “hardcode” and “read from text file” options come to mind. This, of course, is possible, but then there is no need to talk about any easy editing of the cards. Thoughts about the level editor come to mind, the more recently I saw a tasty article ... No! So the trees of the forest will not be visible. I remind myself that the goal is working Pacman and as quickly as possible.
But I just learned how to download png! Pixels of different colors denote the cells of the walls, food, empty space, Pacman, etc. And Paint is quite suitable as a level editor. Card size can vary, up to 32x32.
This approach has proven itself 100%. I got very easily editable levels almost for free.
Another problem for me was the graphical user interface. How to give the user the ability to click a button or make a swipe? How to react to this? How convenient is it to organize the software part? For myself, I answered these questions myself. In the class diagram, my answer looks something like this:
It has a base abstract class
In addition, there is a class
In the game, in addition to Pacman, there are enemy monsters. Each of them must be able to move through the maze, collide with the walls, eat each other, in the end. Their logic is implemented as state machines (StateMachine). For unification, a hierarchy was built:
Since the map is represented by an array, it is not difficult to search for a path. I implemented a slightly modified wave algorithm with conservation of the wave front. Since you can move along the maze only in 4, and not in directions, the implementation is quite trivial.
The class
Algorithm for finding a path at any time:
These tricks are needed in order not to count the same routes repeatedly. All smart monsters use the same cards. Each map is built no more than once. Quite a lot of cards are never built (since Pacman cannot walk through walls).
For a card without walls measuring 20x20 cells in the worst case, 20 * 20 * 20 * 20 * 4 = 640,000 bytes or 625 kilobytes of memory will be used up. In reality, this number is much smaller due to the presence of walls.
That was the result of almost three weeks of development. Monsters run after Pacman, Pacman eats food and knows how to die three times. The user can pause the game, go to the next level when winning, or return to the menu and select another level. Pacman 'is animated, monsters are not. I will write more about Pacman animation in the next part.
In this form, the assignment was sent for verification to ZeptoLab, after which I was invited for an interview. Frankly - neither before nor after that I was not so worried and dumb on the simplest questions. It felt like an epic fail. I was advised to read several books on algorithms and C ++, offered to meet again in February. There was a HR review about the game: “One of the best submissions.” And by the way, I'm still looking for work.
Open access project ongithub .
And in the Google Play Market Link is removed so that there is no advertising in the profile hubs.
Link to the second part.
The last few months, in my free time, I have been developing a clone of the famous Pacman game for Android OS. How it was, and what came of it, I want to tell.
Why pacman?
The answer to this question is quite simple, and, perhaps, one of the readers has already flickered in the thoughts. Yes, that's right, it was a test case for ZeptoLab. From the requirements of this assignment, the tools used in the development are also clear: Android NDK, C ++, OpenGL.
Pacman: The Beginning
So, the decision is made, the tools are selected. What's next? There is no experience with Android NDK, experience with OpenGL is limited to the theory and laboratory work from the 2011 course in computer graphics. There is experience in C ++ development, but not in game dev. Well, let's get started.
The first thing I did was install Android NDK (the installation is detailed on a variety of resources, both foreign and runet) and ran several examples from its delivery: first, the GL2JNI example, and secondly SanAngeles. The first draws a triangle using OpenGL ES 2.0, the second shows a 3D movie assembled from primitives using OpenGL ES. The code looks creepy at first glance. Yes, and the second too. Actually, the starting point for me was the gl_code.cpp file from the GL2JNI project.
Why OpenGL ES 2.0?
Of course, for a simple 2D game, the OpenGL ES static pipeline is enough, no shaders are needed, why all this? Answer: I wanted to try. In the laboratory work on computer graphics, it was not possible to touch the shaders, so why not catch up?
The study of OpenGL ES 2.0 began from here, with habrahabr, with the translation of the article All about OpenGL ES 2.x - (part 1/3). Unfortunately, I can’t find the translation now, perhaps the author put it in draft copies. The author of the article talks about OpenGL ES 2.x in relation to iOS, but almost all the same is true for Android. After reading the first part in Russian and realizing that this is not enough, I rushed to the English-language resources (mainly part 2 and 3 of the above article, but also used other sources), where I gained all the knowledge on OpenGL ES 2.0, which I subsequently used .
It's time for a screenshot
This is one of the very first screenshots of my future game. The very first ones were all kinds of screens, paved with triangles and Rastaman triangles, fantastically changing colors.
What can be seen in this seemingly primitive screenshot? Enough is enough:
- Loading textures. Yes, it is important, it was a big step;
- Map. It is, on it walls, food and empty places are distinguished;
- GUI A button is visible in the lower left corner. Yes, that was the very first button.
Details for each item:
Loading textures
Texture loading in Android NDK is possible in several ways:
- Use libpng and libzip to access apk resource files directly;
- Use AAssetManager, read the file and interpret its contents as a picture manually;
- Use jni to access android.graphics.Bitmap.
Perhaps there are still ways, but I have not found them. The third option seemed the most acceptable; I implemented it.
A bit of Java code
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();
}
}
A bit of C ++ code
/*Контейнер для бинарных данных текстуры*/
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;
}
Here it’s worth a little dwell on the class
Art. The idea of this class with static methods and members was taken from Notch (from one of his open source games), as was the name of the class itself. It stores everything related to art: textures, music, sounds, etc. The class has static methods init(), free(), getTexture(int id)and a bunch of all sorts of other useful things.Map
From the very beginning of development, I was thinking about how to make a mechanism for loading levels. The “hardcode” and “read from text file” options come to mind. This, of course, is possible, but then there is no need to talk about any easy editing of the cards. Thoughts about the level editor come to mind, the more recently I saw a tasty article ... No! So the trees of the forest will not be visible. I remind myself that the goal is working Pacman and as quickly as possible.
But I just learned how to download png! Pixels of different colors denote the cells of the walls, food, empty space, Pacman, etc. And Paint is quite suitable as a level editor. Card size can vary, up to 32x32.
This approach has proven itself 100%. I got very easily editable levels almost for free.
GUI
Another problem for me was the graphical user interface. How to give the user the ability to click a button or make a swipe? How to react to this? How convenient is it to organize the software part? For myself, I answered these questions myself. In the class diagram, my answer looks something like this:
It has a base abstract class
IRenderable, which is inherited Control, which is inherited Label, Button, CheckBoxand Menu (containing a list of Control's). All other menus ( Pause/Game/GameOveretc.) are inherited from Menu. All they need to do is when creating, define a list of Control's ( Button, Labeletc.) that will appear when the menu is activated. In addition, they can determine their reactions to events (for example, GameMenutracks a swipe). render()Each next class calls the method from the previous one. In addition, there is a class
Enginethat is responsible for the global logic of the game. Download, switch between menus, receive messages about user actions, etc. There is a field in it Menu* currentMenu, which he asks about the reaction to the user's action. Enginealso causes Menu::onShow().Game logic
In the game, in addition to Pacman, there are enemy monsters. Each of them must be able to move through the maze, collide with the walls, eat each other, in the end. Their logic is implemented as state machines (StateMachine). For unification, a hierarchy was built:
StupidMonsterand CleverMonsterdiffer in their behavior defined by the method newDirectionEvent(): StupidMonsterwalks through the maze randomly, not paying attention to Pacman'a. CleverMonsterchasing Pacman'oh along the most optimal route. At this point, I actually implemented a bicycle, which is scientifically called the “Strategy” design patternSearch for the best way.
Since the map is represented by an array, it is not difficult to search for a path. I implemented a slightly modified wave algorithm with conservation of the wave front. Since you can move along the maze only in 4, and not in directions, the implementation is quite trivial.
The class
CleverMonsterhas a static field maps, which is an array (the size is equal to the size of the map) of the maps. When creating the first instance CleverMonster , memory is allocated for this array. When the last instance is destroyed, the memory is cleared. This is implemented by counting the number of created objects. Algorithm for finding a path at any time:
- Find out the coordinates of Pacman (pX, pY);
- Look into the maps array at the coordinates: maps [pX, pY];
- If the corresponding map is not yet built (NULL), then go to step 3;
- Otherwise go to step 5
- Create a map of the same size as the original, save in maps [pX, pY];
- Using the wave algorithm, fill the created map completely, starting from the cell (pX, pY);
- Build a path based on the map maps [pX, pY];
These tricks are needed in order not to count the same routes repeatedly. All smart monsters use the same cards. Each map is built no more than once. Quite a lot of cards are never built (since Pacman cannot walk through walls).
For a card without walls measuring 20x20 cells in the worst case, 20 * 20 * 20 * 20 * 4 = 640,000 bytes or 625 kilobytes of memory will be used up. In reality, this number is much smaller due to the presence of walls.
The result of the first part
That was the result of almost three weeks of development. Monsters run after Pacman, Pacman eats food and knows how to die three times. The user can pause the game, go to the next level when winning, or return to the menu and select another level. Pacman 'is animated, monsters are not. I will write more about Pacman animation in the next part.
In this form, the assignment was sent for verification to ZeptoLab, after which I was invited for an interview. Frankly - neither before nor after that I was not so worried and dumb on the simplest questions. It felt like an epic fail. I was advised to read several books on algorithms and C ++, offered to meet again in February. There was a HR review about the game: “One of the best submissions.” And by the way, I'm still looking for work.
Open access project ongithub .
Link to the second part.