Автокликер Clickermann :: Форум
Основной раздел => Использование => Topic started by: Vint on May 15, 2015, 12:23:27 PM
-
Очередная интересная задача до которой дошли руки.
Решил реализовать известный алгоритм поиска пути A*. Принципы и описание брал здесь (http://www.policyalmanac.org/games/aStarTutorial_rus.htm).
Упоминание началось в темах:
http://crapware.aidf.org/forum/index.php?topic=1837.0
http://crapware.aidf.org/forum/index.php?topic=1878.0
Хотелось посмотреть как со скоростью на Clickermann, реально ли на нём использовать, ну и заодно неплохая тренировка создания кода. Ограничился как в примере полем разбитым на квадраты. Произвольные графы пока не делал, с этим стоит заморачиваться, если нужно, только под конкретную задачу когда такая появится.
Определился со способом хранения карты, а так же рабочей инфы: открытого и закрытого списков, стоимости F (G и H решил расчитывать по надобности на лету).
Для удобства создания сделал себе шаблончик как в источнике
(https://i109.fastpic.ru/thumb/2019/0301/db/c1f25d877f93e1be81bedde9a3711edb.jpeg) (https://fastpic.ru/view/109/2019/0301/c1f25d877f93e1be81bedde9a3711edb.png.html)
Код под спойлером и во вложении
[spoiler]#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]
Итоги.
Опробовал на трёх небольших картах (во вложении).
Самая маленькая из разработки вычисляется меньше секунды
(https://i110.fastpic.ru/thumb/2019/0301/3b/304fc942a20e9cb63d6de1ecbb49ae3b.jpeg) (https://fastpic.ru/view/110/2019/0301/304fc942a20e9cb63d6de1ecbb49ae3b.png.html)
Следующая побольше. Здесь глубокая засада-карман из которого алгоритму долго выбираться. На рабочем компе считалось аж 9 минут :o
(https://i109.fastpic.ru/thumb/2019/0301/7b/dc04556fa44b3fb3f521d8d3f9d4507b.jpeg) (https://fastpic.ru/view/109/2019/0301/dc04556fa44b3fb3f521d8d3f9d4507b.png.html)
И последняя, размером как вторая, но с лабиринтом. Здесь решилось за 1 мин. 20 сек. В принципе неплохо. Пришлось скрин разбить на 2, решение длинное.
(https://i109.fastpic.ru/thumb/2019/0301/32/871b998a87d6eaf78dd00186e70c9c32.jpeg) (https://fastpic.ru/view/109/2019/0301/871b998a87d6eaf78dd00186e70c9c32.png.html)
(https://i110.fastpic.ru/thumb/2019/0301/ee/de1b061aebe578c5bb5f1f90bf8546ee.jpeg) (https://fastpic.ru/view/110/2019/0301/de1b061aebe578c5bb5f1f90bf8546ee.png.html)
Вот и всё.
Учитесь и развивайтесь.
Интересно теперь повторить с улучшениями на другой проге, более скоростной. Уже начал.
-
Жаль что никого не заинтересовало...
Я тут наткнулся на лабиринтик и написал продолжение. Идею вводить карту руками сразу отмёл и сделал автоматизированное определение и возможность рисования пути.
Вот такое решение, правда долго зараза
(https://i109.fastpic.ru/thumb/2019/0301/ac/c65b8e64d30a7ff0229a476791b772ac.jpeg) (https://fastpic.ru/view/109/2019/0301/c65b8e64d30a7ff0229a476791b772ac.png.html)
Вот даже видео сделал:
http://youtu.be/sA_-N495Nio
А дальше уже сам нарисовал "коровку"-болота.
Прохождение без диагональных передвижений
(https://i109.fastpic.ru/thumb/2019/0301/46/f0d3ecdf304297b6d6beaa483d2cba46.jpeg) (https://fastpic.ru/view/109/2019/0301/f0d3ecdf304297b6d6beaa483d2cba46.png.html)
И с диагональными
(https://i109.fastpic.ru/thumb/2019/0301/9f/4a99a589182101086c1c297bce17179f.jpeg) (https://fastpic.ru/view/109/2019/0301/4a99a589182101086c1c297bce17179f.png.html)
-
Не совсем понимаю как делать чтобы передвигаться по лабиринту не упираясь в тены
-
Смотря что за лабиринт и чем там передвигается.
-
Лабиринт как на картинке, он всегда одинаковый, черная область это стены, в белой области находятся мобы ( всегда в разных местах )
Цель не пройти из точки А в точку Б а передвигаться по белой области не упираясь в стены, когда находит моба за стеной должен её обойти.
Мобы появляются беспорядочно, часто бывает что нужно ходить по несколько раз из конца в конец лабиринта пока всех не перебьёшь.
-
Жаль что никого не заинтересовало...
вроде как заинтересовало, сразу появилась идея создания маршрута в играх по карте из точки А в точку Б, где эти точки находятся в рандомных координатах. но както не доходили руки проверить алгоритм в деле.
задача такова. есть небольшой кусок карты. персонаж стоит в рандомном месте. появляется метка (также в рандомном месте). алгоритм должен определить ближайший маршрут. персонаж с помощью скрипта бежит по контрольным точкам, которые ранее определил "алгоритма поиска пути A" к метке, делает свое дело. появляется новая метка. бежим к ней, и так далее. вроде всё просто :D.
в принципе метки появляются в определенных местах, этих мест всего 25. есть рабочий бот который бегает до этих меток по заранее записанному маршруту в тхт, НО приходится после каждой метки бежать в стартовую точку,и далее со стартовой точки к следующей метке. а это перемещение впустую примерно в двое увеличивает время работы. да, конечно можно записать все маршруты, всех меток ко всем меткам. но таких будет 25х25=оооочень много. а "алгоритма поиска пути A" вроде как должен выдать оптимальный маршрут без каких либо лишних махинаций.
начал с того, что нарисовал карту. один кликер определял координаты персонажа с карты игры и писал в ини. второй кликер, в привязке к паинту, читал эти координаты и отрисовывал в паинте местонахождение персонажа. пробежался по всем дорогам, немного подредактировал, вышло вроде ничего
(http://i.imgur.com/Ihicbfu.png)
для примерного понимания расстояния, бегом из левого угла в правый угол этой карты(не по дороге, напрямую) занимает гдето 40-50сек.
далее, начал переводить карту в текстовый файл. оптимальное разрешение ноликов-едениц вышло 66х57, по 5 пикселей карты на один нолик или единицу (это примерно чуть меньше ширины дороги в игре), опять же слегка подредактировал, для теста.
[spoiler]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]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]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]
пока он там чтото считал, я успел покушать, повтыкал перед теликам, чуть не уснул ;D. 40 МИН !!!!!!!!!!!
это слишком. было бы мега круто если бы расчет проходил за секунды. ведь это же только кусочек карты. а у меня были планы на всю карту :D, все дороги (кроме эстакад и тоннелей) для движения уже на транспорте.
чтож очень жаль :( . хотя судя по постам выше, итог моей задачи был явным с самого начала, но всеже проверить чесались руки.
-
Так...
У тебя расчёт идёт с движением по диагонали, хотя лабиринт позволяет ходить без диагоналей.
Без диагоналей расчёт почти всегда в 2 раза быстрей. + скорость расчёта от компа зависит.
У меня результаты первого теста:
диагониль + обходить углы: 9,073 сек
диагониль + не обходить углы: 8,489 сек (этот вариант ты делал)
без диагонилей: 5,931 сек
Приложу вычисление 1 теста с настройками как у тебя (диагональ-не обходить углы)
[spoiler]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]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]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]
Так что используй второй способ и по возможности без диагоналей (если бегать углами будет быстрее и выгодней, чем потеря времени на расчёте ;D).
Расчёт не кликером быстрей от x18 раз на простых случаях, до х256 раз на сложных. Вот почему я просил скорости кликеру :( :P
И как раз для таких случаев я делал задание точек старта-финиша не в карте, а отдельно. Карта картой, точки -сами даём. Это так-же может ускорить, не нужно будет на карте искать старт/финиш.
P.S. ещё глупая идея для твоего случая... Если даже этот расчёт покажется медленным ;D именно во время игры, то 25х25 = 625 путей можно просчитать заранее и сохранить в файл. Это не записывать 625, а всего лишь один раз потратить 650 секунд чистого времени - 10 мин.
Но думаю это будет не нужно.
Во вложении скрипт с твоими примерами.
И да, карту кликером во втором случае тоже можно не читать и если старт/финиш задаются отдельно.
P.P.S. И большие карты целесообразно делить на меньшие. Так в основном и делают если можно. Делят на локации/долины/города/здания/этажи/комнаты... и т.д.
Тогда расчёт сокращается в разы. Например сначала расчёт по карте здания - пути между комнатами. При вхождении в комнату - расчёт обхода мебели/планировки по карте комнаты. Это намного быстрей, чем считать по одной детальной глобальной карте.
-
:D
спасибо за ответ. действительно, с помощью сторонней проги результат готов за секунды. да, комп немного уже устарел, но результат "диагониль + не обходить углы: 5.94 сек" во втором, максимальном тесте, вполне приемлем на деле. будет время, испытаю в игре.
спасибо еще раз. будет чем занять себя на досуге.
-
автору плюс за проделанную работу, есть еще одна интересная задача = генерация рандомных лабиринтов, интересен сам алгоритм реализации автором, пишу это на си в данный момент