Статьи

Игра AI — Введение в деревья поведения

Ноябрь 23, 2018

Игровой ИИ — очень обширный предмет, и хотя там много материала, я не нашел чего-то, что вводило бы концепции мягко и в более медленном, более понятном темпе. В этой статье мы попытаемся объяснить, как спроектировать очень простую, но расширяемую систему искусственного интеллекта, основанную на концепции деревьев поведения.

Что такое ИИ?

Искусственный интеллект — это поведение, подобное человеческому, проявляемое субъектами, участвующими в игре. Это скорее иллюзия интеллекта и вдумчивого действия, совершаемого сущностями, чем действительное поведение, основанное на разумном рассуждении. Цель состоит в том, чтобы попытаться обмануть игрока, думая, что другие «разумные» сущности контролируются людьми, а не машиной. Это легче сказать, чем сделать, но мы можем использовать много хитростей, чтобы добиться действительно хорошего, казалось бы, случайного и «интеллектуального» поведения.

Пример

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

Арена будет доской, и на ней будут случайно размещаться дроиды. Мы сделаем это пошаговой игрой, чтобы мы могли следить за развёртыванием всего ИИ, но его легко превратить в игру в реальном времени.

Правила просты:

  • Доска представляет собой прямоугольник
  • Дроид может перемещать одну плитку за ход в любом направлении к любой из соседних незанятых плиток.
  • У дроида есть радиус действия, и он может стрелять по дроидам в пределах своего диапазона
  • У дроидов будут обычные атрибуты: наносимый им урон и очки жизни

Для простоты мы будем использовать очень простые структуры. Приложение будет иметь класс Droid класс Board . У дроида будут следующие атрибуты, которые его определяют:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Droid {
 
    final String name;
    int x;
    int y;
    int range;
    int damage;
    int health;
 
    Board board;
 
    public Droid(String name, int x, int y, int health, int damage, int range) {
        this.name = name;
        this.x = x;
        this.y = y;
        this.health = health;
        this.damage = damage;
        this.range = range;
    }
 
    public void update() {
        // placeholder for each turn or tick
    }
 
    /* ... */
    /* getters and setters and toString() */
    /* ... */
}

Droid — это просто Pojo с несколькими атрибутами. Атрибуты говорят сами за себя, но вот краткое их описание:

  • name — уникальное имя дроида, также может использоваться для идентификации.
  • x и y — координаты на сетке.
  • health , damage и range — о чем это говорит.
  • board — это ссылка на Board на которой находится дроид вместе с другими дроидами. Нам это нужно, потому что дроид будет принимать решения, зная свое окружение, то есть правление <./ li>

Существует также пустой метод update() который вызывается каждый раз, когда дроид заканчивает свой ход. Если это игра в реальном времени, метод обновления вызывается из игрового цикла, в идеале из игрового движка.

Есть также очевидные методы получения и установки, а также метод toString() которые не включены в листинг. Класс Board очень прост.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Board {
 
    final int width;
    final int height;
 
    private List<Droid> droids = new ArrayList<Droid>();
 
    public Board(int width, int height) {
        this.width = width;
        this.height = height;
    }
 
    public int getWidth() {
        return width;
    }
 
    public int getHeight() {
        return height;
    }
 
    public void addDroid(Droid droid) {
        if (isTileWalkable(droid.getX(), droid.getY())) {
            droids.add(droid);
            droid.setBoard(this);
        }
    }
 
    public boolean isTileWalkable(int x, int y) {
        for (Droid droid : droids) {
            if (droid.getX() == x && droid.getY() == y) {
                return false;
            }
        }
        return true;
    }
 
    public List<Droid> getDroids() {
        return droids;
    }
}

Он имеет width и height и содержит список дроидов. Он также содержит несколько удобных методов, чтобы проверить, присутствует ли дроид в заданной координате, и метод, позволяющий легко добавлять дроидов одного за другим.

