Как я писал классические танки с интеллектом

Вступление

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

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

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

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

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

1
2
3
4
5
6
7
8
9
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
import com.me.tanks1990Intellect.Classes.Pair;
import java.util.*;
 
public class AlgoritmAstar {
 
    static Comparator<PathNode> comparator = new Comparator<PathNode>() {
 
        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<Pair> FindPath(Integer[][] field, Pair start,
            Pair goal) {
 
        // TestMapStructure.printMap(field); TODO: printMap
 
        ArrayList<PathNode> closedSet = new ArrayList<PathNode>();
        ArrayList<PathNode> openSet = new ArrayList<PathNode>();
 
        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<Pair> result = GetPathForNode(currentNode);
                // TestMapStructure.printMap(field, result); //TODO: printMap
 
                return result;
            }
 
            openSet.remove(currentNode);
            closedSet.add(currentNode);
 
            ArrayList<PathNode> neighbours = (ArrayList<PathNode>) GetNeighbours(
                    currentNode, goal, field);
 
            for (final PathNode neighbourNode : neighbours) {
 
                if (ArrayHelper.getCount(closedSet, new Comparator<PathNode>() {
 
                    @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<PathNode>() {
 
                            @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<PathNode> GetNeighbours(PathNode pathNode,
            Pair goal, Integer[][] field) {
 
        ArrayList<PathNode> result = new ArrayList<PathNode>();
 
        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)
                    &amp;&amp;*/ (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<Pair> GetPathForNode(PathNode pathNode) {
 
        ArrayList<Pair> result = new ArrayList<Pair>();
        PathNode currentNode = pathNode;                
 
        while (currentNode != null) {           
 
            result.add(currentNode.Position);
            currentNode = currentNode.CameFrom;
        }
 
        result = ArrayHelper.getReversed(result);       
 
        return result;
    }   
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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:

1
2
3
4
5
6
7
8
9
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.ArrayList;
import java.util.Comparator;
 
public class ArrayHelper {
 
    public static <T> ArrayList<T> getReversed(ArrayList<T> wrappedList) {
 
        ArrayList<T> resultList = new ArrayList<T>();
 
        for (final T each : new ListReverser<T>(wrappedList)) {
 
            resultList.add(each);
        }
 
        return resultList;
    }
 
    public static <T> int getCount(ArrayList<T> wrappedList,
            Comparator<T> comparator) {
 
        int count = 0;
 
        for (T current : wrappedList) {
            if (comparator.equals(current))
                count++;
        }
 
        return count;
    }
 
    public static <T> T getFirstorDefault(ArrayList<T> wrappedList,
            Comparator<T> comparator) {     
 
        for (T current : wrappedList) {                     
 
            if (comparator.equals(current))
 
                return current;                     
        }
 
        return null;
    }
 
    public static <T> ArrayList<T> createCopy(ArrayList<T> copiedMassive) {
 
        ArrayList<T> result = new ArrayList<T>();
 
        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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
 
class ListReverser<T> implements Iterable<T> {
    private ListIterator<T> listIterator;
 
    public ListReverser(List<T> wrappedList) {
        this.listIterator = wrappedList.listIterator(wrappedList.size());
    }
 
    public Iterator<T> iterator() {
        return new Iterator<T>() {
 
            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.

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

Источник

  • ,
  • Метки:

Добавить комментарий