Учусь программировать. Алгоритм авторазметки или подсчет отдельных объектов на поле.
ч.5 Учусь программировать. Marching Cubes
Немного отойду от хронологии событий, все равно все темы самостоятельные, но каждая - мой небольшой шаг в сторону новых возможностей.
Написав свой первый поиск пути, я так и не решил на тот момент толком проблему, что же делать если зона поиска недоступна. Точнее решил ее частично, ограничив максимальное количество перебираемых точек, тем самым ограничив дальность такого поиска. К слову, похожая система была организована в игре Divinity original sin, потому что путь от одного конца карты в другой персонажи отказывались прокладывать напрочь, хотя алгоритм насколько я понял был похожий с моим, не знаю была ли у них реализовано раграничение игрового поля на зоны. В игре тоже были закрытые участки - например запертые дома или временно недоступные зоны :).
Теперь же поднабравшись опыта, я вновь попытался осилить процесс авторазметки игрового поля. Еще одной причиной, по которой я за него не брался изначально (кроме отсутствия знаний) - это как я думал громадные вычислительные затраты на проверку каждой клетки игрового пространства, но все оказалось не так страшно.
В понимании мне также очень хорошо помогла вот эта статья на Хабре Подсчет объектов на бинарном изображении.
В чем же преимущества такого разделения пространства на зоны применительно к поиску пути? Все очень просто, обозначая непроходимые участки как зоны отличные от той, на которой находится игровой персонаж, мы как бы говорим - "Дружище, эта место закрыто для тебя" избавляя его от тонны лишних вычислений.
Есть несколько методов подобной авторазметки: однопроходная, двухпроходная и многопроходная. Я выбрал двухпроходную - она оказалась для меня наиболее понятной и удобной. Работа этого алгоритма очень похожа на работу сканера, который есть в каждом офисе. Вы кладете лист бумаги который необходимо отсканировать и лазер проходит по листу, считывая изображение с листа сверху вниз, а затем в обратную сторону.
В статье по ссылке выше описывается такая проверка методом уголков. то есть каждый пиксель (а в случае с игровым полем - клетка игрового поля) проверяется в совокупности с соседями впереди и сверху и на основе этой проверки выстраивается первоначальное разделение поля на зоны. Но при первом проходе могут возникать так называемые двойные зоны. Затем при втором проходе происходит уточнение клеток которые соединяют эти двойные зоны и происходит их объединение - ничего сложного.
К примеру, вот в этом цикле статей про поиск пути , на основе которого я делал свой первоначальный вариант А*, описан другой метод разделения на зоны - т.н. контурный метод разделения, но он мне показался не очень удобным и не совсем понятным по расчетам, хотя возможно он быстрее.
И вот что у меня получилось в итоге. Так же я дам ссылку на Unity Asset со скриптами и проектом :).
Кстати уголковый метод проверки оказался весьма полезным и я применял его и для других целей :).
ч.7 Учусь программировать. Процедурная вода 2D. Пробую флюиды.
Немного отойду от хронологии событий, все равно все темы самостоятельные, но каждая - мой небольшой шаг в сторону новых возможностей.
Написав свой первый поиск пути, я так и не решил на тот момент толком проблему, что же делать если зона поиска недоступна. Точнее решил ее частично, ограничив максимальное количество перебираемых точек, тем самым ограничив дальность такого поиска. К слову, похожая система была организована в игре Divinity original sin, потому что путь от одного конца карты в другой персонажи отказывались прокладывать напрочь, хотя алгоритм насколько я понял был похожий с моим, не знаю была ли у них реализовано раграничение игрового поля на зоны. В игре тоже были закрытые участки - например запертые дома или временно недоступные зоны :).
Теперь же поднабравшись опыта, я вновь попытался осилить процесс авторазметки игрового поля. Еще одной причиной, по которой я за него не брался изначально (кроме отсутствия знаний) - это как я думал громадные вычислительные затраты на проверку каждой клетки игрового пространства, но все оказалось не так страшно.
В понимании мне также очень хорошо помогла вот эта статья на Хабре Подсчет объектов на бинарном изображении.
В чем же преимущества такого разделения пространства на зоны применительно к поиску пути? Все очень просто, обозначая непроходимые участки как зоны отличные от той, на которой находится игровой персонаж, мы как бы говорим - "Дружище, эта место закрыто для тебя" избавляя его от тонны лишних вычислений.
Есть несколько методов подобной авторазметки: однопроходная, двухпроходная и многопроходная. Я выбрал двухпроходную - она оказалась для меня наиболее понятной и удобной. Работа этого алгоритма очень похожа на работу сканера, который есть в каждом офисе. Вы кладете лист бумаги который необходимо отсканировать и лазер проходит по листу, считывая изображение с листа сверху вниз, а затем в обратную сторону.
В статье по ссылке выше описывается такая проверка методом уголков. то есть каждый пиксель (а в случае с игровым полем - клетка игрового поля) проверяется в совокупности с соседями впереди и сверху и на основе этой проверки выстраивается первоначальное разделение поля на зоны. Но при первом проходе могут возникать так называемые двойные зоны. Затем при втором проходе происходит уточнение клеток которые соединяют эти двойные зоны и происходит их объединение - ничего сложного.
К примеру, вот в этом цикле статей про поиск пути , на основе которого я делал свой первоначальный вариант А*, описан другой метод разделения на зоны - т.н. контурный метод разделения, но он мне показался не очень удобным и не совсем понятным по расчетам, хотя возможно он быстрее.
И вот что у меня получилось в итоге. Так же я дам ссылку на Unity Asset со скриптами и проектом :).
Click to viewКстати уголковый метод проверки оказался весьма полезным и я применял его и для других целей :).
ч.7 Учусь программировать. Процедурная вода 2D. Пробую флюиды.