Реализация алгоритма поиска пути A*

[Vint]

Очередная интересная задача до которой дошли руки.

Решил реализовать известный алгоритм поиска пути A*. Принципы и описание брал здесь.

Упоминание началось в темах:
http://crapware.aidf.org/forum/index.php?topic=1837.0
http://crapware.aidf.org/forum/index.php?topic=1878.0

Хотелось посмотреть как со скоростью на Clickermann, реально ли на нём использовать, ну и заодно неплохая тренировка создания кода. Ограничился как в примере полем разбитым на квадраты. Произвольные графы пока не делал, с этим стоит заморачиваться, если нужно, только под конкретную задачу когда такая появится.

Определился со способом хранения карты, а так же рабочей инфы: открытого и закрытого списков, стоимости F (G и H решил расчитывать по надобности на лету).
Для удобства создания сделал себе шаблончик как в источнике

Код под спойлером и во вложении
[spoiler]

Code: (clickermann) [Select]

#name "Алгоритм A*"
// Author: Vint
// Version: 0.0.4 (08.05.2015)
// Скрипт для Clickermann v4.11 003
#logfile

//===== ОПЦИИ ==========================//
//////////////////////////////////////////

// вывод лога
$log0 = 1
// вывод отладочного лога
$log = 0
// вывод отладочного лога 2 уровня
$log2 = 0

// имя файла карты
$map_name = "map.txt"

// Обходить углы 0 - нет, 1 - да
$bypass_angle = 1

// Старт (маркер)
$start = 4
// Финиш (маркер)
$ending = 5

//////////////////////////////////////////

//==============================================================================
//===  Расчёт H для клетки  ====================================================
SUB(calc_H, $th_X, $th_Y)
   $H = (ABS($endY - $th_Y) + ABS($endX - $th_X)) * 10
END_SUB

//==============================================================================
//===  Добавляем в открытый список  ============================================
SUB(add_open, $tt_X, $tt_Y, $tt_P, $tt_G)
   IF(($tt_X = $endX) & ($tt_Y = $endY))
      $check_end = 1
   END_IF
   calc_H($tt_X, $tt_Y)
   ARRPUSH($open, $tt_X)
   ARRPUSH($open, $tt_Y)
   ARRPUSH($open, $tt_P)
   ARRPUSH($open, $tt_G + $H)
   IF($log = 1)
      LOGWRITE ("Add open:  ", $tt_X, ":", $tt_Y, ":", $tt_P, ":", $tt_G + $H, "    G:", $tt_G, " $H:", $H)
   END_IF
END_SUB

//==============================================================================
//===  Добавляем в закрытый список  ============================================
SUB(add_close, $tt_X, $tt_Y, $tt_P)
   ARRPUSH($close, STRCONCAT($tt_X, ":", $tt_Y, "P", $tt_P))
   IF($log = 1)
      LOGWRITE ("Add close:  ", $tt_X, ":", $tt_Y, "P", $tt_P)
   END_IF
END_SUB

//==============================================================================
//===  Удаляем из открытого списока  ===========================================
SUB(del_open, $best)
   IF($log=1)
      LOGWRITE ("del open ", $best, "   ", $open[$best-3], ":", $open[$best-2], ":", $open[$best-1], ":", $open[$best])
   END_IF
   
   $size_open = ARRSIZE($open)
   IF($size_open > 4)
      FOR($i=$best-3, $i < ($size_open - 4))
         $open[$i] = $open[$i+4]
      END_CYC
   END_IF
   
   $nul = ARRPOP($open)
   $nul = ARRPOP($open)
   $nul = ARRPOP($open)
   $nul = ARRPOP($open)
END_SUB

//==============================================================================
//===  Проверка на вхождение в $close  =========================================
SUB(check_closed, $tc_X, $tc_Y)
   $closed_on = 0
   $sample = STRCONCAT($tc_X, ":", $tc_Y)
   $size_close = ARRSIZE($close)
   FOR($i=0, $i < $size_close)
      $cut_close = STRCUT2($close[$i], 1, STRPOS($close[$i], "P") - 1)
      //LOGWRITE ("close[$i] ", $close[$i], " cut_close ", $cut_close, "  sample ", $sample)
      IF($cut_close = $sample)
         $closed_on = 1
         $P_res = STRCUT2($close[$i], STRPOS($close[$i], "P") + 1, 30)
         $i = $size_close + 1
         IF($log = 1)
            LOGWRITE ($tc_X, "/", $tc_Y, "   входит в $close")
         END_IF
      END_IF
   END_CYC
END_SUB

//==============================================================================
//===  Проверка на вхождение в $open  ==========================================
SUB(check_open, $to_X, $to_Y)
   IF($log = 1)
      LOGWRITE ("проверяем  ",  $to_X, "/", $to_Y)
   END_IF
   
   IF(($to_X > -1) & ($to_Y > -1) & ($to_X < ($width)) & ($to_Y < ($height)))
      $no_filed = 0
      check_closed($to_X, $to_Y)
      IF($closed_on = 0)
         $opened_on = 0
         $size_open = ARRSIZE($open)
         FOR($i=0, $i < $size_open, 4)
            IF(($open[$i] = $to_X) & ($open[$i+1] = $to_Y))
               $opened_on = 1
               $ind_open = $i
               calc_H($to_X, $to_Y)
               $H_old = $H
               $G_old = $open[$i+3] - $H_old
               
               $P_res = $open[$i+2]
               $i = $size_open + 1
               IF($log = 1)
                  LOGWRITE ($to_X, "/", $to_Y, "   входит в $open")
               END_IF
            END_IF
         END_CYC
      END_IF
   ELSE
      $no_filed = 1
      IF($log = 1)
         LOGWRITE ($to_X, "/", $to_Y, "   за пределами поля")
      END_IF
   END_IF
END_SUB

//==============================================================================
//===  Чтение состояния клетки  ================================================
SUB(read, $tt_X, $tt_Y)
   //check_closed($tt_X, $tt_Y)
   IF(($closed_on = 1) | ($tt_X < 0) | ($tt_Y < 0) | ($tt_X = $width) | ($tt_Y = $height))
      $state = 1
   ELSE
      $state = INT(STRCUT($map[$tt_Y], $tt_X + 1, 1))
      //IF($state = $ending)
      //   $check_end = 1
      //END_IF
   END_IF
   
   IF($log2 = 1)
      LOGWRITE ("$state=", $state, "   ",$tt_X, "/", $tt_Y)
   END_IF
END_SUB

//==============================================================================
//===  Если уже входит в $open  ================================================
SUB(already_open, $ta_P, $ta_G)
   IF($ta_G < $G_old)
      $open[$ind_open+2] = $ta_P
      $ta_X = $open[$ind_open]
      $ta_Y = $open[$ind_open+1]
      calc_H($ta_X, $ta_Y)
      $open[$ind_open+3] = $ta_G + $H
     
      IF($log = 1)
         LOGWRITE ("Update open:  ", $ta_X, ":", $ta_Y, ":", $ta_P, ":", $ta_G + $H)
      END_IF
   ELSE
      IF($log = 1)
         LOGWRITE ("не обновляем в $open")
      END_IF
   END_IF
END_SUB

//==============================================================================
//===  Вывод в лог $open  ======================================================
SUB(log_open)
   IF($log = 1)
      $size_open = ARRSIZE($open)
      LOGWRITE ("$open:")
      FOR($i=0, $i < $size_open, 4)
         LOGWRITE ($open[$i], ":", $open[$i+1], ":", $open[$i+2], ":", $open[$i+3])
      END_CYC
   END_IF
END_SUB

