Вступление
Я являюсь независимым разработчиком приложений под Android (а конкретней — полтора года разработки интеллектуальной версии классической всеми любимой культовой игры "Танчики 1990").
Почему я решил написать эту игру: к играм я имею ещё более непосредственное отношение (играю в них). В плэймаркете я не увидел ни одной 2D-игры, где присутствовал бы алгоритм принятия решений о поиске кратчайшего пути. Я не говорю о более сложных играх, написанных на мощных движках. От чего зависит процент таких игр, я не знаю. Или это следствие идейной составляющей, или же результат конъюнктуры игрового рынка в целом, мне неизвестно. Моё личное мнение: таких игр должно быть больше.
Под интеллектуальной составляющей игры мы будем понимать ботов, имитирующих живых партнёров (оппонентов, союзников), в зависимости от игрового процесса в целом.
Имитация оппонента в контексте мною написанной игры — это скорее "псевдоинтеллект" (оптимизированное варьирование между целями — задачами и, как следствие, между поиском путей).
Как алгоритм поиска пути я использовал А* (A-star). Вот его моя реализация на java:
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) &&*/ (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:
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 <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:
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).
(рис. 1)
Каждая игровая 2D-карта может быть интерпретирована как набор пустых и закрашенных клеток (пустая клетка — свободная для размещения на ней динамического юнита, закрашенная — занятая).
На просторах интернета мне не удалось накопать ни одной статьи о поиске пути для игрового юнита размером в n клеток, где n > 1. И мне пришлось додумывать самому (рис. 2).
(рис. 2)
Всё оказалось весьма прозаично: мы можем просто интерпретировать игровую матрицу M с пустыми и закрашенными ячейками как карту M — acordingSize с пустыми элементами там, где может находиться наш юнит на нижнем левом своём углу. Красные ячейки (ранее не закрашенные) — те, на которые юнит, опираясь, пересекает чёрные, то есть закрытые элементы карты (рис. 3).
(рис. 3)
И теперь, имея в виду элементы карты, отличные от незакрашенных, как занятые, мы можем использовать наш алгоритм A-star для юнита, занимающего более одной ячейки на карте M — acordingSize (рис. 4).
(рис. 4)
private static int maxIteratorsCount = 100;
Эта строчка кода означает, что A — star ищет путь, перебирая не более сотни клеток.
Карта моей игры состояла из более чем 2 500 ячеек, и при "закрытости" в 10 процентов количество переборов ячеек могло достигать более 1500, что сильно тормозило игру. Поэтому я решил воспользоваться алгоритмом поиска свободной ячейки (vacantCell), находящейся по тому же направлению, что и ячейка финиша, и притом расстояние от этой ячейки (vacantCell) до нашего юнита, ищущего путь, должно минимально отличаться от некого числа = const (рис. 5).
(рис. 5)
Но этот способ лишь приближает юнит к цели, и при приближении нашего плеера к ячейки (vacantCell), должна быть заново вызвана процедура поиска другой ячейки vacantCell.
Во избежание многочисленного перебора свободных клеток матрицы M — acordingSize, мы можем разбить карту на замкнутые прямоугольные под-области и уже создавать граф со связями между вершинами. Каждой вершине графа ставится в соответствие одна замкнутая прямоугольная под-область матрицы M — acordingSize. Связь между вершиной "B1" и вершиной "B2" существует, если наш с вами юнит может перебраться из прямоугольной области "B1" в прямоугольную область "B2". И затем поиск пути должен рассчитываться, исходя из нашего графа (например "Алгоритм Дейкстры"). В этой статье я не буду приводить пример его реализации.
Разбитая на под — области карта M — acordingSize (рис. 6).
(рис. 6)
Граф, каждой вершине которого ставится в соответствие одна под-область из M — acordingSize (рис. 7).
(рис. 7)
Кому интересно — игру можно найти в плеймаркете под названием tanks 1990 intellect.
Спасибо за внимание!