Алгоритм морфинга 2D-сегмента

Question

Создание игры-головоломки, в которой я хочу, чтобы фигуры морфировались на основе пользовательского ввода. Пользователь нажимает на вершину и перетаскивает точку, изменяя форму. Например, если пользователь нажимает на A и перетаскивает вниз (сокращая сегмент AG), точка B будет уменьшаться на равную величину (сокращая BC), точка F будет перемещаться влево, сокращая как AF, так и FG, наконец, точка E также переместится на слева, чтобы оставаться в соответствии с точкой F.

Существует массив сегментов линии, каждый отрезок линии представляет собой массив, который содержит две конечные точки. При переключении у меня есть поиск цикла для всех равных точек. Ничто из этого не сделано в камне, желая внести какие-либо изменения, необходимые для того, чтобы это работало.

Я работаю над этим в течение двух дней и полностью в тупике.

   A 
    B-------------\ 
    |   | \ 
    |   | \ 
    |   | \ 
    |   | \ 
    C------------------\F 
    |   G  | 
    |     | 
    |     | 
    D-------------------E 

Answer 1

Одновременные уравнения, не так ли?

Я предполагаю, что каждая линия должна сохранять свой наклон. Тогда ваша фигура удовлетворяет эти уравнения (или почти эти уравнения, я не 100% уверен, что наклон линии AF):

Bx = Cx = Dx

К = Ау

Су = Гр = Fy

Dy = Еу

Ах = Сх

Рх = Ех

(A.y - F.y) = 2 (F.x - A.x)

Когда игрок тащит, то A.y и A.x эффективно постоянны, поэтому у вас есть одиннадцать уравнений и двенадцать неизвестных. (Есть несколько ограничений, как указывает Бета, поскольку три уравнения Bx = Cx = Dx не относятся ни к одному из других, и ни Dy = Ey)

Что вы, вероятно, хотите, это решение, которое изменяет наименьшую из ваших переменных. Я не знаю, как это сделать. Но так как это игра, это, вероятно, не имеет значения, если изредка вы не получаете довольно минимальный набор изменений. Таким образом, может быть, жадный алгоритм будет работать следующим образом:

• Пусть S - множество переменных, которые мы сохраняем постоянными. Инициализируйте его до пустого набора.
• Для каждой переменной V, если можно решить множество уравнений, сохраняя переменные в S ∪ {V} contant, добавьте V в S.
• Последнее решение, которое вы нашли, - это тот, который вы используете.

Answer 2

Моей первой мыслью было линейное программирование с помощью симплекс-алгоритма, но я думаю, что это либо неправильно, либо, по крайней мере, неполное. В принципе, большинство, если не все из ваших правил, являются линейными, это-равными - это правила, в которых линейное программирование имеет дело с правилами «нет-меньше-того» (или < = или что-то еще).

Исправить может быть объединение. То есть, выражайте свои правила WRT как можно меньше переменных. Если у вас есть правило f (a) = g (b), вы можете эффективно исключить b, определяя b = g '(f (a)) и заменяя всюду, где вы найдете b. Поскольку фактически подстановка неэффективна, вы можете просто отметить связь между a и b.

С незначительными осложнениями основным подходом является объединение. В случае точного равенства вы должны устранить b, добавив ссылку из b в a. Когда вы находите «b», вы затем определяете (или что-то, с чем оно связано). Поэтому в любое время вы можете эффективно перевести любое правило в форму, в которой используются только неисчерпаемые переменные. Усложнение в этом случае - вам нужно сохранить беговую дорожку стиля g '(f (a)), когда будете следовать ссылкам. Поскольку это все линейно, это не должно быть большой проблемой, но не тривиальной.

Возможно, вам потребуется отменить объединение - запишите ссылки, которые вы установили в стек, чтобы вы могли снова их сбросить в правильном порядке, когда вы разматываете стек.

Я не уверен, что у вас есть какие-либо относительные условия вообще (меньше или что-то еще), но если это так, как только вы устраните как можно больше переменных, вам все равно потребуется некоторое линейное программирование. Если у вас есть две оставшиеся переменные, это концептуально просто. Для каждого линейного условия для этих двух переменных нарисуйте линию на двумерном графике таким образом, чтобы одна сторона линии представляла действительную область. Условия традиционно «нормализуются», поэтому действительная сторона всегда включает начало координат. На основе точек пересечения линии-отрезки, ближайшие к началу координат, образуют выпуклый многоугольник. Оптимальное решение находится на одном из углов и оценивается с использованием правила линейного скоринга (то, что вы оптимизируете), которое в вашем случае будет определено, чтобы дать «лучшую» форму, где есть некоторая двусмысленность или некоторый конфликт приоритетов в ваши правила - например вы не можете проталкивать точку целиком через линию, поэтому в определенных точках вещи блокируются.

Если у вас осталось больше двух переменных, вам нужен многомерный эквивалент выпуклого многоугольника - и это называется симплексом. Практическая реализация симплекс-алгоритма включает в себя матрицы.

Это уже упрощено до такой степени, что, вероятно, это неправильно в некоторых деталях, и это насколько я могу объяснить. IIRC вы можете получить хорошее описание этих компонентов технологии в Sedgewick, хотя Википедия может быть так же хорошо в эти дни.

Решения Simplex иногда используются для макетов окон - я думаю, что wxWidgets использует один для изменения размера элементов управления в окне. Унификация - это определяющая особенность логического программирования (Prolog и т. Д.), Но основополагающие принципы поиска на основе соединений достаточно просты. Основной трюк заключается в том, как преобразовать двумерную фигуру в набор правил, выражающих, как это изменится, и понимание того, как представлять и манипулировать этими правилами, особенно в матричной форме.

Answer 3

Как насчет этого ... ваша головоломка имеет только треугольники, прямоугольники и квадраты? В этом случае вы можете разработать метод обработки каждой фигуры в зависимости от того, какая вершина перемещена и на какие формы влияет перемещение этой вершины ... В вашем примере движущаяся вершина A будет влиять на квадрат ABCG и треугольник AGF. Итак, когда A движется, вершина C остается незатронутой ... вам нужно только «переместить» B и G. Если я не понимаю ваш пример неправильно, я не вижу, как движение A будет влиять на F. НТН.