Алгоритм четырехсторонней навигации

Ответ 1

[EDIT 21/5/2013: Как отметил Джин в комментарии, моя схема взвешивания фактически не гарантирует, что каждый прямоугольник будет доступен из любого другого прямоугольника - только каждый прямоугольник будет подключен к другой прямоугольник в каждом направлении.]

Хороший способ сделать это - максимально взвешенное двухстороннее соответствие.

Мы хотим создать таблицу, определяющую функцию f (r, d), которая возвращает прямоугольник, в который будет перемещен пользователь, если они в настоящее время находятся на прямоугольнике r и направить направление d (вверх, вниз, влево или правильно). Мы хотели бы, чтобы эта функция обладала некоторыми хорошими свойствами, такими как:

• Должно быть возможно достигнуть каждого прямоугольника из любого другого прямоугольника
• Нажатие налево, затем направо или наоборот, или вверх или вниз, или наоборот, должно оставить пользователя в том же месте
• Нажатие, например, слева нужно взять пользователя на прямоугольник влево (это немного сложнее сформулировать точно, но мы можем использовать систему оценки для измерения качества).

Для каждого прямоугольника создайте 4 вершины в графе: по одному для каждого возможного ключа, который можно было бы нажать в этом прямоугольнике. Для определенного прямоугольника r назовите их r _U, r _D, r _L и r _R. Для каждой пары прямоугольников r и s создайте 4 ребра:

• (r _U, s _D)
• (r _D, s _U)
• (r _L, s _R)
• (r _R, s _L)

Этот граф имеет 2 связных компонента: один содержит все U и D вершины, а другой содержит все L и R вершины. Каждый компонент является двудольным, поскольку, например, никакая U-вершина никогда не связана с другой U-вершиной. Фактически мы могли бы запускать согласованное двухстороннее согласование двух сторон по каждому компоненту отдельно, хотя проще просто говорить о его запуске один раз на всем графике после группировки, скажем, U-вершинах с L-вершинами и D-вершинах с R-вершинами.

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

• обратно пропорционально расстояниям между прямоугольниками (вы можете использовать расстояние между их центрами) и
• обратно пропорционально тому, насколько угол между центрами прямоугольников отличается от желаемой горизонтальной или вертикальной линии, и
• ноль, когда прямоугольники ориентированы неверно (например, если для края (r _U, s _D)), если центр r фактически находится над центром с). Кроме того, вы можете просто удалить эти края с нулевым весом.

Эта функция пытается удовлетворить требованиям 3 вверху.

