Перейти к содержимому

Поиск по сайту

Результаты поиска по тегам 'pathfinding'.

  • Поиск по тегам

    Введите теги через запятую.
  • Поиск по автору

Тип публикаций


Блоги

  • Робот Байт
  • Fingercomp's Playground
  • 1Ridav' - блог
  • Totoro Cookies
  • Блог cyber01
  • IncluderWorld
  • KelLiN' - блог
  • Крутой блог
  • eutomatic blog
  • Programist135 Soft
  • Сайт в сети OpenNet
  • PieLand
  • Очумелые ручки
  • Блог недоблоггера
  • В мире Майнкрафт
  • LaineBlog
  • Квантовый блог
  • Блог qwertyMAN'а
  • ДубоБлог
  • Дача Игоря

Форумы

  • Программирование
    • Программы
    • База знаний
    • Разработчикам
    • Вопросы
  • Игровой раздел
    • Игровые серверы
    • Предложения по улучшению игрового процесса
    • Моды и плагины
    • Жалобы на игроков
    • Ивенты
  • Общение
    • Вопрос-ответ
    • Беседка программистов
    • Беседка-флудилка
    • Шкатулка
  • Технический раздел
    • Багтрекер
    • Архив

Искать результаты в...

Искать результаты, которые...


Дата создания

  • Начать

    Конец


Последнее обновление

  • Начать

    Конец


Фильтр по количеству...

Зарегистрирован

  • Начать

    Конец


Группа


AIM


MSN


Сайт


ICQ


Yahoo


Jabber


Skype


ВКонтакте


Gtalk


Facebook


Twitter


Город


Интересы

Найдено 1 результат

  1. Doob

    Поиск пути

    Когда я узнал о JPS, у меня возникла идея упростить A*. Можно выкинуть волновую рекурсию, которая используется во всех алгоритмах поиска пути. Для этого, берем все узлы, которые являются препятствиями, помечаем соседние свободные узлы и строим путь. Из самого описания выходит, что данный алгоритм подойдет не для всех типов графов, но ботам на регулярной сетке в самый раз. Проблема данного алгоритма в том, что препятствий может быть очень много, а на пути между стартом и финишем очень мало. Фактически это алгоритм Дейкстры без рекурсии, прямой переход в самое последнее возможное состояние. Потребление памяти меньше чем у Дейкстры и А*, т. к. отмечается только финальный фронт. Чтобы оптимизировать, будем отмечать только те граничные узлы, которые находятся ближе к стартовой и финишной точке. Получаем JPS, только избыточней, но лучше чем A* по потреблению памяти. Остается построить путь поиском в ширину из доступных оптимальных путей. Вот сравнение по потреблению памяти при обходе препятствий: A* хранит данные о свободных клетках, полученных на данной эвристике. В эти данные входят координаты точки, расстояние до цели, количество предыдущих шагов. Jump Point Search хранит точки перехода на пути от старта к финишу, хранятся только координаты точек и по выбору: координаты соседних переходов или расстояние до финиша. При удалении рекурсии надо хранить координаты граничных точек, а все вычисления производить только при построении пути. Если найти способ не хранить все доступные граничные точки, то алгоритм без рекурсии вполне годится для практического применения. JPS в большинстве применений превосходит A*, он быстрее, потребляет меньше памяти. Но не годится для открытых пространств, если регион поиска искусственно не ограничить, он будет вечно искать оптимальный путь, т. к. его преимущество оборачивается недостатком. Возможно эту проблему уже решили, но никакой информации об этом я не нашел.
×
×
  • Создать...