//==============================================================================
//===  Вывод результата  =======================================================
SUB(result)
   $r_X = $endX
   $r_Y = $endY
   $temp = $log
   $log = 0
   LOGWRITE ("result:")
   check_open($r_X, $r_Y)  // $closed_on = 1  $opened_on = 1
   
   WHILE($P_res > 0)
      SWITCH($P_res)
      CASE(1)
         $direction = "вверх"
         INC($r_Y)
      CASE(2)
         $direction = "вверх-вправо"
         INC($r_Y)
         INC($r_X, -1)
      CASE(3)
         $direction = "вправо"
         INC($r_X, -1)
      CASE(4)
         $direction = "вних-вправо"
         INC($r_Y, -1)
         INC($r_X, -1)
      CASE(5)
         $direction = "вниз"
         INC($r_Y, -1)
      CASE(6)
         $direction = "вниз-влево"
         INC($r_Y, -1)
         INC($r_X)
      CASE(7)
         $direction = "влево"
         INC($r_X)
      CASE(8)
         $direction = "вверх-влево"
         INC($r_Y)
         INC($r_X)
      END_SWITCH
     
      ARRPUSH($preresult, $r_X)
      ARRPUSH($preresult, $r_Y)
      ARRPUSH($preresult, $P_res)
      ARRPUSH($preresult, $direction)
      ARRPUSH($preresult, STRCONCAT($r_X, "/", $r_Y, "  ", $P_res, " - ",$direction))
      check_open($r_X, $r_Y)
   END_CYC
   $log = $temp
   UNDEFINE($result)
   
   // переворачиваем ответ, делаем от старт к финиш
   WHILE(ARRSIZE($preresult) > 0)
      $text = ARRPOP($preresult)
      $direction = ARRPOP($preresult)
      $P_res = ARRPOP($preresult)
      $r_Y = ARRPOP($preresult)
      $r_X = ARRPOP($preresult)
     
      ARRPUSH($result, $r_X)
      ARRPUSH($result, $r_Y)
      ARRPUSH($result, $P_res)
      ARRPUSH($result, $direction)
      ARRPUSH($result, $text)
   END_CYC
   
   // вывод ответа в лог
   IF(ARRSIZE($result) > 0)
      $asize = ARRSIZE($result)
      FOR($i=4, $i < $asize, 5)
         LOGWRITE ($result[$i])   
      END_CYC
   END_IF
END_SUB

//==============================================================================
//===  Добавление соседей в открытый  ==========================================
SUB(vicinage, $t_X, $t_Y, $t_Fprev)
   calc_H($t_X, $t_Y)
   $H_cur = $H
   $G_cur = $t_Fprev - $H_cur
   
   // вверх, 1
   check_open($t_X, $t_Y-1)
   IF($no_filed = 0)
      IF(($opened_on = 0) & ($closed_on = 0))
         read($t_X, $t_Y-1)
         IF($state ! 1)
            add_open($t_X, $t_Y-1, 1, $G_cur + 10)
         END_IF
      ELSE
         IF($closed_on ! 1)
            already_open(1, $G_cur + 10)
         END_IF
      END_IF
   END_IF
   
   // вверх-вправо, 2
   IF($check_end = 0)
      check_open($t_X+1, $t_Y-1)
      IF($no_filed = 0)
         IF(($opened_on = 0) & ($closed_on = 0))
            read($t_X+1, $t_Y-1)
            IF($state ! 1)
               read($t_X, $t_Y-1)
               $state1 = $state
               read($t_X+1, $t_Y)
               IF(($state = 1) & ($state1 = 1))
               ELSE
                  IF(($bypass_angle = 1) & (($state = 1) | ($state1 = 1)))
                  ELSE
                     add_open($t_X+1, $t_Y-1, 2, $G_cur + 14)
                  END_IF
               END_IF
            END_IF
         ELSE
            IF($closed_on ! 1)
               already_open(2, $G_cur + 14)
            END_IF
         END_IF
      END_IF
   END_IF
   
   // вправо, 3
   IF($check_end = 0)
      check_open($t_X+1, $t_Y)
      IF($no_filed = 0)
         IF(($opened_on = 0) & ($closed_on = 0))
            read($t_X+1, $t_Y)
            IF($state ! 1)
               add_open($t_X+1, $t_Y, 3, $G_cur + 10)
            END_IF
         ELSE
            IF($closed_on ! 1)
               already_open(3, $G_cur + 10)
            END_IF
         END_IF
      END_IF
   END_IF
   
   // вниз-вправо, 4
   IF($check_end = 0)
      check_open($t_X+1, $t_Y+1)
      IF($no_filed = 0)
         IF(($opened_on = 0) & ($closed_on = 0))
            read($t_X+1, $t_Y+1)
            IF($state ! 1)
               read($t_X+1, $t_Y)
               $state1 = $state
               read($t_X, $t_Y+1)
               IF(($state = 1) & ($state1 = 1))
               ELSE
                  IF(($bypass_angle = 1) & (($state = 1) | ($state1 = 1)))
                  ELSE
                     add_open($t_X+1, $t_Y+1, 4, $G_cur + 14)
                  END_IF
               END_IF
            END_IF
         ELSE
            IF($closed_on ! 1)
               already_open(4, $G_cur + 14)
            END_IF
         END_IF
      END_IF
   END_IF
   
   // вниз, 5
   IF($check_end = 0)
      check_open($t_X, $t_Y+1)
      IF($no_filed = 0)
         IF(($opened_on = 0) & ($closed_on = 0))
            read($t_X, $t_Y+1)
            IF($state ! 1)
               add_open($t_X, $t_Y+1, 5, $G_cur + 10)
            END_IF
         ELSE
            IF($closed_on ! 1)
               already_open(5, $G_cur + 10)
            END_IF
         END_IF
      END_IF
   END_IF
   
   // вниз-влево, 6
   IF($check_end = 0)
      check_open($t_X-1, $t_Y+1)
      IF($no_filed = 0)
         IF(($opened_on = 0) & ($closed_on = 0))
            read($t_X-1, $t_Y+1)
            IF($state ! 1)
               read($t_X, $t_Y+1)
               $state1 = $state
               read($t_X-1, $t_Y)
               IF(($state = 1) & ($state1 = 1))
               ELSE
                  IF(($bypass_angle = 1) & (($state = 1) | ($state1 = 1)))
                  ELSE
                     add_open($t_X-1, $t_Y+1, 6, $G_cur + 14)
                  END_IF
               END_IF
            END_IF
         ELSE
            IF($closed_on ! 1)
               already_open(6, $G_cur + 14)
            END_IF
         END_IF
      END_IF
   END_IF
   
   // влево, 7
   IF($check_end = 0)
      check_open($t_X-1, $t_Y)
      IF($no_filed = 0)
         IF(($opened_on = 0) & ($closed_on = 0))
            read($t_X-1, $t_Y)
            IF($state ! 1)
               add_open($t_X-1, $t_Y, 7, $G_cur + 10)
            END_IF
         ELSE
            IF($closed_on ! 1)
               already_open(7, $G_cur + 10)
            END_IF
         END_IF
      END_IF
   END_IF
   
   // вверх-влево, 8
   IF($check_end = 0)
      check_open($t_X-1, $t_Y-1)
      IF($no_filed = 0)
         IF(($opened_on = 0) & ($closed_on = 0))
            read($t_X-1, $t_Y-1)
            IF($state ! 1)
               read($t_X-1, $t_Y)
               $state1 = $state
               read($t_X, $t_Y-1)
               IF(($state = 1) & ($state1 = 1))
               ELSE
                  IF(($bypass_angle = 1) & (($state = 1) | ($state1 = 1)))
                  ELSE
                     add_open($t_X-1, $t_Y-1, 8, $G_cur + 14)
                  END_IF
               END_IF
            END_IF
         ELSE
            IF($closed_on ! 1)
               already_open(8, $G_cur + 14)
            END_IF
         END_IF
      END_IF
   END_IF
