Creating your own homemade artificial intelligence

Children's dreams or Pack-Man do it yourself

Everyone in his life made his own bike. To justify his desire to do it, one can only say that if people did not do it periodically, then the world simply would not see many things.

His game, or rather gaming artificial intelligence (AI) to make a wish was a very long time. I will not prevaricate: at first it was simply not enough knowledge, then strangely enough time. I had a few weeks about free time to realize my childhood dream.

I'll tell you what happened, and also describe the path that I walked, and the observations that I made along the way. I will make a reservation right away that I will not describe the code, but the considerations, thoughts, and problems I encountered in the process of realizing the dream.
')

Structure planning stage

When planning the habitat structure, the AI ​​immediately made an attempt to lay down extensibility and at least some universality. It was decided to do everything on dynamic arrays, with the universal application of object-oriented programming approaches wherever possible.

The hierarchy of classes of habitat AI was based on several pairs of classes:

• The key point is the class that reflects the intersection of the path graph connections.
• Path is a class that provides links between Key Points.
• An object is a class that is derived from the class Key Point, instances of which are located on the Path.
• Subject is the same class Object whose instances have decision-making functions.

The world class closes the list of classes, which frames all the listed classes, organizing their interaction with each other.



For work, I needed some specific, not complicated game concept. And as such was chosen the concept of the game Pack-Man , due to a simple set of rules.

Immediately additional subclasses of Objects and Subjects of the game were allocated:

• Packman's subject is the very Packman;
• Fruit objects are those for Pakmanu to eat;
• Ghost subjects are those for which Pakman was created in the game.

Work planning stage

As a superficial analysis showed: the required amount of code for a full-fledged game operation, despite the small amount of system functionality, turned out to be rather large. A natural conclusion was drawn that it was necessary to split up tasks into a multitude of isolated subtasks, so that at least some results of their fuss would be visible - otherwise children's desires could turn into a childishly prolonged nightmare.

The following stages of implementation were immediately highlighted:

1. Creation of classes providing the functioning of the world in which artificial intelligence will live (classes of the World, Key Point and Path);
2. Drawing the World and at the same time creating the basis of the functionality for data visualization.
3. Creating a class Object, its interactions with the environment.
4. Creating the first instance of the Object, namely Fruit and its drawing.
5. Creating an add-on functionality for an Object to turn it into a Subject.
6. Create an instance of Pacman. Rendering. Adding rules to the game.
7. Development of user interaction code, organization of system operation in “real time”.
8. Implementation of the shortest path search algorithm. Connecting him to the management of Pakman and the automatic change of his state of the World in time.
9. Create an instance of Ghost. Rendering. Adding rules to the game.
10. Improving the system for small things.
11. Getting pleasure.

With this plan, I set to work.

Implementation

The first two steps were easy. Three classes were organized: World, Key Point and Path: their constructors, destructors, several functions that ensure the creation of links between instances of classes by reference, and everything.
An instance of the World class with five points was created, where the paths formed an envelope with an offset central point, so that the distances between the points were clearly of different lengths. The drawing was done very, very modestly: with lines and cups - just as much as one could understand what was happening in the World.

Stages # 3 and # 4 also didn’t cause much difficulty - Fruit didn’t run, didn’t harm, it just lay and was drawn.

Since stage number 5, the main work has gone. The Subject's functionality was written using the Object class in the form of a to-do list that the Subject would like to make. The functionality of the World class was added, which monitored the list of cases of the Subjects and carried them out within the time frame of the Subject and the restrictions and rules of the game imposed on the Subject’s actions.

Stage 6 Problems with the emergence of an instance of Pakman as nonstrangely did not begin. Just appeared a copy of the Subject type, as well as drawing on the display in the desired coordinate circle. And there were added rules for eating fruit.

Even at the stage №7 , when one task was generated with the mouse in the form of a “run” command to the specified coordinate, there were no problems. It looked for the nearest point that would fall into the Path, on which Pakman already stood and Pacman obediently went there.

