AI, Pathfind, Pathfollow for characters in the three-dimensional dynamic world (Part 1)
This article pushed me to write the article, as well as the fact that at the moment I am finishing the development of a fairly advanced AI for my server. All that is described here, I already use on the server and it works.
At the end of the cycle (I hope I have enough for several articles) I will try to create an AI for the defenders of the castle and the attackers, and he will not know anything about the castle in advance, will have no waypoints, and the attackers will appear by chance.
Let's start a little out of order - with pathfollow , i.e. from moving along the path already found and generally from the movement of monsters / NPCs. We will talk about how to find this way later ... and so, let's go.
')
We will work in the three-dimensional world. In principle, some algorithms can be applied exclusively for the cubic three-dimensional world (minecraft), but I will try to add information to modify the algorithm so that it works in a smooth world. The Y coordinate is directed upwards, if suddenly someone does not know or uses another coordinate system.
I describe an algorithm by which you can move an object directly from a red dot to a blue one in the figure below without first leading it to a yellow dot.
The object itself “bypasses” the angle. At what the same works with vertical obstacles, while the object jumps and tries to climb the obstacle. That is, the described algorithm can bring the object to a point that can be reached if you go straight and jump; It is not necessary to search for a way around the obstacles and lay in this way where you need to make a jump.
We will move the object, call it Entity. First you need to create a function of the movement of this object in space. How to do this, I will not describe here, this is a topic for a separate article (if anyone is interested), there are ready-made solutions on the Internet, and it’s not so difficult if you don’t take into account fast moving small objects. Instead, I will give the requirements for this function (let's call this function move , its arguments are the motion vector (dx, dy, dz)):
Add a few more variables to the Entity, which will describe its movement:
In principle, everything is simple: we turn the object in the right direction and move it forward . In this article, only this is considered. You should have a separate algorithm that turns the object in the direction where it should go at the moment, check whether it has reached the point, and direct it to the next one. I will talk about these algorithms in the following articles.
The main function of motion processing:
The two main functions are moveForward (float) and applyForces (float). The first makes the movement, the second applies the forces applied to the object.
Why not call the move function once instead of two in the moveForward and applyForces ? In fact, you can. You can simply add moveX and moveZ in the call to applyForces . But then collidedHorizontally may not turn out right. Decide where the balance will be better.
Approximate code of class Entity which turns out. Of course, there is only what is needed for the movement and nothing more. Comments in the code are left to make it clearer.
That all this does not fall apart, you need to manage the object. There should be artificial intelligence , which should not only direct the object to the next point, but also decide when to stand on the spot, and when to go forward. About this, I hope, we will talk in the following parts, if I have enough strength to write them, because I am writing when I want, this article should have been published a month ago ...
Everything that I am describing now works fine on my server, but I still work on mobs. Perhaps there will be problems, then I will supplement and edit the article. Please write your questions and comments below, maybe I missed something considering it too obvious or just missing it. If anything, I will add.
You can see how it all works, on my server. Link in profile.
At the end of the cycle (I hope I have enough for several articles) I will try to create an AI for the defenders of the castle and the attackers, and he will not know anything about the castle in advance, will have no waypoints, and the attackers will appear by chance.
Let's start a little out of order - with pathfollow , i.e. from moving along the path already found and generally from the movement of monsters / NPCs. We will talk about how to find this way later ... and so, let's go.
')
Conditions
We will work in the three-dimensional world. In principle, some algorithms can be applied exclusively for the cubic three-dimensional world (minecraft), but I will try to add information to modify the algorithm so that it works in a smooth world. The Y coordinate is directed upwards, if suddenly someone does not know or uses another coordinate system.
I describe an algorithm by which you can move an object directly from a red dot to a blue one in the figure below without first leading it to a yellow dot.
The object itself “bypasses” the angle. At what the same works with vertical obstacles, while the object jumps and tries to climb the obstacle. That is, the described algorithm can bring the object to a point that can be reached if you go straight and jump; It is not necessary to search for a way around the obstacles and lay in this way where you need to make a jump.
An object
We will move the object, call it Entity. First you need to create a function of the movement of this object in space. How to do this, I will not describe here, this is a topic for a separate article (if anyone is interested), there are ready-made solutions on the Internet, and it’s not so difficult if you don’t take into account fast moving small objects. Instead, I will give the requirements for this function (let's call this function move , its arguments are the motion vector (dx, dy, dz)):
- Should not stop immediately in a collision. For example, if we move an object along a vector (0.3, 0.0, 0.5) (x, y, z, respectively), then if we pass 0.2 in x the object encounters an obstacle, it should not stop, but continue to move along y and z. This is necessary, otherwise the movement at the walls will not be smooth enough.
- At the end of its work, the function should set 2 flags: onGround and stuckHorizontally . The first flag says that after its movement, Entity was on a solid surface, usually on the ground, but it could be on another Entity. It is calculated simply:
if(dy != 0.0D) onGround = dy < 0.0D && dy != movedY;
Where dy is how much the object wanted to move along the y axis, movedY how much Entity really moved along the y axis. As you can see, onGround = true if the entity was moving down and could not move all the desired distance (the obstacle prevented it). The second flag is more complicated:stuckHorizontally = false; if(Math.abs(dz) > Math.abs(dx)) { if(movedZ == 0.0D) stuckHorizontally = true; } else { if(movedX == 0.0D) stuckHorizontally = true; }
dx , dz , movedZ and movedX , I hope, are clear from the last example. The function considers the collision on the more “larger” axis, because it helps to avoid unnecessary “jumping” of our object. It was developed with the help of a large number of experiments, I am ready to listen to suggestions of better ideas. At the beginning, the flag is reset to false.
Add a few more variables to the Entity, which will describe its movement:
- motX , motY , motZ are variables that indicate the current speed of the object. This is not the speed of movement! These are other forces applied to this object, not counting its own movement!
- pitch and yaw are the angles of rotation of the object. The first determines the slope vertically - from -90 (looks exactly down) to 90 (looks exactly up), the second horizontally - from 0 to 360.
- moveX and moveZ - will serve as a place to store information about the next "step" of the object.
- speed and jumpSpeed - the speed of movement of the object in meters per second and the speed that is given to the object when jumping. These are the parameters that are set at the beginning. In order for an object to jump on obstacles of 1 meter, jumpSpeed ​​should be about 6m / s.
- lastTick - time in milliseconds when we last processed the object's movements (for speed in seconds, not ticks)
Algorithm
In principle, everything is simple: we turn the object in the right direction and move it forward . In this article, only this is considered. You should have a separate algorithm that turns the object in the direction where it should go at the moment, check whether it has reached the point, and direct it to the next one. I will talk about these algorithms in the following articles.
The main function of motion processing:
float secDiff = (System.currentTimeMillis() - lastTick) / 1000.0F; // , if(secDiff > 0.5F) // , , // , , secDiff = 0.5F; lastTick = System.currentTimeMillis(); // moveForward(speed * secDiff); if(stuckHorizontally) { // if(onGround) { // if(lastJumping + 500 < System.currentTimeMillis()) { jump(); // lastJumping = System.currentTimeMillis(); // . :) } } } applyForces(secDiff); // motX, motY motZ The two main functions are moveForward (float) and applyForces (float). The first makes the movement, the second applies the forces applied to the object.
protected void moveForward(float distance) { /* * . * — distance — , */ moveSpeedX = (float) -Math.sin(this.yaw / 180.0F * (float) Math.PI) * distance; moveSpeedZ = (float) Math.cos(this.yaw / 180.0F * (float) Math.PI) * distance; // — Java, - Java, -0.0F ... if(moveSpeedX == -0.0F) moveSpeedX = 0.0F; if(moveSpeedZ == -0.0F) moveSpeedZ = 0.0F; // , ... if(moveSpeedX != 0.0F || moveSpeedZ != 0.0F) this.move(moveSpeedX, 0.0D, moveSpeedZ); // , , . , , Minecraft } As I said before, after executing this piece of code, the move function should set the stuckHorizontally flag according to the conditions above. It does not change the onGround flag, because dy is 0, this flag will then be applied by applyForces . If stuckHorizontally is set to true and onGround too, then you need to jump. The jump function will do this: protected void jump() { this.motY = jumpSpeed; } Just give the object speed up ... Well, we use force . Here you can show creativity, depending on the world, the environment in which the object is located, friction and other interesting buns. I will give a simple example: private void applyForces(float secDiff) { // , -. if(Math.abs(this.motX) < 0.1D) this.motX = 0.0F; if(Math.abs(this.motY) < 0.1D) this.motY = 0.0F; if(Math.abs(this.motZ) < 0.1D) this.motZ = 0.0F; /** * . , * , * . . */ float friction = Constants.ENTITY_FLYING_FRICTION; // 0.98. — . 0.0 — . if(this.motY * secDiff != 0.0D || this.motX * secDiff != 0.0D || this.motZ * secDiff != 0.0D) // 0, , this.move(this.motX * secDiff, this.motY * secDiff, this.motZ * secDiff); this.motY -= Constants.GRAVITATION * secDiff; // /* * */ this.motX -= this.motX * friction * secDiff; this.motY -= this.motY * friction * secDiff; this.motZ -= this.motZ * friction * secDiff; } Basically, that's the whole algorithm. (Be careful with friction ... my function is not designed for secDiff more than 1 or friction more than 1!)Why not call the move function once instead of two in the moveForward and applyForces ? In fact, you can. You can simply add moveX and moveZ in the call to applyForces . But then collidedHorizontally may not turn out right. Decide where the balance will be better.
Summarize
Approximate code of class Entity which turns out. Of course, there is only what is needed for the movement and nothing more. Comments in the code are left to make it clearer.
public class Entity { public float speed = 3.0F; public float jumpSpeed = 6.0F; private long lastJumping = 0; private boolean stuckHorizontally = false; public boolean onGround = true; protected float moveSpeedX; protected float moveSpeedZ; public float motX; public float motY; public float motZ; public void tick() { float secDiff = (System.currentTimeMillis() - lastTick) / 1000.0F; // , if(secDiff > 0.5F) // , , // , , secDiff = 0.5F; lastTick = System.currentTimeMillis(); // moveForward(speed * secDiff); if(stuckHorizontally) { // if(onGround) { // if(lastJumping + 500 < System.currentTimeMillis()) { jump(); // lastJumping = System.currentTimeMillis(); // . :) } } } applyForces(secDiff); // motX, motY motZ } private void moveForward(float distance) { /* * . * — distance — , */ moveSpeedX = (float) -Math.sin(this.yaw / 180.0F * (float) Math.PI) * distance; moveSpeedZ = (float) Math.cos(this.yaw / 180.0F * (float) Math.PI) * distance; // — Java, - Java, -0.0F ... if(moveSpeedX == -0.0F) moveSpeedX = 0.0F; if(moveSpeedZ == -0.0F) moveSpeedZ = 0.0F; // , ... if(moveSpeedX != 0.0F || moveSpeedZ != 0.0F) this.move(moveSpeedX, 0.0D, moveSpeedZ); // , , . , , Minecraft } private void applyForces(float secDiff) { // , -. if(Math.abs(this.motX) < 0.1D) this.motX = 0.0F; if(Math.abs(this.motY) < 0.1D) this.motY = 0.0F; if(Math.abs(this.motZ) < 0.1D) this.motZ = 0.0F; /** * . , * , * . . */ float friction = Constants.ENTITY_FLYING_FRICTION; // 0.98. — . 0.0 — . if(this.motY * secDiff != 0.0D || this.motX * secDiff != 0.0D || this.motZ * secDiff != 0.0D) // 0, , this.move(this.motX * secDiff, this.motY * secDiff, this.motZ * secDiff); this.motY -= Constants.GRAVITATION * secDiff; // /* * */ this.motX -= this.motX * friction * secDiff; this.motY -= this.motY * friction * secDiff; this.motZ -= this.motZ * friction * secDiff; } public abstract void move(float dx, float dy, float dz); } What else is needed.
That all this does not fall apart, you need to manage the object. There should be artificial intelligence , which should not only direct the object to the next point, but also decide when to stand on the spot, and when to go forward. About this, I hope, we will talk in the following parts, if I have enough strength to write them, because I am writing when I want, this article should have been published a month ago ...
Instead of conclusion
Everything that I am describing now works fine on my server, but I still work on mobs. Perhaps there will be problems, then I will supplement and edit the article. Please write your questions and comments below, maybe I missed something considering it too obvious or just missing it. If anything, I will add.
You can see how it all works, on my server. Link in profile.
Source: https://habr.com/ru/post/165631/
All Articles