As I wrote classic tanks with intelligence

Introduction

I am an independent developer of applications for Android (and more specifically, a year and a half of developing an intellectual version of the classic favorite cult game Tanchiki 1990).

Why I decided to write this game: I have even more direct relation to the games (I play them). In the playmarket, I did not see a single 2D-game, where there would be an algorithm for making decisions about finding the shortest path. I'm not talking about more complex games written on powerful engines. What does the percentage of such games, I do not know. Either this is a consequence of the ideological component, or the result of the situation in the gaming market as a whole, is unknown to me. My personal opinion: there should be more such games.

By the intellectual component of the game, we will understand bots that imitate living partners (opponents, allies), depending on the gameplay in general.

Imitating an opponent in the context of my written game is rather a “pseudo-intellect” (optimized variation between goals - tasks and, as a result, between the search for ways).

As a pathfinding algorithm, I used A * (A-star). Here is my java implementation:

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 helper class:

 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 helper class:

 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; } } 

Helper class 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(); } }; } } 

This algorithm successfully finds a path for a moving unit the size of a single cell of the map, which freely passes around all filled cells (Fig. 1).

(fig. 1)

Each 2D game map can be interpreted as a set of empty and filled cells (an empty cell is free to place a dynamic unit on it, and a filled cell is occupied).

On the Internet, I did not manage to dig up a single article about finding a path for a gaming unit the size of n cells, where n> 1. And I had to think it out myself (Fig. 2).

(fig. 2)

Everything turned out to be quite prosaic: we can simply interpret the game matrix M with empty and shaded cells as an M-acordingSize map with empty elements where our unit may be on its lower left corner. Red cells (not previously painted over) - those on which the unit, relying, crosses black, that is, closed map elements (Fig. 3).

(pic. 3)

And now, bearing in mind the map elements that are different from the blank ones, as occupied, we can use our A-star algorithm for a unit occupying more than one cell on the M-acordingSize map (Fig. 4).

(pic. 4)

 private static int maxIteratorsCount = 100; 

This line of code means that A-star is looking for a path, going through no more than a hundred cells.

The map of my game consisted of more than 2,500 cells, and with a “closure” of 10 percent, the number of cells searched could reach more than 1,500, which greatly inhibited the game. Therefore, I decided to use the free cell search algorithm (vacantCell), located in the same direction as the finish cell, and, moreover, the distance from this cell (vacantCell) to our unit, which is looking for a path, should be minimally different from a certain number = const (Fig. five).

(pic. 5)

But this method only brings the unit closer to the target, and when our player approaches the cell (vacantCell), the procedure for searching for another vacantCell cell must be called again.

In order to avoid multiple enumeration of free cells of the M-acordingSize matrix, we can break the map into closed rectangular sub-regions and create a graph with connections between the vertices. Each vertex of the graph is associated with one closed rectangular sub-region of the matrix M - acordingSize. The connection between vertex "B1" and vertex "B2" exists if our unit with you can move from the rectangular region "B1" to the rectangular region "B2". And then the search path must be calculated on the basis of our graph (for example, "Dijkstra's Algorithm"). In this article I will not give an example of its implementation.

Broken into sub-areas is the M-acording Size card (Fig. 6).

(pic. 6)

A graph, each vertex of which is assigned one sub-area from M - acordingSize (Fig. 7).

(fig. 7)

Who cares - the game can be found in the playmarket called tanks 1990 intellect.

Thanks for attention!