Як я писав класичні танки з інтелектом

Вступ
Я є незалежним розробником додатків під 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, to Pair) {

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 (T final 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).
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.
Дякую за увагу!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.