Пока что это довольно стандартно. Мы можем разбросать по доске несколько дроидов, но они ничего не сделают. Мы можем создать доску, добавить к ней несколько дроидов и начать вызывать update() . Это всего лишь несколько тупых дроидов.

Не такие тупые дроиды

Чтобы заставить дроида что-то сделать, мы могли бы реализовать логику в его методе update() . Этот метод называется каждый тик или, в нашем случае, каждый ход. Например, мы хотим, чтобы наши дроиды бродили по арене (доске), и если они видят другого дроида в радиусе действия, атакуйте их и начинайте стрелять по ним, пока они не умрут. Это был бы очень элементарный ИИ, но все еще ИИ.

Псевдокод будет выглядеть так:
if enemy in range then fire missile at it
otherwise pick a random adjacent tile and move there

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

if enemy in range then
if enemy is weaker then fight
otherwise
if escape route exists then escape
otherwise fight
otherwise wander

Это все хорошо. Дроиды начнут действовать «разумно», но они все еще будут очень ограничены, если мы не добавим больше кода, чтобы делать более умные вещи. А также они будут действовать так же. Представьте, если вы бросите их на более сложную арену. Арена, где есть такие предметы, как бонусы, чтобы усилить силы, препятствия, которых следует избегать. Например, решите, взять ли вы комплект для ремонта / восстановления здоровья и включить оружие, когда вокруг роятся дроиды.
Это может выйти из рук довольно быстро. И что если мы хотим по-другому вести себя дроидами. Один — штурмовой дроид, а другой — ремонтный дроид. Конечно, мы могли бы достичь этого с помощью композиции объектов , но мозг дроидов будет чрезвычайно сложным, и любое изменение в игровом дизайне потребует огромных усилий для его размещения.

Давайте посмотрим, сможем ли мы придумать систему, которая может решить эти проблемы.

Вот идет мозг

Мы можем думать об AI-модуле дроида как о некоем мозге. Мозг состоит из нескольких рутин, которые действуют на дроида, следуя ряду правил. Эти правила управляют выполнением рутины, таким образом, это максимизирует шансы на выживание и победу в игре в качестве конечной цели. Если мы думаем о нашем человеческом мозге, состоящем из рутин и имеющем иерархию потребностей Маслоу в качестве ориентира, мы можем мгновенно определить несколько рутин.

  • Физиологическая рутина — рутина, которую нужно выполнять каждый раз, иначе жизни не будет
  • Прожиточный минимум — эта рутина должна выполняться после того, как условия жизни будут выполнены, чтобы обеспечить долгосрочное существование
  • Желательная процедура — это будет выполнено, если есть время, оставшееся после того, как прожиточный минимум был обеспечен, и до того, как прожиточный минимум должен быть выполнен снова

Давайте немного сломаем человеческий интеллект. Человеку нужно дышать, чтобы жить. Каждое дыхание потребляет энергию. Можно так много дышать, пока не закончится энергия. Чтобы пополнить энергию, нужно есть. Кушать можно только в том случае, если в его распоряжении есть еда. Если нет доступной еды, ее нужно приобрести, которая потребляет больше энергии. Если заготовка пищи занимает много времени (например, на нее нужно охотиться), а количество получаемой пищи невелико, то после еды человек нуждается в большем количестве еды, и процедура возобновляется без промедления. Если еда была куплена оптом в супермаркете, то после того, как она была съедена, остается много, чтобы человек мог перейти к более интересным вещам, которые есть в его / ее желательном разделе. Например, заводить друзей, вести войну или смотреть телевизор.
Подумайте, сколько вещей в человеческом мозгу, чтобы заставить нас функционировать, и попытайтесь смоделировать это. Это все, игнорируя большинство стимулов, которые мы получаем, и реагируя на них. Чтобы сделать это, нам нужно было бы параметризировать человеческое тело, и каждый датчик, вызванный стимулом, обновит правильные параметры, и выполненная процедура будет проверять новые значения и действовать соответственно. Я не буду описывать это сейчас, но вы поняли идею, я надеюсь.

