Comments 4
Немного покритикую:
1) Наследование карты (Map) от препятствия (Obstacle) — лучше сделать им общего абстрактного предка. У Obstacle еще добавляется функционал и он весь будет унаследован картой.
2) С точки зрения оптимизации каждый кадр в карте пробегать и проверять препятствия — не сдвинулись ли они и не поменяли ли размер — плохое решение. У большинства препятствий 99,9% времени размер и позиция не будут меняться. Лучше чтобы они при изменении позиции или размера уведомлять карту что было изменение (ставить флаг requireRebuild в True или если не хочется чтобы Obstacle знал о Map то завести статичный флаг, скажем, dirty — и его устанавливать при изменении позиции или размера, а из карты его чекать). Будет работать намного быстрее.
3) При изменении положений или размера препятствий обычно всю карту не перестраивают, только часть.
4) «Дело в том, что в unity для указания позиции объекта в пространстве используется простой float который весьма неточен и может быть дробным или отрицательным числом, поэтому его будет сложно использовать для реализации поиска пути на карте. Координаты же выполнены в виде четкого int который всегда будет положительным и с которым работать намного проще при поиске соседних точек.» — не согласен. float-а вполне достаточно, просто чем делать карту и брать из неё точки лучше задать возможные переходы для каждой точки (и можно посчитать их стоимость — чтобы не тратить время в риалтайме), тогда все будет работать нормально, немного больше расход памяти, но работать будет быстрее. A* по большому счету без разницы — сетка это или просто графы, это алгоритм поиска по графам, а сетка лишь частный случай.
5) Реализация A* ваша немного странная — не понял как идет выборка из открытого списка. Такое ощущение что не лучшее совпадение берется, а всегда первый попавшийся. Вы всегда берете первый элемент массива openList[0] без учета эвристики. Или он у вас где-то сортируется? Не очень понял этот момент.
6) Для этого примера лучше бы подошел NavMesh — гораздо меньше узлов пришлось бы обработать, работало бы быстрее. Хотя если просто для примера — то нормально.
7) По самой Job system — инфы мало, хотя статья о нем.
PS: при изменении размеров и позиции препятствий боты глючат.
1) Наследование карты (Map) от препятствия (Obstacle) — лучше сделать им общего абстрактного предка. У Obstacle еще добавляется функционал и он весь будет унаследован картой.
2) С точки зрения оптимизации каждый кадр в карте пробегать и проверять препятствия — не сдвинулись ли они и не поменяли ли размер — плохое решение. У большинства препятствий 99,9% времени размер и позиция не будут меняться. Лучше чтобы они при изменении позиции или размера уведомлять карту что было изменение (ставить флаг requireRebuild в True или если не хочется чтобы Obstacle знал о Map то завести статичный флаг, скажем, dirty — и его устанавливать при изменении позиции или размера, а из карты его чекать). Будет работать намного быстрее.
3) При изменении положений или размера препятствий обычно всю карту не перестраивают, только часть.
4) «Дело в том, что в unity для указания позиции объекта в пространстве используется простой float который весьма неточен и может быть дробным или отрицательным числом, поэтому его будет сложно использовать для реализации поиска пути на карте. Координаты же выполнены в виде четкого int который всегда будет положительным и с которым работать намного проще при поиске соседних точек.» — не согласен. float-а вполне достаточно, просто чем делать карту и брать из неё точки лучше задать возможные переходы для каждой точки (и можно посчитать их стоимость — чтобы не тратить время в риалтайме), тогда все будет работать нормально, немного больше расход памяти, но работать будет быстрее. A* по большому счету без разницы — сетка это или просто графы, это алгоритм поиска по графам, а сетка лишь частный случай.
5) Реализация A* ваша немного странная — не понял как идет выборка из открытого списка. Такое ощущение что не лучшее совпадение берется, а всегда первый попавшийся. Вы всегда берете первый элемент массива openList[0] без учета эвристики. Или он у вас где-то сортируется? Не очень понял этот момент.
6) Для этого примера лучше бы подошел NavMesh — гораздо меньше узлов пришлось бы обработать, работало бы быстрее. Хотя если просто для примера — то нормально.
7) По самой Job system — инфы мало, хотя статья о нем.
PS: при изменении размеров и позиции препятствий боты глючат.
Спасибо за конструктивный комментарий. Прежде всего скажу, что изначально предполагалось разобрать и поиск пути с помощью Job system, но тогда страшно представить какой был бы размер самой статьи.
По пунктам:
1) Создавать целый отдельный абстрактный класс для того чтобы вынести общий функционал!? — ну и зачем, чтобы все более лаконичней смотрелось, плюс дополнительные строки кода и текста.
2) Можно вынести изменения размера и позиции в свойство или метод и устанавливать там параметр изменения, согласен, но опять же размер. К примеру чтобы отлавливать изменения в редакторе придется писать целый кастомный редактор, в общем в любом случае так или иначе нужен будет какой-либо update. Опять же смысла не вижу этого делать для статьи о системе задач в первую очередь.
3) Да все верно, можно брать уже рассчитанные точки и исключать их или создавать новые там где нет препятствий. Но алгоритма как это сделать легко и просто, а еще и уместить в одну статью я так и не смог придумать, ну это моя вина.
4) Да ради бога, как вам удобно так и реализуйте. Так то в принципе можно упрощать и упрощать.
5) Да, здесь нет сортировки. Потестровав, я понял что нужно или сортировку переносить в многоступенчатую задачу IJobParallelFor или просто отказаться от нее, что даст более простую реализацию в коде, но меньшую скорость работы.
6) Не совсем понял в чем смысл этого комментария, для 2D это в каком месте можно использовать NavMesh?
7) В самом начале ссылка на статью именно о самой системе в деталях.
"PS: при изменении размеров и позиции препятствий боты глючат."
Каждый раз при перестройки карты боты также отправляют запрос на постройку нового пути, даже если они не находятся в той зоне где произошли изменения… Извиняюсь, это конечно моя недоработка, исправим!
По пунктам:
1) Создавать целый отдельный абстрактный класс для того чтобы вынести общий функционал!? — ну и зачем, чтобы все более лаконичней смотрелось, плюс дополнительные строки кода и текста.
2) Можно вынести изменения размера и позиции в свойство или метод и устанавливать там параметр изменения, согласен, но опять же размер. К примеру чтобы отлавливать изменения в редакторе придется писать целый кастомный редактор, в общем в любом случае так или иначе нужен будет какой-либо update. Опять же смысла не вижу этого делать для статьи о системе задач в первую очередь.
3) Да все верно, можно брать уже рассчитанные точки и исключать их или создавать новые там где нет препятствий. Но алгоритма как это сделать легко и просто, а еще и уместить в одну статью я так и не смог придумать, ну это моя вина.
4) Да ради бога, как вам удобно так и реализуйте. Так то в принципе можно упрощать и упрощать.
5) Да, здесь нет сортировки. Потестровав, я понял что нужно или сортировку переносить в многоступенчатую задачу IJobParallelFor или просто отказаться от нее, что даст более простую реализацию в коде, но меньшую скорость работы.
6) Не совсем понял в чем смысл этого комментария, для 2D это в каком месте можно использовать NavMesh?
7) В самом начале ссылка на статью именно о самой системе в деталях.
"PS: при изменении размеров и позиции препятствий боты глючат."
Каждый раз при перестройки карты боты также отправляют запрос на постройку нового пути, даже если они не находятся в той зоне где произошли изменения… Извиняюсь, это конечно моя недоработка, исправим!
Я не собирался спорить с вами, просто высказал мысли о том что можно улучшить, которые появились после прочтения статьи.
5) Сортировка списка не нужна, это будет лишняя трата ресурсов, достаточно просто поиска минимума (это намного быстрее). Без неё (то что у вас сейчас) — это другой алгоритм, не A* (поиск в ширину по моему называется, точно не помню сейчас).
6) Я не имел в виду использовать юнитевский, я имел в виду написать свой NavMesh.
5) Сортировка списка не нужна, это будет лишняя трата ресурсов, достаточно просто поиска минимума (это намного быстрее). Без неё (то что у вас сейчас) — это другой алгоритм, не A* (поиск в ширину по моему называется, точно не помню сейчас).
6) Я не имел в виду использовать юнитевский, я имел в виду написать свой NavMesh.
Да, я Вас понял — возвращать минимальную точку из открытого списка.
На счет многопоточнго навмеша, а смысл? Многопоточные поиски пути уже давно не в новинку, я думаю штуки 2-3 на ассет сторе точно есть, и для 2д и для 3д, есть целые проекты направленные на это. А написание нового это — будет просто изобретение очередного велосипеда.
Sign up to leave a comment.
Job system и поиск пути