AI, Pathfind, Pathfollow для персонажей в трехмерном динамическом мире (Часть 1)

в 6:34, , рубрики: game development, Gamedev, java, minecraft, server-side, Алгоритмы, искусственный интеллект, метки: , , ,

На написание статьи меня подтолкнула данная статья а так же тот факт, что в данный момент я заканчиваю разработку довольно продвинутого AI для своего сервера. Все что описано здесь я уже использую на сервере и это работает.

В конце цикла (надеюсь, меня хватит на несколько статей) я постараюсь создать AI для защитников замка и нападающих на него, при чем он не будет знать заранее ничего о замке, не будет иметь ни каких вэйпоинтов, а нападающие будут появляться случайно.

Начнём немного не по порядку – с pathfollow, т.е. с передвижения по уже найденному пути и вообще с движения монстров/NPC. О том, как найти этот путь, мы поговорим позже… и так, поехали.

Условия

Мы будем работать в трехмерном мире. В принципе, некоторые алгоритмы могут быть применимы исключительно для кубического трехмерного мира (minecraft), но я постараюсь дополнить информацией для изменения алгоритма, чтобы он работал и в гладком мире. Координата Y направленна вверх, если вдруг кто не знает или использует другую систему координат.

Я описываю алгоритм, с помощью которого можно двигать объект напрямую из красной точки в синюю на рисунке ниже не приводя его перед этим в желтую точку.
image
Объект сам «обойдет» угол. При чем то же самое работает при вертикальных препятствиях, при этом объект подпрыгнет и постарается забраться на препятствие. То есть, описываемый алгоритм может привести объект в точку, до которой можно добраться, если идти прямо и прыгать; не обязательно искать путь в обход каждого препятствия и закладывать в этом пути, где нужно совершить прыжок.

Объект

Перемещать мы будем объект, назовём его Entity. Для начала необходимо создать функцию передвижения этого объекта в пространстве. Как это сделать я не буду описывать здесь, это тема для отдельной статьи (если кому интересно), есть готовые решения в интернете, да и это не так сложно, если не учитывать быстро движущиеся малые объекты. Вместо этого я приведу требования к этой функции (назовём эту функцию move, её аргументы — вектор движения (dx, dy, dz)):

  • Не должна немедленно останавливаться при столкновении. Например если мы двигаем объект по вектору (0.3, 0.0, 0,5) (x, y, z, соответственно), то если пройдя 0.2 по x объект натолкнется на препятствие, он должен не остановиться, а продолжить двигаться по y и z. Это необходимо, иначе движение у стен не будет достаточно плавным.
  • В конце своей работы функция должна устанавливать 2 флага: onGround и stuckHorizontally. Первый флаг говорит о том, что после своего движения Entity оказалось на твердой поверхности, обычно на земле, но может и на другом Entity. Вычисляется просто: 
    if(dy != 0.0D)
	onGround = dy < 0.0D && dy != movedY;

    Где dy — на сколько объект хотел сдвинуться по оси y, movedY — на сколько Entity реально сдвинулось по оси y. Как видно, onGround = true, если entity двигалось вниз и при этом не смогло сдвинуться на все желаемое расстояние (помешало препятствие). Второй флаг посложнее:

    stuckHorizontally = false;
if(Math.abs(dz) > Math.abs(dx)) {
	if(movedZ == 0.0D)
		stuckHorizontally = true;
	} else {
		if(movedX == 0.0D)
			stuckHorisontally = true;
	}

    dx, dz, movedZ и movedX, надеюсь, понятны по прошлому примеру. Функция считает столкновение именно по более «большей» оси, потому что это помогает избегать лишних «прыганий» нашего объекта. Она выведена при помощи большого числа экспериментов, я готова выслушать предложения более лучших идей. В начале флаг сбрасывается в false.

Добавим ещё несколько переменных к Entity, которые будут описывать его движение:

  • motX, motY, motZ — переменные, которые указывают текущую скорость объекта. Это не скорость движения! Это другие силы, приложенные к данному объекту, не считая его собственного движения!
  • pitch и yaw — углы поворота объекта. Первый определяет наклон по вертикали — от -90 (смотрит ровно вниз) до 90 (смотрит ровно вверх), второй по горизонтали — от 0 до 360.
  • moveX и moveZ — будет служить местом для хранения информации о следующем «шаге» объекта.
  • speed и jumpSpeed — скорость передвижения объекта в метрах в секунду и скорость, которая придаётся объекту при прыжке. Это параметры, которые задаются в начале. Чтобы объект мог запрыгивать на препятствия в 1 метр высотой jumpSpeed должен быть около 6м/с.
  • lastTick — время в миллисекундах, когда мы последний раз обрабатывали движения объекта (для скорости в секундах, а не тиках)

