Универсальные способы написания методов Path-Finding

Универсальные способы написания методов Path-Finding
Path-Finding

Проблема, с которой сталкивался каждый начинающий гейм-девелопер — что же такое PathFinding, и как его написать. Для начала, что же это такое — pathfinding это метод, с помощью которого объект ищет возможный путь из точки А в точку Б. Само использование этого метода подразумевает наличие между этими точками препятствий, которые необходимо тем или иным образом обогнуть. Наверняка вы не раз встречались с ситуацией в играх, когда NPC просто застревал на месте, или не мог найти путь, что говорит о том, что даже в крупных студиях не всегда могут написать качественные методы нахождения пути. Каким же образом можно написать эти методы?
Как и любая хорошая функция, pathfinding должен быть разделен но более мелкие и простые задачи, первой из которых будет разбиение области между точкой А и точкой Б на клетки своеобразной сеткой. Область может быть какой угодно, но классически используется параллелограмм. Получив таким образом сетку, с помощью соответствующих функций, которые должны быть написаны заранее, необходимо определить, соседствует ли данная точка с объектом, который является препятствием для нас. Таким образом, отсеиваются точки, в которые вы не можете попасть. Далее, координатами оставшихся точек заполняется двумерный массив, где каждый из индексов величина координаты точки по оси абсцисс или ординат.
Вторым и самым легким с точки зрения написания этапом является нахождение ближайшей к точке А точки из вашего двумерного массива.
 Нахождение расстояния в двумерной плоскости находится с помощью обыкновенной теоремы Пифагора и двойного цикла (цикла, вложенного в другой цикл).
Третьей, самой сложной частью, является составление из нового двумерного массива своеобразного графа, с ветками которого придется работать отдельно. Для заполнения нового двумерного массива придется использовать тройной цикл (цикл, вложенный в цикл, вложенный в цикл). Первый индекс массива будет просто условным номером точки, под вторым вы будете хранить опять таки координаты, и индекс точки, через которую вы пришли в данную точку. Таким образом, с помощью тройного цикла вы сперва находите все точки, до которых вы можете добраться из точки, ближайшей к нашей цели (точке А), записываем их координаты, в качестве же индекса точки, из которой можно попасть в нашу точку, пишем ноль — таким образом нулевой по первому индексу элемент массива будет нашей финальной точкой. Далее, берем следующую по первому индексу точку, и смотрим, куда вы можете из неё попасть (кроме нашей предыдущей точки). Если вы попали в точку, из которой некуда больше идти, используется ключевой слово break для прерывания цикла и эта ветвь графа полностью удаляется из памяти. Таким образом вы получаете двумерный массив, представляющий из себя граф, все ветви которого являются путями из точки А в точку Б.

0 Комментариев

Оставить комментарий