Вернемся к нашим гораздо более простым дроидам. Если мы попытаемся приспособить человеческие рутины к дроидам, мы получим что-то вроде этого:

  • Физиологический / экзистенциальный — эту часть мы можем игнорировать для этого примера, потому что мы разрабатываем роботов, а они — механические существа. Конечно, для их существования им по-прежнему нужна энергия (например, точки действия), которую они могут получить от батареи или от другого источника энергии, который может быть истощен. Ради простоты мы будем игнорировать это и считать источник энергии бесконечным.
  • Прожиточный минимум / безопасность — эта процедура гарантирует, что дроид выживет в текущем повороте и выживет, избегая непосредственной угрозы.
  • Вдохновенный — это срабатывает, как только программа безопасности проверила ОК, и не нужно было активировать процедуру бегства дроида. Текущее простое стремление дроида — убить других дроидов.

Хотя описанные процедуры очень просты и могут быть жестко запрограммированы, подход, который мы предпримем для реализации, немного более сложен. Мы будем использовать подход, основанный на деревьях поведения .

Прежде всего, мы должны передать все действия дроида его мозгу. Я назову это Routine вместо мозга. Он может называться Brain или AI или как угодно, но я выбрал Routine, потому что он будет служить базовым классом для всех подпрограмм, которые будут состоять. Также он будет отвечать за управление потоком информации в мозге. Сама Routine является конечным автоматом с 3 состояниями.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public abstract class Routine {
 
    public enum RoutineState {
        Success,
        Failure,
        Running
    }
 
    protected RoutineState state;
 
    protected Routine() { }
 
    public void start() {
        this.state = RoutineState.Running;
    }
 
    public abstract void reset();
 
    public abstract void act(Droid droid, Board board);
 
    protected void succeed() {
        this.state = RoutineState.Success;
    }
 
    protected void fail() {
        this.state = RoutineState.Failure;
    }
 
    public boolean isSuccess() {
        return state.equals(RoutineState.Success);
    }
 
    public boolean isFailure() {
        return state.equals(RoutineState.Failure);
    }
 
    public boolean isRunning() {
        return state.equals(RoutineState.Running);
    }
 
    public RoutineState getState() {
        return state;
    }
}

3 состояния:

  • Running — процедура в настоящий момент выполняется и будет действовать на дроида в следующем ходу. Например. рутина несет ответственность за перемещение дроида в определенную позицию, и дроид находится в пути и все еще движется непрерывно.
  • Success — рутина закончилась, и она преуспела в том, что должна была сделать. Например, если подпрограмма все еще является «перемещением в позицию», она преуспела, когда дроид достиг цели.
  • Failure — в предыдущем примере (перейти к) перемещение дроида было прервано (либо дроид был уничтожен, либо появилось какое-то неожиданное препятствие, либо помешала какая-то другая рутина), и он не достиг цели.

Класс Routine имеет абстрактный метод act(Droid droid, Board board) . Нам нужно передать дроида и Board потому что когда действует рутина, она действует на дроида и при знании окружения дроида, которым является доска. Например, процедура moveTo будет менять положение дроида каждый ход. Обычно, когда рутина воздействует на дроида, она использует знания, полученные из окружающей среды. Эти знания смоделированы на реалиях ситуации. Представьте, что дроид (как и мы, люди) не может видеть весь мир, но только настолько далеко, насколько его видит. У нас, людей, поле зрения составляет около 135 градусов, поэтому, если мы будем имитировать человека, мы передадим кусочек мира, содержащий видимую часть и все видимые компоненты в нем, и позволим обычному процессу просто так в меру своих возможностей и прийти к выводу. Мы можем сделать это и для дроидов, и просто перейдем к той части доски, которая покрыта range , но пока мы будем просты и будем использовать всю доску. Методы start() , succeed() и fail() являются простыми общедоступными переопределяемыми методами, которые соответствующим образом устанавливают состояние. Метод reset() с другой стороны, является абстрактным, и он должен быть реализован каждой конкретной подпрограммой для сброса любого внутреннего состояния, принадлежащего этой подпрограмме. Остальные — это удобные методы для запроса состояния подпрограммы.