END_SUB

//==============================================================================
//===  Поиск индекса в open с наилучшим F  =====================================
SUB(find_best)
   $min = 100000
   $size_open = ARRSIZE($open)
   FOR($i=$size_open-1, $i > 0, -4)
      IF($open[$i] < $min)
         $min = $open[$i]
         $best = $i
      END_IF
   END_CYC
   
   IF($log = 1)
      LOGWRITE ("best: ", $open[$best-3], "/", $open[$best-2], "  значение: ", $min, " поз. ", $best)
   END_IF
END_SUB

//==============================================================================
//===  Чтение карты  ===========================================================
SUB(read_map)
   IF($log0 = 1)
      LOGWRITE("--- читаем карту ---")
   END_IF
   TFREADARR ($map_name, $map)
   $size_arrmap = ARRSIZE($map)
   FOR($i=0, $i < ($size_arrmap - 1))
      $map[$i] = $map[$i+1]
   END_CYC
   $nul = ARRPOP($map)
   
   //   $i = 1
   //   $count_line = TFCOUNT($map_name)
   //   WHILE($i < ($count_line + 1))
   //      ARRPUSH($map, TFREAD($map_name, $i))
   //      INC($i)
   //   END_CYC
   
   // находим стартовую и конечную позиции
   $exit = 0
   $size_arrmap = ARRSIZE($map)
   IF($log0 = 1)
      //LOGWRITE ("$size_arrmap: ", $size_arrmap)
      FOR($i=0, $i < $size_arrmap)
         LOGWRITE($map[$i])
      END_CYC
   END_IF
   
   FOR($i=0, $i < $size_arrmap)
      $str = $map[$i]
      $pos_start = STRPOS($str, $start)
      IF($pos_start > 0)
         $start_X = $pos_start - 1
         $start_Y = $i
         IF($endX > -1)
            $exit = 1
         END_IF
      END_IF
      $pos_end = STRPOS($str, $ending)
      IF($pos_end > 0)
         $endX = $pos_end - 1
         $endY = $i
         IF($start_X > -1)
            $exit = 1
         END_IF
      END_IF
      IF($exit = 1)
         $i = $size_arrmap + 1
      END_IF
   END_CYC
   // ширина карты
   $width = STRLEN($map[0])
   // высота карты
   $height = ARRSIZE($map)
   
   IF($log0 = 1)
      LOGWRITE ("start: ", $start_X, "/", $start_Y)
      LOGWRITE ("end:   ", $endX, "/", $endY)
      LOGWRITE ("width/height ", $width, "/", $height)
      LOGWRITE (" ")
   END_IF
END_SUB

//==============================================================================
//===  Включение окна лога  ====================================================
SUB(initial)
   LOGCLEAR
   WAITMS(500)
   MOVE($_xmax,0)
   WAITMS(50)
   IF($log=1)
      LOGSHOW (1,$_xmax-335,28) // отображение окна лога
      WNDSIZE(WNDFIND("Clickermann - Лог"),336,560) // изменения размеров окна лога 260
   END_IF
END_SUB

//==============================================================================


initial()

// карта
$map = 0
// флаг завершения
$check_end = 0
// индекс в open клетки с лучшим F
$best = -1
// Старт
$start_X = -1
$start_Y = -1
// Финиш
$endX = -1
$endY = -1
// открытый список
//$open = 0
// закрытый список
//$close = 0

read_map()

// Добавляем стартовую в открытый список
add_open($start_X, $start_Y, 0, 0)

WHILE((ARRSIZE($open) > 3) & ($check_end = 0))
   log_open()
   find_best()
   
   // Текущая обрабатываемая
   $cur_F = $open[$best] // стоимость F текущей
   $cur_parent = $open[$best-1]   // направление на родителя
   $cur_Y = $open[$best-2] // позиция Y
   $cur_X = $open[$best-3] // позиция X
   
   del_open($best)
   add_close($cur_X, $cur_Y, $cur_parent)
   vicinage($cur_X, $cur_Y, $cur_F)
   IF($log=1)
      LOGWRITE (" ")
   END_IF
END_CYC

IF($check_end = 0)
   LOGWRITE ("Решения нет")
   HALT
END_IF

result()
LOGWRITE ("===============  финита ля комедия  ===============")
LOGWRITE (" ")
HALT[/spoiler]

Итоги.
Опробовал на трёх небольших картах (во вложении).
Самая маленькая из разработки вычисляется меньше секунды



Следующая побольше. Здесь глубокая засада-карман из которого алгоритму долго выбираться. На рабочем компе считалось аж 9 минут 



И последняя, размером как вторая, но с лабиринтом. Здесь решилось за 1 мин. 20 сек. В принципе неплохо. Пришлось скрин разбить на 2, решение длинное.




Вот и всё.
Учитесь и развивайтесь.

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

[Vint]

Жаль что никого не заинтересовало...

Я тут наткнулся на лабиринтик и написал продолжение. Идею вводить карту руками сразу отмёл и сделал автоматизированное определение и возможность рисования пути.
Вот такое решение, правда долго зараза


Вот даже видео сделал:
http://youtu.be/sA_-N495Nio

А дальше уже сам нарисовал "коровку"-болота.
Прохождение без диагональных передвижений


И с диагональными

[Уральский]

Не совсем понимаю как делать чтобы передвигаться по лабиринту не упираясь в тены

[Vint]

Смотря что за лабиринт и чем там передвигается.

[Уральский]

Лабиринт как на картинке, он  всегда одинаковый, черная область это стены, в белой области находятся мобы ( всегда в разных местах )
Цель не пройти из точки А в точку Б а передвигаться по белой области не упираясь в стены, когда находит моба за стеной должен её обойти.
Мобы появляются беспорядочно, часто бывает что нужно ходить по несколько раз из конца в конец лабиринта пока  всех не перебьёшь.

[dramster]

Жаль что никого не заинтересовало...

вроде как заинтересовало, сразу появилась идея создания маршрута в играх по карте из точки А в точку Б, где эти точки находятся в рандомных координатах. но както не доходили руки проверить алгоритм в деле.

  задача такова. есть небольшой кусок карты. персонаж стоит в рандомном месте. появляется метка (также в рандомном месте). алгоритм должен определить ближайший маршрут. персонаж с помощью скрипта бежит по контрольным точкам, которые ранее определил "алгоритма поиска пути A" к метке, делает свое дело. появляется новая метка. бежим к ней, и так далее. вроде всё просто  .
  в принципе метки появляются в определенных местах, этих мест всего 25. есть рабочий бот который бегает до этих меток по заранее записанному маршруту в тхт, НО приходится после каждой метки бежать в стартовую точку,и далее со стартовой точки к следующей метке. а это перемещение впустую  примерно в двое увеличивает время работы. да, конечно можно записать все маршруты,  всех меток ко всем меткам. но таких будет 25х25=оооочень много. а "алгоритма поиска пути A" вроде как должен выдать оптимальный маршрут без каких либо лишних махинаций.
 начал с того, что нарисовал карту. один кликер определял координаты персонажа с карты игры и писал в ини. второй кликер, в привязке к паинту, читал эти координаты и отрисовывал  в паинте местонахождение персонажа. пробежался по всем дорогам, немного подредактировал, вышло вроде ничего

для примерного понимания расстояния, бегом из левого угла в правый угол этой карты(не по дороге, напрямую) занимает гдето 40-50сек.
  далее, начал переводить карту в текстовый файл. оптимальное разрешение ноликов-едениц вышло 66х57, по 5 пикселей карты на один нолик или единицу (это примерно чуть меньше ширины дороги в игре), опять же слегка подредактировал, для теста.
