エントリー
私はAndroid用アプリケーションの独立した開発者です（より具体的には、誰もがクラシックなクラシックカルトゲーム「Tanchiki 1990」の知的バージョンを開発した1年半）。
私がこのゲームを書くことにした理由：私はゲームとさらに直接関係があります（私はゲームをプレイします）。 プレイマーケットでは、最短経路を見つけることを決定するためのアルゴリズムがある単一の2Dゲームは見ませんでした。 私は、強力なエンジンで書かれたより複雑なゲームについて話しているのではありません。 そのようなゲームの割合を決定するものは、私にはわかりません。 これがイデオロギー的要素の結果であるか、ゲーム市場全体の結末の結果であるかは、私にはわかりません。 私の個人的な意見：このようなゲームがもっとあるはずです。
ゲームの知的要素とは、ゲームプロセス全体に応じて、生きているパートナー（相手、同盟国）を模倣するボットを意味します。
私が書いたゲームのコンテキストでの相手の模倣は、「疑似知能」（目標-タスク間、結果として経路を見つける間の最適化されたバリエーション）に似ています。
パス検索アルゴリズムとして、A *（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> 1のサイズのセル（n> 1）のゲームユニットの方法を見つけることについて、単一の記事を掘り下げることはできませんでした（そして、図2）。
（図2）
すべてが非常に散文的であることが判明しました。ゲームマトリックスMを空のセルと塗りつぶされたセルでマップM-ユニットを左下隅に配置できる空の要素を持つacordingSizeとして単純に解釈できます。 赤色のセル（以前は塗りつぶされていません）は、ユニットが傾いて黒を越えている、つまり閉じたマップ要素です（図3）。
（図3）
そして、空のマップとは異なるビジーなマップの要素を念頭に置いて、Mマップ上の複数のセルを占有するユニットにa-starアルゴリズム-acordingSizeを使用できます（図4）。
（図4）
private static int maxIteratorsCount = 100;
このコード行は、A-スターがパスを探し、100個以下のセルをソートすることを意味します。
私のゲームのマップは2,500を超えるセルで構成されており、10パーセントの「クロージャー」により、セル検索の数が1,500を超える可能性があり、ゲームが大幅に遅くなりました。 そのため、フィニッシュセルと同じ方向にあるフリーセル検索アルゴリズム（vacantCell）を使用することにしました。このセル（vacantCell）からパスを探しているユニットまでの距離は、特定の数= const 5）。
（図5）
ただし、このメソッドはユニットをターゲットに近づけるだけで、プレーヤーがセル（vacantCell）に近づくと、別のvacantCellセルの検索手順を再度呼び出す必要があります。
マトリックスM-acordingSizeのフリーセルの複数の列挙を回避するために、マップを閉じた長方形のサブエリアに分割し、頂点間の接続でグラフを作成することができます。 グラフの各頂点は、マトリックスMの1つの閉じた長方形のサブエリアacordingSizeに関連付けられています。 ユニットが矩形領域「B1」から矩形領域「B2」に移動できる場合、頂点「B1」と頂点「B2」の間の接続が存在します。 そして、グラフに基づいてパス検索を計算する必要があります（たとえば、ダイクストラのアルゴリズム）。 この記事では、その実装例を示しません。
M-acordingSizeカード、サブ領域に分割（図6）。
（図6）
各頂点がMの1つのサブエリアに関連付けられているグラフ-acordingSize（図7）。
（図7）
誰が気にします-ゲームはタンク1990知性と呼ばれるプレイマーケットで見つけることができます。
ご清聴ありがとうございました！