Учиться ходить

Давайте реализуем первую конкретную процедуру, которая будет MoveTo обсуждаемой выше.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class MoveTo extends Routine {
 
    final protected int destX;
    final protected int destY;
 
    public MoveTo(int destX, int destY) {
        super();
        this.destX = destX;
        this.destY = destY;
    }
 
    public void reset() {
        start();
    }
 
    @Override
    public void act(Droid droid, Board board) {
        if (isRunning()) {
            if (!droid.isAlive()) {
                fail();
                return;
            }
            if (!isDroidAtDestination(droid)) {
                moveDroid(droid);
            }
        }
    }
 
    private void moveDroid(Droid droid) {
        if (destY != droid.getY()) {
            if (destY > droid.getY()) {
                droid.setY(droid.getY() + 1);
            } else {
                droid.setY(droid.getY() - 1);
            }
        }
        if (destX != droid.getX()) {
            if (destX > droid.getX()) {
                droid.setX(droid.getX() + 1);
            } else {
                droid.setX(droid.getX() - 1);
            }
        }
        if (isDroidAtDestination(droid)) {
            succeed();
        }
    }
 
    private boolean isDroidAtDestination(Droid droid) {
        return destX == droid.getX() && destY == droid.getY();
    }
}

Это очень простой класс, который будет перемещать дроида на одну клетку к месту назначения, пока не достигнет его. Он не проверяет наличие каких-либо других ограничений, кроме как, если дроид жив. Это условие неудачи. Процедура имеет 2 параметра: destX и destY . Это последние атрибуты, которые подпрограмма MoveTo будет использовать для достижения своей цели. Единственная обязанность рутины — переместить дроида. Если он не может этого сделать, он потерпит неудачу. Вот и все. Единственная ответственность здесь очень важна. Мы увидим, как мы скомбинируем их для достижения более сложного поведения. Метод reset() просто устанавливает статус на Running . У него нет другого внутреннего состояния или значений, с которыми нужно иметь дело, но его необходимо переопределить.
Сердцем этой процедуры является метод act(Droid droid, Board board) который выполняет действие и содержит логику. Сначала он проверяет состояние отказа, если дроид мертв. Если он мертв и подпрограмма активна (ее состояние « Running ), то подпрограмма не смогла сделать то, что должна была. Он вызывает метод fail() по умолчанию для суперкласса, чтобы установить статус Failure и завершает работу метода.
Вторая часть метода проверяет условие успеха. Если дроид еще не в пункте назначения, то переместите дроида на одну клетку к месту назначения. Если оно достигло места назначения, установите состояние « Success . Проверка isRunning() выполняется, чтобы убедиться, что подпрограмма действует только в том случае, если подпрограмма активна и еще не завершена.

Нам также нужно заполнить метод update Droid чтобы он использовал процедуру. Это просто простая делегация. Вот как это выглядит:

1
2
3
4
5
6
7
public void update() {
        if (routine.getState() == null) {
            // hasn't started yet so we start it
            routine.start();
        }
        routine.act(this, board);
    }

Он должен состоять только из строки № 6, но я также вставил проверку, чтобы увидеть, является ли состояние null и если да, то start процедуру. Это хак для запуска процедуры при первом вызове update . Это квази-командный шаблон, так как в методе act в качестве параметра принимается получатель команды действия, которым является сам дроид. Я также изменил класс Routine для регистрации различных событий в нем, чтобы мы могли видеть, что происходит.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
// --- omitted --- */
    public void start() {
        System.out.println(">>> Starting routine: " + this.getClass().getSimpleName());
        this.state = RoutineState.Running;
    }
 
    protected void succeed() {
        System.out.println(">>> Routine: " + this.getClass().getSimpleName() + " SUCCEEDED");
        this.state = RoutineState.Success;
    }
 
    protected void fail() {
        System.out.println(">>> Routine: " + this.getClass().getSimpleName() + " FAILED");
        this.state = RoutineState.Failure;
    }
    // --- omitted --- */

