имеем 3-х мерный массив описывающий некоторый лабиринт. Пусть 0 — нет стенки, 1 — стенка. И две точки между которыми надо проложить путь.
1) Путь должен проходить на максимальном удалении от стенок лабиринта.
2) Если пути не существует, то можно пройти через стенку, но минимальное количество раз и с учётом первого условия.
Подскажите в какую сторону рыть, какие методы или ещё что-нибудь.

Здравствуйте, js67257, Вы писали:

J>имеем 3-х мерный массив описывающий некоторый лабиринт. Пусть 0 — нет стенки, 1 — стенка. И две точки между которыми надо проложить путь.
J>1) Путь должен проходить на максимальном удалении от стенок лабиринта.
J>2) Если пути не существует, то можно пройти через стенку, но минимальное количество раз и с учётом первого условия.
J>Подскажите в какую сторону рыть, какие методы или ещё что-нибудь.

А чем поиск в 3D отличается от поиска в 2D, кроме того что граф путей не планарный получается?

Здравствуйте, js67257, Вы писали:

J>имеем 3-х мерный массив описывающий некоторый лабиринт. Пусть 0 — нет стенки, 1 — стенка. И две точки между которыми надо проложить путь.
J>1) Путь должен проходить на максимальном удалении от стенок лабиринта.
J>2) Если пути не существует, то можно пройти через стенку, но минимальное количество раз и с учётом первого условия.
J>Подскажите в какую сторону рыть, какие методы или ещё что-нибудь.
На правах идеи (решение в лоб).
Лабиринт определен массивом, фактически это значит, что пространство поделено на кубики, в которых определена проходимость.
Для каждого кубика (Block) вычисляем расстояние до ближайшей стенки (Dist) и "стоимость посещения" (Cost) как Const/Dist (константа подбирается экспериментально).
Строим граф переходов по смежным проходимым кубикам.
Определяем стоимость перехода (вес ребра) между смежными кубиками (Block0, Block1) как расстояние между ними * среднее арифметическое стоимости посещения (Cost0+Cost1)/2. ((Cost0+Cost1)/2 — чтобы стоимость перемещения между кубиками была одинаковой в обе стороны. Есть бездоказательное интуитивное предположение, что "так правильно" ) (заметка на полях: возможно что-то удасться нагуглить по ключевым словам "метод потенциалов")

Находим путь с помощью алгоритма поиска на графе. Если путь не найден, то строим новый граф, в котором возможны переходы сквозь стены. Делаем их стоимость очень высокой. Запускаем алгоритм снова. Путь будет найден.

ПС. Хы. Как обычно, все хорошее придумано до нас Причем, лет дцать назад http://www.keldysh.ru/papers/2001/prep40/prep2001_40.html

Здравствуйте, Trean, Вы писали:

T>Здравствуйте, js67257, Вы писали:

J>>имеем 3-х мерный массив описывающий некоторый лабиринт. Пусть 0 — нет стенки, 1 — стенка. И две точки между которыми надо проложить путь.
J>>1) Путь должен проходить на максимальном удалении от стенок лабиринта.
J>>2) Если пути не существует, то можно пройти через стенку, но минимальное количество раз и с учётом первого условия.
J>>Подскажите в какую сторону рыть, какие методы или ещё что-нибудь.

T>А чем поиск в 3D отличается от поиска в 2D, кроме того что граф путей не планарный получается?
хорошо бы ещё побыстрее. Потому как обходить всё это дело например при массиве 512х512х512 получится ну очень долго.

Здравствуйте, FreshMeat, Вы писали:

FM>Здравствуйте, js67257, Вы писали:

J>>имеем 3-х мерный массив описывающий некоторый лабиринт. Пусть 0 — нет стенки, 1 — стенка. И две точки между которыми надо проложить путь.
J>>1) Путь должен проходить на максимальном удалении от стенок лабиринта.
J>>2) Если пути не существует, то можно пройти через стенку, но минимальное количество раз и с учётом первого условия.
J>>Подскажите в какую сторону рыть, какие методы или ещё что-нибудь.
FM>На правах идеи (решение в лоб).
FM>Лабиринт определен массивом, фактически это значит, что пространство поделено на кубики, в которых определена проходимость.
FM>Для каждого кубика (Block) вычисляем расстояние до ближайшей стенки (Dist) и "стоимость посещения" (Cost) как Const/Dist (константа подбирается экспериментально).
FM>Строим граф переходов по смежным проходимым кубикам.
FM>Определяем стоимость перехода (вес ребра) между смежными кубиками (Block0, Block1) как расстояние между ними * среднее арифметическое стоимости посещения (Cost0+Cost1)/2. ((Cost0+Cost1)/2 — чтобы стоимость перемещения между кубиками была одинаковой в обе стороны. Есть бездоказательное интуитивное предположение, что "так правильно" ) (заметка на полях: возможно что-то удасться нагуглить по ключевым словам "метод потенциалов")

FM>Находим путь с помощью алгоритма поиска на графе. Если путь не найден, то строим новый граф, в котором возможны переходы сквозь стены. Делаем их стоимость очень высокой. Запускаем алгоритм снова. Путь будет найден.

FM>ПС. Хы. Как обычно, все хорошее придумано до нас Причем, лет дцать назад http://www.keldysh.ru/papers/2001/prep40/prep2001_40.html
Спасибо. Похоже то что нужно. Ушёл изучать и воплощать.

FM>>ПС. Хы. Как обычно, все хорошее придумано до нас Причем, лет дцать назад http://www.keldysh.ru/papers/2001/prep40/prep2001_40.html
J>Спасибо. Похоже то что нужно. Ушёл изучать и воплощать.

Бегло просмотрел. Интересная задача
Решение для 2D в готовом виде есть в Graphviz (http://www.graphviz.org/, точнее здесь: http://www.graphviz.org/Misc/spline-o-matic/).
Правда там контура, а не массивы, но, думаю сделать контура из массива — задача вполне решаемая.

Здравствуйте, js67257, Вы писали:

J>хорошо бы ещё побыстрее. Потому как обходить всё это дело например при массиве 512х512х512 получится ну очень долго.

Почему долго? Надо только формализовать оптимизируемую функцию. А так, я не вижу, чем эта задача отличается от обычного поиска пути в лабиринте. Поиск в лабиринте — это O(N^3*log(N)), в данном случае, где N — размерность лабиринта. Это в случае реализации Дейкстры. Можно реализовать A* — будет быстрее.