[spoiler]

Code: [Select]

111111111111111111111111111111111111100000000000111111111111111111
111111111111111111000000000000000000000011111000001111111111111111
111111111111111110000111111111111111111111111111000001111111111111
111111111111111100111111111111111111111111111111111000111111111111
111111111111111100111111111111111000000000000001111110001111111111
111111111111111110010000000000000000011111111000011111000111111111
111111111111111111000001111111111111111111111000000111100011111111
111111111111111111111111111111111100000000000001100011110011111111
111111111111111111110000000000000000000000000001110001111001111111
111111111111111000000000111111111111111111111000011100111100111111
111111111111000001111111111111110001111000011110001110011100111111
111111111110001111111100000000000000000000000111000110001110011111
111111111110011111000000001111111100000111110001100011000110001111
111111111100110000001111111111111100111111111001110011100111001111
111111111001100011111111000000011100111111111100111001110011100111
111111110000001111110000000000000000000011111110011000110011100111
111111100000111111100001111111111111000000001110011100111001100111
111111100111111111100111111111111111111110000111001100011000110011
111111001111111111101111111111111111111111110011001110011100110011
111111001111111111101111111111111111111111110011100110001110010011
111111001000000000001111111111111111111111111000100111001110010011
111111000000000011001111111111111111111111111100110111000111001011
111111000011111111001111111111111111111111111110110011100111001011
111111000111111111001111111111111111111111111110010011100111100011
100000001111111111011111111111111111111111111110111000000111100011
001100011111111111011111111111111111111111111110111000010111000000
011100000111111111011111111111111111111111111100111101110011001100
010000000000001111011111111111111111111111111100111101110011001100
011110011110000010011111111111111111111111111001111001110011001110
001110011111110000011111111111111111111111110001111001110011001110
100111001111111100011111111111111111111111100011111001110011101110
100111000111111100111111111111111111111111100111111001110011101110
110111100111111100111111111111111111111111001111111001110011101110
110111110011111100000000000111111111111110011111111001110011101110
110111111001111100000011100011111111111100011111111001110011001110
110111111000111100111111110011111111111100111111111001110011001110
110111111100001111111111111001111111111001111111111001110011001110
100111111111000111111111111000111111110011111111111011110111001110
100111111111000011111111111100000111100111111111111011110111001110
111111111110010001111111111111000000001111111111110011100111011100
111111111110011000011111111111111110011111111111110011100111011100
111111111111001100000000111111111111111111111111100111001111011100
111111111111001111111000000011111111111111111110001111001110011001
111111111111001111111111110000011111111111110000011110011100011001
111111111000001111111111111110000001111110000001111100011000110011
111111111000000001111111111111110000000000001111111000110001110011
111111111111111000011111111111111111111111111111110001100011100111
111111111111111110000111111111111111111111111111000011000111000111
111111111111111111100000111111111111111111111111001110011110001111
111111111111111111111100001111111111111111111111111100111100011111
111111111111111111111111000001111111111111111111111001111000111111
111111111111111111111111111000001111111111111111100011100001111111
111111111111111111111111111111000000000000000000000000000111111111
111111111111111111111111111111111100000000000010000000011111111111
111111111111111111111111111111111111111111111110011111111111111111
111111111111111111111111111111111111111111110000011111111111111111
111111111111111111111111111111111111111000000011111111111111111111[/spoiler]


первый тест:
[spoiler]

Code: [Select]

1:53:49 --- читаем карту ---
1:53:49 111111111111111111111111111111111111100000000000111111111111111111
1:53:49 111111111111111111000000000000000000000011111000001111111111111111
1:53:49 111111111111111110000111111111111111111111111111000001111111111111
1:53:49 111111111111111100111111111111111111111111111111111000111111111111
1:53:49 111111111111111100111111111111111000000000000001111110001111111111
1:53:49 111111111111111110010000000000000000011111111000011111000111111111
1:53:49 111111111111111111000001111111111111111111111000000111100011111111
1:53:49 111111111111111111111111111111111100000000000001100011110011111111
1:53:49 111111111111111111110000000000000000000000000001110001111001111111
1:53:49 111111111111111000000000111111111111111111111000011100111100111111
1:53:49 111111111111000001111111111111110001111000011110001110011100111111
1:53:49 111111111110001111111100000000000000000000000111000110001110011111
1:53:49 111111111110011111000000001111111100000111110001100011000110001111
1:53:49 111111111100110000001111111111111100111111111001110011100111001111
1:53:49 111111111001100011111111000000011100111111111100111001110011100111
1:53:49 111111110000001111110000000000500000000011111110011000110011100111
1:53:49 111111100000111111100001111111111111000000001110011100111001100111
1:53:49 111111100111111111100111111111111111111110000111001100011000110011
1:53:49 111111001111111111101111111111111111111111110011001110011100110011
1:53:49 111111001111111111101111111111111111111111110011100110001110010011
1:53:50 111111001000000000001111111111111111111111111000100111001110010011
1:53:50 111111000000000011001111111111111111111111111100110111000111001011
1:53:50 111111000011111111001111111111111111111111111110110011100111001011
1:53:50 111111000111111111001111111111111111111111111110010011100111100011
1:53:50 100000001111111111011111111111111111111111111110111000000111100011
1:53:50 001100011111111111011111111111111111111111111110111000010111000000
1:53:50 011100000111111111011111111111111111111111111100111101110011001100
1:53:50 010000000000001111011111111111111111111111111100111101110011001100
1:53:50 011110011110000010011111111111111111111111111001111001110011001110
1:53:50 001110011111110000011111111111111111111111110001111001110011001110
1:53:50 100111001111111100011111111111111111111111100011111001110011101110
1:53:50 100111000111111100111111111111111111111111100111111001110011101110
1:53:50 110111100111111100111111111111111111111111001111111001110011101110
1:53:50 110111110011111100000000000111111111111110011111111001110011101110
1:53:50 110111111001111100000011100011111111111100011111111001110011001110
1:53:50 110111111000111100111111110011111111111100111111111001110011001110
1:53:50 110111111100001111111111111001111111111001111111111001110011001110
1:53:50 100111111111000111111111111000111111110011111111111011110111001110
1:53:50 140111111111000011111111111100000111100111111111111011110111001110
1:53:50 111111111110010001111111111111000000001111111111110011100111011100
1:53:50 111111111110011000011111111111111110011111111111110011100111011100
1:53:50 111111111111001100000000111111111111111111111111100111001111011100
1:53:50 111111111111001111111000000011111111111111111110001111001110011001
1:53:50 111111111111001111111111110000011111111111110000011110011100011001
1:53:50 111111111000001111111111111110000001111110000001111100011000110011
1:53:50 111111111000000001111111111111110000000000001111111000110001110011
1:53:50 111111111111111000011111111111111111111111111111110001100011100111
1:53:50 111111111111111110000111111111111111111111111111000011000111000111
1:53:50 111111111111111111100000111111111111111111111111001110011110001111
1:53:50 111111111111111111111100001111111111111111111111111100111100011111
1:53:50 111111111111111111111111000001111111111111111111111001111000111111
1:53:50 111111111111111111111111111000001111111111111111100011100001111111
1:53:50 111111111111111111111111111111000000000000000000000000000111111111
1:53:50 111111111111111111111111111111111100000000000010000000011111111111
1:53:50 111111111111111111111111111111111111111111111110011111111111111111
1:53:50 111111111111111111111111111111111111111111110000011111111111111111
1:53:50 111111111111111111111111111111111111111000000011111111111111111111
1:53:50 start: 1/38
1:53:50 end:   30/15
1:53:50 width/height 66/57
1:53:50 
1:54:11 result:
1:54:13 1/38  2 - вверх-вправо
1:54:13 2/37  1 - вверх
1:54:13 2/36  1 - вверх
1:54:13 2/35  1 - вверх
1:54:13 2/34  1 - вверх
1:54:13 2/33  1 - вверх
1:54:13 2/32  1 - вверх
1:54:13 2/31  1 - вверх
1:54:13 2/30  8 - вверх-влево
1:54:13 1/29  8 - вверх-влево
1:54:13 0/28  1 - вверх
1:54:13 0/27  1 - вверх
1:54:13 0/26  2 - вверх-вправо
1:54:13 1/25  2 - вверх-вправо
1:54:13 2/24  3 - вправо
1:54:13 3/24  3 - вправо
1:54:14 4/24  3 - вправо
1:54:14 5/24  2 - вверх-вправо
1:54:14 6/23  2 - вверх-вправо
1:54:14 7/22  2 - вверх-вправо
1:54:14 8/21  2 - вверх-вправо
1:54:14 9/20  3 - вправо
1:54:14 10/20  3 - вправо
1:54:14 11/20  3 - вправо
1:54:14 12/20  3 - вправо
1:54:14 13/20  3 - вправо
1:54:14 14/20  3 - вправо
1:54:14 15/20  3 - вправо
1:54:14 16/20  3 - вправо
1:54:14 17/20  3 - вправо
1:54:14 18/20  2 - вверх-вправо
1:54:14 19/19  1 - вверх
1:54:14 19/18  2 - вверх-вправо
1:54:14 20/17  2 - вверх-вправо
1:54:14 21/16  2 - вверх-вправо
1:54:14 22/15  3 - вправо
1:54:14 23/15  3 - вправо
1:54:14 24/15  3 - вправо
1:54:14 25/15  3 - вправо
1:54:14 26/15  3 - вправо
1:54:14 27/15  3 - вправо
1:54:14 28/15  3 - вправо
1:54:14 29/15  3 - вправо
1:54:14 ===============  финита ля комедия  ===============
1:54:14 
[/spoiler]
ну вроде всё сработало, но... 20 с лишним сек!!!! многовато 

