Перейти к публикации

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

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

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

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

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


Блоги

  • TEMP BLOG
  • Робот Байт
  • Fingercomp's Playground
  • DUIIIES ' - блог
  • 1Ridav' - блог
  • Totoro Cookies
  • Блог cyber01
  • Another Brick In The Wall
  • IncluderWorld
  • KelLiN' - блог
  • Крутой блог
  • eutomatic blog
  • Programist135 Soft
  • Создаем собственный сайт в сети OpenNet
  • PieLand
  • Очумелые ручки
  • Блог недоблоггера
  • В мире майнкрафта, его модификаций и не только
  • Матрица
  • LaineBlog
  • Квантовый блог
  • Велосипедный блог
  • Как Pofigist кодить пытается
  • Блог qwertyMAN'а
  • NullException - DevBlog
  • Гайды для новичков и программы от LuaGamer`a
  • some blog name
  • Дача Игоря

Категории и разделы

  • Программирование
    • База знаний
    • Библиотеки
    • Робототехника
    • Сетевые технологии
    • Игры
    • Операционные системы
    • Графика
    • Инфраструктура
    • Программы новичков
    • За пределами Minecraft
    • Программирование в других играх
    • Всякое-Разное
    • Чулан
    • Стол заказов
    • Конкурсы
  • Игровой раздел
    • Игровые сервера
    • Предложения игроков по улучшению игрового процесса
    • Моды и плагины
    • Гайды, обзоры по модам
    • Жалобы на игроков
    • Ивенты
  • Общение
    • Ответы на частые вопросы
    • Вопрос-ответ
    • Вопросник по Lua и модам Opencomputers и ComputerCraft
    • Беседка для программистов
    • Беседка-флудилка
    • Шкатулка
  • Технический раздел
    • Новости проекта
    • Предложения по улучшению работы форума и игровых серверов
    • Проблемы в работе игрового сервера, клиента, форума и их решение
    • Архив

Группы продуктов

Нет результатов для отображения.


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

Искать результаты, содержащие...


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

  • Начать

    Конец


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

  • Начать

    Конец


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

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

  • Начать

    Конец


Группа


AIM


MSN


Сайт


ICQ


Yahoo


Jabber


Skype


ВКонтакте


Gtalk


Facebook


Twitter


Город


Интересы

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

  1. Doob

    Поиск пути

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