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

[Krutoy 1 165]

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

---

 

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


Я реализовал этот алгоритм на 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

 

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

Изменено 11 апреля, 2015 пользователем Krutoy

[Zer0Galaxy 2 187]

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

[Krutoy Автор темы 1 165]

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

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

[NEO 541]

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

[Krutoy Автор темы 1 165]

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

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

[NEO 541]

это да

[Krutoy Автор темы 1 165]

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

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

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

[Krutoy Автор темы 1 165]

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

[Asummonster 592]

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

[Krutoy Автор темы 1 165]

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

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

[LeshaInc 623]

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

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

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

[Krutoy Автор темы 1 165]

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

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

 

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

Изменено 25 июня, 2015 пользователем Krutoy

[Asummonster 592]

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

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

 

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

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

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

[Zer0Galaxy 2 187]

Вот лабиринтик: http://habrastorage.org/getpro/habr/post_images/ceb/7ee/5f3/ceb7ee5f3d4ad81b4d9ff390f4cff97e.png

[Doob 2 746]

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

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

[Krutoy Автор темы 1 165]

 

 

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

 

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

 Пфф...

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

[Doob 2 746]

 Пфф...

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

 

 

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

[Asummonster 592]

Пфф...

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

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

 

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

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

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