Лабиринты Java, часть 4: класс AStarPathfinder

Ну что ж, наконец-то мы переходим к реализации класса поиска пути по алгоритму А-стар. Ниже его код с комментариями. Алгоритм реализован как статический метод, поскольку алгоритму поиска пути действительно не нужно поддерживать (сохранять) какое-либо состояние между его вызовами.

import java.util.HashMap;
import java.util.HashSet;

public class AStarPathfinder
{
    /**
     * Эта константа устанавливает максимальный предел отсечения для стоимости путей. Если
      * конкретная путевая точка превышает этот предел стоимости, путевая точка
      * исключается.
     **/
    public static final float COST_LIMIT = 1e6f;

    
    /**
     * Попытки вычислить путь, который проходит между началом и концом
      * локации указанной карты. Если путь может быть найден, путевая точка
      * возвращается как <em> последний </em> шаг пути. Если путь не может быть найден,
      * Возвращается <code>null</code>.
     **/
    public static Waypoint computePath(Map2D map)
    {
        // Переменные, необходимые для поиска A*.
        AStarState state = new AStarState(map);
        Location finishLoc = map.getFinish();

        // Установим начальную путевую точку, чтобы начать поиск A *.
        Waypoint start = new Waypoint(map.getStart(), null);
        start.setCosts(0, estimateTravelCost(start.getLocation(), finishLoc));
        state.addOpenWaypoint(start);

        Waypoint finalWaypoint = null;
        boolean foundPath = false;
        
        while (!foundPath && state.numOpenWaypoints() > 0)
        {
            // Находим лучшую (то есть с минимальной стоимостью) путевую точку.
            Waypoint best = state.getMinOpenWaypoint();
            
            // Если лучшее место-это место финиша, то мы закончили!
            if (best.getLocation().equals(finishLoc))
            {
                finalWaypoint = best;
                foundPath = true;
            }
            
            // Добавляем/обновляем всех соседей текущего лучшего местоположения. Это
           // эквивалентно попытке выполнить все "следующие шаги" из этого места.
            takeNextStep(best, state);
            
            // Наконец, перемещаем это местоположение из списка "открыто" в список "закрыто".
            state.closeWaypoint(best.getLocation());
        }
        
        return finalWaypoint;
    }

    /**
     * Этот статический вспомогательный метод принимает путевую точку и генерирует все действительные "следующие".
      * шаги "от этой путевой точки. Новые путевые точки добавляются в "открытую "
      * waypoints коллекцию переданного объекта состояния A*.
     **/
    private static void takeNextStep(Waypoint currWP, AStarState state)
    {
        Location loc = currWP.getLocation();
        Map2D map = state.getMap();
        
        for (int y = loc.yCoord - 1; y <= loc.yCoord + 1; y++)
        {
            for (int x = loc.xCoord - 1; x <= loc.xCoord + 1; x++)
            {
            	//здесь закомменттировано то, что нельзя "ходить по диагоналям".
            	//if ((y == loc.yCoord -1 && x == loc.xCoord - 1) || (y == loc.yCoord + 1 && x == loc.xCoord - 1)
            		//	|| (y == loc.yCoord - 1 && x == loc.xCoord + 1)
            		//	|| (y == loc.yCoord + 1 && x == loc.xCoord +1)) {
            		//continue;
            	//}
            	
                Location nextLoc = new Location(x, y);
                
                // Если "следующее местоположение" находится за пределами карты, пропускаем его.
                if (!map.contains(nextLoc))
                    continue;
                
                // If "next location" is this location, skip it.
                if (nextLoc == loc)
                    continue;
                
                // Если "следующее местоположение" - это это местоположение, пропускаем его.
                if (state.isLocationClosed(nextLoc))
                    continue;

                // Создаем путевую точку для этого "следующего местоположения".
                
                Waypoint nextWP = new Waypoint(nextLoc, currWP);
                
                // Хорошо, мы обманываем и используем смету для вычисления фактического
                // стоимость из предыдущей ячейки. Затем мы добавляем стоимость из
                // ячейки карты, на которую мы ступаем, чтобы установить барьеры и т. д.

                float prevCost = currWP.getPreviousCost() +
                    estimateTravelCost(currWP.getLocation(),
                                       nextWP.getLocation());

                prevCost += map.getCellValue(nextLoc);
                
                // Пропускаем следующую локацию, если стоимость такая же
                if (prevCost >= COST_LIMIT)
                    continue;
                
                nextWP.setCosts(prevCost,
                    estimateTravelCost(nextLoc, map.getFinish()));

                // Добавляем путевую точку в набор открытых путевых точек. Если там
// оказывается, уже является путевой точкой для этого местоположения, новая
// путевая точка заменяет старую путевую точку только в том случае, если она менее затратна
// чем предыдущая.
                state.addOpenWaypoint(nextWP);
            }
        }
    }
    
    /**
     * Оценивает стоимость путешествия между двумя указанными местоположениями.
      * Фактическая стоимость рассчитывается как расстояние по прямой между
      * двумя местами.
     **/
    private static float estimateTravelCost(Location currLoc, Location destLoc)
    {
        int dx = destLoc.xCoord - currLoc.xCoord;
        int dy = destLoc.yCoord - currLoc.yCoord;
        
        return (float) Math.sqrt(dx * dx + dy * dy);
    }
}

Ну а в следующей части мы уже создадим свой лабиринт, путь по нему и поговорим о теории.