Конференция "Прочее" » Поиск широкого пути в двухмерном лабиринте
 
  • _ПЛОВ © (05.03.19 11:47) [0]
    Как бы лучше оптимизировать алгоритм поиска, если нужно не просто найти путь из А в Б, а путь шириной, например, 2 клетки? Юзаю алгоритм Дейкстры. Что-то идей совсем нету :(
  • Sha © (05.03.19 12:22) [1]
    увеличить препятствия и искать узкий путь?
  • manaka © (05.03.19 12:41) [2]

    > Как бы лучше оптимизировать алгоритм поиска, если нужно
    > не просто найти путь из А в Б, а путь шириной, например,
    >  2 клетки?


    А чем поиск пути путь шириной в 2 клетки отличается от поиска обычного?
    Чуть-чуть изменить алгоритм стандартного поиска:
    Если при следующем шаге ширина стала равной 1, считаем данное направление тупиком.
  • Sha © (05.03.19 13:43) [3]
    отличие в необходимости проверять ширину
  • _ПЛОВ © (07.03.19 15:10) [4]
    Получилось) Просто проверять ширину недостаточно, нужно еще и диагонали, чтобы понять что "куб" 2х2 туда пролезет
 
Конференция "Прочее" » Поиск широкого пути в двухмерном лабиринте
Есть новые Нет новых   [99655   +9][b:0.001][p:0.001]