Алгоритм

В принципе, все просто: поворачиваем объект в нужную сторону и двигаем его вперед. В рамках данной статьи рассматривается только это. У вас должен быть отдельный алгоритм, который поворачивает объект в ту сторону, куда он должен идти в данный момент, проверять, дошел ли он до точки, и направлять его к следующей. Я расскажу об этих алгоритмах в следующих статьях.
Основная функция обработки движения: 

float secDiff = (System.currentTimeMillis() - lastTick) / 1000.0F; // Вычисляем время в секундах, которое прошло с прошлого цикла
if(secDiff > 0.5F) // В случае лага, будет очень неприятно, если эта цифра станет слишком большой
                   // В частности, сервер скорее всего начнет лагать ещё больше, пока цифра не достигнет огромных значений
	secDiff = 0.5F;
lastTick = System.currentTimeMillis(); // Сохраняем текущее время
moveForward(speed * secDiff, secDiff);
if(stuckHorizontally) { // Если объект застрял
	if(onGround) { // И находится на земле
		if(lastJumping + 500 < System.currentTimeMillis()) {
			jump(); // То надо прыгнуть
			lastJumping = System.currentTimeMillis(); // Время последнего прыжка. Не стоит прыгать слишком часто :)
		}
	}
}
applyForces(secDiff); // Применяем motX, motY и motZ и гравитацию

Две основные фнукции — moveForward(float, float) и applyForces(float). Первая совершает движение, вторая применяет силы, приложенные к объекту.

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
}

Как я уже говорила, после выполнения этого куска кода функция move должна установить флаг stuckHorizontally по условиям, приведенным выше. Флаг onGround она не меняет, потому что dy равен 0, этим флагом займётся потом applyForces. Если stuckHorizontally установлен в true и onGround тоже, то нужно прыгнуть. Этим займется функция jump:

protected void jump() {
	this.motY = jumpSpeed;
}

Всего-то придаём объекту скорость вверх… Ну и применяем силы. Тут можно проявить креативность, в зависимость от мира, среды, в которой находится объект, трения и прочих интересных плюшек. Я же приведу простой пример:

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;
	double var9;

	/**
	 * Трение объекта об воздух. У меня дополнительно проверяется,
	 * на какой поверхности стоит объект,  и устанавливается трение
	 * этой поверхности. Сделать это не сложно.
	 */
	float friction = Constants.ENTITY_FLYING_FRICTION; // Моё значение 0.98. Чем выше — тем меньше трение. 1.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;
}

В принципе, вот и весь алгоритм.

Почему не вызывать функцию move один раз вместо двух в moveForward и applyForces? На самом деле, можно. Можно просто прибавить moveX и moveZ в вызове move в applyForces. Но тогда collidedHorizontally может получиться не правильным. Сами решайте, где баланс будет лучше.

Суммируем

Примерный код класса Entity, который получится. Конечно, тут только то, что нужно для движения и ничего более. Комментарии в коде оставлены, чтобы было понятнее. 

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;
		double var9;

		/**
		 * Трение объекта об воздух. У меня дополнительно проверяется,
		 * на какой поверхности стоит объект,  и устанавливается трение
		 * этой поверхности. Сделать это не сложно.
		 */
		float friction = Constants.ENTITY_FLYING_FRICTION; // Моё значение 0.98. Чем выше — тем меньше трение. 1.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);
}

Что ещё нужно.

Чтобы все это не развалилось, нужно объектом управлять. Должен быть искусственный интеллект, который должен не только направлять объект в следующую точку, но ещё и решать, когда объекту стоять на месте, а когда идти вперед. Об этом, я надеюсь, поговорим в следующих частях, если мне хватит сил их написать, потому что пишу, когда вздумается, эта статья должна была выйти месяц назад…

Вместо заключения

Все что я описываю сейчас отлично работает у меня на сервере, но над мобами я ещё работаю. Возможно, обнаружатся проблемы, тогда я буду дополнять и править статью. Пожалуйста, пишите ваши вопросы и замечания ниже, возможно я что-то пропустила посчитав слишком очевидным или просто упустив. Если что, допишу.

Можете посмотреть, как всё это работает, у меня на сервере. Ссылка в профиле.

Автор: Rena4ka

Источник

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js