Пилю A*, 2D и 3D Tile Map Editor

[Salamandr]

раньше использовали IME (вроде такое название команд) прерывание в Ассемблере, ещё за долго появления многоядерных процессоров. Это давала эффект параллельности, да чё далеко ходить, WIndows так работал. Но на самом деле, это было поступательно.
не важно сколько процессоров или потоков, важен алгоритм )
А спросил потому что мой, работает по "автоматному" принципу. Каждый раз он считает лишь 1 клетку и выходит, и тем самым не вешает юньку. Общий процесс поиска, по времени, естественно больше. А время от точки до точки, я думаю равны с твоими показателями (у меня более чёткое и специфичное поле из-за игры). Кроме того объект отправляет в путь гораздо раньше, чем завершит прокладку пути, в данном моём случае, это допустимо. У тебя же общий случай, тебе гораздо сложнее )

[bwolf88]

А спросил потому что мой, работает по "автоматному" принципу. Каждый раз он считает лишь 1 клетку и выходит, и тем самым не вешает юньку.

Не совсем понял на счет автоматного расчета. Точнее ты же описывал его, но как я понял там был просчет не одной клетки, а определнного количества. А тут идет просчет одной клетки, функция прерывается, (возможно бот начинает путь) затем функция поиска запускается заново, новая клетка пробегает по своим соседям и функция прерывается снова ? А как тогда записывается правильный путь? И при таком раскладе он может быть не совсем правльным. Попробуй тест с прохождением большого П-образного препятствия, когда конечная точка за верхней планкой (чтобы бот точки внутри "буквы" просчитывал) и если не трудно можешь видео записать , очень интересно посмотреть на другую реализацию.

[Salamandr]

Скрытый текст: показать

phpBB [video]

мой алгоритм сейчас, не обойдет P (честно говоря пока не понимаю почему не обходит), надо дописывать через: "Алгоритм последовательных приближений при поиске в глубину (IDDFS)" (именно эту статью я нашел после "звезды"*) http://pmg.org.ru/ai/stout.htm (тут много разных)
на прохождение пути самим ботом уходит прилично времени (это, и так задумано, и так должно быть) Поэтому как только, поиск пути находит изменение направления движения в поиске пути, уже есть смысл двигаться.
кроме того, надо расширить мой алгоритм немного.
у "звезды" есть хороший такой финт

уже отсекает неверный путь, ещё в процессе вычислений. по пути 6,12,18,19 мы уже никогда не пойдем, он УЖЕ длиннее (жаль что это не подходит для моего случая. ведь диагонали я использовать не могу)

суть моего алгоритма состоит в том, что, каждому направлению дается вес. если объект левее, то на точку влево +1 при выборе точки. если ниже, то +1 И к низу и т.д. То есть всегда два направления положительны и два отрицательны (запасные, в случае тупика). Он также не ходит там, где уже побывал. Он естественно не идеален, кроме того, при встрече с объектом лучше запускать два луча в разные стороны, а у меня только один.

[bwolf88]

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

уже отсекает неверный путь, ещё в процессе вычислений. по пути 6,12,18,19 мы уже никогда не пойдем, он УЖЕ длиннее (жаль что это не подходит для моего случая. ведь диагонали я использовать не могу)

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

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

А вообще свой поиск пути тоже интересно, я как то пытался запилить обход любых препятствий с помощью raycast_ов - небольшие нормально обходили, на больших тупить начинали . Зато не было привязке к сеткам и карте.

добавлено: вот похожий алгоритм обхода пилил как в первой статье. На больших препятствиях или в лабиринте - полный тупик :):).

И еще вопрос: а почему бот при первом передвижении на непроходимую клетку наступает ?

[Salamandr]

И еще вопрос: а почему бот при первом передвижении на непроходимую клетку наступает ?

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

[bwolf88]

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

Статья написана в 1997 году. В то время каждый килобайт был как драгоценный алмаз, скорость процессоров далеко на ГГц. и алгоритмы разрабатывали соответствующие. Это сейчас 100 метров туда, 200 метров сюда и как то не напрягаешься.
А вообще, я эту плюшку возьму на вооружение в два раза более быстрый перебор.

