2844

Подписчиков:

Постов:

песочница2844geekdevblogadminguidegamedevИгрыреактора

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

,песочница,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,gamedev,Игры,реактора

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

Карта была разбита на "слои". Точнее на этапы генерации. Террейн был вынесен в отдельный лист, где он лежит как источник данных и никому не мешает. Юниты (B и U) были вынесены в отдельный лист Units, а ресурсы в отдельный лист Resources. Теперь карта из себя представляет не один забитый данными и артефактами оставшимся от расчёта пути, а несколько отдельных источников данных, и финальный результат наложенный на лист GUI. Сначала берутся данные о террейне, на них исходя из данных во вкладе Units накладываются имеющиеся там юниты, и поверх имеющегося результата накладываются ещё и ресурсы. После уже готовый результат размещается на вкладе GUI и уже от этого пляшет алгоритм поиска пути, повторно считывающий и модифицирующий карту уже своими данными и пвторно её перерисовывающий.

Как оказалось ранее реализованный алгоритм поиска пути, удалось перестроить с поиска пути от U до Res, на поиск пути от U до B, всего парой правок. Это потенциально облегчит доведение элементов работы с перемещением и карты до ума. Хотя как правильно заметили в комментариях ранее, я очень сильно перемудрил, и мне это перемещение вообще было не нужно, для проверки концепта можно было бы убрать лабирин и просто двигать юнит до ресурса по прямой, без лишних расчётов.

16 15 14 13 12
16 15 14 13 12
31 31 311 В 16 15 14 13 12
30 30 * 30 30 16 15 14 13 12
29 * 29 29 30 16 15 14 13 12
* 28 28
* 27 27 27 27 27 15 14 13 12 *
* 26 26 26 26 26 15 14 13 * 11
* 25 25 25 25 25 15 14 * 11
25 * 24 24 24 24 45 * 14 11
25 24 * 23

Строим путь от U до B

vv w vv w vv vv vv w VV w
9 8 7
9 8 * I
9 * 8
Res

w w vv vv w vv vv w w w vv vv w w w w w w vv w w w w vv w 24
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
vv vv w vv
6 6 6 w
5 5 5 vv
4 4 4 vv
3 3 3 vv
if 2 2 vv
I 2 * 1 vv
2 и vv
2 1 1

Исправив всего пару строк, строим путь от U до Res

Хоть пока что не очень гибко и тем более не динамично, но таки по крайней мере оно уже работает, хоть пока и кривенько :)

AdminGuide

песочница2844devblogadminguideигры реакторавидео

DEVVLOG 001. SCP 2844. Идея игры по SCP. Пытаемся вкатиться в геймдев с нуля.

Видео к посту https://joyreactor.cc/post/5775652

AdminGuide

песочница2844geekdevblogadminguidegamedevИгрыигры реактора

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

После получения обратной связи и анализа имеющегося плана, было решено пока остановиться и сосредоточиться на реализации такого процесса как “поиск, добыча и переработка ресурсов с развитием оборудования участвующего в процессе”. Это будет эдаким корлупом, по крайней мере на\ближайшее время. Всем большое спсибо за советы! В вопросах реализации того, что не знаешь особо как делать и что должно получиться в итоге, обратная связь бесценна!

Из новостей "разработки", реализован топорный и немного кривенький волновой алгоритм поиска пути, который не удалось реализовать на момент написания второго девблога. Заняло это 146 строк статичного говнокода, который наверное устарел ещё в процессе реализации алгоритма.

Поле карты стало чуть-чуть красивее благодаря условному форматированию :).

Алгоритм теперь исправно распространяет волну по карте в поисках захардкоженной цели.

