На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

Лабиринты 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);
    }
}
Ну а в следующей части мы уже создадим свой лабиринт, путь по нему и поговорим о теории.



Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.



тегизаметки, программирование, java, лабиринт

Читайте также:




Классический остросюжетный детектив
Урок 36. Коллекция Hashtable C#


© upread.ru 2013-2021
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.