Давайте проверим это с помощью простого класса Test .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
public class Test {
 
    public static void main(String[] args) {
        // Setup
        Board board = new Board(10, 10);
 
        Droid droid = new Droid("MyDroid", 5, 5, 10, 1, 2);
        board.addDroid(droid);
 
        Routine moveTo = new MoveTo(7, 9);
        droid.setRoutine(moveTo);
        System.out.println(droid);
 
        // Execute 5 turns and print the droid out
        for (int i = 0; i < 5; i++) {
            droid.update();
            System.out.println(droid);
        }
    }
}

Это стандартный класс с методом main который первым устанавливает квадратную Board 10 x 10 и добавляет Droid с предоставленными атрибутами в координатах 5,5 . В строке # 10 мы создаем процедуру MoveTo которая устанавливает пункт назначения (7,9) . Мы устанавливаем эту подпрограмму как единственную подпрограмму дроида (строка № 11 ) и печатаем состояние дроида (строка № 12 ). Затем мы выполняем 5 ходов и показываем состояние дроида после каждого хода.

Запустив Test мы видим следующее, напечатанное в sysout:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
Droid{name=MyDroid, x=5, y=5, health=10, range=2, damage=1}
 
>>> Starting routine: MoveTo
 
Droid{name=MyDroid, x=6, y=6, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=7, y=7, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=7, y=8, health=10, range=2, damage=1}
 
>>> Routine: MoveTo SUCCEEDED
 
Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}

Как мы видим, дроид стартует в позиции (5,5), как и ожидалось. При первом MoveTo метода update запускается процедура MoveTo . Последующие 3 вызова для обновления переместят дроида к месту назначения, меняя его координаты каждый ход на один. После успешного выполнения подпрограммы все вызовы, переданные подпрограмме, игнорируются, поскольку она завершена.

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

Бродить о

Но давайте начнем с рутины Wander . Это не что иное, как MoveTo но мы генерируем случайный пункт назначения, учитывая, что мы знаем доску.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Wander extends Routine {
 
    private static Random random = new Random();
    private final Board board;
    private MoveTo moveTo;
 
    @Override
    public void start() {
        super.start();
        this.moveTo.start();
    }
 
    public void reset() {
        this.moveTo = new MoveTo(random.nextInt(board.getWidth()), random.nextInt(board.getHeight()));
    }
 
    public Wander(Board board) {
        super();
        this.board = board;
        this.moveTo = new MoveTo(random.nextInt(board.getWidth()), random.nextInt(board.getHeight()));
    }
 
    @Override
    public void act(Droid droid, Board board) {
        if (!moveTo.isRunning()) {
            return;
        }
        this.moveTo.act(droid, board);
        if (this.moveTo.isSuccess()) {
            succeed();
        } else if (this.moveTo.isFailure()) {
            fail();
        }
    }
}

Следуя принципу единственной ответственности, единственной целью класса Wander является выбор случайного пункта назначения на доске. Затем он использует процедуру MoveTo чтобы доставить дроида к новому месту назначения. Метод reset перезапустит его и выберет новый случайный пункт назначения. Назначение задается в конструкторе. Если бы мы хотели, чтобы наш дроид блуждал, мы изменили бы класс Test на следующий:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
public class Test {
    public static void main(String[] args) {
        // Setup
        Board board = new Board(10, 10);
 
        Droid droid = new Droid("MyDroid", 5, 5, 10, 1, 2);
        board.addDroid(droid);
 
        Routine routine = new Wander(board);
        droid.setRoutine(routine);
        System.out.println(droid);
 
        for (int i = 0; i < 5; i++) {
            droid.update();
            System.out.println(droid);
        }
    }
}

Вывод будет примерно таким:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
Droid{name=MyDroid, x=5, y=5, health=10, range=2, damage=1}
 
>>> Starting routine: Wander
 
>>> Starting routine: MoveTo
 
