Let the computer make the decision or write the AI to play together.
Have you ever thought about how easy it is to write your artificial intelligence, which will itself make decisions in the game? But it is really easy. Let him first make a random decision, but later you can educate him, teach him to analyze the situation, and then he will make conscious decisions. In this article I will tell you how I wrote my bot, and also show how you can write mine in a few minutes. Our computer will play a clone of the game Tron , or rather the part where you need to defeat enemies on a motorcycle.
Under the cat gif-file megabytes at 10.
In the game you control a motorcycle, which reserves a wall of light. The playing field is limited, and rivals have the same motorcycles. Motorcycle rides constantly, you can only turn. Free space on the field ends, and avoiding obstacles becomes more difficult. The winner is the one who will last longer. I made a clone of the game browser-based multiplayer using node.js and socket.io. Control of two buttons - turn left and turn right.
')
Since I use socket.io, I was handling the players on the server in the form of working on an array of special socket objects that socket.io creates. Of these objects, I used only id, emit and broadcast functions. So, painlessly for the game itself, you can implement the socket interface and use it in processing, as if playing another user. I called the class BotSocket .
The emit (event, data) method of the bot performs almost the same actions as the client for incoming data from the server, namely:
To transfer commands to control your motorcycle to the server, it was necessary to save a link to the game object that processes such commands from ordinary users. The method of the Game class is called onControl (socket, data) , so I added a method to the BotSocket
When a motorcycle data update command is received from the server (they were moved), I check if I have a motorcycle under control, have it collided and if it has been moved, and if successful, I call the main method for the AI to work. update () .
The interface is ready, now you can add the AI itself.
No matter how loud it may sound, but in the games of the players for whom the computer plays, it is usually called AI, or bots. The BotSocket object has the necessary game data to make a decision. There are only three possible solutions:
When I decided to write a bot, I had no idea how to do it. I tried a very simple code:
The behavior was something like this:
I looked at him and felt great joy, it seemed to me that he was now independent. It seemed that he himself was looking for attempts to survive, beating there, as if alive. A touching sight.
But I wanted him to live as much as possible. I began to look for information on how to write AI to games. Found articles that described different approaches. But I was looking for something extremely simple. I found on Habré in one of the articles about the bot for a game like Zuma mentioning the wave method . He's the Lee algorithm. It seemed to me very simple and suitable. This is an algorithm for finding the shortest path from one point to another along a field where cells can be either free or occupied. The point is simple. We start from the destination point, assign the value 1 to it and mark all adjacent free cells with one more digit. Then we take all the neighboring free marked ones and again mark one more. So we expand to the whole field until we reach the destination point. And we build a path by searching from neighboring ones to reduce the number, until we reach 1. I looked at the shortest path search algorithms in the graphs, but this one seemed to me the most appropriate.
I transferred the copy-paste algorithm from the page to the wiki, gave it the name BotSocket.prototype.algorithmLee . For the field, I first created a battleground object, in which, with each update, I marked the occupied points with their coordinates. And in the algorithm, Lee reduced this field to the same, but in increments of 1.
It was necessary to somehow determine the destination. I decided to choose it randomly at regular intervals. Made a method to search for a random free point on the field:
Now I could rewrite the update:
The moveToPoint method is mentioned here , which rotates, if necessary, to reach the first point of the shortest path, taking into account the current direction.
Later, I decided to make the bots more aggressive and instead of the random desired point, I was looking for a point in front of the enemies to block their way. Or that they do not play for so long with themselves.
I decided to try to transfer the bot to the client side. Since the project is on node.js, I can use the written code for the bot and on the client side. To do this, I expanded BotSocket with a separate client file that overrides the emit () and control () methods in order to properly interact with the server without reference to the game object.
Locally everything worked fine, and after deploying to the remote server there was some kind of strange picture:
Long thinking, I realized that the matter is in delay. The bot sent a rotation command, but it reached after updating its position on the server, which often caused him to not get on the straight path to the desired point. But I wanted a normal bot on the client side. Therefore, I decided to take into account the delay. To do this, again wrote the extension BotSocket. The article is a long one, so I will describe the main decisions. Before calling the Lee algorithm instead of the current point, I substituted the predicted position taking into account the current position and direction, as well as the delay multiplier. The delay multiplier is a number, how many times the delay exceeds the frequency of updating the position on the server. I still needed to predict the future point in the moveToPoint () method.
Prediction worked if played alone. But if there were other participants, the bot did not take this into account and sent it to where some other player had already traveled. To solve this problem, I changed the method that marks the cells of the field occupied. I began to mark them occupied in a certain range of motion of motorcycles. The radius depends on the delay multiplier.
Previously, I supplied the bot with debugging functions, which we drew the desired point and occupied points on the field. My version of the client bot, taking into account the delay, now moves like this:
My little red, the rest of the server.
The main purpose of this article is to arouse interest in writing a bot. I did a lot to beat your laziness. For this, I added the ability to load my own script with a bot that will extend my base client class. Go to the project and click on the text “Show options for room with your own bot”, and then click on the “Create room for test your own bot” button. A room will be created where bots can be applied easily; by default, your bot will be a bot without delay. Now it's time for your code.
Two simple options for using your code in business, use any:
If you have decided on the method of entering your code, try overriding the methods of the BotSocket class. To begin with the simplest:
After that, re-create the botSocket object by typing
In this case, the code on the page will recreate itself and fill the object. This will change the standard behavior of the bot to random. And then the matter is for your imagination or deep knowledge.
You can also connect the script of my improved bot, taking into account the delay, by inserting into the url for the bot https://raw.github.com/rnixik/tronode-js/master/public/javascripts/MyBotSocketClient.js
I told how I created my AI on the server, then how I transferred it to the client and how I tried to teach him to play with high ping. I really hope that I was able to interest you, and you tried to write your AI, if you have never done this before. Of course, in the high-end games, completely different approaches are used, but it is worth starting small.
Github source code: github.com/rnixik/tronode-js
If you do not have node.js at hand, you can use the applications I deployed:
1) tronode.livelevel.net is the cheapest VPS on DigitalOcean,
2) tronode-js.herokuapp.com is a free virtual unit on Heroku.
The first, most likely, the first can not cope with the load, and the second on some computers resets the socket.io-transport in xhr-polling, because of this, the game lags very much.
If you want to learn more about how I programmed the game logic, you can read here . In the same place about scanning of node.js and a little about a graphic part.
If you do not have an account in Habré, then you can ask questions or send me your interesting suggestions to the mail dev@1i1.be.
Under the cat gif-file megabytes at 10.
About the game
In the game you control a motorcycle, which reserves a wall of light. The playing field is limited, and rivals have the same motorcycles. Motorcycle rides constantly, you can only turn. Free space on the field ends, and avoiding obstacles becomes more difficult. The winner is the one who will last longer. I made a clone of the game browser-based multiplayer using node.js and socket.io. Control of two buttons - turn left and turn right.
')
Bot interface
Since I use socket.io, I was handling the players on the server in the form of working on an array of special socket objects that socket.io creates. Of these objects, I used only id, emit and broadcast functions. So, painlessly for the game itself, you can implement the socket interface and use it in processing, as if playing another user. I called the class BotSocket .
The emit (event, data) method of the bot performs almost the same actions as the client for incoming data from the server, namely:
- Saves data on all playing motorcycles when they are added
- Saves a link to your bike when it is added.
- Updates data on all playing motorcycles.
- Resets the state when restarting the game.
To transfer commands to control your motorcycle to the server, it was necessary to save a link to the game object that processes such commands from ordinary users. The method of the Game class is called onControl (socket, data) , so I added a method to the BotSocket
BotSocket.prototype.control = function(data) { this.game.onControl(this, data); }; When a motorcycle data update command is received from the server (they were moved), I check if I have a motorcycle under control, have it collided and if it has been moved, and if successful, I call the main method for the AI to work. update () .
The interface is ready, now you can add the AI itself.
Artificial Intelligence
No matter how loud it may sound, but in the games of the players for whom the computer plays, it is usually called AI, or bots. The BotSocket object has the necessary game data to make a decision. There are only three possible solutions:
- Nothing to do, go straight
- Turn right
- Turn left
When I decided to write a bot, I had no idea how to do it. I tried a very simple code:
BotSocket.prototype.update = function() { var r = Math.random(); if (r > 0.95) { this.control({'button': 'right'}); } else if (r > 0.90) { this.control({'button': 'left'}); } } The behavior was something like this:
I looked at him and felt great joy, it seemed to me that he was now independent. It seemed that he himself was looking for attempts to survive, beating there, as if alive. A touching sight.
But I wanted him to live as much as possible. I began to look for information on how to write AI to games. Found articles that described different approaches. But I was looking for something extremely simple. I found on Habré in one of the articles about the bot for a game like Zuma mentioning the wave method . He's the Lee algorithm. It seemed to me very simple and suitable. This is an algorithm for finding the shortest path from one point to another along a field where cells can be either free or occupied. The point is simple. We start from the destination point, assign the value 1 to it and mark all adjacent free cells with one more digit. Then we take all the neighboring free marked ones and again mark one more. So we expand to the whole field until we reach the destination point. And we build a path by searching from neighboring ones to reduce the number, until we reach 1. I looked at the shortest path search algorithms in the graphs, but this one seemed to me the most appropriate.
I transferred the copy-paste algorithm from the page to the wiki, gave it the name BotSocket.prototype.algorithmLee . For the field, I first created a battleground object, in which, with each update, I marked the occupied points with their coordinates. And in the algorithm, Lee reduced this field to the same, but in increments of 1.
It was necessary to somehow determine the destination. I decided to choose it randomly at regular intervals. Made a method to search for a random free point on the field:
BotSocket.prototype.getDesiredPoint = function() { var point = []; var H = Object.keys(this.battleground[0]).length - 1; var W = Object.keys(this.battleground).length - 1; var x, y, i, j; var found = false; var iter = 0; do { i = this.getRandomInt(1, W); j = this.getRandomInt(1, H); x = i * this.moveStepSize; y = j * this.moveStepSize; if (this.battleground[x][y] === this.BG_EMPTY) { found = true; } iter++; } while (!found && iter < 100); point = [x, y]; return point; }; Now I could rewrite the update:
BotSocket.prototype.update = function() { if (!this.desiredPoint || this.movements % this.updDestinationInterval === 0) { this.desiredPoint = this.getDesiredPoint(); } if (!this.desiredPoint) { return; } var currentPoint = [this.myBike.x, this.myBike.y]; var path = this.algorithmLee(currentPoint, this.desiredPoint); if (path && typeof path[1] !== 'undefined') { this.moveToPoint(path[1]); } else { this.desiredPoint = this.getDesiredPoint(); } }; The moveToPoint method is mentioned here , which rotates, if necessary, to reach the first point of the shortest path, taking into account the current direction.
Later, I decided to make the bots more aggressive and instead of the random desired point, I was looking for a point in front of the enemies to block their way. Or that they do not play for so long with themselves.
Bot on the client side
I decided to try to transfer the bot to the client side. Since the project is on node.js, I can use the written code for the bot and on the client side. To do this, I expanded BotSocket with a separate client file that overrides the emit () and control () methods in order to properly interact with the server without reference to the game object.
Locally everything worked fine, and after deploying to the remote server there was some kind of strange picture:
Long thinking, I realized that the matter is in delay. The bot sent a rotation command, but it reached after updating its position on the server, which often caused him to not get on the straight path to the desired point. But I wanted a normal bot on the client side. Therefore, I decided to take into account the delay. To do this, again wrote the extension BotSocket. The article is a long one, so I will describe the main decisions. Before calling the Lee algorithm instead of the current point, I substituted the predicted position taking into account the current position and direction, as well as the delay multiplier. The delay multiplier is a number, how many times the delay exceeds the frequency of updating the position on the server. I still needed to predict the future point in the moveToPoint () method.
Prediction worked if played alone. But if there were other participants, the bot did not take this into account and sent it to where some other player had already traveled. To solve this problem, I changed the method that marks the cells of the field occupied. I began to mark them occupied in a certain range of motion of motorcycles. The radius depends on the delay multiplier.
Previously, I supplied the bot with debugging functions, which we drew the desired point and occupied points on the field. My version of the client bot, taking into account the delay, now moves like this:
My little red, the rest of the server.
The most important thing is to try to make the bot yourself.
The main purpose of this article is to arouse interest in writing a bot. I did a lot to beat your laziness. For this, I added the ability to load my own script with a bot that will extend my base client class. Go to the project and click on the text “Show options for room with your own bot”, and then click on the “Create room for test your own bot” button. A room will be created where bots can be applied easily; by default, your bot will be a bot without delay. Now it's time for your code.
Two simple options for using your code in business, use any:
- Put js-file on any server that will be accessible to your browser. Insert the url to your script in the game next to the “Load your AI script” button. After clicking on this button, a new botSocket object will be created and populated, and the start () method will be called.
- Use the browser console (Firebug - F12, Firefox - Ctrl + Shift + K, Chrome - Ctrl + Shift + J, others are here ).
If you have decided on the method of entering your code, try overriding the methods of the BotSocket class. To begin with the simplest:
BotSocket.prototype.update = function() { var r = Math.random(); if (r > 0.95) { this.control({'button': 'right'}); } else if (r > 0.90) { this.control({'button': 'left'}); } } After that, re-create the botSocket object by typing
botSocket = null; In this case, the code on the page will recreate itself and fill the object. This will change the standard behavior of the bot to random. And then the matter is for your imagination or deep knowledge.
You can also connect the script of my improved bot, taking into account the delay, by inserting into the url for the bot https://raw.github.com/rnixik/tronode-js/master/public/javascripts/MyBotSocketClient.js
Conclusion
I told how I created my AI on the server, then how I transferred it to the client and how I tried to teach him to play with high ping. I really hope that I was able to interest you, and you tried to write your AI, if you have never done this before. Of course, in the high-end games, completely different approaches are used, but it is worth starting small.
Github source code: github.com/rnixik/tronode-js
If you do not have node.js at hand, you can use the applications I deployed:
1) tronode.livelevel.net is the cheapest VPS on DigitalOcean,
2) tronode-js.herokuapp.com is a free virtual unit on Heroku.
The first, most likely, the first can not cope with the load, and the second on some computers resets the socket.io-transport in xhr-polling, because of this, the game lags very much.
If you want to learn more about how I programmed the game logic, you can read here . In the same place about scanning of node.js and a little about a graphic part.
If you do not have an account in Habré, then you can ask questions or send me your interesting suggestions to the mail dev@1i1.be.
Source: https://habr.com/ru/post/207648/
All Articles