[lwe]

Хмм я спокойно использую потоки(не корутины) - создаю объекты просто которые содержат: проходимость, цена, угол, позиция2д - для потоков это подходит - нет юнити объектов

[bwolf88]

Хмм я спокойно использую потоки(не корутины) - создаю объекты просто которые содержат: проходимость, цена, угол, позиция2д - для потоков это подходит - нет юнити объектов

Если угол и позиция в int, а не векторах, то подходит. А если нет, то будет ругаться.

[bwolf88]

Сегодня попытался ускорить алгоритм, провозился с двусвязными списками, чтобы вообще убрать все переборы и ничего не добился, точнее по скорости в 3 раза быстрее, но путь не совсем красивый. Потом на бумажке все расписал, по логике не получается сделать умную вставку в список, чтобы не приходилось прогонять его на поиск минимального значения, как не пытался. Так что на сегодняшний день это почти предел моей оптимизации. Пока что забил с этим, зато сделал первичную поддержку юнитов не единичных размеров. Размеры юнита задаются изначально обычными переменными и исходя и них автоматически определяется проходимость коридора. На видео первичный тест: кроме юнитов единичных размеров есть 2х1, 2х2, 3х3. У каждого получается своя зона проходимости, которая считается автоматом при построении пути. На производительности это вроди не очень сильно сказывается. ТАк что теперь можно делать игру с гигантскими юнитами
Это первый пробный тест, еще не до конца реализовано определение динамических препятствий. На видео бот 3х3 при появлении препятствия немного проходит в него, затем перестраивает путь как нужно.

PS: внизу глюк, из за записывающей проги.
Добавлено: сейчас еще раз посмотрел, для юнитов с одной единичной координатой (2х1 или 1х2 например) почему то не правильно коридор строит. Буду разбираться.
Добавлено: все, теперь все работает, как обычно моя невнимательность, с 3 утра сижу .

[lwe]

Вычисляете путь в апдейте?
Вы же говорили что используете корутину.

[bwolf88]

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

[bwolf88]

Переделываю все с нуля . Первый вариант был не 3Д - не 2Д. Точнее он сделан под 2Д, но вторая ось Z вместо Y, поэтому решил переделать и немного облагородить по ходу. Будет 2 варианта, чисто под 2Д с правильной ориентаций и полный 3Д (Хотя с последним пока додумываю логику MapEditor)

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

Получилось что то больше похожее на урезанный кривой паинт . Никогда не думал что смогу сделать рисовалку, тем более текстурами. Если быстро водить мышкой - не успевает среагировать, поскольку куча обновляемой по клетке информации происходит. На самом деле никто так карту не заполняет, если заполнять приблизив хотя бы до масштаба карты в Героях 3, то провалов не будет .
В планах сделать MapEditor по типу Героев 3, очень уж он мне нравится, в свое время много часов провел составляя на нем свои карты и сценарии .

А пока, вот что получилось. На видео косяк, когда достигаешь границы - закрашивал на другом конце, это из за записи, при выключенной записи такого нет.


Чуть позже первую вариацию 2Д А* и выложу видео с заполнением карты и пробным поиском по ней.

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

[lol]

А агенты будут обходить друг друга?

[bwolf88]

А агенты будут обходить друг друга?

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

[bwolf88]

Переименовал я немного тему, поскольку тут же, чтобы не плодить, буду делать редактор 2Д карт.
Сейчас в частности занялся изготовлением тайлов - такая , поюзал немного редактор героев 3, только уже с точки зрения конструкции, а не игры - это ж сколько рисовать придется. Я посчитал на каждый тип земли нужно 56 кусков разносторонних кусков клепать, это если делать через переход 2 видов нейтральной земли. Если через один, то всего 14. А если делать смешивание каждой с каждой - это никакого атласа не хватит. Поэтому буду делать либо через 2 либо через 1 нейтральную землю. Как нарисую и заскриптую запишу видео чего получилось.