Adventures began at stage number 8 , where the implementation of the shortest path algorithm was performed. The shortest path search function was a modified Lee algorithm, adapted to dynamic arrays and graph structures. The main difficulties were when writing code, where the reverse was implemented. To reduce the number of changes in the structure of the graph when moving instances of Objects, the Objects were made not as nodal Key points connected by Paths, but as Key points belonging to the Path. Having at the time of writing the article working code, still not sure about the correctness of the chosen solution. What is simpler: either rebuild locally the graph of the World and at the same time the routes of the Subjects that move through the modified fragments of the graph or simply place the classes of Subjects and Objects on the immutable graph of the Paths.



Of course, at all stages of work, memory access errors constantly flashed. The most cruel case was when the message took off somewhere in the middle of the game. I forgot to remove the link between the Paths and the destroyed copies of the Fruit when they were eaten. The error manifested itself after eating after rewriting memory. While the data of the destroyed object were stored there and they were not overwritten by the new dynamic object, everything was normal, i.e. the crash of the program was not instantaneous.

Finally, in step 9 , the first Ghost was added. The destination was always the Pakman coordinate. We used the already written search function for the shortest path, which was called continuously 24 times in 1 second. After generating the list of actions, the movement of the Ghost was carried out by the system (World) automatically.

When he came to the stage number 10 , then, as they say, the sleigh rushed!
A random map generator was made. When creating a map for generating Paths, several criteria for their admissible creation were made: no more than 4 Paths should intersect at the nodal points, and the nodal points should be no closer to the already laid Paths of a certain distance, as well as paths should not be longer than a certain constant.

Then a few Ghosts were added that persistently pursued Pakman.

Playing with such ghosts was just unreal. And then it dawned on me that a “fog of war” was needed, then the Ghosts would behave more naturally, rather than radically changing their route, when you slightly changed the Pacman route somewhere on the other end of the map.
The first thought was for each Subject to make an array of visible elements of the world, as well as to complete the memory of the Subject to store where, whom and when he saw. Thinking, I realized that for a spider who wants to eat a fly it's all very difficult and cumbersome to implement.

The exit was found as simple as that. Randomly, there was a point on the map where the Ghost followed (thus, a simple map walk and Pakman search were organized). In the case of Pakmen falling into a certain (specified by a constant) visibility range of the Ghost, the Ghost was rebuilt the route to it. When the victim was in sight, the Ghost constantly rebuilt his route to her, and when Pakmen went out of sight, the Ghost continued to follow to the point where his victim had last seen. Upon reaching this point, the blind wandering around the map began again.



This actually stopped and calmly turned his breath.
At the end, the decorative elements were completed: “The end of the game” (eaten by Pakmen), the scoring (the number of eaten Fruit), “Completion of the level” (eaten by all Fruit).

The results of torment.

Despite the large amount of spilled sweat and blood, relatively small results were achieved: for further research, the basis of the World was realized, in which the intellect of the simplest predator of the spider type lives. Apparently, it is necessary to create a modification of the existing AI algorithm to implement the behavior of the “Sacrifice” (within the framework of the game, these are the Runaway Fruits running away), as well as the combined AI (“Predator-prey”), which will allow the Packman bot to do so and not on "play", but only with pleasure to watch on throwing in the test tube of this "Kolobka".



You can see for yourself what happened “ Here ” (executable file for Win32) *. Pay attention to the matrix mode toggle switch. When it is turned on, you can see how the system makes decisions, and feel a little like Neo. Unfortunately, I thought of doing it at the 10th stage, for a better understanding of the work of AI. If I had done earlier, I spent less time debugging the shortest path search algorithm.

PS Not everything and not always done for reasons of economic expediency and optimality, some things are done for fun. Despite the simplicity of the graphics, when “She” breathed, I experienced indescribable joy.

* Already after the completion of all the planned works and the writing of the article, I discovered another rarely falling out error. The location of the error indicates that the problem is related to the fact that the simulation of the game world is performed in the handler of a regular timer, and the management of Pakmen in a normal mouse handler. In general, there are no ordinary semaphores and other similar "abstruse" things, which would ensure the integrity of the data, to which calls are made in both functions. I think before the wedding heals the commercial version of the bug will be corrected.

Thanks for the edits: evocatus .