As I wrote Pacman'a, and what came of it. Part 1
Hello, dear habrakrady!
The last few months, in my spare time, I was developing a clone of the famous Pacman game for the Android OS. How it was, and what came of it, I want to tell.
The answer to this question is quite simple, and, perhaps, has already flashed in the thoughts of someone from the readers. Yes, quite right, it was a test task for the ZeptoLab company. From the requirements of this task, the tools used in the development are 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 theory and laboratory work from the 2011 computer graphics course . Development experience on With ++ is, but not in a game dev. Well, let's get started.
')
The first thing I did was install the Android NDK (the installation is described in detail on a variety of resources, both foreign and Runet) and launched several examples from its delivery: firstly, GL2JNI, and secondly, SanAngeles. The first displays a triangle using OpenGL ES 2.0, the second shows a 3D movie assembled from primitives using OpenGL ES. The code looks scary at first. Yes, and the second too. Actually, the gl_code.cpp file from the GL2JNI project was the starting point for me.
Of course, for a simple 2D game, a static OpenGL ES pipeline is enough, no shaders are needed, why all this? Answer: I wanted to try. It was not possible to touch the shaders in the computer graphics labs, so why not catch up?
The study of OpenGL ES 2.0 began from here, with a habrabra, with the translation of the article All about OpenGL ES 2.x - (part 1/3) . Unfortunately, now I can’t find the translation, perhaps the author has removed it in drafts. The author of the article speaks about OpenGL ES 2.x as applied to iOS, but almost all of 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 learned all the knowledge about OpenGL ES 2.0, which I later used .
This is one of the very first screenshots of my future game. The very very first were all sorts of screens, paved with triangles and rastaman triangles, fancifully changing color.
What can be seen on this seemingly primitive screenshot? Quite a lot:
More about each item:
Loading textures in the Android NDK is possible in several ways:
Perhaps there are more ways, but I did not find them. The third option seemed the most acceptable, and I implemented it.
It is worth a little stop at the
From the very beginning of development, I was thinking about how to make the level loading mechanism. The options of “hard-code” and “read from a text file” come to mind. This, of course, is possible, but then there is no reason to talk about any easy editing of the maps. Thoughts of a level editor come to mind, especially since I recently saw a tasty article ... No! So for the trees of the forest will not be visible. I remind myself that the goal is a working Pacman and as soon 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. Map size can vary, up to 32x32.
This approach is 100% justified. I got very easily editable levels for free.
Another problem for me was the graphical user interface. How to give the user the opportunity to press a button or make a swipe? How to react to it? How convenient to organize the software part? For myself, I answered these questions on my own. On the class diagram, my answer looks like this:
There is a base abstract class
In addition, there is a class
In the game, in addition to Pacman, there are monsters and opponents. Each of them must be able to move through the maze, collide with the walls, eat each other, after all. Their logic is implemented as state machines (StateMachine). For unification, a hierarchy was built:
Since the map is represented by an array, making a search is easy. I implemented a slightly modified wave algorithm with preservation of the wave front. Since it is possible to move through the labyrinth only in 4 directions, not directions, the implementation is rather trivial.
The
Algorithm for finding a path at any time:
These tricks are needed in order not to repeatedly take the same routes. All clever monsters use the same cards. Each map is built no more than once. A large enough part of the cards is never built (since Pacman cannot walk through walls).
For a map without walls of 20x20 cells in the worst case, 20 * 20 * 20 * 20 * 4 = 640,000 bytes or 625 kilobytes of memory will be spent. In reality, this number is much smaller due to the presence of walls.
This was the result of almost three weeks of development. Monsters run after Pacman, Pacman eats food and can die three times. The user can pause the game, go to the next level upon winning, or return to the menu and select another level. Pacman 'is animated, monsters are not. I will write more about Pacman’s animation in the next section.
In this form, the task was sent to check in ZeptoLab, after which I was invited for an interview. Frankly speaking, neither before nor after that I was so worried and not stupid on the simplest questions. According to my feelings, it was epic fail. I was advised to read several books on algorithms and C ++, offered to meet again in February. About the game was a review of HR: "One of the best submitted works." And by the way, I'm still looking for work.
The project is in the public domain on github .
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 spare time, I was developing a clone of the famous Pacman game for the 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, has already flashed in the thoughts of someone from the readers. Yes, quite right, it was a test task for the ZeptoLab company. From the requirements of this task, the tools used in the development are 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 theory and laboratory work from the 2011 computer graphics course . Development experience on With ++ is, but not in a game dev. Well, let's get started.
')
The first thing I did was install the Android NDK (the installation is described in detail on a variety of resources, both foreign and Runet) and launched several examples from its delivery: firstly, GL2JNI, and secondly, SanAngeles. The first displays a triangle using OpenGL ES 2.0, the second shows a 3D movie assembled from primitives using OpenGL ES. The code looks scary at first. Yes, and the second too. Actually, the gl_code.cpp file from the GL2JNI project was the starting point for me.
Why OpenGL ES 2.0?
Of course, for a simple 2D game, a static OpenGL ES pipeline is enough, no shaders are needed, why all this? Answer: I wanted to try. It was not possible to touch the shaders in the computer graphics labs, so why not catch up?
The study of OpenGL ES 2.0 began from here, with a habrabra, with the translation of the article All about OpenGL ES 2.x - (part 1/3) . Unfortunately, now I can’t find the translation, perhaps the author has removed it in drafts. The author of the article speaks about OpenGL ES 2.x as applied to iOS, but almost all of 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 learned all the knowledge about OpenGL ES 2.0, which I later used .
It's time for a screenshot.
This is one of the very first screenshots of my future game. The very very first were all sorts of screens, paved with triangles and rastaman triangles, fancifully changing color.
What can be seen on this seemingly primitive screenshot? Quite a lot:
- Loading textures. Yes, this is important, it was a big step;
- Map. It is, on it walls, food and empty places differ;
- GUI. In the lower left corner is visible button. Yes, it was the very first button.
More about each item:
Texture loading
Loading textures in the 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 more ways, but I did not find them. The third option seemed the most acceptable, and I implemented it.
Some 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(); } } Some 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; } It is worth a little stop at the
Art class. The idea of ​​this class with static methods and members is taken from Notch (from one of his open source games), as well as the class name itself. It contains everything related to art: textures, music, sounds, etc. The class has static methods init(), free(), getTexture(int id) and a init(), free(), getTexture(int id) .Map
From the very beginning of development, I was thinking about how to make the level loading mechanism. The options of “hard-code” and “read from a text file” come to mind. This, of course, is possible, but then there is no reason to talk about any easy editing of the maps. Thoughts of a level editor come to mind, especially since I recently saw a tasty article ... No! So for the trees of the forest will not be visible. I remind myself that the goal is a working Pacman and as soon 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. Map size can vary, up to 32x32.
This approach is 100% justified. I got very easily editable levels for free.
GUI
Another problem for me was the graphical user interface. How to give the user the opportunity to press a button or make a swipe? How to react to it? How convenient to organize the software part? For myself, I answered these questions on my own. On the class diagram, my answer looks like this:
There is a base abstract class
IRenderable , from which Control inherits, from which Label, Button, CheckBox and Menu (Containing a list of Contro l'ov). All other menus ( Pause/Game/GameOver , etc.) are inherited from Menu . All they need to do is create a list of Controls ( Button, Label , etc.) that will appear when the menu is activated. In addition, they can define their reactions to events (for example, GameMenu tracks the swipe). The render() method calls each next class to the previous one.In addition, there is a class
Engine , which is responsible for the global logic of the game. Loading, switching between menus, receiving messages about user actions, etc. It has the Menu* currentMenu , which it asks for a reaction to the user's action. Engine also calls Menu::onShow() .The logic of game characters
In the game, in addition to Pacman, there are monsters and opponents. Each of them must be able to move through the maze, collide with the walls, eat each other, after all. Their logic is implemented as state machines (StateMachine). For unification, a hierarchy was built:
StupidMonster and CleverMonster are distinguished by their behavior, specified by the method newDirectionEvent() : StupidMonster walks randomly through the maze, ignoring Pacman 'a. CleverMonster chases Pacman on the most optimal route. In this place, I actually realized the bike, which is scientifically called the “Strategy” design pattern .Search for the best path.
Since the map is represented by an array, making a search is easy. I implemented a slightly modified wave algorithm with preservation of the wave front. Since it is possible to move through the labyrinth only in 4 directions, not directions, the implementation is rather trivial.
The
CleverMonster class has a static maps field, which is an array (the size is equal to the size of the map) of the maps. When creating the first instance of 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 objects created.Algorithm for finding a path at any time:
- Find out the coordinates of Pacman'a (pX, pY);
- Look at the maps array by coordinates: maps [pX, pY];
- If the corresponding map has not yet been built (NULL), then go to step 3;
- Otherwise, go to step 5
- Create a map of the same size as the original, save to maps [pX, pY];
- Using the wave algorithm, fill in the created map completely, starting with the cell (pX, pY);
- Build a path based on maps [pX, pY];
These tricks are needed in order not to repeatedly take the same routes. All clever monsters use the same cards. Each map is built no more than once. A large enough part of the cards is never built (since Pacman cannot walk through walls).
For a map without walls of 20x20 cells in the worst case, 20 * 20 * 20 * 20 * 4 = 640,000 bytes or 625 kilobytes of memory will be spent. In reality, this number is much smaller due to the presence of walls.
The result of the first part
This was the result of almost three weeks of development. Monsters run after Pacman, Pacman eats food and can die three times. The user can pause the game, go to the next level upon winning, or return to the menu and select another level. Pacman 'is animated, monsters are not. I will write more about Pacman’s animation in the next section.
In this form, the task was sent to check in ZeptoLab, after which I was invited for an interview. Frankly speaking, neither before nor after that I was so worried and not stupid on the simplest questions. According to my feelings, it was epic fail. I was advised to read several books on algorithms and C ++, offered to meet again in February. About the game was a review of HR: "One of the best submitted works." And by the way, I'm still looking for work.
The project is in the public domain on github .
Link to the second part.
Source: https://habr.com/ru/post/178037/
All Articles