следующий тест, примерно самый дальний маршрут, с одного угла в другой:
[spoiler]

Code: [Select]

1:07:52 --- читаем карту ---
1:07:53 111111111111111111111111111111111111100000000000111111111111111111
1:07:53 111111111111111111000000000000000000000011111000001111111111111111
1:07:53 111111111111111110000111111111111111111111111111000001111111111111
1:07:53 111111111111111100111111111111111111111111111111111000111111111111
1:07:53 111111111111111100111111111111111000000000000001111110001111111111
1:07:53 111111111111111110010000000000000000011111111000011111000111111111
1:07:53 111111111111111111000001111111111111111111111000000111100011111111
1:07:53 111111111111111111111111111111111100000000000001100011110011111111
1:07:53 111111111111111111110000000000000000000000000001110001111001111111
1:07:53 111111111111111000000000111111111111111111111000011100111100111111
1:07:53 111111111111000001111111111111110001111000011110001110011100111111
1:07:53 111111111110001111111100000000000000000000000111000110001110011111
1:07:53 111111111110011111000000001111111100000111110001100011000110001111
1:07:53 111111111100110000001111111111111100111111111001110011100111001111
1:07:53 111111111001100011111111000000011100111111111100111001110011100111
1:07:53 111111110000001111110000000000000000000011111110011000110011100111
1:07:53 111111100000111111100001111111111111000000001110011100111001100111
1:07:53 111111100111111111100111111111111111111110000111001100011000110011
1:07:53 111111001111111111101111111111111111111111110011001110011100110011
1:07:53 111111001111111111101111111111111111111111110011100110001110010011
1:07:53 111111001000000000001111111111111111111111111000100111001110010011
1:07:53 111111000000000011001111111111111111111111111100110111000111001011
1:07:53 111111000011111111001111111111111111111111111110110011100111001011
1:07:53 111111000111111111001111111111111111111111111110010011100111100011
1:07:53 000000001111111111011111111111111111111111111110111000000111100011
1:07:53 001100011111111111011111111111111111111111111110111000010111000000
1:07:53 011100000111111111011111111111111111111111111100111101110011001100
1:07:53 010000000000001111011111111111111111111111111100111101110011001100
1:07:53 011110011110000010011111111111111111111111111001111001110011001110
1:07:53 001110011111110000011111111111111111111111110001111001110011001110
1:07:53 100111001111111100011111111111111111111111100011111001110011101110
1:07:53 100111000111111100111111111111111111111111100111111001110011101110
1:07:53 110111100111111100111111111111111111111111001111111001110011101110
1:07:53 110111110011111100000000000111111111111110011111111001110011101115
1:07:53 110111111001111100000011100011111111111100011111111001110011001110
1:07:53 110111111000111100111111110011111111111100111111111001110011001110
1:07:53 110111111100001111111111111001111111111001111111111001110011001110
1:07:53 100111111111000111111111111000111111110011111111111011110111001110
1:07:53 140111111111000011111111111100000111100111111111111011110111001110
1:07:53 111111111110010001111111111111000000001111111111110011100111011100
1:07:53 111111111110011000011111111111111110011111111111110011100111011100
1:07:53 111111111111001100000000111111111111111111111111100111001111011100
1:07:53 111111111111001111111000000011111111111111111110001111001110011001
1:07:53 111111111111001111111111110000011111111111110000011110011100011001
1:07:53 111111111000001111111111111110000001111110000001111100011000110011
1:07:53 111111111000000001111111111111110000000000001111111000110001110011
1:07:53 111111111111111000011111111111111111111111111111110001100011100111
1:07:53 111111111111111110000111111111111111111111111111000011000111000111
1:07:53 111111111111111111100000111111111111111111111111001110011110001111
1:07:53 111111111111111111111100001111111111111111111111111100111100011111
1:07:53 111111111111111111111111000001111111111111111111111001111000111111
1:07:53 111111111111111111111111111000001111111111111111100011100001111111
1:07:53 111111111111111111111111111111000000000000000000000000000111111111
1:07:53 111111111111111111111111111111111100000000000010000000011111111111
1:07:53 111111111111111111111111111111111111111111111110011111111111111111
1:07:53 111111111111111111111111111111111111111111110000011111111111111111
1:07:53 111111111111111111111111111111111111111000000011111111111111111111
1:07:53 start: 1/38
1:07:53 end:   65/33
1:07:53 width/height 66/57
1:07:53 
1:46:36 result:
1:47:07 1/38  2 - вверх-вправо
1:47:07 2/37  1 - вверх
1:47:07 2/36  1 - вверх
1:47:07 2/35  1 - вверх
1:47:07 2/34  1 - вверх
1:47:07 2/33  1 - вверх
1:47:07 2/32  1 - вверх
1:47:07 2/31  8 - вверх-влево
1:47:07 1/30  1 - вверх
1:47:07 1/29  7 - влево
1:47:07 0/29  1 - вверх
1:47:07 0/28  1 - вверх
1:47:07 0/27  1 - вверх
1:47:07 0/26  1 - вверх
1:47:07 0/25  2 - вверх-вправо
1:47:07 1/24  3 - вправо
1:47:07 2/24  3 - вправо
1:47:07 3/24  3 - вправо
1:47:07 4/24  4 - вних-вправо
1:47:07 5/25  4 - вних-вправо
1:47:07 6/26  5 - вниз
1:47:07 6/27  5 - вниз
1:47:07 6/28  5 - вниз
1:47:07 6/29  5 - вниз
1:47:07 6/30  4 - вних-вправо
1:47:07 7/31  4 - вних-вправо
1:47:07 8/32  5 - вниз
1:47:07 8/33  3 - вправо
1:47:07 9/33  5 - вниз
1:47:07 9/34  4 - вних-вправо
1:47:07 10/35  4 - вних-вправо
1:47:07 11/36  3 - вправо
1:47:07 12/36  5 - вниз
1:47:07 12/37  5 - вниз
1:47:07 12/38  5 - вниз
1:47:07 12/39  5 - вниз
1:47:07 12/40  5 - вниз
1:47:07 12/41  4 - вних-вправо
1:47:07 13/42  5 - вниз
1:47:07 13/43  5 - вниз
1:47:07 13/44  5 - вниз
1:47:07 13/45  3 - вправо
1:47:07 14/45  3 - вправо
1:47:07 15/45  4 - вних-вправо
1:47:07 16/46  3 - вправо
1:47:07 17/46  4 - вних-вправо
1:47:07 18/47  3 - вправо
1:47:07 19/47  4 - вних-вправо
1:47:07 20/48  3 - вправо
1:47:07 21/48  3 - вправо
1:47:07 22/48  4 - вних-вправо
1:47:07 23/49  3 - вправо
1:47:07 24/49  4 - вних-вправо
1:47:07 25/50  3 - вправо
1:47:07 26/50  3 - вправо
1:47:07 27/50  4 - вних-вправо
1:47:07 28/51  3 - вправо
1:47:07 29/51  3 - вправо
1:47:07 30/51  4 - вних-вправо
1:47:07 31/52  3 - вправо
1:47:07 32/52  3 - вправо
1:47:07 33/52  3 - вправо
1:47:07 34/52  3 - вправо
1:47:07 35/52  3 - вправо
1:47:07 36/52  3 - вправо
1:47:07 37/52  3 - вправо
1:47:07 38/52  3 - вправо
1:47:07 39/52  3 - вправо
1:47:07 40/52  3 - вправо
1:47:07 41/52  3 - вправо
1:47:07 42/52  3 - вправо
1:47:07 43/52  3 - вправо
1:47:07 44/52  3 - вправо
1:47:07 45/52  3 - вправо
1:47:07 46/52  3 - вправо
1:47:07 47/52  3 - вправо
1:47:07 48/52  3 - вправо
1:47:07 49/52  3 - вправо
1:47:07 50/52  3 - вправо
1:47:07 51/52  3 - вправо
1:47:07 52/52  3 - вправо
1:47:07 53/52  3 - вправо
1:47:07 54/52  3 - вправо
1:47:07 55/52  2 - вверх-вправо
1:47:07 56/51  3 - вправо
1:47:07 57/51  2 - вверх-вправо
1:47:07 58/50  2 - вверх-вправо
1:47:07 59/49  2 - вверх-вправо
1:47:07 60/48  2 - вверх-вправо
1:47:07 61/47  2 - вверх-вправо
1:47:07 62/46  1 - вверх
1:47:07 62/45  2 - вверх-вправо
1:47:07 63/44  1 - вверх
1:47:07 63/43  2 - вверх-вправо
1:47:07 64/42  1 - вверх
1:47:07 64/41  2 - вверх-вправо
1:47:07 65/40  1 - вверх
1:47:07 65/39  1 - вверх
1:47:07 65/38  1 - вверх
1:47:07 65/37  1 - вверх
1:47:07 65/36  1 - вверх
1:47:07 65/35  1 - вверх
1:47:07 65/34  1 - вверх
1:47:07 ===============  финита ля комедия  ===============
1:47:07 
[/spoiler]
пока он там чтото считал, я успел покушать, повтыкал перед теликам, чуть не уснул  . 40 МИН !!!!!!!!!!!

 это слишком. было бы мега круто если бы расчет проходил за секунды. ведь это же только кусочек карты. а у меня были планы на всю карту , все дороги (кроме эстакад и тоннелей) для движения уже на транспорте.

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

