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

A* - Поиск пути

Рекомендуемые сообщения

Обновление 25.03.15 - увеличена скорость работы в 1000 раз. Поиск по объему 100х100х100 проходит за 0.1 секунды.


 

Когда мы используем робота\черепашку, часто нужно научить ее обходить блоки или препятствия, особенно если она сама что то строила.
Для этого подойдет один из лучших алгоритмов поиска пути A-Star
http://ru.wikipedia.org/wiki/Алгоритм_поиска_A*
Astar_progress_animation.gif

Я реализовал этот алгоритм на LUA в 3д для роботов или черепашек:
http://pastebin.com/CHCB8nDz
 

Использование очень простое. Ниже пример:
 

 

-- Создаем новый мир - трехмерный массив. Размеры по X,Y,Z

local world = arr3d()

 

-- Сделать клетку непроходимой. Индексы начинаются с [0]

-- Последовательность индексов [x][y][z]

world:set(1,4,3,true)

 

 

local p_start = {x=1,y=2,z=3} -- Точка начала пути

local p_end   = {x=1,y=6,z=3} -- Конец пути

 

-- Функция нахождения пути

-- Возвращает первую хлебную крошку из списка

local crumb = AStarFindPath(world, p_start, p_end)

 

if crumb == nil then

  print('Path not found')

else

  io.write('['.. crumb.pos.x..","..crumb.pos.y..","..crumb.pos.z..]->")

 

  -- BreadCrumbs - связанный список. crumb.next - след. точка пути

  crumb.next

  while crumb.next ~= nil do

    crumb = crumb.next

    io.write('['.. crumb.pos.x..","..crumb.pos.y..","..crumb.pos.z..(crumb.next and ]->" or "]"))

  end

end

 

Надеюсь, и вам это пригодится!

Изменено пользователем Krutoy

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

На сколько я понял, алгоритм А* предполагает, что карта черепахе известна. Если черепаха сама ее строила, тогда понятно. А если нет, тогда как?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

А если нет, тогда как?

А если карта неизвестна, то это уже не поиск пути. Для этого тебе нужно дописывать код самому.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Алгоритм ли лучше

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Алгоритм ли лучше

Луше, пока ты не связываешься с третьим пространством.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

это да

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Оказалось, что из за досадной ошибки первая версия алгоритма работала в 1000 раз медленнее чем должна.

Теперь я это исправил и функция просчитывает путь в кубе 100х100х100 за 0.1 секунды.

Новая версия в первом посте.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Снова обновил код. Теперь поиск пути строится более точнее.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

То есть она не пытаеться прийти по определённым координатам, а идёт по уже известной карте?Так скучно=(Я уже на твоей программе распечатал лабиринт, а она оказывается только по известной карте ходит=(

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

То есть она не пытаеться прийти по определённым координатам, а идёт по уже известной карте?Так скучно=(Я уже на твоей программе распечатал лабиринт, а она оказывается только по известной карте ходит=(

Это же просто реализовать! Поставь контроллер предметов, и если работ видит перед собой блок, пишет world:set(x,y,z,true) что бы пометить этот блок непроходимым, и еще раз запускает поиск пути.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Это же просто реализовать! Поставь контроллер предметов, и если работ видит перед собой блок, пишет world:set(x,y,z,true) что бы пометить этот блок непроходимым, и еще раз запускает поиск пути.

Можно геосканер применить, и если плотность "не та", то ставить твой world:set.

И времени это займёт в 2 раза меньше.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я нашел еще один уже давно написаный поиск пути, прямо с реализацией создания карты мира у самого робота. Теперь робот может проходить лабиринты самостоятельно!

Подробнее тут.

 

Видео-презентация

Изменено пользователем Krutoy

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я нашел еще один уже давно написаный поиск пути, прямо с реализацией создания карты мира у самого робота. Теперь робот может проходить лабиринты самостоятельно!

Подробнее тут.

 

Видео-презентация

Пришло время тестировать!=)

P.S. Вот лабиринтик=): https://yadi.sk/i/IwhAkg8UhCSHp

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Это было еще в ComputerCraft

Для таких плоских лабиринтов достаточно использовать правило правой/левой руки, а если лабиринт трехмерный или с выходом в пустотном кармане, то без A* не обойтись.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 

 

P.S. Вот лабиринтик=): https://yadi.sk/i/IwhAkg8UhCSHp

 

Вот лабиринтик: http://habrastorage....390f4cff97e.png
 Пфф...

Вот это ЛАБИРИНТИК:

syAQ8vC.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 Пфф...

Вот это ЛАБИРИНТИК:

 

 

Такой лабиринт в майн нельзя)) Большие шумовые конструкции роняют сервер.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Пфф...

Вот это ЛАБИРИНТИК:

Отпечатывал=)Твоей прогой=)В магике есть функция создания лабиринтов=)

 

Отпечатывал=)Твоей прогой=)В магике есть функция создания лабиринтов=)

Около 3-х часов ждал=) 126x126x126

Изменено пользователем Asummonster
Удаляйте картинки в цитатах!

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...