Droid{name=MyDroid, x=6, y=6, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=7, y=7, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=7, y=8, health=10, range=2, damage=1}
 
>>> Routine: MoveTo SUCCEEDED
 
>>> Routine: Wander SUCCEEDED
 
Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}

Обратите внимание, как Wander содержит и делегирует подпрограмму MoveTo .

Повторите, Повторите, Повторите …

Это все хорошо, но что, если мы хотим, чтобы дроид постоянно бродил? Мы сделаем процедуру Repeat которая будет содержать процедуру, которую нужно повторить. Также мы сделаем эту процедуру так, чтобы она могла принимать параметр, чтобы указать, сколько раз мы хотим повторить процедуру. Если он не будет принимать параметр, он будет повторять содержащуюся процедуру навсегда или до тех пор, пока дроид не умрет.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Repeat extends Routine {
 
    private final Routine routine;
    private int times;
    private int originalTimes;
 
    public Repeat(Routine routine) {
        super();
        this.routine = routine;
        this.times = -1; // infinite
        this.originalTimes = times;
    }
 
    public Repeat(Routine routine, int times) {
        super();
        if (times < 1) {
            throw new RuntimeException("Can't repeat negative times.");
        }
        this.routine = routine;
        this.times = times;
        this.originalTimes = times;
    }
 
    @Override
    public void start() {
        super.start();
        this.routine.start();
    }
 
    public void reset() {
        // reset counters
        this.times = originalTimes;
    }
 
    @Override
    public void act(Droid droid, Board board) {
        if (routine.isFailure()) {
            fail();
        } else if (routine.isSuccess()) {
            if (times == 0) {
                succeed();
                return;
            }
            if (times > 0 || times <= -1) {
                times--;
                routine.reset();
                routine.start();
            }
        }
        if (routine.isRunning()) {
            routine.act(droid, board);
        }
    }
}

Код легко следовать, но я объясню несколько вещей, которые были добавлены. Процедура атрибута передается в конструкторе, и эта процедура будет повторяться. originalTimes — это переменная хранения, которая содержит начальное значение количества раз, поэтому мы можем перезапустить подпрограмму с помощью вызова reset() . Это просто резервная копия исходного состояния. Атрибут times указывает, сколько раз предоставленная процедура будет повторена. Если это -1 то это бесконечно. Все это закодировано в логике внутри метода act . Чтобы проверить это, нам нужно создать процедуру Repeat и указать, что повторить. Например, чтобы дроид бесконечно бродил, у нас было бы следующее:

1
2
Routine routine = new Repeat((new Wander(board)));
        droid.setRoutine(routine);

Если мы будем вызывать update несколько раз, мы увидим, что дроид будет постоянно двигаться. Проверьте этот пример вывода:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
Droid{name=MyDroid, x=5, y=5, health=10, range=2, damage=1}
 
>> Starting routine: Repeat
 
>>> Starting routine: Wander
 
>>> Starting routine: MoveTo
 
Droid{name=MyDroid, x=4, y=6, health=10, range=2, damage=1}
 
>>> Routine: MoveTo SUCCEEDED
 
>>> Routine: Wander SUCCEEDED
 
Droid{name=MyDroid, x=4, y=7, health=10, range=2, damage=1}
 
>>> Starting routine: Wander
 
>>> Starting routine: MoveTo
 
Droid{name=MyDroid, x=5, y=6, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=6, y=5, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=7, y=4, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=8, y=3, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=8, y=2, health=10, range=2, damage=1}
 
>>> Routine: MoveTo SUCCEEDED
 
>>> Routine: Wander SUCCEEDED
 
Droid{name=MyDroid, x=8, y=1, health=10, range=2, damage=1}
 
>>> Starting routine: Wander
 
>>> Starting routine: MoveTo
 
Droid{name=MyDroid, x=7, y=2, health=10, range=2, damage=1}
 
Droid{name=MyDroid, x=6, y=3, health=10, range=2, damage=1}

Обратите внимание, как процедура Repeat не заканчивается.

Сборка интеллекта