[Vint]

Так...
У тебя расчёт идёт с движением по диагонали, хотя лабиринт позволяет ходить без диагоналей.
Без диагоналей расчёт почти всегда в 2 раза быстрей.  + скорость расчёта от компа зависит.

У меня результаты первого теста:
диагониль + обходить углы:      9,073 сек
диагониль + не обходить углы: 8,489 сек     (этот вариант ты делал)
без диагонилей:                         5,931 сек

Приложу вычисление 1 теста с настройками как у тебя (диагональ-не обходить углы)
[spoiler]

Code: [Select]

12:35:15 --- читаем карту ---
12:35:15 111111111111111111111111111111111111100000000000111111111111111111
12:35:15 111111111111111111000000000000000000000011111000001111111111111111
12:35:15 111111111111111110000111111111111111111111111111000001111111111111
12:35:15 111111111111111100111111111111111111111111111111111000111111111111
12:35:15 111111111111111100111111111111111000000000000001111110001111111111
12:35:15 111111111111111110010000000000000000011111111000011111000111111111
12:35:15 111111111111111111000001111111111111111111111000000111100011111111
12:35:15 111111111111111111111111111111111100000000000001100011110011111111
12:35:15 111111111111111111110000000000000000000000000001110001111001111111
12:35:15 111111111111111000000000111111111111111111111000011100111100111111
12:35:15 111111111111000001111111111111110001111000011110001110011100111111
12:35:15 111111111110001111111100000000000000000000000111000110001110011111
12:35:15 111111111110011111000000001111111100000111110001100011000110001111
12:35:15 111111111100110000001111111111111100111111111001110011100111001111
12:35:15 111111111001100011111111000000011100111111111100111001110011100111
12:35:15 111111110000001111110000000000500000000011111110011000110011100111
12:35:15 111111100000111111100001111111111111000000001110011100111001100111
12:35:15 111111100111111111100111111111111111111110000111001100011000110011
12:35:15 111111001111111111101111111111111111111111110011001110011100110011
12:35:15 111111001111111111101111111111111111111111110011100110001110010011
12:35:15 111111001000000000001111111111111111111111111000100111001110010011
12:35:15 111111000000000011001111111111111111111111111100110111000111001011
12:35:15 111111000011111111001111111111111111111111111110110011100111001011
12:35:15 111111000111111111001111111111111111111111111110010011100111100011
12:35:15 100000001111111111011111111111111111111111111110111000000111100011
12:35:15 001100011111111111011111111111111111111111111110111000010111000000
12:35:15 011100000111111111011111111111111111111111111100111101110011001100
12:35:15 010000000000001111011111111111111111111111111100111101110011001100
12:35:15 011110011110000010011111111111111111111111111001111001110011001110
12:35:15 001110011111110000011111111111111111111111110001111001110011001110
12:35:15 100111001111111100011111111111111111111111100011111001110011101110
12:35:15 100111000111111100111111111111111111111111100111111001110011101110
12:35:15 110111100111111100111111111111111111111111001111111001110011101110
12:35:15 110111110011111100000000000111111111111110011111111001110011101110
12:35:15 110111111001111100000011100011111111111100011111111001110011001110
12:35:15 110111111000111100111111110011111111111100111111111001110011001110
12:35:15 110111111100001111111111111001111111111001111111111001110011001110
12:35:15 100111111111000111111111111000111111110011111111111011110111001110
12:35:15 140111111111000011111111111100000111100111111111111011110111001110
12:35:15 111111111110010001111111111111000000001111111111110011100111011100
12:35:15 111111111110011000011111111111111110011111111111110011100111011100
12:35:15 111111111111001100000000111111111111111111111111100111001111011100
12:35:15 111111111111001111111000000011111111111111111110001111001110011001
12:35:15 111111111111001111111111110000011111111111110000011110011100011001
12:35:15 111111111000001111111111111110000001111110000001111100011000110011
12:35:15 111111111000000001111111111111110000000000001111111000110001110011
12:35:15 111111111111111000011111111111111111111111111111110001100011100111
12:35:15 111111111111111110000111111111111111111111111111000011000111000111
12:35:15 111111111111111111100000111111111111111111111111001110011110001111
12:35:15 111111111111111111111100001111111111111111111111111100111100011111
12:35:15 111111111111111111111111000001111111111111111111111001111000111111
12:35:15 111111111111111111111111111000001111111111111111100011100001111111
12:35:15 111111111111111111111111111111000000000000000000000000000111111111
12:35:15 111111111111111111111111111111111100000000000010000000011111111111
12:35:15 111111111111111111111111111111111111111111111110011111111111111111
12:35:15 111111111111111111111111111111111111111111110000011111111111111111
12:35:16 111111111111111111111111111111111111111000000011111111111111111111
12:35:16 start: 1/38
12:35:16 end:   30/15
12:35:16 width/height 66/57
12:35:16 
12:35:23 result:
12:35:24 1/38  2 - вверх-вправо
12:35:24 2/37  1 - вверх
12:35:24 2/36  1 - вверх
12:35:24 2/35  1 - вверх
12:35:24 2/34  1 - вверх
12:35:24 2/33  1 - вверх
12:35:24 2/32  1 - вверх
12:35:24 2/31  1 - вверх
12:35:24 2/30  8 - вверх-влево
12:35:24 1/29  8 - вверх-влево
12:35:24 0/28  1 - вверх
12:35:24 0/27  1 - вверх
12:35:24 0/26  2 - вверх-вправо
12:35:24 1/25  2 - вверх-вправо
12:35:24 2/24  3 - вправо
12:35:24 3/24  3 - вправо
12:35:24 4/24  3 - вправо
12:35:24 5/24  2 - вверх-вправо
12:35:24 6/23  2 - вверх-вправо
12:35:24 7/22  2 - вверх-вправо
12:35:24 8/21  2 - вверх-вправо
12:35:24 9/20  3 - вправо
12:35:24 10/20  3 - вправо
12:35:24 11/20  3 - вправо
12:35:24 12/20  3 - вправо
12:35:24 13/20  3 - вправо
12:35:24 14/20  3 - вправо
12:35:24 15/20  3 - вправо
12:35:24 16/20  3 - вправо
12:35:24 17/20  3 - вправо
12:35:24 18/20  2 - вверх-вправо
12:35:24 19/19  1 - вверх
12:35:24 19/18  2 - вверх-вправо
12:35:24 20/17  2 - вверх-вправо
12:35:24 21/16  2 - вверх-вправо
12:35:24 22/15  3 - вправо
12:35:24 23/15  3 - вправо
12:35:24 24/15  3 - вправо
12:35:24 25/15  3 - вправо
12:35:24 26/15  3 - вправо
12:35:24 27/15  3 - вправо
12:35:24 28/15  3 - вправо
12:35:24 29/15  3 - вправо
12:35:24 ===============  конец расчёта  ===============
12:35:24 расчёт Сlickermann занял: 8489 мс
12:35:24 0:0:8.489
12:35:24  [/spoiler]

