gistfile1.txt

//Одним из самых интересных моментов в процессе разработки игры была реализация искуственного интеллекта для ботов.
//Чтобы они не просто двигались по карте случайным образом, а пытались окружить и поймать героя. Я решил
//реализовать волновой алгоритм поиска кратчайшего пути. Суть этого алгоритма заключается в том, что мы
//начинаем обход всей карты от исходной точки и на каждом шаге присваем клетке, на которую перешли, значение соответственно
//номеру шага. Таким образом у нас получается множество возможных маршрутов движения, один из которых в конце концов
//приводит нас к цели. И тогда остается только пройти от цели к источнику по номерам шагов в обратном порядке и передать
//уже готовый маршрут боту.

private void fillRouteMap(int routeMap[][]) {
    int x;
    int y;

    for (int step = 1; step < MAX_ROUTE_STEP_COUNT; step++) {
        for (int i = 0; i < routeMap.length; i++) {
            for (int j = 0; j < routeMap[i].length; j++) {
                if (routeMap[i][j] != step - 1) continue;

                for (Direction direction : Direction.values()) {
                    x = i + direction.getX();
                    y = j + direction.getY();

                    if (x < 0 || y < 0 || x >= routeMap.length || y >= routeMap[x].length) continue;

                    if (routeMap[x][y] == ROUTE_TARGET_CELL) {
                        fillRouteList(x, y, routeMap, step);
                        return;
                    }

                    if (routeMap[x][y] == ROUTE_EMPTY_CELL) {
                        if (gameManager.isCellEmpty(x, y)) {
                            routeMap[x][y] = step;
                        } else {
                            routeMap[x][y] = ROUTE_WALL_CELL;
                        }
                    }
                }
            }
        }
    }
}

На скриншоте с примером работы волнового алгоритма видно как заполняется маршрутная карта и строится уже готовый маршрут, который передаётся ботам: