* проблема коллизии препятствия первооткрывателя
Я работаю над проектом с роботом, который должен найти его путь к объекту и избежать некоторых препятствий при движении в тот объект, который он должен взять.
Проблема заключается в этом робот и объект, который должен взять робот, оба один пиксель шириной в первооткрывателе. В действительности они намного больше. Часто* первооткрыватель принимает решение поместить маршрут вдоль краев препятствий, иногда заставляя это столкнуться с ними, которых мы не хотим должными быть делать.
Я попытался добавить еще некоторые недоступные пешеходу поля к препятствиям, но это не всегда удается очень хорошо. Это все еще сталкивается с препятствиями, также добавляя слишком много точек, где не позволяется идти, результаты, в которых нет никакого пути, на котором это может работать.
У Вас есть какие-либо предложения на том, что сделать об этой проблеме?
Править:
Таким образом, я сделал как Justin L предложенный путем добавления большого количества стоимости вокруг препятствий, которая приводит к folling: Сетка без пути http://sogaard.us/uploades/1_grid_no_path.png
Здесь Вы видите стоимость вокруг препятствий, первоначально средние два препятствия должны посмотреть точно так же, как те в углах, но после выполнения нашего первооткрывателя она походит, затраты переопределяются:
Сетка с путем http://sogaard.us/uploades/1_map_grid.png
Изображение выше показывает то, какие вещи найдены на изображении.
Соедините каналом нашел http://sogaard.us/uploades/3_path.png
Это - путь, найденный, которым, поскольку также была наша проблема, прежде обнимает препятствие.
Сетка до с путем на http://sogaard.us/uploades/4_mg_path.png
И другое изображение со стоимостью отображается с путем на.
Таким образом, то, что я нахожу странными, - то, почему* первооткрыватель переопределяет эту полевую стоимость, которая ОЧЕНЬ высока.
Это было бы, когда это оценивает узлы в открытом списке с текущим полем, чтобы видеть, короче ли текущий полевой путь, чем одна внутренняя часть открытый список?
И вот код, который я использую для первооткрывателя:
Pathfinder.cs: http://pastebin.org/343774
Field.cs и Grid.cs: http://pastebin.org/343775
3 ответа
Рассматривали ли вы добавление стоимости градиента к пикселям рядом с объектами?
Возможно, такой простой, как линейный градиент:
C = -mx + b
Где x - расстояние до ближайшего объекта, b - это стоимость прямо за границами, а m - скорость, с которой стоимость умирает. Конечно, если C отрицательно, он должен быть установлен в 0.
Возможно, простой гиперболический распад
C = b/x
, где b - желаемая стоимость прямо за границей, опять же. Установите отсечку до 0, как только он достигнет определенной нижней точки.
В качестве альтернативы вы можете использовать экспоненциальное затухание
C = k e^(-hx)
, где k - постоянная масштабирования, а h - скорость затухания. Опять же, иметь отсечку - это разумно.
Второе предложение
Я никогда не применял A * к карте с пиксельным отображением; почти всегда плитка.
Вы могли бы попробовать значительно уменьшить «разрешение» ваших плиток? Может быть, одна плитка на набор пикселей десять на десять или двадцать на двадцать; стоимость тайла - это наибольшая стоимость пикселя в тайле.
Кроме того, вы можете попробовать обесценить эвристику кратчайшего расстояния, которую вы используете для A *.
Я сделал одного такого физического робота. Мое решение заключалось в том, чтобы делать один шаг назад всякий раз, когда нужно сделать поворот налево и направо.
Красная линия, насколько я понимаю, ваша проблема. Черная линия - это то, что я сделал, чтобы решить проблему. Робот может сделать шаг назад прямо, а затем повернуть направо.
Вы можете попробовать увеличить препятствия, принимая во внимание размер робота. Можно закруглить углы препятствий, чтобы решить проблему блокировки. Тогда заполненные промежутки будут слишком малы, чтобы робот мог протиснуться через них.