второй тест - максимальный
диагониль + не обходить углы: 17 мин   2,361 сек     (этот вариант ты делал)
без диагонилей:                           8 мин 20,665 сек
[spoiler]

Code: [Select]

12:15:40 --- читаем карту ---
12:15:40 111111111111111111111111111111111111100000000000111111111111111111
12:15:40 111111111111111111000000000000000000000011111000001111111111111111
12:15:40 111111111111111110000111111111111111111111111111000001111111111111
12:15:40 111111111111111100111111111111111111111111111111111000111111111111
12:15:40 111111111111111100111111111111111000000000000001111110001111111111
12:15:40 111111111111111110010000000000000000011111111000011111000111111111
12:15:40 111111111111111111000001111111111111111111111000000111100011111111
12:15:40 111111111111111111111111111111111100000000000001100011110011111111
12:15:40 111111111111111111110000000000000000000000000001110001111001111111
12:15:40 111111111111111000000000111111111111111111111000011100111100111111
12:15:40 111111111111000001111111111111110001111000011110001110011100111111
12:15:40 111111111110001111111100000000000000000000000111000110001110011111
12:15:40 111111111110011111000000001111111100000111110001100011000110001111
12:15:40 111111111100110000001111111111111100111111111001110011100111001111
12:15:40 111111111001100011111111000000011100111111111100111001110011100111
12:15:40 111111110000001111110000000000000000000011111110011000110011100111
12:15:40 111111100000111111100001111111111111000000001110011100111001100111
12:15:40 111111100111111111100111111111111111111110000111001100011000110011
12:15:40 111111001111111111101111111111111111111111110011001110011100110011
12:15:40 111111001111111111101111111111111111111111110011100110001110010011
12:15:40 111111001000000000001111111111111111111111111000100111001110010011
12:15:40 111111000000000011001111111111111111111111111100110111000111001011
12:15:40 111111000011111111001111111111111111111111111110110011100111001011
12:15:40 111111000111111111001111111111111111111111111110010011100111100011
12:15:40 100000001111111111011111111111111111111111111110111000000111100011
12:15:40 001100011111111111011111111111111111111111111110111000010111000000
12:15:40 011100000111111111011111111111111111111111111100111101110011001100
12:15:40 010000000000001111011111111111111111111111111100111101110011001100
12:15:40 011110011110000010011111111111111111111111111001111001110011001110
12:15:40 001110011111110000011111111111111111111111110001111001110011001110
12:15:40 100111001111111100011111111111111111111111100011111001110011101110
12:15:40 100111000111111100111111111111111111111111100111111001110011101110
12:15:40 110111100111111100111111111111111111111111001111111001110011101110
12:15:40 110111110011111100000000000111111111111110011111111001110011101115
12:15:40 110111111001111100000011100011111111111100011111111001110011001110
12:15:40 110111111000111100111111110011111111111100111111111001110011001110
12:15:40 110111111100001111111111111001111111111001111111111001110011001110
12:15:40 100111111111000111111111111000111111110011111111111011110111001110
12:15:40 140111111111000011111111111100000111100111111111111011110111001110
12:15:40 111111111110010001111111111111000000001111111111110011100111011100
12:15:40 111111111110011000011111111111111110011111111111110011100111011100
12:15:40 111111111111001100000000111111111111111111111111100111001111011100
12:15:40 111111111111001111111000000011111111111111111110001111001110011001
12:15:40 111111111111001111111111110000011111111111110000011110011100011001
12:15:40 111111111000001111111111111110000001111110000001111100011000110011
12:15:40 111111111000000001111111111111110000000000001111111000110001110011
12:15:40 111111111111111000011111111111111111111111111111110001100011100111
12:15:40 111111111111111110000111111111111111111111111111000011000111000111
12:15:40 111111111111111111100000111111111111111111111111001110011110001111
12:15:40 111111111111111111111100001111111111111111111111111100111100011111
12:15:40 111111111111111111111111000001111111111111111111111001111000111111
12:15:40 111111111111111111111111111000001111111111111111100011100001111111
12:15:40 111111111111111111111111111111000000000000000000000000000111111111
12:15:40 111111111111111111111111111111111100000000000010000000011111111111
12:15:40 111111111111111111111111111111111111111111111110011111111111111111
12:15:40 111111111111111111111111111111111111111111110000011111111111111111
12:15:40 111111111111111111111111111111111111111000000011111111111111111111
12:15:40 start: 1/38
12:15:40 end:   65/33
12:15:40 width/height 66/57
12:15:40 
12:32:20 result:
12:32:42 1/38  2 - вверх-вправо
12:32:42 2/37  1 - вверх
12:32:42 2/36  1 - вверх
12:32:42 2/35  1 - вверх
12:32:42 2/34  1 - вверх
12:32:42 2/33  1 - вверх
12:32:42 2/32  1 - вверх
12:32:42 2/31  8 - вверх-влево
12:32:42 1/30  1 - вверх
12:32:42 1/29  7 - влево
12:32:42 0/29  1 - вверх
12:32:42 0/28  1 - вверх
12:32:42 0/27  1 - вверх
12:32:42 0/26  1 - вверх
12:32:42 0/25  3 - вправо
12:32:42 1/25  1 - вверх
12:32:42 1/24  3 - вправо
12:32:42 2/24  3 - вправо
12:32:42 3/24  3 - вправо
12:32:42 4/24  4 - вних-вправо
12:32:42 5/25  4 - вних-вправо
12:32:42 6/26  5 - вниз
12:32:42 6/27  5 - вниз
12:32:42 6/28  5 - вниз
12:32:42 6/29  5 - вниз
12:32:42 6/30  4 - вних-вправо
12:32:42 7/31  4 - вних-вправо
12:32:42 8/32  5 - вниз
12:32:42 8/33  3 - вправо
12:32:42 9/33  5 - вниз
12:32:42 9/34  4 - вних-вправо
12:32:42 10/35  4 - вних-вправо
12:32:42 11/36  3 - вправо
12:32:42 12/36  5 - вниз
12:32:42 12/37  5 - вниз
12:32:42 12/38  5 - вниз
12:32:42 12/39  5 - вниз
12:32:42 12/40  5 - вниз
12:32:42 12/41  4 - вних-вправо
12:32:42 13/42  5 - вниз
12:32:42 13/43  5 - вниз
12:32:42 13/44  5 - вниз
12:32:42 13/45  3 - вправо
12:32:42 14/45  3 - вправо
12:32:42 15/45  4 - вних-вправо
12:32:42 16/46  3 - вправо
12:32:42 17/46  4 - вних-вправо
12:32:42 18/47  3 - вправо
12:32:42 19/47  4 - вних-вправо
12:32:42 20/48  3 - вправо
12:32:42 21/48  3 - вправо
12:32:42 22/48  4 - вних-вправо
12:32:42 23/49  3 - вправо
12:32:42 24/49  4 - вних-вправо
12:32:42 25/50  3 - вправо
12:32:42 26/50  3 - вправо
12:32:42 27/50  4 - вних-вправо
12:32:42 28/51  3 - вправо
12:32:42 29/51  3 - вправо
12:32:42 30/51  4 - вних-вправо
12:32:42 31/52  3 - вправо
12:32:42 32/52  3 - вправо
12:32:42 33/52  3 - вправо
12:32:42 34/52  3 - вправо
12:32:42 35/52  3 - вправо
12:32:42 36/52  3 - вправо
12:32:42 37/52  3 - вправо
12:32:42 38/52  3 - вправо
12:32:42 39/52  3 - вправо
12:32:42 40/52  3 - вправо
12:32:42 41/52  3 - вправо
12:32:42 42/52  3 - вправо
12:32:42 43/52  3 - вправо
12:32:42 44/52  3 - вправо
12:32:42 45/52  3 - вправо
12:32:42 46/52  3 - вправо
12:32:42 47/52  3 - вправо
12:32:42 48/52  3 - вправо
12:32:42 49/52  3 - вправо
12:32:42 50/52  3 - вправо
12:32:42 51/52  3 - вправо
12:32:42 52/52  3 - вправо
12:32:42 53/52  3 - вправо
12:32:42 54/52  3 - вправо
12:32:42 55/52  2 - вверх-вправо
12:32:42 56/51  3 - вправо
12:32:42 57/51  2 - вверх-вправо
12:32:42 58/50  2 - вверх-вправо
12:32:42 59/49  2 - вверх-вправо
12:32:42 60/48  2 - вверх-вправо
12:32:42 61/47  2 - вверх-вправо
12:32:42 62/46  1 - вверх
12:32:42 62/45  2 - вверх-вправо
12:32:42 63/44  1 - вверх
12:32:42 63/43  2 - вверх-вправо
12:32:42 64/42  1 - вверх
12:32:42 64/41  2 - вверх-вправо
12:32:42 65/40  1 - вверх
12:32:42 65/39  1 - вверх
12:32:42 65/38  1 - вверх
12:32:42 65/37  1 - вверх
12:32:42 65/36  1 - вверх
12:32:42 65/35  1 - вверх
12:32:42 65/34  1 - вверх
12:32:42 ===============  конец расчёта  ===============
12:32:42 расчёт Сlickermann занял: 1022361 мс
12:32:42 0:17:2.361
12:32:42 
[/spoiler]

