3D.ru

Всем привет!
Возникла необходимость создания случайной ломаной по узлам сетки (для "полупроцедурной" текстуры), при этом соблюдая следующие условия:
1) У каждой ломаной есть начало и конец (желтые круги на рисунке в спойлере первом), которые в итоге должны соединиться.
2) Учесть возможность как игнорировать другие линии, так и проходить через них N-раз.
3) Должна быть возможность настраивать "кривизну" - отклонение от самого короткого пути.
4) Линия проходит только по тем узлам сетки. Между ними нельзя, т.е. линия строго вертикальная или горизонтальная.
5) Линия не должна себя пересекать, отрезать себе путь и прочие условия, позволяющие избежать волшебного зацикливания.
Пока что текстура создается по сетке, каждый узел содержит в себе тип узло (короче, массив [sizeX, sizeY] типа enum NodeType { Shape, Joint, Free, Blocked и т.д } ).
Как это выглядит сейчас - видно на скрине во втором спойлере. Поставил разные узоры WxH размера. Пока линий нет. Думаю о том, как же соединить две точки линией случайным образом. На ум пока приходит поочередное переключение со случайного направления при построении линии на какой-нибудь алгоритм нахождения кратчайшего пути, но пока мне видится это странным: вот линия N узлов идет точно к точке, а вот она резко поворачивает в сторону и ведет себя случайно другие N узлов. Может есть какие-то алгоритмы построения случайных линий?