[Из песочницы] Как я писал классические танки с интеллектом

Вступление

Я являюсь независимым разработчиком приложений под Android (а конкретней — полтора года разработки интеллектуальной версии классической всеми любимой культовой игры «Танчики 1990»).

Почему я решил написать эту игру: к играм я имею ещё более непосредственное отношение (играю в них). В плэймаркете я не увидел ни одной 2D-игры, где присутствовал бы алгоритм принятия решений о поиске кратчайшего пути. Я не говорю о более сложных играх, написанных на мощных движках. От чего зависит процент таких игр, я не знаю. Или это следствие идейной составляющей, или же результат конъюнктуры игрового рынка в целом, мне неизвестно. Моё личное мнение: таких игр должно быть больше.

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

Имитация оппонента в контексте мною написанной игры — это скорее «псевдоинтеллект» (оптимизированное варьирование между целями — задачами и, как следствие, между поиском путей).

Как алгоритм поиска пути я использовал А* (A-star). Вот его моя реализация на java:

import com.me.tanks1990Intellect.Classes.Pair;
import java.util.*;

public class AlgoritmAstar {

    static Comparator comparator = new Comparator() {

        public int compare(PathNode pathNode1, PathNode pathNode2) {

            int fullPath1 = pathNode1.EstimateFullPathLength();
            int fullPath2 = pathNode2.EstimateFullPathLength();

            return fullPath1 > fullPath2 ? 1 : fullPath1 == fullPath2 ? 0 : -1;
        }
    };

    private static int iteratorsCount = 0;
    private static int maxIteratorsCount = 100;

    public static int getIteratorsCount () {

        return iteratorsCount;
    }

    public static ArrayList FindPath(Integer[][] field, Pair start,
            Pair goal) {

        // TestMapStructure.printMap(field); TODO: printMap

        ArrayList closedSet = new ArrayList();
        ArrayList openSet = new ArrayList();

        PathNode startNode = new PathNode();

        startNode.Position = start;
        startNode.CameFrom = null;
        startNode.PathLengthFromStart = 0;
        startNode.HeuristicEstimatePathLength = GetHeuristicPathLength(start,
                goal);

        openSet.add(startNode);

        iteratorsCount = 0;

        while (openSet.size() > 0) {

            if (++iteratorsCount > maxIteratorsCount)
                return null;

            Collections.sort(openSet, comparator);
            PathNode currentNode = openSet.get(0);

            if (currentNode.Position.equals(goal)) {

                ArrayList result = GetPathForNode(currentNode);
                // TestMapStructure.printMap(field, result); //TODO: printMap

                return result;
            }

            openSet.remove(currentNode);
            closedSet.add(currentNode);

            ArrayList neighbours = (ArrayList) GetNeighbours(
                    currentNode, goal, field);

            for (final PathNode neighbourNode : neighbours) {

                if (ArrayHelper.getCount(closedSet, new Comparator() {

                    @Override
                    public boolean equals(Object obj) {
                        return ((PathNode) obj).Position
                                .equals(neighbourNode.Position);
                    }

                    @Override
                    public int compare(PathNode o1, PathNode o2) {
                        return 0;
                    }
                }) > 0)
                    continue;

                PathNode openNode = ArrayHelper.getFirstorDefault(openSet,
                        new Comparator() {

                            @Override
                            public boolean equals(Object obj) {
                                return ((PathNode) obj).Position
                                        .equals(neighbourNode.Position);
                            }

                            @Override
                            public int compare(PathNode o1, PathNode o2) {
                                return 0;
                            }
                        });

                if (openNode == null)
                    openSet.add(neighbourNode);
                else if (openNode.PathLengthFromStart > neighbourNode.PathLengthFromStart) {

                    openNode.CameFrom = currentNode;
                    openNode.PathLengthFromStart = neighbourNode.PathLengthFromStart;
                }
            }
        }

        return null;
    }

    private static int GetDistanceBetweenNeighbours() {
        return 1;
    }

    private static int GetHeuristicPathLength(Pair from, Pair to) {

        return (int) (Math.abs(from.getValue0() - to.getValue0()) + Math
                .abs(from.getValue1() - to.getValue1()));
    }

    private static Collection GetNeighbours(PathNode pathNode,
            Pair goal, Integer[][] field) {

        ArrayList result = new ArrayList();

        Pair[] neighbourPoints = new Pair[4];
        neighbourPoints[0] = new Pair(pathNode.Position.getValue0() + 1,
                pathNode.Position.getValue1());
        neighbourPoints[1] = new Pair(pathNode.Position.getValue0() - 1,
                pathNode.Position.getValue1());
        neighbourPoints[2] = new Pair(pathNode.Position.getValue0(),
                pathNode.Position.getValue1() + 1);
        neighbourPoints[3] = new Pair(pathNode.Position.getValue0(),
                pathNode.Position.getValue1() - 1);

        for (Pair point : neighbourPoints) {            

            if (point.getValue0() < 0 || point.getValue0() >= field.length)
                continue;
            if (point.getValue1() < 0 || point.getValue1() >= field[0].length)
                continue;

            if (/*(field[(int) point.getValue0()][(int) point.getValue1()] != 0)
                    &&*/ (field[(int) point.getValue0()][(int) point.getValue1()] == 1))
                continue;

            PathNode neighbourNode = new PathNode();

            neighbourNode.Position = point;
            neighbourNode.CameFrom = pathNode;
            neighbourNode.PathLengthFromStart = pathNode.PathLengthFromStart
                    + GetDistanceBetweenNeighbours(); //  + 1
            neighbourNode.HeuristicEstimatePathLength = GetHeuristicPathLength(
                    point, goal);

            result.add(neighbourNode);
        }
        return result;
    }