[EDIT # 2 24/5/2013: добавлена ​​примерная функция ниже.]

Вот псевдокод C-ish для примерной функции, удовлетворяющей этим свойствам. Он принимает центральные точки из двух прямоугольников и направление от прямоугольника 1 (направление от прямоугольника 2 всегда противоположно этому направлению):

const double MAXDISTSQUARED = /* The maximum possible squared distance */;
const double Z = /* A +ve number. Z > 1 => distance more important than angle */

// Return a weight in the range [0, 1], with higher indicating a better fit.
double getWeight(enum direction d, int x1, int y1, int x2, int y2) {
    if (d == LEFT  && x1 < x2 ||
        d == RIGHT && x1 > x2 ||
        d == UP    && y1 < y2 ||
        d == DOWN  && y1 > y2) return 0;

    // Don't need to take sqrt(); in fact it probably better not to
    double distSquared = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    double angle = abs(atan2(x1 - x2, y1 - y2));   // 0 => horiz; PI/2 => vert
    if (d == UP || d == DOWN) angle = PI / 2 - angle;
    return 1 - pow(distSquared / MAXDISTSQUARED, Z) * (2 * angle / PI);
}

Теперь запустите максимальное взвешенное двухстороннее соответствие. Это попытается найти множество ребер, имеющих самый высокий общий вес, так что каждая вершина (или, по крайней мере, как можно больше) смежна с выбранным ребром, но никакая вершина не смежна с более чем одним ребром. (Если мы допустили, чтобы вершина была смежна с более чем одним ребром, это означало бы, что нажатие этой клавиши в этом прямоугольнике приведет вас к более чем одному прямоугольнику адресата, что не имеет смысла.) Каждое ребро в этом сопоставлении соответствует к двунаправленной паре нажатий клавиш, так что нажатие, например, а затем вниз, чтобы вернуться туда, где вы были, автоматически удовлетворяя требование 2 вверху.

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

[РЕДАКТИРОВАТЬ 21/5/2013: Как говорит Джин, мое утверждение ниже этого свойства 1 удовлетворено новой схемой взвешивания, которую я предлагаю, неверно. Во многих случаях каждый прямоугольник будет доступен, но в целом вам необходимо решить проблему циклического цикла с гамильтонианом, чтобы гарантировать это. Я оставлю объяснение, потому что он доставит нас оттуда. В любом случае его можно взломать, регулируя веса между подключенными компонентами вверх, когда обнаруживаются подциклы.]

Чтобы гарантировать, что алгоритм сопоставления всегда возвращает соответствие, в котором доступен каждый прямоугольник, нам нужно отрегулировать вес ребер, чтобы никогда не было возможно совпадения с результатом больше, чем совпадение с большим количеством ребер. Это может быть достигнуто путем масштабирования функции подсчета от 0 до 1 и добавления количества прямоугольников n к каждому весу кромки. Это работает, потому что полное совпадение тогда имеет оценку как минимум 4n ^ 2 (т.е. Даже если показатель качества равен 0, сам край имеет вес n, а их 4n), в то время как любое совпадение с меньшим количеством ребер имеет наибольшее значение 4 (n-1) (n + 1) = 4n ^ 2 - 4, что строго меньше.

Ответ 2

Это трюизм, что человеку с молотом все выглядит как гвоздь. Самые короткие алгоритмы пути являются очевидным инструментом здесь, потому что кратчайшее расстояние кажется интуитивным.

Однако мы разрабатываем интерфейс, где логическое расстояние гораздо важнее физического расстояния.

Так что попробуй думать иначе.

Одно ограничение состоит в том, что многократное попадание стрелки вверх (справа, вниз или влево) должно, в конечном счете, проходить через все прямоугольники. В противном случае возможны недостижимые "сироты". Достижение этого с помощью алгоритма, основанного на физическом (2d) расстоянии, затруднено, потому что ближайший элемент в 2d может оказаться в неправильном направлении в 1-й проекции, соответствующей используемой паре стрелок. То есть нажатие стрелки вверх может легко выбрать поле под током. Уч.

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

Также сделайте то же самое с y-координатами. Использование циклов "вверх" и "вниз" в этом порядке.

Ключ (каламбур) к успеху добавляет динамическую информацию на экран во время циклирования, чтобы показать пользователю логику происходящего. Вот предложение. Другие возможны.

Сначала вертикальная (вверх или вниз) клавиша, над прямоугольниками появляется бледное полупрозрачное наложение. Они затенены бледно-красным или синим в шаблоне, который чередуется по координате y центра тяжести. Существуют также горизонтальные хэш-метки совпадающего цвета по всему окну. Единственная причина для двух цветов - предоставить визуальный индикатор соответствия между строками и прямоугольниками. Выбранный в данный момент прямоугольник не является просвечивающим, а хэш-знак ярче всех остальных. Когда вы продолжаете нажимать клавишу "вверх" или "вниз", выделенное поле изменяется в y-порядке центроида, как описано выше. Наложение исчезает, если никакая стрелка не была удалена в течение половины секунды или около того.

Очень похоже наложение, если нажата горизонтальная клавиша, только вертикальные хэш-метки и x-порядок.

Как пользователь, мне бы очень понравилась эта схема. Но YMMV.

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

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

Bare Boxes

Выбор со стрелкой вверх или вниз

Выбор со стрелкой влево или вправо

Ответ 3

Как построить график движения следующим образом:

• для любого направления, попробуйте перейти к ближайшему прямоугольнику в заданном направлении, центром которого является середина текущей стороны прямоугольника.
• попытайтесь устранить петли, например. перемещение "справа" от A должно пытаться создать другой прямоугольник, чем перемещение "вверх-вправо" от A. Например, в этот рисунок, справа "от зеленого должно быть оранжевым, хотя розовый будет ближайшей серединой.
• (Спасибо biziclop): если какие-либо прямоугольники не достижимы на графике, тогда переформатируйте один из соседних прямоугольников, чтобы добраться до него, вероятно, с наименьшей ошибкой. Повторяйте, пока все прямоугольники не достигнут (я думаю, что алгоритм завершится...)

Затем сохраните график и используйте его только для навигации. Вы не хотите изменять направления в середине сеанса.

Ответ 4

Эта проблема может быть смоделирована как проблема graph, а algorithm of navigation может использоваться как shortest path routing.

Вот моделирование.

Каждый прямоугольник является вершиной в графе. Из каждой вершины (aka rectangle) у вас есть четыре варианта: вверх, вниз, влево, вправо. Таким образом, вы можете достичь четырех разных прямоугольников, т.е. Эта вершина будет иметь четыре соседства, и вы добавите эти ребра в график.

Я не уверен, что это часть проблемы. "Несколько прямоугольников могут быть достигнуты из прямоугольника с использованием определенного действия (например, вверх)". Если нет, приведенное выше модели достаточно хорошее. Если да, то добавьте все такие вершины, как сосед для этой вершины. Следовательно, вы можете не иметь 4-правильного графа. В противном случае вы будете моделировать свою проблему в 4-правильном графике.

Теперь вопрос: how do you define your "navigation" algorithm. Если вы не хотите различать свои действия, т.е. Если все вверх, вниз, влево и вправо равны, то вы можете добавить вес 1 ко всем ребрам.

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

Если вы решите, что все грани up не равны, то есть расстояние между A и B меньше, чем расстояние между C и D, тогда вы можете соответствующим образом назначить веса краям в процессе построения графика,

Вот маршрут

Теперь, как найти маршрут - вы можете использовать dijkstra algorithm, чтобы найти кратчайший путь между данной парой вершин. Если вас интересуют несколько кратчайших путей, вы можете использовать алгоритм k-shortest path, чтобы найти k кратчайшие пути между парой node, а затем выбрать лучший путь.

Обратите внимание, что график, в котором вы закончили, не обязательно должен быть ориентированным графом. Если вы предпочитаете ориентированный граф, вы можете назначить направления к краям при их создании. В противном случае вы должны хорошо использовать неориентированный граф, так как все, что вам нужно, - использовать край, чтобы достичь вершины от другого. Более того, если прямоугольник A может быть достигнут с помощью up из прямоугольника B, то rectangle B может быть достигнуто с помощью down из прямоугольника A. Таким образом, направления действительно не имеют значения, если они вам не нужны по другим причинам. Если вам не нравится предположение, которое я только что сделал, вам нужно построить ориентированный граф.

Надеюсь, что это поможет.