Вступление
Я являюсь независимым разработчиком приложений под 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.
Спасибо за внимание!
Автор: atereshkovets
