Допустим есть кубик рубика произвольного размера NxNxN.
На входе имеем начальное положение блока A(Xa, Ya, Za), конечное положение B(Xb
Yb, Zb) и углы вращения вокруг трёх осей, на которые блок повернулся в процессе перемещения..
Траектория перемещения может быть очень запутанной и нам не интересна. Эти входные данные абсолютно однозначно определяют конечное состояние одного из блоков (положение и разворот). Пытаюсь вывести алгоритм который по входным данным возвратит куда переместилась наклейка на данном блоке.
Рассмотрим пример по картинке:
Цифрой 1 обозначим начальное положение блока A(0, 2, 2).
Цифрой 2 - конечное положение блока B(2, 2, 0).
Для лучшего понимания можно добавить что второе положение из первого в данном случа
мы получили прокрутив: (R U R') (описание снизу) Потому имеем повороты вокруг трёх осей R(-90, 90, 0) (т.е. при повороте R блок 1 не менял положения, при U повернулся вокруг Y по часовой, при R' - вокруг X против часовой).
На выходе нужно вычислить, что если белая наклейка в исходном положении была сверху
то в конечном стала спереди, соответственно оранжевая была слева, стала сверху, а синяя была сзади, стала справа
Важно что какие были повороты мы не знаем, на входе их нет, а к конечной позици
можно прийти другим путём и иметь другие повороты, хотя внешне ничего не изменится (другие блоки будут на других местах, но они нам не интересны), потому как их задействовать в алгоритме пока не ясно, но они необходимы!
Т.е. при цепочке, например (L F) мы окажемся в том же положении, так же развёрнуты
но развороты будут на входе R(90, 0, 90), а при цепочке (L2 D R) тоже достигнем нужного положенияи разворота, но развороты будут R(90, -90, 0).
Необходим свежий взгляд со стороны, что-то я немного подзавис!
PS:
Классическая запись вращений: Up, Down, Left, Right, Front, Back начальные букв
названий сторон для поворота по часовой стрелке (если она находится перед нами) и с апострофом, например R' для поворота против часовой стрелки, а так же с 2, например R2 для поворота на 180 градусов.
Классическое расположение цветов: F - зеленый, U - белый, B - синий, R - красный, L - оранжевый, D - жёлтый.
Работа ведётся с двухмерной разметкой кубика.
Информация к размышлению: только мне кажется, что тут какая-то логическая ошибка?
Рассмотрим несколько простых примеров(в каждом примере следим за передним-правым-верхним углом):
Прокручиваем F2 L2
Имеем вектор разворота R(180, 0, 180), По оси Y он не поворачивался, но если бы м
не знали как он был туда поставлен, могли бы с уверенностью сказать поворотом вокруг Y на 180!
Прокручиваем R B L F
Наблюдаемый кубик возвращается в исходное положение, т.е. разница векторов координа
(0, 0, 0), развороты вокруг осей сокращаются и тоже получаем R(0, 0, 0). Т.е. вообще никакой информации, но кубик развёрнут по часовой стрелке!
Прокручиваем F' L' B' R'
Наблюдаемый кубик возвращается в исходное положение, т.е. разница векторов координа
(0, 0, 0), развороты вокруг осей так же сокращаются и тоже получаем R(0, 0, 0). Т.е. снова вообще никакой информации, но кубик развёрнут уже против часовой стрелки!
Ответы
Ответ 1
Давайте попробуем составить алгоритм. Я предлагаю алгоритм — поиск в ширину.
Определим обьект кубика. У куба 6 сторон. 6 цветов. Каждая сторона — 9 элементов
Давайте куб опишем массивом на 54 (6 × 9 = 54) элемента. Тогда конечная цель — чтобы каждые 9 элементов были равны. Давайте "нарисуем" модель.
18 19 20
21 22 23
24 25 26
0 1 2 9 10 11 36 37 38 45 46 47
3 4 5 12 13 14 39 40 41 48 49 50
6 7 8 15 16 17 42 43 44 51 52 53
27 28 29
30 31 32
33 34 35
Давайте определим действия, которые можно делать с кубиком. И так, у нас есть 6 граней
каждую сторону можно вращать вокруг собственной оси в обе стороны. Итого, у нас ест
6 × 2 = 12 действий. Нужно описать все 12 действий. Я опишу вам одно, остальные — самостоятельно. Для описания — элементы будут меняться местами. Для наглядности — давайте вращать грань 9-17 вокруг себя, тогда я парами указываю элементы, которые поменяются местами:
18 19 20
21 22 23
24-36 25-39 26-42
0 1 2-26 9-11 10-14 11-17 36-29 37 38 45 46 47
3 4 5-25 12-10 13 14-16 39-28 40 41 48 49 50
6 7 8-24 15-9 16-12 17-15 42-27 43 44 51 52 53
27-2 28-5 29-8
30 31 32
33 34 35
В виде пар это будет вид
24-36,25-39,26-42, 2-26, 9-11,10-14,11-17,36-29,5-25, 12-10,
14-16,39-28, 8-24, 15-9,16-12,17-15,42-27,27-2 ,28-5, 29-8
Вышло 20-ть пар. 12 + 8 = 20. Если пары поменять местами — будет вращение в противоположную сторону. Таких пар по 20 штук должно быть 12 вариантов. Я показываю один.
Попробую описать вращение рисунков в 3D. Вращение будет происходить только для
элементов, с 9-того по 17 включая 13. Остальные вращаться не будут, если это 2D проекция, а уже переводя это в 3D проекцию, получим больше вариантов.
Упакованый вариант разворота
a[i] = (a[i] & 7) + ((a[i] + 8) & (8+16)) и влево a[i] = (a[i] & 7) + ((a[i] - 8
& (24)) применить это для 9 елементов после перестановок. Тогда (a[i] & 24) = {0,8,16,24} в зависимости от разворота.
Вариант разворота простой с and x.size = (x.side+1)&3 или x.size = (x.side-1)&3
Вариант разворота усложнённый if (x.size=3) x.size = 0; else x.size++ или if (x.size=0) x.size = 3; else x.size--
UPD Важно: при операции вращения, лучше создавать отдельный массив, поскольку можн
"случайно" присвоить два раза одну ячейку. Например при в 11 мы присвоили 9, а в 17 присваиваем 11 — и получаем "сбой", поэтому слева от присваивания должен быть исходный массив, а справа (куда приваиваем) — дубликат исходного массива.
ИТОГ: делаем 20 операций перестановки, потом 9-операций 2D вращения, при этом один из 9 — центральный элемент, который не вошёл в 20.
Имея обьект кубика, давайте определим конечное условие: это будет о[0]=o[1]=…=o[8], о[9]=o[10]=…=o[17], …, т.е. все каждые 9 элементов массива должны быть равны.
Теперь, когда у нас есть "обьект", то мы создаём массив обьектов, и начинаем строит
дерево. Каждый новый уровень, добавляет по несколько элементов в массив. Нужно это для того, чтоб убрать "лишнии" движения, и найти решение используя поиск в ширину.
Делаем структуру (№итерации, №действия(1-12), №элемента, который привёл к появлению даного, "обьект"(массив на 54))
Далее строим 1-вую итерацию, т.е. цикл на 12 перестановок граней, получаем
a[0]=(0,0,0,-1,obj),a[1]=(1,1,0,obj),a[2]=(1,2,0,obj),a[3]=(1,3,0,obj),
a[4]=(1,4,0,obj)..a[12]=(1,12,0,obj);
Каждый обьект, проверяем условие [3]. Делаем 2-рую итерацию. Тут уже возникнет проблема
Начнут появляться дубли. Дубли образуются тогда, когда мы одну и ту же грань вращае
сначала влево, а потом на 2-й итерации, её же вправо. Можно придумать как алгоритмическ
этого избежать, но сложно. Кроме того, нужно ещё фильтровать 4-х кратное вращение
т.д., поэтому проще — просто фильтровать дубли. Т.е, как по мне — то проще — проверять с добавлением нового элемента массива — нет ли дублей ниже, в элементах a[0]…a[n] (a[12]). Вторая итерация принесёт 12 × 12 = 144 элемента, но половина — будут точно дубли. Поэтому будет где-то +72 элемента. Для упрощения сделаем так. Второй уровень будет иметь примерно такой вид
a[0]=(0,0,0,-1,obj),a[1]=(1,1,0,obj),a[2]=(1,2,0,obj),a[3]=(1,3,0,obj),
a[4]=(1,4,0,obj)..a[12]=(1,12,0,obj);
a[13]=(2,1,1,obj),a[14]=(2,1,2,obj)...a[84]=(2,12,6,obj)
За тем повторяем итерации, до тех пор, пока решение не будет найдено (т.е. услови
[3] не будет выполнено. По массиву можно будет установить ход событий (т.е. если ответ 84, то 84 породил элемент 6, который породил элемент 0. в элементе 6, указано куда вращали).
P.S. При 3D рендеринге, будет 6 × 4 = 24 положения рисунка. Если рендеринг буде
плавным, то нужно будет из одного из 24 положений плавно переходить к другому. Квадрат можно наклеить на куб 4-мя вариантами.
У куба 6 сторон, поэтому для 3D — у вас 24 вариата. Но если оперировать 24-мя вариантами
то задача вращения усложняется, т.к. прийдётся вращать все 20-ть элементов (20 пар и
[2]). Проще вращать 9-елементов 4-мя комбинациями, а +6 комбинаций добавить на фаз
рендеринга в 3Д (6- в зависимости на какой стороне куба мы оказались). Т.е. при рендеринг
будет realside = side+ kubeside* 4 где size — значение одного из 54 елементов, size в пределах [0..3], а kubeside в пределах [0..5] — означает на какой стороне куба мы находимся. После проецирование на 2D проскость, может оказаться что эти 24 варианта перешли в 12 или меньше, но именно цифра 24 дает основу, которая "убирает" хаос. Т.е. задаёт порядок такой, что грань не может быть развёрнута "не туда".
Мне показалось что про 24 комбинации не совсем понятно. Попробую нарисовать
^ ^ ^
< ^ v
> > >
< ^ > ^ ^ > ^ ^ ^ > > >
< v > v v > ^ < < < ^ v
< v > ^ ^ v < < < v v v
< < >
^ ^ >
V V V
это комбинация из 4-х положений на двухмерке. Она домножится на 6 вариантов, потом
что кажую из 6 сторон, прийдётся рендерить на 3D 6-ю способами. А 3D модель будет… над
подумать в чём можно быстро нарисовать… Имеется ввиду что комбинация 0..53 × 4 вариант
развотота × 6 вариантов нахожнения на стороне дадут всегда однозначно 3D-вектор. 0..53 даст однозначно 3D координату вектора, а 24 (4 × 6) даёт разворот, направление вектора трехмерное. Т.е. можно составить массив на 54 координаты, и на 24 вектора направлености — и 3D преобразование гладко пройдет.
Расписываю 24. В 2D у нас будет 4-ре плоских вектора: 0, 90, 180, 270 (поворот
плоскости XY).
В 3Д наложатся такие повороты (XY, XZ, YZ).
^y 2 (0,0,90)
0(0,270,0) 1 (0,0,0) 4(0,90,0) 5(0,0,180)
3 (0,0,270) --x>
Надеюсь, я правильно вектора поворота в градусах расписал. Добавив (0, 90, 180, 270) в первую координату вращения XY — получим 24 комбинации разворота.
5-тый (спинка) — спорный, если его развернуть на 180 по XZ и ещёраз на 180 по Y
— то мы получим "исходное положение обьекта" в почти "зеркальном виде". 5(0,180,0) Не могу сказать, как правильно 5(0,180,0) или так 5(0,180,180) или так 5(0,0,180).
Ускорение. Так как кубик безсмысленно крутить одну сторону влево-вправо и т.п., можно добаить в цикл на 12 условия запрещающие это делать. Например, так
if (level >= 2) /*then*/ {
if (( a[a[i].prev].turn & 14 ) == (turn & 14)) /*then*/{
// Если предыдущую грань двигали ту же самую
if (a[a[i].prev].turn != turn ) /*then*/
continue; //Если Если предыдущую грань двигали в другую сторону
// то не рассматриваем дальше, убрать туда-сюда движение
// сюда код прийдёт, если более одного раза двигаем одну грань
if (a[a[a[i].prev].prev].turn == turn)
continue; // Запрет поворачивать третий раз куб в одну сторону
}
Т.е. в итоге алгоритм будет такой.
Задаём начальное условие
Начало итераций, цикл на 12 движений
Проверяем условия на лишние движения, если такие есть — переходим на 2.
Выполняем движение, готовим a`
Проверяем "граничное условие" что кубик "собран". Если собран — решение найдено.
Проверяем что а' отсутствует в массиве а. Если присутствует — к п 2.
добавляем а' в массив, и переходим к 2.
По завершению цикла создаём ещё одну итерацию.
Почитав про кубик-рубика в википедии, я нашел запись, что за 20 ходов можно найт
решение. Возможно, более эффективным будет поиск вглубину с ограничением на 20. Для такого поиска нужен будет массив на 20, а не на несколько тысяч, как в этом варианте.
Ответ 2
Может кому пригодится:
"Правильное" решение было найдено с помощью кватернионов. Если не нужно плавное вращени
каждой грани, а достаточно фиксированных поворотов (как в 2х-мерной развёртке), то вполн
достаточно таблички из единичных кватернионов. Они описывают все возможные значени
поворотом и обладают приятным преимуществом перед матричными вращениями: перемножаясь бесконечно переходят друг в друга не попадая в так называемые "шарнирные замки". Для плавной 3д-анимации потом так же просто интерполируются между кватернионами конечных положений.
Так же, в качестве оптимизации, была сгенерирована таблица их целочисленного умножения
чтобы не резать производительность плавающей арифметикой и не накапливать ошибку вычислений.
В результате общее время работы практически не пострадало (добавилось 2 сек на 100млн комбинаций)
Комментариев нет:
Отправить комментарий