Diploma: tanchiki and genetic programming
Hey.
When choosing a diploma theme, the desire to implant something practical was taken into account, which influenced the choice of the topic. It was decided to develop a platform for conducting competitions on programming of an AI tank. In general, the idea is not new and such things have already been done ( http://robocode.sourceforge.net , for example). But there are several reasons for choosing exactly tanchiki:
I will not talk about evolutionary programming, because it has already been discussed here many times, and, moreover, it is not a pleasure to describe it again after writing a diploma.
')
Unlike other implementations, my tanks are in 3D. They drive around the landscape, which is read from an external file with a height map . Also, the plans had at least some realistic physics, but this was not enough time and effort.
Binary protocol over UDP is used for communication. Why UDP? It preserves message boundaries because it is a message-based protocol. This means that the data comes in exactly the same portions as they were sent, which greatly simplifies the network part. In the face of time constraints, in my opinion, this is a reasonable solution. Instead of UDP, you could use SCTP, for example. But it is not implemented under Windows, and development was carried out under this OS.
The protocol consists of packets, each of which begins with id. Therefore, the packet size is often known in advance — by the first byte. For packages of variable length, the body of the package provides a static part, which allows you to determine the size of the entire package.
In the code, packages are described by C-structures with disabled alignments.
The tanks consist of a network server, a test and “genetic” clients and a viewer program.
The server processes requests, sends notifications and performs all calculations.
The test client is intended for debugging. It reads tank control commands from the standard input and sends it to the server. For example, pi (power increase) - increase engine power, s (shoot) shoot, ll (look left) - turn gun slightly to the left.
“Genetic” client - launches the Slash / A tank control genetic program. It is a language specially developed for GP and VM for its execution. The command set of VMs was extended by tank-specific commands.
Sample Slash / A program:
Viewer program is designed to monitor the fight. You can hover over the card using WASD, F, V and rotate the camera with the mouse.
During development, a couple of test clients (for the victim tank and the winning tank) and the viewer were some of the basic debugging tools.
Screen:
In C11 added a lot of different features. These were useful to me:
Also, Variable Length Arrays and Designated Initializers from C99 were useful. Well, the ability to declare variables not only at the beginning of the scope was also very useful.
To build the C part, an excellent pellesc.de compiler was used with excellent library, language and environment help.
GCC (MinGW) was used to build C ++ parts.
Link to source: http://code.google.com/p/morrigan . Unfortunately, I am not well versed in licenses, so for the second project I choose “Other Open Source”. Somehow, be sure to read some kind of educational program.
In principle, only one non-portable dependency is Winsock. Why morrigan - wiki . From the very beginning, I decided to call the project a female name, and then an idea came up about the goddess of war.
I graduated the diploma myself in LaTex, which I never regret and advise everyone. This is not at all as scary as it may seem, especially after a year of preparing the protocols for the laboratory in LaTex. If difficulties arose, I was saved by google (which resulted mainly on tex.stackexchange.com ) and good documentation for the packages. Looking at my friends, who painfully manually put the page numbers in a frame, captions to figures and tables and links to them, I once again made sure that the decision was made correctly.
Overall, I am satisfied. It was possible to distract a little from the omnipresent PLO and program it to your pleasure.
When choosing a diploma theme, the desire to implant something practical was taken into account, which influenced the choice of the topic. It was decided to develop a platform for conducting competitions on programming of an AI tank. In general, the idea is not new and such things have already been done ( http://robocode.sourceforge.net , for example). But there are several reasons for choosing exactly tanchiki:
- These same tanchiki served as a platform for the theoretical part of the diploma: the study of GP applied to the object management problem
- As mentioned above, I wanted to code something different, develop a protocol, program the server and clients.
- Work with OpenGL in practice
- Try C11
I will not talk about evolutionary programming, because it has already been discussed here many times, and, moreover, it is not a pleasure to describe it again after writing a diploma.
')
Unlike other implementations, my tanks are in 3D. They drive around the landscape, which is read from an external file with a height map . Also, the plans had at least some realistic physics, but this was not enough time and effort.
Protocol
Binary protocol over UDP is used for communication. Why UDP? It preserves message boundaries because it is a message-based protocol. This means that the data comes in exactly the same portions as they were sent, which greatly simplifies the network part. In the face of time constraints, in my opinion, this is a reasonable solution. Instead of UDP, you could use SCTP, for example. But it is not implemented under Windows, and development was carried out under this OS.
The protocol consists of packets, each of which begins with id. Therefore, the packet size is often known in advance — by the first byte. For packages of variable length, the body of the package provides a static part, which allows you to determine the size of the entire package.
In the code, packages are described by C-structures with disabled alignments.
Components
The tanks consist of a network server, a test and “genetic” clients and a viewer program.
The server processes requests, sends notifications and performs all calculations.
The test client is intended for debugging. It reads tank control commands from the standard input and sends it to the server. For example, pi (power increase) - increase engine power, s (shoot) shoot, ll (look left) - turn gun slightly to the left.
“Genetic” client - launches the Slash / A tank control genetic program. It is a language specially developed for GP and VM for its execution. The command set of VMs was extended by tank-specific commands.
Sample Slash / A program:
input/ # gets an input from user and saves it to register F 0/ # sets register I = 0 save/ # saves content of F into data vector D[I] (ie D[0] := F) input/ # gets another input, saves to F add/ # adds to F current data pointed to by I (ie D[0] := F) output/. # outputs result from F Viewer program is designed to monitor the fight. You can hover over the card using WASD, F, V and rotate the camera with the mouse.
During development, a couple of test clients (for the victim tank and the winning tank) and the viewer were some of the basic debugging tools.
Screen:
C11
In C11 added a lot of different features. These were useful to me:
- Type-independent macros (math and math.h)
- Multithreading
Also, Variable Length Arrays and Designated Initializers from C99 were useful. Well, the ability to declare variables not only at the beginning of the scope was also very useful.
To build the C part, an excellent pellesc.de compiler was used with excellent library, language and environment help.
GCC (MinGW) was used to build C ++ parts.
Link to source: http://code.google.com/p/morrigan . Unfortunately, I am not well versed in licenses, so for the second project I choose “Other Open Source”. Somehow, be sure to read some kind of educational program.
In principle, only one non-portable dependency is Winsock. Why morrigan - wiki . From the very beginning, I decided to call the project a female name, and then an idea came up about the goddess of war.
I graduated the diploma myself in LaTex, which I never regret and advise everyone. This is not at all as scary as it may seem, especially after a year of preparing the protocols for the laboratory in LaTex. If difficulties arose, I was saved by google (which resulted mainly on tex.stackexchange.com ) and good documentation for the packages. Looking at my friends, who painfully manually put the page numbers in a frame, captions to figures and tables and links to them, I once again made sure that the decision was made correctly.
Overall, I am satisfied. It was possible to distract a little from the omnipresent PLO and program it to your pleasure.
Links
- www.gamedev.ru - articles about the landscape, height maps and Collision Detection
- Collision Detection in Interactive 3D Environments - the whole book about Collision Detection
- www.libsdl.org - cross-platform library for working with graphics, sound and input devices
- Standard C11
- Slash / A library
- Help Pelles C
- c.learncodethehardway.org is an interesting C tutorial (even for those who know) and a wonderful header debug.h
Source: https://habr.com/ru/post/186670/
All Articles