games

MENcraft

Привычка

DevBlog 002. SCP 2844. Карта и перемещение юнитов. Часть 1

В прошлом посте я описал какая примерно у меня планируется тестовая карта. 25х25 поле в спредшите.

На данный момент мне уже удалось чуть-чуть это поле оживить. Текущая цель - научить "игру" находить путь между точками А и B в двумерном пространстве, с учётом препятствий. Есть много всяких разных алгоритмов поиска пути, эффективных и не очень, но на мой взгляд самым нативно понятным и доступным в реализации алгоримом является "Волновой Алгоритм Поиска Пути".

Я к несчастью самоучка, и когда я учился увы небыло никаких учебных материалов кроме находящейся в зачаточном состоянии википедии, о которой знал то далеко не каждый и сухих каких-то учебников и прочего. Цензуры кстати тоже небыло. Светлое ламповое время зачаточного интернета по карточкам и гостевых книг, даже форумы считались прям вообще редкостью и признаком ылитарности. Таких вещей как "О ГОСПАДИ КУРС ПО <подставить_любую_тему> ОНЛАЙН! СТАНЬ СПЕЦИАЛИСТОМ ВСЕГО ЗА <подставить_желаемый_срок>. БЕЗ ПРЕДОПЛАТЫ \ В КРЕДИТ \ ПЛАТИ ПОСЛЕ ТРУДОУСТРОЙСТВА \ БЕСПЛАТНО", небыло не то что и в помине, а те кто реализовал первые их варианты, вероятно ещё так же как я страдали от отсутствия каких-то материалов для обучения. А на практически любые вопросы на тематических страницах и форумах в ответ обоссывали. Потому вероятнее всего как последствие детских душевных травм, я всё стараюсь оформить как некие учебный материал или пособие. Чтобы если кто-то захочет пройти мой путь, у него были какие-то готовые подсказки, потому не обессутьте, ниже вас ждёт стена текста.

Wall of text hit you for over 9000 Holy Damage

Ну и описываю я всё так, как было бы понятно мне самому, тоесть для дибилов, с деменцией и памятью как у аквариумной рыбки.

Волновой Алгоритм Поиска Пути

Суть этого алгоритма заключается в том, что мы обозначаем откуда мы хотим найти путь и куда мы хотим попасть в рамках двумерного массива. И в случае с таблицами, нам достаточно представить игровое поле на скрине выше как двумерный массив, коим оно и является, где по оси Y у нас имеется 25 строк с номерами от 0 до 24, и в каждой строке есть 25 колонок по оси X, с номерами от 0 до 25. В виду специфики спредшитов, и отсутствия у меня желания переворачивать массив делая так называемый transpose, я везде буду использовать координаты исходя из того что в координатной паре, Y стоит на первом месте, а X на втором. Тоесть Y,X, в отличии от привычных всем X,Y. Запись 13,17 будет означать 13 по Y, 17 по X. Y - вертикальная шкала (справа), X - горизонтальная (снизу)

В случае со спредшитами, чтобы начать работать с таким массивом, нам достаточно в переменную например map, считать диапазон "A1:Y25". В этом случае мы получим массив размером от map[0][0] до map[24][24], забитый пустыми значениями, кроме следующих позиций:
Юнит с обозначением U будет находиться в map[1][1]
Ресурс с обозначением Res, будет находиться в map[13][17]
База с обозначением B, будет находиться в map[14][3]

Распространение волны от U до Res

Нулевым шагом будет сканирование всего массива данных по Y и X на предмет наличия в ячейке значения U. Как только это значение будет найдено, необходимо проверить всё в радиусе одной ячейки от U на предмет возможости совершить первый ход. Чтоо в данном случае будет проще рассмотреть на более маленьком поле, например 7х7

Пусть выдуманное поле выглядит вот так

Тогда когда мы найдём U и проскаируем все соседний ячейки куда можно сделать первый шаг и разметим их, наше поле станет выглядеть следующим образом.
Шаг 0. Из U мы считаем куда мы можем шагнуть в Шаг 1.

При этом, рассчитывая куда мы можем шагнуть возле каждой текущей проверяемой цифры, мы проверяем не только можем ли мы туда сделать шаг, а ещё нет ли случаем там нашей цели Res

Шаг 1. Из 1 мы считаем куда мы можем шагнуть в Шаг 2.

Шаг 4. Из 4 мы считаем куда мы можем шагнуть в Шаг 5.

Шаг 5. Из 5 мы считаем куда мы можем шагнуть в Шаг 6.

Шаг 6. Из 6 мы считаем куда мы можем шагнуть в Шаг 7.

Шаг 7. Из 7 мы считаем куда мы можем шагнуть в Шаг 8.

Но на этом этапе, сканируя поле сверху в низ, перебирая строки, и в каждой строке перебирая поколоночно слева направо ячейки на наличие цифры 7, чтобы рассчитать 8й шаг, мы находим первую семёрку. Относительно этой семёрки мы начинаем проверять слева сверху вправо вниз каждую соседнюю ячейку, и так получилось что прямо слева сверху этой семёрки, мы находим нашу цель Res. Дальше рассчёты мы не ведём. Волна была пущена и достигла своей цели.

Поиск пути в волне

Мы пустили волну от U и она дошла до Res. Теперь внутри этой волны нам нужно найти путь. Но если мы начнём считать путь от U, то на этапе рассчёта куда можно шагнуть из U, мы сразу же получим кучу вариантов, и многие из них будут неправильными. Потому чтобы искать путь, мы должны вести рассчёты в обратном напавлении. от Res до U. Но теперь нам будет проще.

Мы знаем координаты Res т.к. мы уже нашли Res в ходе распространения волны. Поиск маршрута мы начинаем от Res.

Шаг 7. Мы ищем вокруг Res минимальную цифру или U
Так как вокруг Res кроме 7 вообще нет никаких цифр, мы отмечаем 7 как шаг следующий шаг.

Шаг 6. Мы ищем вокруг 7 минимальную цифру или U

Шаг 5. Мы ищем вокруг 6 минимальную цифру или U

Шаг 4. Мы ищем вокруг 5 минимальную цифру или U

Шаг 3. Мы ищем вокруг 4 минимальную цифру или U

Шаг 2. Мы ищем вокруг 3 минимальную цифру или U

Шаг 1. Мы ищем вокруг 2 минимальную цифру или U

Шаг 0. Мы ищем вокруг 1 минимальную цифру или U

U найдено, на этом этапе в теории у нас есть всё необходимое для того чтобы получить маршрут от U до Res.

Но на словах всё просто, а на деле чуть-чуть не получилось. Написанный код зацикливается на 2м этапе

Продолжение следует :)