Ways of moving computer characters (Part 1)
Everyone who started to engage in the implementation of game artificial intelligence, probably faced with the problem of the implementation of the movements of their characters. The fact is that the behavior in the real world to a greater extent determines the intellectuality of this or that being. Even people of each other are often judged by their behavior (which is a little wrong). This article is intended for those who are just starting to implement their first gaming AI. I will talk about the types of movements, their advantages and disadvantages, as well as show by example how you can implement this or that method in C ++. Comments and criticism, as well as their points of view are welcome.
Before proceeding to the enumeration of possible types of movements, it is worth considering the form in which the objects of the game or computer world can exist. Depending on this can be identified:
')
The tile method, as I wrote earlier, is when the whole world is divided into cells of the same size and all movements are carried out strictly along these cells. The most commonly used squares and hexagons. It is used in strategies (especially turn-based), RPG, etc.
To implement this method of movement is quite simple. We make the class “cell” (class Cell), create a two-dimensional array of these “cells” of the desired size (Cell Map [width] [height]). Next we generate a map, assigning certain parameters to the cells. Create a mob class (class Mob) and a dynamic array of all living beings of our world (vector mobs). Here is the source code of the blank for our tile AI:
Now we need to do our mobs. As already mentioned, the movement can be implemented in two main forms - situational and target.
When situational , there must be some direction or action that will be performed at the moment. All intelligence is aimed at changing this current action to a more optimal one in response to external or internal influences. This can be done by neural networks, a simple conditional algorithm, etc. In any case, the mob has sensory organs (for example, “seeing” a few cells forward) and a set of actions (“turn left, turn right, take a step” or “step left, step right, step forward, step back”). His "brain" reacts to data from the senses, giving the appropriate behavior.
Here is an example source code that implements a simple tiled movement. Our mob goes in a straight line until it hits the wall, then it turns in a random direction and continues to move:
And although the code is not the best, it is indicative enough for a better understanding of the displacement algorithm.
The next type of movement is target . Here it is meant that our character has some kind of plan of action, or ultimate goal. Such a plan can be a pre-compiled action template stored in a separate array. Such a pattern can be formed in different ways, from a simple blank (“left, left, forward, forward”) to a complex path generated by some sort of search algorithm (for example, A *). Moving further through this template is even easier than the previous example. Add a couple of values ​​to the mobs class and one new way to move:
These examples were supposed to show an exemplary implementation of different tile-based movement methods. Naturally, there are many realizations of displacements, and I do not claim to be the only true implementation.
The main advantages of the tile method:
The main disadvantages are:
The article turned out a little more than I had planned, so I’ll have to finish it with tiled movements. Next time I will talk about vector and mixed displacements, I will also describe the main ways to implement them, and give examples.
Modes of movement
Before proceeding to the enumeration of possible types of movements, it is worth considering the form in which the objects of the game or computer world can exist. Depending on this can be identified:
- Separate object . The most common implementation method is when a moving object is a representative of a separate class (Mob), and at the level they are stored in an array of this class (Mobs []). Most often use dynamic arrays. Thus, access to a specific mob is provided by accessing an array element (Mobs [15] .DoSomething). This is very convenient, although for very large values ​​of the array there are difficulties in miscalculation of the interaction of objects with each other, and this optimization should be further optimized.
- An object can be a state of the world . For example, if you create a two-dimensional array of values ​​(bool Map [] []), then the presence or absence of an object in this cell can be set by the cell state of the array (if there is an object in cell 15,10, Map [15] [10] = true) . According to this principle, the game "Life" is implemented.
- You can use mixed methods . When an array of individual objects is duplicated by a two-dimensional array on the map, where not only the presence or absence of the character in the cell can be entered, but also his id or pointer, so that it can be easily accessed in the general array.
')
Modes of movement
- Tiled . The whole world is a two-dimensional array of cells, and movement is carried out strictly along them. An example is playing chess, checkers, etc.
- Vector . Movement is carried out on some vector, and can be directed in any direction and at any angle (except in the case of obstacles).
- Mixed The sharing of tile and vector modes.
Modes of movement
- Situational . The character has the current direction of movement, and it is constant until it collides with something that changes its state, and hence the direction. It simply responds to external and internal influences by changing behavior.
- Trust . There is a plan or route of action, which the character follows.
- Mixed It is clear from the title - having a general plan and following it, an object can react situationally if it encounters an unexpected obstacle, and after its elimination returns to its plan.
Tiled movements
The tile method, as I wrote earlier, is when the whole world is divided into cells of the same size and all movements are carried out strictly along these cells. The most commonly used squares and hexagons. It is used in strategies (especially turn-based), RPG, etc.
To implement this method of movement is quite simple. We make the class “cell” (class Cell), create a two-dimensional array of these “cells” of the desired size (Cell Map [width] [height]). Next we generate a map, assigning certain parameters to the cells. Create a mob class (class Mob) and a dynamic array of all living beings of our world (vector mobs). Here is the source code of the blank for our tile AI:
class Cell { bool Free;// // 0-, 1-, 2-,... int Type; // int Cost; }; Cell Map[20][20];// class Mob { … }; vector<Mob> Mobs;// Now we need to do our mobs. As already mentioned, the movement can be implemented in two main forms - situational and target.
When situational , there must be some direction or action that will be performed at the moment. All intelligence is aimed at changing this current action to a more optimal one in response to external or internal influences. This can be done by neural networks, a simple conditional algorithm, etc. In any case, the mob has sensory organs (for example, “seeing” a few cells forward) and a set of actions (“turn left, turn right, take a step” or “step left, step right, step forward, step back”). His "brain" reacts to data from the senses, giving the appropriate behavior.
Here is an example source code that implements a simple tiled movement. Our mob goes in a straight line until it hits the wall, then it turns in a random direction and continues to move:
const int CellSize = 10;// class Cell { public: bool Free;// }; Cell Map[20][20];// class Mob { public: int Direction;// : 0-, 1-, 2-, 3- int X, Y;// void ChangeDirection();// bool TestStep();// true void Move();// }; void Mob::ChangeDirection() { // int Random = rand()%2;// 0 1 if(Random==0){ Direction++; if(Direction>3) Direction = 0;// } else { Direction--; if(Direction<0) Direction = 3;// } } bool Mob::TestStep() {// true int _x = int(X/CellSize);// int _y = int(Y/CellSize); switch(Direction) { case 0: return Map[_x-1][_y].Free; break; case 1: return Map[_x][_y-1].Free; break; case 2: return Map[_x+1][_y].Free; break; case 3: return Map[_x][_y+1].Free; break; } } void Mob::Move(){// switch(Direction) { case 0: if(TestStep()==true) X-=CellSize; else ChangeDirection();// - case 1: if(TestStep()==true) Y-=CellSize; else ChangeDirection();// - case 2: if(TestStep()==true) X+=CellSize; else ChangeDirection(); case 3: if(TestStep()==true) Y+=CellSize; else ChangeDirection(); } } vector<Mob> Mobs;// for(int i=0;i<Mobs.size();i++) Mobs.at(i).Move();// And although the code is not the best, it is indicative enough for a better understanding of the displacement algorithm.
The next type of movement is target . Here it is meant that our character has some kind of plan of action, or ultimate goal. Such a plan can be a pre-compiled action template stored in a separate array. Such a pattern can be formed in different ways, from a simple blank (“left, left, forward, forward”) to a complex path generated by some sort of search algorithm (for example, A *). Moving further through this template is even easier than the previous example. Add a couple of values ​​to the mobs class and one new way to move:
class Mob { public: int Direction;// : 0-, 1-, 2-, 3- int X, Y;// int Steps;//- vector<int> Path;// , Direction void ChangeDirection();// bool TestStep();// true void Move();// void PathStep();// }; void Mob::PathStep() {// switch(Path.at(Steps)) {// case 0: if(TestStep()==true) X-=CellSize; else ChangeDirection();// - case 1: if(TestStep()==true) Y-=CellSize; else ChangeDirection();// - case 2: if(TestStep()==true) X+=CellSize; else ChangeDirection(); case 3: if(TestStep()==true) Y+=CellSize; else ChangeDirection(); } Steps++;// - } for(int i=0;i<Mobs.size();i++) Mobs.at(i).PathStep();// These examples were supposed to show an exemplary implementation of different tile-based movement methods. Naturally, there are many realizations of displacements, and I do not claim to be the only true implementation.
The main advantages of the tile method:
- 1. Ease of implementation
- 2. Fewer failures
- 3. Easy to get information about the world
The main disadvantages are:
- 1. The inability to implement realistic physics
- 2. Synthetic, unnatural movements
The article turned out a little more than I had planned, so I’ll have to finish it with tiled movements. Next time I will talk about vector and mixed displacements, I will also describe the main ways to implement them, and give examples.
Source: https://habr.com/ru/post/164489/
All Articles