Trimax Oct 28 2013 at 11:43

Motion planning: граф видимости, дорожные карты

10 min

27K

Game development*Algorithms*Mathematics*

From sandbox

+55

Comments 15

withkittens Oct 28 2013 at 12:12

Спасибо за статью. Пожалуйста, пишите ещё, буду рад вас почитать.

Trimax Oct 28 2013 at 16:55

Спасибо.

ZumZoom Oct 28 2013 at 15:28

Хорошо пишете. Добавлю от себя немного :)

1. Существует более быстрый вариант построения графа видимости, использующий Rotation Trees. Асимптотически работает за O(n^2), а пишется даже быстрее чем алгоритм с заметающей прямой по углу. Почитать можно здесь.
2. Вместо Грэхэма лучше писать Грэхэма с оптимизациями Эндрю. Асимптотически они одинаковы, но в варианте Эндрю сортировка работает быстрее за счет упрощения операций сравнения.
3. Вы почему-то решили не указывать оставшихся двух авторов книги Computational Geometry, а зря, потому что они обязательно должны быть упомянуты в любой содержательной статье по вычислительной геометрии :)

Trimax Oct 28 2013 at 16:55

Спасибо. Господ M. van Kreveld и M. Overmars добавил. Странно что я их продинамил. Что касается Rotation Trees, большое спасибо — обязательно прочитаю.

evilkost Oct 28 2013 at 16:51

Знаком немного с темой в контексте роботики и мне кажется, самый интиресный алгоритм — это RRT* ).
Еще стоит не забывать о габаритах персонажа и кинематике движения, иначе можно получить нереализумый путь.

Trimax Oct 28 2013 at 17:20

Да, «как есть» этот алгоритм использовать не получится. К тому же, вряд ли все ходят по стеночкам. :) Нужно добавлять потенциалы вершинам или заведомо увеличивать полигоны.

Zibx Oct 28 2013 at 19:43

Я уже давно хожу по стеночкам после исследования этих самых алгоритмов :).

stanislaw Oct 28 2013 at 22:59

На Java есть либа решающая подобные задачи Straightedge

Trimax Oct 28 2013 at 23:16

Спасибо за ссылку, думаю будет полезно.

Shc Oct 29 2013 at 14:47

Можно доказать, что оптимальный путь — это кусочно-линейная ломаная, вершины которой совпадают с вершинами препятствий.

Ой ли? ;)

рисунок

ZumZoom Oct 29 2013 at 15:03

Кроме начальной и конечной, естественно, потому что они заданы изначально.

Trimax Oct 29 2013 at 15:13

Это, разумеется, понятно. Это вырожденный случай. К тому же, ведь путь мы ищем на расширенном графе, в который добавлены вершины s & f.

Shc Oct 29 2013 at 15:27

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

Trimax Oct 29 2013 at 15:37

Понял. Да я тоже педант, каюсь, проглядел. :)

DoctorGester Oct 29 2013 at 16:50

А можно сурс приложения с последнего скриншота?

Show the best of all time