1 1 1 2 3 4 5|
'I U i 2 3 4 5
1 1 1 2 3 4 5
2 2 2 2 3 4 5
3 3 3 3 3 4 5
4 4 4 4 4 4 5
5 5 5 5 5 5 5
6 6 6 6 6 6 6
7 7 7 7 7 7 7
8 8 8 8 8 8 8
9 9 9 9 9 9 9
10 10 10 10 10 10 10
11 11 11 11 11 11 11
12 12 12 12 12 12 12
13 13 »I ■ I 13 13 13
14 14 14 14 14 14 14
15 15 15 15 15 15 15

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

1 1 1 2 3 4 5
1 U| 1 2 3 4 5
1 1c 1 2 3 4 5
2 * 2 2 3 4 5
3 1c 3 3 3 4 5
4 1c 4 4 4 4 5
5 1c 5 5 5 5 5
6 1c 6 6 6 6 6
7 1c 7 7 7 7 7
8 1c 8 8 8 8 8
9 1c 9 9 9 9 9
10 1c 10 10 10 10 10
11 1c 11 11 11 11 11
12 1C 12 12 12 12 12
13 1c 13 ■ I 13 13 13
14 1c 14 14 14 14 14
15 1c 15 15 15

В ближайших планах допиливать алгоритм, а также поработать над автоматической генерацией карты по хранящимся независимо от самой карты вводным данным. Потому что стало очевидно что несмотря на то что алгоритм поиска пути как-то да работает, и визуально результат даже виден, использовать его как часть игры невозможно ввиду того что он пока не может работать достаточно гибко для того чтобы принимать различные данные, отличные от тех что в него захардкожены. А для этого надо патчить карту :)

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

AdminGuide

2844geekdevblogadminguideпесочницаgamedevИгры

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

,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
В с D Е F G H i J к L M N 0 P Q R s T U V

U

На данный момент мне уже удалось чуть-чуть это поле оживить. Текущая цель - научить "игру" находить путь между точками А и 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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
С D Е F G H i J K L M N 0 P Q R s T U V w X Y Z
0
I □

2
3

Тоесть в случае, если необходимо найти путь между U находящимся в map[1][1] до Res, находящимся в map[13][17], для начала, нам необходимо последовательно распространить волну вычислений от U до Res.

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

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

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

q 0
и q Res 1
q 2
q q q 3
4
q 5
q 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

q - Это стена, куда нельзя сделать шаг

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

1 1 q 0
1 и q Res 1
1 1 q 2
q q q 3
4
q 5
q 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

Следующим шагом мы должны просканировать всё поле на предмет наличия там следов первого шага. И проверить все на наличие там Res и пустые клетки вокруг каждой единицы, и те куда можно сделать шаг, отметить цифрой 2, так как это будет уже второй шаг. И так мы должны сканировать каждый новый шаг, находя цифры предыдущего шага, проверять возде них все соседние пустые клетки куда можно сделать шаг и вписывать туда число текущего шага.

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

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

1 1 q 0
1 U q Res 1
1 1 q 2
2 2 q q q 3
4
q 5
q 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

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

1 1 q 0
1 U q Res 1
1 1 q 2
2 2 q q q 3
3 3 3 4
q 5
q 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

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

1 1 q 0
1 U q Res 1
1 1 q 2
2 2 q q q 3
3 3 3 4 4
4 4 4 q 5
q 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

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

1 1 q 0
1 U q Res 1
1 1 q 2
2 2 q q q 3
3 3 3 4 5 4
4 4 4 q 5 5
5 5 5 q 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

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

1 1 q 0
1 U q Res 1
1 1 q 2
2 2 q q q 6 3
3 3 3 4 5 6 4
4 4 4 q 5 6 5
5 5 5 q 6 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

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

1 1 q 0
1 U q Res 1
1 1 q 7 7 7 2
2 2 q q q 6 7 3
3 3 3 4 5 6 7 4
4 4 4 q 5 6 7 5
5 5 5 q 6 7 6
0 1 2 3 4 5 6,2844,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,devblog,adminguide,песочница,gamedev,Игры

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

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

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

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

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

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