    private static ArrayList GetPathForNode(PathNode pathNode) {

        ArrayList result = new ArrayList();
        PathNode currentNode = pathNode;                

        while (currentNode != null) {           

            result.add(currentNode.Position);
            currentNode = currentNode.CameFrom;
        }

        result = ArrayHelper.getReversed(result);       

        return result;
    }   
}

Вспомогательный класс PathNode:

import com.me.tanks1990Intellect.Classes.Pair;

class PathNode {

    public Pair Position;

    public int PathLengthFromStart;

    public PathNode CameFrom;

    public int HeuristicEstimatePathLength;

    public int EstimateFullPathLength() {

        return this.PathLengthFromStart + this.HeuristicEstimatePathLength;

    }
}

Вспомогательный класс ArrayHelper:


import java.util.ArrayList;
import java.util.Comparator;

public class ArrayHelper {

    public static  ArrayList getReversed(ArrayList wrappedList) {

        ArrayList resultList = new ArrayList();

        for (final T each : new ListReverser(wrappedList)) {

            resultList.add(each);
        }

        return resultList;
    }

    public static  int getCount(ArrayList wrappedList,
            Comparator comparator) {

        int count = 0;

        for (T current : wrappedList) {
            if (comparator.equals(current))
                count++;
        }

        return count;
    }

    public static  T getFirstorDefault(ArrayList wrappedList,
            Comparator comparator) {     

        for (T current : wrappedList) {                     

            if (comparator.equals(current))

                return current;                     
        }

        return null;
    }

    public static  ArrayList createCopy(ArrayList copiedMassive) {

        ArrayList result = new ArrayList();

        for (T innerTypeObject : copiedMassive) {

            result.add(innerTypeObject);
        }

        return result;
    }

    public static Integer[][] createCopy(Integer[][] cells) {

        Integer[][] cellsReturn = new Integer[cells.length][cells.length];

        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells.length; j++) {

                cellsReturn[i][j] = cells[i][j];

            }
        }

        return cellsReturn;
    }
}

Вспомогательный класс ListReverser:

import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

class ListReverser implements Iterable {
    private ListIterator listIterator;

    public ListReverser(List wrappedList) {
        this.listIterator = wrappedList.listIterator(wrappedList.size());
    }

    public Iterator iterator() {
        return new Iterator() {

            public boolean hasNext() {
                return listIterator.hasPrevious();
            }

            public T next() {
                return listIterator.previous();
            }

            public void remove() {
                listIterator.remove();
            }
        };
    }
}

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

image
(рис. 1)

Каждая игровая 2D-карта может быть интерпретирована как набор пустых и закрашенных клеток (пустая клетка — свободная для размещения на ней динамического юнита, закрашенная — занятая).

На просторах интернета мне не удалось накопать ни одной статьи о поиске пути для игрового юнита размером в n клеток, где n > 1. И мне пришлось додумывать самому (рис. 2).

image
(рис. 2)

Всё оказалось весьма прозаично: мы можем просто интерпретировать игровую матрицу M с пустыми и закрашенными ячейками как карту M — acordingSize с пустыми элементами там, где может находиться наш юнит на нижнем левом своём углу. Красные ячейки (ранее не закрашенные) — те, на которые юнит, опираясь, пересекает чёрные, то есть закрытые элементы карты (рис. 3).

image
(рис. 3)

И теперь, имея в виду элементы карты, отличные от незакрашенных, как занятые, мы можем использовать наш алгоритм A-star для юнита, занимающего более одной ячейки на карте M — acordingSize (рис. 4).

image
(рис. 4)

private static int maxIteratorsCount = 100;

Эта строчка кода означает, что A — star ищет путь, перебирая не более сотни клеток.

Карта моей игры состояла из более чем 2 500 ячеек, и при «закрытости» в 10 процентов количество переборов ячеек могло достигать более 1500, что сильно тормозило игру. Поэтому я решил воспользоваться алгоритмом поиска свободной ячейки (vacantCell), находящейся по тому же направлению, что и ячейка финиша, и притом расстояние от этой ячейки (vacantCell) до нашего юнита, ищущего путь, должно минимально отличаться от некого числа = const (рис. 5).

image
(рис. 5)

Но этот способ лишь приближает юнит к цели, и при приближении нашего плеера к ячейки (vacantCell), должна быть заново вызвана процедура поиска другой ячейки vacantCell.

Во избежание многочисленного перебора свободных клеток матрицы M — acordingSize, мы можем разбить карту на замкнутые прямоугольные под-области и уже создавать граф со связями между вершинами. Каждой вершине графа ставится в соответствие одна замкнутая прямоугольная под-область матрицы M — acordingSize. Связь между вершиной «B1» и вершиной «B2» существует, если наш с вами юнит может перебраться из прямоугольной области «B1» в прямоугольную область «B2». И затем поиск пути должен рассчитываться, исходя из нашего графа (например «Алгоритм Дейкстры»). В этой статье я не буду приводить пример его реализации.

Разбитая на под — области карта M — acordingSize (рис. 6).

image
(рис. 6)

Граф, каждой вершине которого ставится в соответствие одна под-область из M — acordingSize (рис. 7).

image
(рис. 7)

Кому интересно — игру можно найти в плеймаркете под названием tanks 1990 intellect.

Спасибо за внимание!

© Habrahabr.ru