Что мы имеем:
1) Карта с кружками которую ты мне прислал.
Исходный мир
2) Нарисованная мною карта содержащая 3 вариации твоего мира по сути своей каждый из которых является точной копией твоего мира.
3) Жестко заданное условие что если мы перемещаемся в локацию находящуюся дальше чем ближайшие соседствующие локации, мы прежде чем попасть в нужную, пройдем еще Nное количество локаций.
Что нам надо:
Найти путь из пункта А в пункт Б. Полученный путь должен содержать в себе все промежуточные вейпоинты которые встречаются на пути.
Разметка поля (индексирование). В зависимости от того как мы построим нашу логику текущего алгоритма, мы можем индексировать клетки возрастающими числами или уменьшающимися. Если мы индексируем от меньшего к большему то в полученный результат нам придется "переворачивать" ибо в конце мы получим путь не от старта к финишу а от финиша к старту, или же нам придется стартом обозначать пункт куда мы хотим прийти а финишем путь откудова мы начинаем путь.
Или мы используем индексацию от большего числа (старта) к меньшему (финиш) в таком случае пройдя от старта до финишам нам просто надо будет составить путь переходя в ближайшую ячейку хранящую наименьшее значение.
В связи с тем что у нас очень маленький мир я выбрал индексацию с 1000 к 0, тоесть наш бот сможет составить путь длинной не более в 1000 шагов.
Итак, помня как работает волновой алгоритм из этой темы: http://autoit-script.ru/index.php?topic=4375.0
Мы знаем что он идет вширь и просматривает все считаемые возможными для прохождения ячейки до тех пор пока не найдет финиш. Внеся небольшие изменения в код предложенный в вышеуказанной теме, мы сможем индексировать "ключевые вейпоинты" на пути нашего бота.
Итак, нам надо попасть из пункта 1 в пункт 5.
Поиск идет из пункта 1 в пункт 5.
У ячейки 1 будет индекс 1000
1) Алгоритм идет в ширь, видит проходимую клетку но не являющуюся вейпоинтом, индексирует ее числом равным числу той клетки из которой пришел поиск -1 (в нашем случае 1000-1=999)
2 )Идет дальше видит клетку 2 являющуюся проходимой и одновременно вейпоинтом но не целевой точкой. Индексируем эту клетку при этом оставляя метку вейпоинта. (поиск пришел из клетки с индексом 999 => индекс текущей клетки будет равен 998
3) Идем дальше видим 2 проходимых клетки не являющиеся вейпоинтами, индексируем их (Не упускаем из внимание что независимо от того сколько проходимых клеток поиск нашел рядом с той откудова пришел, индекс каждой новой найденной клетки = индекс предыдущей -1, то есть клетка выше 2 так же как и клетка правее 2 будет иметь индекс 998-1=997
4) Идем дальше, видим снова 2 клетки 3 и 6, обе являются вейпоинтами но не являются финишем, индексируем их и оставляем метки вейпоинта. (клетка 3 будет иметь индекс 996, клетка 6 будет так же иметь индекс 996)
Вейпоинт 3 оказался тупиковым, поиск продолжается с вейпоинта 6
5) Идем дальше, видим 3 клетки, все проходимые и ни одна не является вейпоинтом, индексируем (клетка выше 6 будет иметь индекс 995, так же как и клетка правее и ниже клетки 6)
6) Идем дальше, видим 3 клетки, все вейпоинты, ни одна не финишь, делаем тоже что и раньше. (индексы клетки 4 = 8 = 7 = 994
Вейпоинты 7 и 8 оказались тупиковыми, продолжаем поиск с 4-й.
7) видим проходимую клетку не вейпоинт, индексируем (993)
8) Видим клетку, она является вейпоинтом и при этом финишем.
Скрипт проиндексировал путь от старта до финиша. Теперь стартом поиска пути становится клетка 5.
Алгоритм заносит в сферическую переменную "Путь" имя локации: "5"
старт: Ищет среди прилегающих ячеек ячейку с наибольшим индексом (в нашем случае 993) переходим в нее и ищем дальше
993: видим ячейку 994, переходим в нее, т.к. она еще и вейпоинт в переменную "Путь" добавляем им локации "4", ищем дальше
994: видим ячейку с индексом 995, переходим в нее, она не вейпоинт, ищем дальше
995: находим ячейку с индексом 996, переходим, видим что вейпоинт, добавляем в переменную "Путь" имя локации "6", продолжаем осматривать ближайшие ячейки.
996: Мы видим что вокруг ячейки 6 есть 4 ячейки куда можно пойти, но мы помним что нам надо идти в ячейку с наибольшим значением, ячейка выше 6 = 995, ячейка справа 6 = 995, ячейка снизу 6 = 995, ячейка слева 6 = 997. Вот туда то нам и надо, переходим
...
видим ячейку 2 с индексом 998, заносим в переменную "путь" имя текущей локации "2"
...
видим ячейку 1, она является стартом, заносим в переменную "путь" имя текущей локации "1", возвращаем переменную "путь" со значением найденного пути = 12645
Как то так, я не программист, понятнее объяснить не могу
Описанные выше шаги будут справедливы для всех миров A B и С, единственное отличие C от A и B в том что в C будет проделано между вейпоинтами больше промежуточных шагов.
P.S. жду мегатонну репы, я в место того чтобы ходить за пивом рисовал эту карту
