We place up to 2000 units (XNA)
Hi, in this post will be presented a little code, a couple of pictures and a few videos, about how I implemented a fast algorithm for the interaction of missiles and units on XNA (2000 - 3000 units) and not only.
Bugs write in lichku
')
To begin with, when writing a game, there was a question about the interaction of projectiles with units. At first I thought, “Well, now it will take a couple of minutes to complete the conditions with a cycle and everything will be in chocolate.”
Here is what the first was on your mind:
In my place, most likely, most newbies used the same thing.
It worked quickly until I introduced the AI ​​system, which controlled several ships. At first there were 6 units (plus my ship) and two teams. Everything was fine, but clearly not enough drive. And I changed one line countBot = 6; at countBot = 100; and then lags (21 FPS) rushed, at first I was at a loss and really could not understand where to optimize.
Here, I found the very first version of the game, where there are 6 more units.
A little back from the topic, as you can see, there were many problems, the first and main one is orientation. Where the ship is located, how quickly it flies, where it flies - the FIG knew it (then this problem will be partially solved). The second one is not less important - there was no interface (in the video console mode), it was impossible even to find out how much HP was left with your ship and to determine who your enemy was and who was ally (the latter was calculated only when shooting opponents and allies). I didn’t like the sight much - but there wasn’t much imagination to draw, but I wanted something original (I’ll replace it with the most banal).
Well, now back to the search and solution of the problem.
In the search for lags, the old, goodinsulating tape design helped:
This design measures the execution time of the code, which allows you to find the place of inhibition. Do you think it's always easy to find such places? But no. My case, of course, is simple, but there were more serious moments.
The output looked like this (with 100 units):
As you can see, the processing of the method took 41 ms each. which is approximately 23 - 24 FPS
So one minute was spent searching for the problem, it was, you guessed it, in the lines that were proposed to solve the collision problem. So what was the problem? And it was that two nested loops were used. Well, imagine 100 units, each firing 13 rockets per second, which is about 1300 missiles per second (of course I bent, just like I didn’t shoot all the units at the same time, but still). 1300 missiles need to be checked with a hundred ships, or 1300 * 100 = 130 thousand checks per second.
And I wanted a game from 2000, even 3000 units. There was and is such a game " Cossacks: Again War ", in it there are many units of different types interacting withover 9999 , with physics and other fitchami. And since such a game was (such that up to 10,000 units were quietly placed in it), then there is a way out.
At first there were stupid attempts to optimize the code, a lot of conditions appeared, all sorts of garbage, but nothing helped. I had to come to terms with the need to invent a new processing algorithm. After two or three days, a more advanced idea came to mind.
The idea was to divide the map into 12 large check zones (marked with blue lines in the figure), then it was necessary to sort the units into these zones and check only within these zones. You know, it worked, the speed increased several times - it damn strongly pleased me. Well, further, why not experiment? I reduced the zones themselves, thereby increasing their number, now there were 48 (pink lines in the figure). The speed has increased even more, then it was just interesting at what stage in the increase in the number of zones the performance would start to die (there was such a moment, but I don’t remember how many zones there were then).
Having played with this, I caught up with the fact that it is easier to build a two-dimensional array of cells with the size of one ship. Next, to update this array every clock, to check for collisions, it was necessary to take the coordinates of the rocket and divide them by the size of the ship, which gave us the coordinates of the location of the projectile in the two-dimensional array of ships. Well, then the simplest thing is to compare the cell of the array for the presence of a ship.
What it looks like in my code:
Now questions that could arise during the consideration of the code.
Before: Attempts to optimize the old design led tosuffering and loss of time to accommodate up to 225 ships.
If you noticed - the cursor has become easier and more informative, although this one also pisses me off.
After: Optimization was so successful that I was able to place up to 2000 units. The video podlagivaet bit (like the previous ones) only because the screen capture program was used.
The latest version has music (in the game itself - it plays on video), a moving background, due to which the orientation problem is partially solved.
I drew all the textures myself, unfortunately I am not an artist to paint better. This is because I lack a 2D artist for simple toys like this one.
TDS Vis 0.21 - when I’ll finish it (if I’ll finish it), I’ll post a project on GitHub. If there are interesting moments, then posts about them will surely appear.
If interested, I can write about the full development of the game from beginning to end.
The first beta version of the game (do not judge much)
PS Once again, about errors and ochepyatka write in a personal.
P.S2 Songs from video:
Remorse Code - Transcend
Katie Melua - The Flood (Jakwob remix)
A couple of songs by Eric Brosius from the game Tribes
Bugs write in lichku
')
How it all began
To begin with, when writing a game, there was a question about the interaction of projectiles with units. At first I thought, “Well, now it will take a couple of minutes to complete the conditions with a cycle and everything will be in chocolate.”
Here is what the first was on your mind:
foreach (var rocket in rockets) { foreach (var unit in units) { if (Contact(rocket, unit)) // { unit.HP -= rocket.damage; // } } } In my place, most likely, most newbies used the same thing.
Problem
It worked quickly until I introduced the AI ​​system, which controlled several ships. At first there were 6 units (plus my ship) and two teams. Everything was fine, but clearly not enough drive. And I changed one line countBot = 6; at countBot = 100; and then lags (21 FPS) rushed, at first I was at a loss and really could not understand where to optimize.
Here, I found the very first version of the game, where there are 6 more units.
A little back from the topic, as you can see, there were many problems, the first and main one is orientation. Where the ship is located, how quickly it flies, where it flies - the FIG knew it (then this problem will be partially solved). The second one is not less important - there was no interface (in the video console mode), it was impossible even to find out how much HP was left with your ship and to determine who your enemy was and who was ally (the latter was calculated only when shooting opponents and allies). I didn’t like the sight much - but there wasn’t much imagination to draw, but I wanted something original (I’ll replace it with the most banal).
Well, now back to the search and solution of the problem.
In the search for lags, the old, good
DateTime start = DateTime.Now; // // ... TimeSpan finish = DateTime.Now - start; // Write(finish); //
This design measures the execution time of the code, which allows you to find the place of inhibition. Do you think it's always easy to find such places? But no. My case, of course, is simple, but there were more serious moments.
The output looked like this (with 100 units):
As you can see, the processing of the method took 41 ms each. which is approximately 23 - 24 FPS
So one minute was spent searching for the problem, it was, you guessed it, in the lines that were proposed to solve the collision problem. So what was the problem? And it was that two nested loops were used. Well, imagine 100 units, each firing 13 rockets per second, which is about 1300 missiles per second (of course I bent, just like I didn’t shoot all the units at the same time, but still). 1300 missiles need to be checked with a hundred ships, or 1300 * 100 = 130 thousand checks per second.
And I wanted a game from 2000, even 3000 units. There was and is such a game " Cossacks: Again War ", in it there are many units of different types interacting with
At first there were stupid attempts to optimize the code, a lot of conditions appeared, all sorts of garbage, but nothing helped. I had to come to terms with the need to invent a new processing algorithm. After two or three days, a more advanced idea came to mind.
Idea
The idea was to divide the map into 12 large check zones (marked with blue lines in the figure), then it was necessary to sort the units into these zones and check only within these zones. You know, it worked, the speed increased several times - it damn strongly pleased me. Well, further, why not experiment? I reduced the zones themselves, thereby increasing their number, now there were 48 (pink lines in the figure). The speed has increased even more, then it was just interesting at what stage in the increase in the number of zones the performance would start to die (there was such a moment, but I don’t remember how many zones there were then).
Total
Having played with this, I caught up with the fact that it is easier to build a two-dimensional array of cells with the size of one ship. Next, to update this array every clock, to check for collisions, it was necessary to take the coordinates of the rocket and divide them by the size of the ship, which gave us the coordinates of the location of the projectile in the two-dimensional array of ships. Well, then the simplest thing is to compare the cell of the array for the presence of a ship.
What it looks like in my code:
public int gridWidth = (int)(Ship.Size.X); // public int gridHeight = (int)(Ship.Size.Y); public List<Ship>[,] grid; // ( ) // public void UpdateGrid() { grid = new List<Ship>[map.border.Width / gridWidth, map.border.Height / gridHeight]; // map.border - foreach (var ship in ships) { if (ship.isDead) // continue; int x = (int)(ship.position.X / gridWidth); // int y = (int)(ship.position.Y / gridHeight); if (x < 0) // , x = 0; if (y < 0) y = 0; if (x + 1 > grid.GetLength(0)) x = grid.GetLength(0) - 1; if (y + 1 > grid.GetLength(1)) y = grid.GetLength(1) - 1; if (grid[x, y] == null) // ( ) grid[x, y] = new List<Ship>(); grid[x, y].Add(ship); // } } // public void RocketContact() { // foreach , - for (int i = 0; i < rockets.Count; i++) { int x = (int)(rockets[i].position.X / gridWidth); // int y = (int)(rockets[i].position.Y / gridHeight); if (x < 0) // x = 0; if (y < 0) y = 0; if (x + 1 > grid.GetLength(0)) x = grid.GetLength(0) - 1; if (y + 1 > grid.GetLength(1)) y = grid.GetLength(1) - 1; if (grid[x, y] != null) // , { Ship ship = grid[x, y][0]; // - if (!ship.isDead) // , =) { if (ship.teamID != rockets[i].teamID) // { ship.HP -= rockets[i].damage; if (rockets[i].hostPlayer != null) // { rockets[i].hostPlayer.rocketHit++; // - if (ship.isDead) // { rockets[i].hostPlayer.AddKill(); // } } if (ship.isDead && ship.hostPlayer != null) // , , ship.hostPlayer.AddDead(); rockets.RemoveAt(i); // ( ) i--; } } } }
Now questions that could arise during the consideration of the code.
- Why do we need a two-dimensional array of ship lists? In my game, one ship can fly close with another ship, and the projectile is one, so only one ship can be hit. I understand that it would be more appropriate to write something like this: Ship ship = grid [x, y] [Random.Next (grid [x, y] .Count)]; But the post is not about that.
- What about performance? Productivity has increased exactly a hundred times. Now there were not 1.3 million checks but only 13 thousand.
- Why crutch? Cause, this is my old code, in a new code a little different. There, if the object is outside the array, then it is simply not calculated.
- How much memory is spent on this design? It depends on what size of the map and how many objects, I have a 10000x10000 pix map, a 100x100 pix grid size with 2000 units - about 2 - 10 mb. of memory. If you have more questions, ask in the comments (your devotee CEP).
Comparison
Before: Attempts to optimize the old design led to
If you noticed - the cursor has become easier and more informative, although this one also pisses me off.
After: Optimization was so successful that I was able to place up to 2000 units. The video podlagivaet bit (like the previous ones) only because the screen capture program was used.
The latest version has music (in the game itself - it plays on video), a moving background, due to which the orientation problem is partially solved.
End
I drew all the textures myself, unfortunately I am not an artist to paint better. This is because I lack a 2D artist for simple toys like this one.
TDS Vis 0.21 - when I’ll finish it (if I’ll finish it), I’ll post a project on GitHub. If there are interesting moments, then posts about them will surely appear.
If interested, I can write about the full development of the game from beginning to end.
The first beta version of the game (do not judge much)
PS Once again, about errors and ochepyatka write in a personal.
P.S2 Songs from video:
Remorse Code - Transcend
Katie Melua - The Flood (Jakwob remix)
A couple of songs by Eric Brosius from the game Tribes
Source: https://habr.com/ru/post/165825/
All Articles