Это что касается первоначального скрипта с расчётом только кликером. Там же два варианта: самим кликером и сторонней программой. Сторонней быстрей.
Аааа, я наверно не выкладывал этот вариант. 
Я тогда ещё глянул, что приемлемо по времени только на небольших полях и сразу взялся за симбиоз, вынес расчёт самого алгоритма в другую программу.

Расчёт не самим кликером

первый тест:
диагониль + обходить углы:      0,428 сек
диагониль + не обходить углы: 0,326 сек
без диагонилей:                         0,323 сек

второй тест:
диагониль + обходить углы:      4,006 сек
диагониль + не обходить углы: 3,886 сек
без диагонилей:                         1,949 сек

[spoiler]

Code: [Select]

12:54:42 ===============  конец расчёта  ===============
12:54:42 расчёт AutoIt занял: 4006 мс
12:54:42 0:0:4.006
12:54:42 

12:55:45 ===============  конец расчёта  ===============
12:55:45 расчёт AutoIt занял: 3886 мс
12:55:45 0:0:3.886
12:55:45 

12:56:22 start: 1/38
12:56:22 end:   65/33
12:56:22 width/height 66/57
12:56:22 
12:56:24 ===============  конец расчёта  ===============
12:56:24 расчёт AutoIt занял: 1949 мс
12:56:24 0:0:1.949
12:56:24  [/spoiler]

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

Расчёт не кликером быстрей от x18 раз на простых случаях, до х256 раз на сложных. Вот почему я просил скорости кликеру 

И как раз для таких случаев я делал задание точек старта-финиша не в карте, а отдельно. Карта картой, точки -сами даём. Это так-же может ускорить, не нужно будет на карте искать старт/финиш.

P.S. ещё глупая идея для твоего случая... Если даже этот расчёт покажется медленным  именно во время игры, то 25х25 = 625 путей можно просчитать заранее и сохранить в файл. Это не записывать 625, а всего лишь один раз потратить 650 секунд чистого времени - 10 мин.
Но думаю это будет не нужно.
Во вложении скрипт с твоими примерами.

И да, карту кликером во втором случае тоже можно не читать и если старт/финиш задаются отдельно.

P.P.S. И большие карты целесообразно делить на меньшие. Так в основном и делают если можно. Делят на локации/долины/города/здания/этажи/комнаты...  и т.д.
Тогда расчёт сокращается в разы. Например сначала расчёт по карте здания - пути между комнатами. При вхождении в комнату - расчёт обхода мебели/планировки по карте комнаты. Это намного быстрей, чем считать по одной детальной глобальной карте.

[dramster]

 
 спасибо за ответ. действительно, с помощью сторонней проги результат готов за секунды. да, комп немного уже устарел, но результат "диагониль + не обходить углы: 5.94 сек" во втором, максимальном тесте, вполне приемлем на деле. будет время, испытаю  в игре.

 спасибо еще раз. будет чем занять себя на досуге.
 

[Луций]

автору плюс за проделанную работу, есть еще одна интересная задача = генерация рандомных лабиринтов, интересен сам алгоритм реализации автором, пишу это на си в данный момент