Пока что мы просто сочиняем поведения. Но что, если мы хотим добавить принятие решений к дроидам и построить более сложное поведение? Введите деревья поведения. Этот термин не описывает, что это такое, а также большинство статей, которые я нашел. Сначала я начну с того, чего хочу достичь, и, надеюсь, все это будет иметь смысл. Я хочу реализовать поведение, описанное в начале статьи. Я хочу, чтобы мой дроид сканировал, если в его радиусе действия находился более слабый дроид, и включал его, если он есть, или убегал иначе. Посмотрите на следующую диаграмму. Это показывает дерево. Это не что иное, как подпрограмма, состоящая из нескольких разных подпрограмм. Каждый узел является подпрограммой, и нам нужно будет реализовать некоторые специальные подпрограммы.

Дерево Поведения

Droid AI (Дерево Поведения)

Давайте сломать рутины вниз.

  • Repeat — это процедура, реализованная ранее. Он будет повторять данную процедуру вечно или до тех пор, пока встроенная процедура не завершится неудачно.
  • Sequence — подпрограмма последовательности будет успешной только тогда, когда все подпрограммы, которые она содержит, были успешны. Например, чтобы атаковать дроида, вражеский дроид должен находиться в радиусе действия, оружие должно быть заряжено, и дроид должен нажать на курок. Все в этом порядке. Таким образом, последовательность содержит список подпрограмм и действует на них, пока все не выполнятся. Если оружие не заряжено, нет смысла нажимать на курок, поэтому вся атака провалена.
  • Selector — эта подпрограмма содержит список из одной или нескольких подпрограмм. Когда это действует, это будет успешно, когда одна из подпрограмм в списке будет успешной. Порядок, в котором выполняются подпрограммы, определяется порядком, в котором передаются подпрограммы. Если мы хотим рандомизировать выполнение подпрограмм, легко создать подпрограмму Random , единственная цель которой состоит в том, чтобы рандомизировать список подпрограмм. прошло.
  • Все серые процедуры — это листья в дереве, что означает, что у них не может быть никаких последующих процедур, и они действуют на дроида, который является получателем.

Вышеупомянутое дерево представляет собой базовый ИИ, который мы хотели реализовать. Давайте проследим за этим, начиная с корня.
Repeat — будет повторять селектор бесконечно, пока ни одна из ветвей не может быть успешно выполнена. Процедуры в селекторе: Attack a droid и Wander . Если оба не удаются, это означает, что дроид мертв. Подпрограмма « Attack a droid — это последовательность подпрограмм, означающая, что все они должны преуспеть для того, чтобы преуспела вся ветвь. Если это не удается, то отступить — выбрать случайный пункт назначения через Wander и двигаться туда. Тогда повторите.

Все, что нам нужно сделать, это реализовать подпрограммы. Например, IsDroidInRange может выглядеть примерно так:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class IsDroidInRange extends Routine {
 
    public IsDroidInRange() {}
 
    @Override
    public void reset() {
        start();
    }
 
    @Override
    public void act(Droid droid, Board board) {
        // find droid in range
        for (Droid enemy : board.getDroids()) {
            if (!droid.getName().equals(enemy)) {
                if (isInRange(droid, enemy)) {
                    succeed();
                    break;
                }
            }
        }
        fail();
    }
 
    private boolean isInRange(Droid droid, Droid enemy) {
        return (Math.abs(droid.getX() - enemy.getX()) <= droid.getRange()
                || Math.abs(droid.getY() - enemy.getY()) < droid.getRange());
    }
}

Это очень простая реализация. Он определяет, находится ли дроид в радиусе действия, итерацией всех дроидов на доске, и если вражеский дроид (предполагая, что имена уникальны) находится в пределах досягаемости, то это удается. В противном случае это не удалось. Конечно, нам нужно как-то скормить этого дроида следующей процедуре, то есть IsEnemyStronger . Этого можно достичь, предоставив дроиду контекст. Одним простым способом может быть то, что класс Droid может иметь атрибут nearestEnemy и в случае success процедура заполнит это поле, а при nearestEnemy очистит его. Таким образом, следующая процедура может получить доступ к внутренностям дроида и использовать эту информацию для разработки сценариев его успеха или неудачи. Конечно, это может быть и должно быть расширено, так что дроид будет содержать список дроидов в своем диапазоне и иметь рутину, чтобы решить, должен ли дроид летать или сражаться. Но это не сфера применения этого введения.

