Ways of moving computer characters (part 3)

This is the final part of a series of articles describing the movement of computer characters. I will talk about the mixed types of movement, which combine vector and tiled methods, a small optimization of tiled movements and the acceleration of miscalculations by adding a grid to the vectors. And I will also lead a general comparison of all the described methods in the form of a table.

Animation of tiled movements

Tiled movements seem to be very “ragged”, and if this is permissible for a step-by-step strategy, it looks frankly poor in real-time mode. In order to remain within the framework of tiled movements, but to give a bit of gloss, they came up with one interesting approach: the transitions between the cells are carried out gradually (pixel-by-pixel) at a certain speed, but such movement cannot be interrupted. That is, if our mob went ahead - then the “animation” of its movement was activated, and it smoothly passed into the desired cell. This is also good in order to be able to set the speed of movement, not only for artificial intelligence, but also for the character that we control. I encountered this method in Final Fantasy II (on mobile), but I think this is used in all tiled RPGs of this type. The implementation of such a movement is not much different from the usual movement in the tile world. There will be two types of coordinates - in pixels (for character drawing - float x, y) and in cells (for calculations - int PosX, PosY). We need to add the walking flag (bool Walk) - which indicates whether our object is in motion or not. Another counter made mob steps (int Steps). And slightly modify the move function. I will show with the example of a movement to the left - only the variable X will change:

void Mob::Move(int Direction) { switch(Direction) { case 0: if(Walk == true) break;//  -  x -=1;//    1,    Steps++;//   if(Steps>CellSize) {//     Walk = false;//  Steps = 0;//   PosX = int(x/CellSize);//    } } } 

')

The combination of vector and pixel displacements

If the motion of agents is carried out using vectors, then we face a number of problems, for example, miscalculation of collisions. This can be optimized and accelerated by adding a grid, or invisible tiles. The most common are two options: cross grid and duplicating the position of objects on the grid. In both cases, it is necessary that collisions and interactions with objects, like the position of the mob itself in cellular coordinates, be determined along all of its borders. It is best to use grid sizes equal to the size of objects - then in the worst case, you will need to check the 4 neighboring cells on which our object is located.

Grid cross

In most cases, the obstacles can be outlined by some primitive, and sometimes a rectangle. In this case, there is no need to calculate collisions with all the bumps and irregularities of the obstacle. But all the same, if there are many such objects, we have to consider a collision with all potential objects, which can be resource-intensive. Then apply the grid patency. An invisible grid is superimposed on the entire world map, which is a two-dimensional array of variables of bool type. If there is an obstacle in some cell, then the value becomes true, respectively, and vice versa. The grid duplicates obstacles, but collision errors become much simpler, and even if our object moves along a vector, it can easily turn to this grid with a query: are there any obstacles there? The cell size must be selected so as to optimize the accuracy and the number of errors: too large will lead to rough angular obstacles, too small - to a greater number of errors. To determine whether it is possible to move to the next point, you need to calculate which cell of the cross-country grid we will go into and find out its condition. To do this, divide the coordinates by the cell size and discard the fractional part.

 void Mob::Move() { int NewX, NewY;//     NewX = int((x+Way.x)/CellSize);//     NewY = int((y+Way.y)/CellSize); if(Map[NewX][NewY] == true) {//    x += Way.x;//  -  y += Way.y; } } 

Optimization of vector displacements

If we have a lot of objects (more than 200), then errors of “all with all” collisions can be costly. Just for this you can use the next combination of vector and tiled worlds. As in the previous example, all objects, especially dynamic ones, are duplicated in the grid, but this time instead of the “free / busy” flag there will be the id of the mob, or even a pointer to it so that you can quickly access it. The truth will have to face the difficulty - if the object goes beyond the cell (which is quite possible), you will have to indicate its position in several adjacent cells. It is also possible to simultaneously find several objects in a single cell, so it is better to use dynamic arrays for this. Here is an example of the “cell” class, which then consists of an array of all the cells of the map.

 class Cell {//  bool Free;//   vector<int> MobsID;//  Id ,     }; 

Moving mobs is carried out in the same ways as before, only work with an array of cells is added - with each move you have to remove yourself from the previous cell and write it into a new one so that we can be found. The code is presented for a better understanding of the subject matter, it does not pretend to be optimal.

 void Mob::Move() { ... int XCell, YCell;//    XCell = int(x/CellSize);//    YCell = int(y/CellSize);//      Map[XCell][YCell].Free = false;//  Map[XCell][YCell].MobsID.pop_back(ID);//    ID ... } 

Access to a specific mob in a particular cell can be obtained as follows:

 int Id = Map[X][Y].MobsID[0];// Id      Mobs[Id].DoSomething;//  Id     

Comparison of displacement methods

We single out a number of criteria and compare all the displacement methods discussed above. I emphasize that there are optimization methods that can eliminate some of the shortcomings of the methods, we will evaluate them, so to speak, "in pure form."

findings

Thus, I found three basic ways to move computer characters. Some easier, others harder. All have their own characteristics, and the choice of a particular method will depend on the tasks. It is not necessary to implement realistic physics everywhere, giving in to fashion — in some games it is simply not needed. If you know some other ways that I haven’t written about, I’ll be happy to hear and learn from you. This is especially true of mixed methods and optimization methods, about which I have written very little.