Я не буду реализовывать все подпрограммы в этой статье, но вы сможете проверить код на github: https://github.com/obviam/behavior-trees, и я буду добавлять все больше и больше подпрограмм.

Куда пойти отсюда?

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Static convenience methods to create routines
 */
public class Routines {
 
    public static Routine sequence(Routine... routines) {
        Sequence sequence = new Sequence();
        for (Routine routine : routines) {
            sequence.addRoutine(routine);
        }
        return sequence;
    }
 
    public static Routine selector(Routine... routines) {
        Selector selector = new Selector();
        for (Routine routine : routines) {
            selector.addRoutine(routine);
        }
        return selector;
    }
 
    public static Routine moveTo(int x, int y) {
        return new MoveTo(x, y);
    }
 
    public static Routine repeatInfinite(Routine routine) {
        return new Repeat(routine);
    }
 
    public static Routine repeat(Routine routine, int times) {
        return new Repeat(routine, times);
    }
 
    public static Routine wander(Board board) {
        return new Wander(board);
    }
 
    public static Routine IsDroidInRange() {
        return new IsDroidInRange();
    }
 
}

Это позволит протестировать некоторые сценарии более элегантным способом. Например, чтобы разместить 2 дроидов с различным поведением, вы можете сделать следующее:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void main(String[] args) {
        Board board = new Board(25, 25);
        Droid droid1 = new Droid("Droid_1", 2, 2, 10, 1, 3);
        Droid droid2 = new Droid("Droid_2", 10, 10, 10, 2, 2);
 
        Routine brain1 = Routines.sequence(
                Routines.moveTo(5, 10),
                Routines.moveTo(15, 12),
                Routines.moveTo(2, 4)
        );
        droid1.setRoutine(brain1);
 
        Routine brain2 = Routines.sequence(
            Routines.repeat(Routines.wander(board), 4)
        );
        droid2.setRoutine(brain2);
 
        for (int i = 0; i < 30; i++) {
            System.out.println(droid1.toString());
            System.out.println(droid2.toString());
            droid1.update();
            droid2.update();
        }
    }

Конечно, это далеко не лучшее решение, но оно все же лучше, чем постоянное создание процедур. В идеале ИИ должен быть написан на сценарии и загружен из внешнего источника, либо с помощью сценариев, либо, по крайней мере, предоставлен, например, в виде JSON, и создать его должен ассемблер ИИ. Таким образом, нет необходимости перекомпилировать игру каждый раз, когда ИИ настраивается. Но опять же, это не является предметом данной статьи.

Кроме того, как мы должны решить, какое действие займет ход / тик или оценивается мгновенно? Одним из возможных решений может быть выделение очков действия дроиду, чтобы он мог потратить один ход (отметьте галочкой в ​​режиме реального времени), и для каждого действия назначьте цену. Всякий раз, когда у дроида заканчиваются точки, мы можем двигаться дальше. Нам также необходимо отследить, какая подпрограмма является текущей, чтобы мы могли оптимизировать обход дерева. Это полезно, если ИИ очень сложны, особенно в играх реального времени.

Если вы считаете, что статья была полезной и хотите получить код, пожалуйста, проверьте репозиторий github. Вы также можете проверить, потому что я собираюсь расширить и обновить его, чтобы он превратился в более полный пример ИИ. Так как это моя первая встреча с ИИ, будет много чего улучшить, и я всегда открыт для критики и идей о том, как улучшить.

Ссылка: AI игры — введение в деревья поведения от нашего партнера JCG Impaler в блоге Against the Grain .
83
Share: