Известна аккордная клавиатура, состоящая как минимум из четырёх мини-джойстиков (далее «стики»).
В данной статье будет показано, как уменьшить количество стиков до двух, с поддержкой двух режимов: оптимального для сложившейся мобильной экосистемы ПО (с малой нагрузкой на клавиши и активным использованием сенсорного экрана) и оптимального для сложившейся экосистемы ПО на платформе ПК, избежав при этом сложных жестов и использования промежуточных (диагональных) направлений.
Чтобы обеспечить нужное количество комбинаций, учитываются следующие обстоятельства:
1) Какой из двух стиков использовался в аккорде первым.
2) В какое из 4 возможных положений был переключён первый стик аккорда.
3) В какое из 4 возможных положений был переключён второй стик аккорда.
4) Какой из двух стиков был отпущен первым.
Поскольку стики находятся под двумя большими пальцами, движения ими можно выполнять с минимальным временным интервалом, т. е. по суммарному времени использования каждый аккорд приближается к той сумме движений, которая требуется на стандартной QWERTY-клавиатуре, чтобы найти и нажать нужную клавишу. Количество возможных аккордов (2*4*4*2 = 64) также является вполне достаточным.
В качестве предварительной оптимизации были выделены следующие типы аккордов:
1) Одиночное нажатие стика. Если перевести один стик в любое из 4 положений и вернуть его обратно, не нажимая второй стик, можно воспользоваться дополнительными (к главным 64-м) особо быстрыми клавишами. В качестве таковых были выбраны стрелки курсора (для левого стика) и клавиши Esc, Enter, Backspace и пробел для правого стика.
2) Одиночное нажатие с удержанием. Разновидность (1), при которой стик не возвращается обратно до начала автоповтора. На начальной стадии обучения пользователя может представлять определённую сложность, поскольку пользователь может чрезмерно задуматься над тем, в какое положение перевести второй стик, и за это время начнётся автоповтор. Проблема исчезает через несколько часов обучения.
3) Неоконченный аккорд. После перевода второго стика в любое из 4 положений не производится возвращение стиков в исходное положение до начала автоповтора. При этом для автоповтора выбирается не один из двух знаков, доступных в данном состоянии при помощи отпускания левого либо правого стика (обыкновенный аккорд), а третий знак, что даёт дополнительно 32 знака. Кроме этого, поскольку данные знаки не могут быть нажаты одиночно (только в режиме автоповтора), следует рассматривать возможность ограничить количество автоматически набираемых символов, вплоть до одного (что по факту является отключением автоповтора и реализацией типичного режима «нажать и держать, чтобы напечатать альтернативный символ»).
В связи с необходимостью ожидать время автоповтора, с неудобством, аналогичным (2) для неопытных пользователей, а также достаточностью имеющихся комбинаций для алфавитов размером 33 и менее букв, практически данный режим не был реализован.
4) Оконченный аккорд с автоповтором. После отпускания одного из стиков, что даёт окончательный выбор знака из 64 возможных, второй стик удерживается до начала автоповтора.
В качестве окончательной оптимизации были введены так называемые комбо. Суть их в том, что после окончания аккорда можно не отпускать второй стик, а использовать его в качестве первого стика для следующего символа, что уменьшает суммарное количество движений пальцами. Разумеется, для этого нужно выбрать следующий символ раньше, чем начнётся автоповтор текущего, но после некоторой тренировки эта опция становится крайне ценной. Рассмотрим возможные движения подробнее (в качестве первого и второго стиков, разумеется, могут выступать как левый и правый, так и правый и левый).
1) Самое трудоёмкое движение состоит из нажатия первого стика, нажатия второго, отпускания первого и отпускания второго. Каждое движение требует отдельного внимания со стороны моторных отделов мозга, итого цена аккорда составляет 4 движения.
2) Второе по трудоёмкости — это нажатие первого стика, нажатие и отпускание второго и отпускание первого. Нетрудно видеть, что работа вторым стиком производится в виде слитного действия, итого цена аккорда составляет 3.5 движения.
3) Третье — комбо, где отпущенный стик нажимается вторично (в любом направлении), затем он же и отпускается. Цена такой буквы — 1.5 движения (необходимость отпустить затем второй стик не учитывается, потому что «перешла» в комбо из предыдущего символа).
4) Последнее — это комбо, где отпущенный стик нажимается вторично, но отпускается затем не он. Цена — 2 движения.
Для оптимизации раскладки использовались первые найденные в Сети таблицы частотности монограмм и биграмм, там присутствуют сочетания в стиле «ЪУЪ», заставляющие сомневаться в аккуратности используемых для их составления текстов (в лучшем случае эту статистику обеспечили сленг и фэнтези, в худшем — ошибки OCR с печатных текстов или смешение текстовой информации с любой бинарной, например, с разметкой файлов). Такие таблицы должны быть сделаны по одному и тому же входному набору данных, потому что для учёта частотности использования каждой буквы в отсутствие предыдущей (т. е. случаев, когда с неё начинается слово) нужно вычесть из общей частотности буквы все биграммы, в которых она фигурирует в качестве второй.
Для оценки средней сложности символа производилось умножение сложности каждого символа на его частотность во всех 34 возможных способах набора (в качестве начальной буквы в слове и в качестве биграммы вслед за каждой из остальных 33 букв). Сложность каждого символа состоит из числа движений, требующихся для его набора в той или иной биграмме или вне её, и «непривычности положения», выраженной как расстояние между привычным местом символа на клавиатуре ЙЦУКЕНГ машинописного типа (с «Ё» после «ТЬБЮ») и местом на диаграмме-подсказке, взятой с малым весом (т. е. чтобы обеспечить разницу между одинаковыми по среднему числу движений раскладками, но не более).
Для оптимизации использовался метод случайных перестановок с цепочкой длиной 64. До начала оптимизации неалфавитным символам были назначены сравнительно интуитивные положения на диаграмме-подсказке, оставшиеся же 33 места были произвольно заполнены буквами русского алфавита. Далее циклически производилась следующая операция:
1) Запомнить текущую раскладку.
2) Поменять местами две случайные буквы.
3) Вычислить сложность.
4) Если сложность хуже текущей и п. 2 выполнялся менее 64 раз, то вернуться в (2).
5) Если не была достигнута сложность лучше текущей, то вернуться к текущей раскладке.
6) Повторять с (1) до остановки оператором.
Алгоритму позволено «так далеко уходить» в своих поисках от текущего лучшего варианта, чтобы обеспечить гарантированный выход из локальных экстремумов (ценой, разумеется, медленной оптимизации).
Очевидна значительная избыточность этих цепочек, т. к. вероятность того, что очередной шаг увенчается успехом, уменьшается экспоненциально и становится практически нулевой задолго до 64-го. Но поскольку при этом сложность растёт не экспоненциально, а всего лишь линейно, заведомо избыточное значение так и осталось в коде.
Итогом стала небольшая тестовая программа, позволяющая попробовать реальность такого набора как при помощи стандартного геймпада (квадрат кнопок «зелёный-жёлтый-синий-красный» используется в качестве второго стика), так и при помощи клавиатурной эмуляции (WASD + PL:", — последняя, для упрощения написания, требует держать в фокусе окно консоли программы, а не окно GUI, чтобы не смешивались реальные нажатия на клавиатуре и результаты аккордов). Большинство не-символьных клавиш отображаются в логе по первой букве названия, а не выполняют свою реальную функцию (на данной стадии развития проекта это было бы бессмысленной тратой времени).
![image](https://habrastorage.org/webt/mg/9p/w3/mg9pw3jtl9v6swmmirimnatgnic.gif)
Программа имеет три реальные кнопки и диаграмму-подсказку, состоящую из множества «ненажимаемых» кнопок. При наличии более-менее оптимизированной раскладки, лежащей в файле «Current_Layout.hex» в рабочей директории программы, следует в первую очередь загрузить её соответствующей кнопкой, что отобразится на изменении надписей на диаграмме. Для продолжения оптимизации раскладки следует после этого нажать вторую из «длинных» кнопок (отключить этот режим вряд ли удастся, потому что он практически парализует интерфейс, юзабилити снова принесена в жертву вопросу «сделать так или вообще бросить проект»). Запись файла «Generated_Layout.hex» с достигнутыми результатами происходит в тот момент, когда в консоли печатается очередная строчка с информацией о достигнутой сложности. Последняя кнопка переключает программу в режим «мобильной клавиатуры» (и обратно).
Поскольку ПО платформы PC, особенно игры, подразумевает активное использование клавиатуры, режим PC подразумевает наличие дополнительных аппаратных клавиш Ctrl, Shift и Alt, при этом аккорд Caps Lock влияет только на буквенные клавиши, но не на те, где Shift выбирает один из двух символов (например, 5/% или =/+) — для них работает аппаратный Shift (при наличии реального геймпада в качестве такового можно использовать «курки», но это пока не сделано). Переключение языков подразумевается через аппаратный Ctrl+Shift или Alt+Shift, согласно системным настройкам.
Мобильное ПО, включая игры, в основном адаптировано к отсутствию клавиатуры, поэтому мобильный режим отключает учёт состояния Shift и вместо него вводит второе состояние Caps Lock (Caps одноразовый, сбрасывающийся после следующей клавиши), которое (как и основное состояние Caps Lock) распространяется в том числе и на выбор символов из символьного ряда (4/$, 5/%, =/+ и т. д.) Переключение языков подразумевается через аккорд Fn, поскольку использование функциональных клавиш F1-F12 для мобильного ПО нетипично и в любом случае требует подключения внешней клавиатуры через OTG (поскольку реализована только русская раскладка, аккорд Fn в таком качестве реально не используется).
Поскольку проект достиг того уровня, когда может быть оценен широкой аудиторией без дополнительных работ, на этом авторское ведение проекта заканчивается и проект открывается вместе с исходными кодами. Нерешённые на данный момент вопросы:
1) Выбор лицензионно чистого набора статистических данных по монограммам и биграммам для оптимизации раскладки, не вызывающего подозрений в попадании туда разметок текстовых файлов;
2) Ускорение перебора вариантов раскладки, возможно, с коллективным перебором на графических ускорителях;
3) Решение задачи оптимизации для алфавитов менее 33, в первую очередь для английского.
Последний вопрос интересен хотя бы тем, что некоторые символы можно дублировать с тем, чтобы участить их попадание в комбо, что, в свою очередь, ставит вопрос «в данной биграмме участвует та W из левой половины диаграммы, которая идёт обычно после O, или та W из серединки, с которой начинаются всякие What и Where?». Это может ещё более замедлить и без того медленный перебор вариантов раскладки.
Дальнейшая часть статьи представляет собой разбор работы ознакомительной программы по функциям и предназначена исключительно для желающих перехватить эстафету в работе над проектом. Чтобы просто оценить скорость обучения набору стиками, чтение этой части статьи не требуется.
В качестве архитектуры было выбрано WinAPI-приложение в стиле Win32 конца 90-х, на основе стандартного системного оконного класса диалога. Для сборки использовался OpenWatcom 1.9, в качестве редактора диалогов — Resource editor 2.2.0.6c KetilO © 2010 (ЕМНИП бесплатный, но с закрытым исходным кодом).
base_layout.h — базовая раскладка, где все плейсхолдеры будущих букв обозначены буквами «А», всего 33 штуки.
Остальные (цифры и знаки) уже на своих местах.
Хранится в виде массива строк, смысл индексов указан внутри массива, в комментариях.
Первый — это флаг «первым был нажат правый стик» (соответственно, 0 = левый).
Второй и третий индексы — это направление движения первого и второго стика. Причём второй может иметь волшебное значение 4 — «стик не был нажат вовсе» (используется для клавиш курсора, Enter и остальных «сверхбыстрых»).
Четвёртый — флаг «первым был отпущен левый стик», он же — флаг «после отпускания удерживался правый стик». То есть смысл его примерно как у первого индекса: номер стика, который НАЖАТ (0=левый, 1=правый).
Но у него есть дополнительное значение «2», которое используется в смысле «ни один не был отпущен» и там должны храниться как раз те дополнительные 32 символа, которые для набора требуют удержания неоконченного аккорда до начала автоповтора, а также те 8 «сверхбыстрых», которые не требуют нажатия второго стика. Причём первые 32 поля не только пустуют, но и не поддерживаются кодом — не работает этот режим, чтобы проще было учиться (хотя бы после нажатия обоих стиков есть время подумать).
Пятый индекс — обычное значение аккорда, значение с нажатым Shift и значение в режиме Fn (Fn+Shift считается за одно и то же в рамках тестовой проги).
Чему нас учит эта чехарда? Правильно, сразу надо было использовать структуру из структур структур, до того, как это стало явно необходимым, но уже требовало пол-кода отрефакторить. Коммерческий код, конечно, я бы отрефакторил, пет-проект — извините, времени столько нет.
Не используется, не ищите в них смысл. Я не добрался до этой части.
Эта часть писалась раньше всего и несовместима с требованиями, которые выдвинули остальные части. Там вот так лихо объединить первые два индекса в общий уже не катило, а рефакторить было поздно. Эти переменные хранят текущее состояние аккорда и используются как с геймпадом, так и с клавиатурной эмуляцией в режиме демонстрации и обучения.
А вот и этот самый выбор режима. Переключается гуйной кнопкой и виснет так, что для выключения надо или минут 10 мышь держать нажатой (чтобы гуй заметил это), или просто снять прогу нажатием Ctrl+C в консоли. Сойдёт на данном этапе.
Расписано в статье. Кто есть кто — комментарии говорят сами за себя.
Чисто отладочная вещь, нужна для рисования примерно в одном масштабе QWERTY и наложенной на неё диаграммы-подсказки.
А вот эти четыре друга получают на вход номер буквы (отсортированной не по алфавиту, а в порядке «ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЁ») и выдают координаты центра. Нужны не только для рисования отладочной равки, но и для оценки «фактора непривычности положения» в процессе оптимизации.
Собственно, в комментариях всё сказано.
Инициализация, вызывается один раз. Размечает «рыбу» из .H-файла следующими данными:
1) Реальная буква вместо «А», порядок — стартовый (т. е. от балды).
2) Ключевое значение «PA» в третьем (неиспользуемом) поле, предназначенном для неоконченных аккордов с ожиданием автоповтора (32 бонусных знака).
Кроме этого, вносит «заклинание» для набора данного знака в «книгу заклинаний» (она же — перечень аккордов), и вдобавок рисует отладочную равку с наложенной друг на друга обычной клавиатурой и шпаргалкой, чтобы можно было удостовериться, что четвёрка Диаграм-что-то-там возвращает правильные координаты.
Маниакальное использование крошечных полей «чтоб не пропадали» под тот же «PA» как бы намекает, что мысленно я уже в контроллерах клавиатуры с их единицами килобайт памяти.
Эти две функции — «оживлялки» для подсказки, показывают группы кнопок, которые на данный момент выбраны данным сочетанием положений стиков.
В телефоне, наверное, можно рисовать их прямо поверх текста большее или меньшее время, в зависимости от опытности пользователя (совсем опытный вслепую печатает, так что можно вообще не рисовать).
Ещё одна «оживлялка», но рисует не то, что выбрано стиками, а то, что соответствует текущим модификаторам. В том числе Shift, Fn, Caps и так далее.
Для простоты я при наборе просто граблю из кнопки её подпись, так что никакой рассинхронизации между реальным функционалом и этими надписями не может быть в принципе. Тут меня занесло в другую сторону — пожертвовал всем ради упрощения кода и отладки.
Вызывается не только при изменении состояния модификаторов, но и при любой перегруппировке раскладки (допустим, при оптимизации).
Про работу этих двух функций написана половина статьи.
Эта функция получает на вход номер контрола в винапишном диалоге, представляющий собой тот элемент шпаргалки, на котором в конце концов завершился аккорд.
Она грабит его название и добавляет первый символ названия в окошко лога. Некоторые вещи типа бэкспейса я всё-таки реализовал, потому что без них тест уже не тест.
Кроме этого, некоторые аккорды типа Fn или Caps Lock приводят к переключению соответствующих статусов, причём по-разному в пекашном и мобильном режиме.
Тут осталась не написанной (и даже не начатой!) вторая половинка, которая позволила бы практически как-то это всё использовать. Она аналогично должна менять режимы статусных переменных, но вместо ковыряния лога просто генерировать нажатие соответствующей клавиши, понятное для любой той проги, которая сейчас держит фокус ввода. Для этого наверху была та простынка VKeyNames[256][8], которая так и не пригодилась.
Поскольку эмулировать клавиатуру с клавиатуры — очень экзотическая задача для тех случаев, когда основную её часть отгрыз няшный зверь Alot, плюс есть риск чтения сдуру собственных сгенерированных нажатий — этот режим предполагался только для работы по реальному физическому геймпаду.
Вызывается по таймеру, так было проще. Опрашивает клавиатуру (если нет джойстика), в том числе шифт (даже если есть джойстик, но только не в режиме мобилки).
Модифицирует переменные текущего состояния аккорда и если оно «аккорд закончен», «истекло время автоповтора» и т. д. — принимает соответствующие меры по генерации символов.
Отсчитывает счётчик автоповтора (вызывается-то по таймеру, период которого известен!), вызывает перерисовывалку нажатых областей на диаграмме-подсказке (чтобы было видно текущий выбор), а ещё имеет пару отдельных веток для комбо (если аккорд уже закончен, но не отпущен второй стик — переписывает статусы так, чтобы это было начало нового аккорда).
Про это написана вторая половина статьи. Обратите внимание на реликтовые следы попыток делать только одну перестановку — этот вариант тут же засел в локальном экстремуме, из которого можно выбраться только цепочкой перестановок совершенно невменяемой длины.
Если предположить, что существует только одна верная цепочка, то длина 64 — конечно, чепухня. Перебрать все 33! вариантов займёт меньше возрастов Вселенной, чем нащупать вслепую такую цепочку.
Но моё 33-мерное пространственное воображение пасует представить, как именно там могут располагаться экстремумы и какой формы 33-мерные сёдла могут вести из одного в другой.
Возможно, число пригодных вариантов тоже стремительно растёт и мы угадываем не одну цепочку, а любую из огромного списка вариантов. Во всяком случае, цепочки длиной 8 мне реально встречались!
Поэтому для страховки беру максимум 64 — это всего лишь в 8 раз медленнее, чем цепочка в 8.
В принципе, комментарии говорят сами за себя. Обратите внимание отдельно на обработчик событий от джойстика, который костылями приделан сбоку к ProcessKeys(), заменяя её родную GetAsyncKeyState в режиме работы с реальным геймпадом.
Ну, и вызывалка для диалога, предварённая всякими тестовыми и инициализирующими вызовами.
Что-то из этого можно было бы сделать и в обработчике WM_INITDIALOG, если не всё.
InitFreq определён в Freq.h (дурной стиль, я знаю), вместо нормальной таблицы.
Так было проще копипастить нагуглённые частотности, не требовалось переписывать по порядку все строки.
В одном запуске я добился 2.9482, в другом — 2.9106. В любом случае обычно получается около 2.9, что меньше трёх — а если считать обычную клавиатуру за 3 (переместить палец на клавишу, опустить палец, поднять палец), то, с поправкой на «мультипоточность» работы пальцев на обычной клавиатуре, мы уже наступаем ей на пятки!
С другой стороны, значение сложности как будто в доску Гальтона падает, причём в неаккуратно сделанную, с корявым дном. В зависимости от пути, оно прилетает в один из довольно глубоких локальных экстремумов, которые далеко друг от друга отстоят (раскладки получаются очень разные), но имеют почти одинаковую глубину (около 2.9) и перепрыгнуть от одного экстремума в другой по этим причинам шансы околонулевые (всего один раз получилось, так и добился рекорда; жаль, длину цепочки не записал). Но, может быть, где-то прячется ямка глубиной 2.5 и ниже? ;)
Отдельное спасибо всем, дочитавшим сюда, удачи!
В данной статье будет показано, как уменьшить количество стиков до двух, с поддержкой двух режимов: оптимального для сложившейся мобильной экосистемы ПО (с малой нагрузкой на клавиши и активным использованием сенсорного экрана) и оптимального для сложившейся экосистемы ПО на платформе ПК, избежав при этом сложных жестов и использования промежуточных (диагональных) направлений.
Чтобы обеспечить нужное количество комбинаций, учитываются следующие обстоятельства:
1) Какой из двух стиков использовался в аккорде первым.
2) В какое из 4 возможных положений был переключён первый стик аккорда.
3) В какое из 4 возможных положений был переключён второй стик аккорда.
4) Какой из двух стиков был отпущен первым.
Поскольку стики находятся под двумя большими пальцами, движения ими можно выполнять с минимальным временным интервалом, т. е. по суммарному времени использования каждый аккорд приближается к той сумме движений, которая требуется на стандартной QWERTY-клавиатуре, чтобы найти и нажать нужную клавишу. Количество возможных аккордов (2*4*4*2 = 64) также является вполне достаточным.
В качестве предварительной оптимизации были выделены следующие типы аккордов:
1) Одиночное нажатие стика. Если перевести один стик в любое из 4 положений и вернуть его обратно, не нажимая второй стик, можно воспользоваться дополнительными (к главным 64-м) особо быстрыми клавишами. В качестве таковых были выбраны стрелки курсора (для левого стика) и клавиши Esc, Enter, Backspace и пробел для правого стика.
2) Одиночное нажатие с удержанием. Разновидность (1), при которой стик не возвращается обратно до начала автоповтора. На начальной стадии обучения пользователя может представлять определённую сложность, поскольку пользователь может чрезмерно задуматься над тем, в какое положение перевести второй стик, и за это время начнётся автоповтор. Проблема исчезает через несколько часов обучения.
3) Неоконченный аккорд. После перевода второго стика в любое из 4 положений не производится возвращение стиков в исходное положение до начала автоповтора. При этом для автоповтора выбирается не один из двух знаков, доступных в данном состоянии при помощи отпускания левого либо правого стика (обыкновенный аккорд), а третий знак, что даёт дополнительно 32 знака. Кроме этого, поскольку данные знаки не могут быть нажаты одиночно (только в режиме автоповтора), следует рассматривать возможность ограничить количество автоматически набираемых символов, вплоть до одного (что по факту является отключением автоповтора и реализацией типичного режима «нажать и держать, чтобы напечатать альтернативный символ»).
В связи с необходимостью ожидать время автоповтора, с неудобством, аналогичным (2) для неопытных пользователей, а также достаточностью имеющихся комбинаций для алфавитов размером 33 и менее букв, практически данный режим не был реализован.
4) Оконченный аккорд с автоповтором. После отпускания одного из стиков, что даёт окончательный выбор знака из 64 возможных, второй стик удерживается до начала автоповтора.
В качестве окончательной оптимизации были введены так называемые комбо. Суть их в том, что после окончания аккорда можно не отпускать второй стик, а использовать его в качестве первого стика для следующего символа, что уменьшает суммарное количество движений пальцами. Разумеется, для этого нужно выбрать следующий символ раньше, чем начнётся автоповтор текущего, но после некоторой тренировки эта опция становится крайне ценной. Рассмотрим возможные движения подробнее (в качестве первого и второго стиков, разумеется, могут выступать как левый и правый, так и правый и левый).
1) Самое трудоёмкое движение состоит из нажатия первого стика, нажатия второго, отпускания первого и отпускания второго. Каждое движение требует отдельного внимания со стороны моторных отделов мозга, итого цена аккорда составляет 4 движения.
2) Второе по трудоёмкости — это нажатие первого стика, нажатие и отпускание второго и отпускание первого. Нетрудно видеть, что работа вторым стиком производится в виде слитного действия, итого цена аккорда составляет 3.5 движения.
3) Третье — комбо, где отпущенный стик нажимается вторично (в любом направлении), затем он же и отпускается. Цена такой буквы — 1.5 движения (необходимость отпустить затем второй стик не учитывается, потому что «перешла» в комбо из предыдущего символа).
4) Последнее — это комбо, где отпущенный стик нажимается вторично, но отпускается затем не он. Цена — 2 движения.
Для оптимизации раскладки использовались первые найденные в Сети таблицы частотности монограмм и биграмм, там присутствуют сочетания в стиле «ЪУЪ», заставляющие сомневаться в аккуратности используемых для их составления текстов (в лучшем случае эту статистику обеспечили сленг и фэнтези, в худшем — ошибки OCR с печатных текстов или смешение текстовой информации с любой бинарной, например, с разметкой файлов). Такие таблицы должны быть сделаны по одному и тому же входному набору данных, потому что для учёта частотности использования каждой буквы в отсутствие предыдущей (т. е. случаев, когда с неё начинается слово) нужно вычесть из общей частотности буквы все биграммы, в которых она фигурирует в качестве второй.
Для оценки средней сложности символа производилось умножение сложности каждого символа на его частотность во всех 34 возможных способах набора (в качестве начальной буквы в слове и в качестве биграммы вслед за каждой из остальных 33 букв). Сложность каждого символа состоит из числа движений, требующихся для его набора в той или иной биграмме или вне её, и «непривычности положения», выраженной как расстояние между привычным местом символа на клавиатуре ЙЦУКЕНГ машинописного типа (с «Ё» после «ТЬБЮ») и местом на диаграмме-подсказке, взятой с малым весом (т. е. чтобы обеспечить разницу между одинаковыми по среднему числу движений раскладками, но не более).
Для оптимизации использовался метод случайных перестановок с цепочкой длиной 64. До начала оптимизации неалфавитным символам были назначены сравнительно интуитивные положения на диаграмме-подсказке, оставшиеся же 33 места были произвольно заполнены буквами русского алфавита. Далее циклически производилась следующая операция:
1) Запомнить текущую раскладку.
2) Поменять местами две случайные буквы.
3) Вычислить сложность.
4) Если сложность хуже текущей и п. 2 выполнялся менее 64 раз, то вернуться в (2).
5) Если не была достигнута сложность лучше текущей, то вернуться к текущей раскладке.
6) Повторять с (1) до остановки оператором.
Алгоритму позволено «так далеко уходить» в своих поисках от текущего лучшего варианта, чтобы обеспечить гарантированный выход из локальных экстремумов (ценой, разумеется, медленной оптимизации).
Очевидна значительная избыточность этих цепочек, т. к. вероятность того, что очередной шаг увенчается успехом, уменьшается экспоненциально и становится практически нулевой задолго до 64-го. Но поскольку при этом сложность растёт не экспоненциально, а всего лишь линейно, заведомо избыточное значение так и осталось в коде.
Итогом стала небольшая тестовая программа, позволяющая попробовать реальность такого набора как при помощи стандартного геймпада (квадрат кнопок «зелёный-жёлтый-синий-красный» используется в качестве второго стика), так и при помощи клавиатурной эмуляции (WASD + PL:", — последняя, для упрощения написания, требует держать в фокусе окно консоли программы, а не окно GUI, чтобы не смешивались реальные нажатия на клавиатуре и результаты аккордов). Большинство не-символьных клавиш отображаются в логе по первой букве названия, а не выполняют свою реальную функцию (на данной стадии развития проекта это было бы бессмысленной тратой времени).
![image](https://habrastorage.org/webt/mg/9p/w3/mg9pw3jtl9v6swmmirimnatgnic.gif)
Программа имеет три реальные кнопки и диаграмму-подсказку, состоящую из множества «ненажимаемых» кнопок. При наличии более-менее оптимизированной раскладки, лежащей в файле «Current_Layout.hex» в рабочей директории программы, следует в первую очередь загрузить её соответствующей кнопкой, что отобразится на изменении надписей на диаграмме. Для продолжения оптимизации раскладки следует после этого нажать вторую из «длинных» кнопок (отключить этот режим вряд ли удастся, потому что он практически парализует интерфейс, юзабилити снова принесена в жертву вопросу «сделать так или вообще бросить проект»). Запись файла «Generated_Layout.hex» с достигнутыми результатами происходит в тот момент, когда в консоли печатается очередная строчка с информацией о достигнутой сложности. Последняя кнопка переключает программу в режим «мобильной клавиатуры» (и обратно).
Поскольку ПО платформы PC, особенно игры, подразумевает активное использование клавиатуры, режим PC подразумевает наличие дополнительных аппаратных клавиш Ctrl, Shift и Alt, при этом аккорд Caps Lock влияет только на буквенные клавиши, но не на те, где Shift выбирает один из двух символов (например, 5/% или =/+) — для них работает аппаратный Shift (при наличии реального геймпада в качестве такового можно использовать «курки», но это пока не сделано). Переключение языков подразумевается через аппаратный Ctrl+Shift или Alt+Shift, согласно системным настройкам.
Мобильное ПО, включая игры, в основном адаптировано к отсутствию клавиатуры, поэтому мобильный режим отключает учёт состояния Shift и вместо него вводит второе состояние Caps Lock (Caps одноразовый, сбрасывающийся после следующей клавиши), которое (как и основное состояние Caps Lock) распространяется в том числе и на выбор символов из символьного ряда (4/$, 5/%, =/+ и т. д.) Переключение языков подразумевается через аккорд Fn, поскольку использование функциональных клавиш F1-F12 для мобильного ПО нетипично и в любом случае требует подключения внешней клавиатуры через OTG (поскольку реализована только русская раскладка, аккорд Fn в таком качестве реально не используется).
Поскольку проект достиг того уровня, когда может быть оценен широкой аудиторией без дополнительных работ, на этом авторское ведение проекта заканчивается и проект открывается вместе с исходными кодами. Нерешённые на данный момент вопросы:
1) Выбор лицензионно чистого набора статистических данных по монограммам и биграммам для оптимизации раскладки, не вызывающего подозрений в попадании туда разметок текстовых файлов;
2) Ускорение перебора вариантов раскладки, возможно, с коллективным перебором на графических ускорителях;
3) Решение задачи оптимизации для алфавитов менее 33, в первую очередь для английского.
Последний вопрос интересен хотя бы тем, что некоторые символы можно дублировать с тем, чтобы участить их попадание в комбо, что, в свою очередь, ставит вопрос «в данной биграмме участвует та W из левой половины диаграммы, которая идёт обычно после O, или та W из серединки, с которой начинаются всякие What и Where?». Это может ещё более замедлить и без того медленный перебор вариантов раскладки.
Дальнейшая часть статьи представляет собой разбор работы ознакомительной программы по функциям и предназначена исключительно для желающих перехватить эстафету в работе над проектом. Чтобы просто оценить скорость обучения набору стиками, чтение этой части статьи не требуется.
В качестве архитектуры было выбрано WinAPI-приложение в стиле Win32 конца 90-х, на основе стандартного системного оконного класса диалога. Для сборки использовался OpenWatcom 1.9, в качестве редактора диалогов — Resource editor 2.2.0.6c KetilO © 2010 (ЕМНИП бесплатный, но с закрытым исходным кодом).
#include <conio.h>
#include <iostream.h>
#include <fstream.h>
#include <windows.h>
#include <math.h>
#include "base_layout.h"
#include "Freq.h"
base_layout.h — базовая раскладка, где все плейсхолдеры будущих букв обозначены буквами «А», всего 33 штуки.
Остальные (цифры и знаки) уже на своих местах.
Хранится в виде массива строк, смысл индексов указан внутри массива, в комментариях.
Первый — это флаг «первым был нажат правый стик» (соответственно, 0 = левый).
Второй и третий индексы — это направление движения первого и второго стика. Причём второй может иметь волшебное значение 4 — «стик не был нажат вовсе» (используется для клавиш курсора, Enter и остальных «сверхбыстрых»).
Четвёртый — флаг «первым был отпущен левый стик», он же — флаг «после отпускания удерживался правый стик». То есть смысл его примерно как у первого индекса: номер стика, который НАЖАТ (0=левый, 1=правый).
Но у него есть дополнительное значение «2», которое используется в смысле «ни один не был отпущен» и там должны храниться как раз те дополнительные 32 символа, которые для набора требуют удержания неоконченного аккорда до начала автоповтора, а также те 8 «сверхбыстрых», которые не требуют нажатия второго стика. Причём первые 32 поля не только пустуют, но и не поддерживаются кодом — не работает этот режим, чтобы проще было учиться (хотя бы после нажатия обоих стиков есть время подумать).
Пятый индекс — обычное значение аккорда, значение с нажатым Shift и значение в режиме Fn (Fn+Shift считается за одно и то же в рамках тестовой проги).
Чему нас учит эта чехарда? Правильно, сразу надо было использовать структуру из структур структур, до того, как это стало явно необходимым, но уже требовало пол-кода отрефакторить. Коммерческий код, конечно, я бы отрефакторил, пет-проект — извините, времени столько нет.
static const char VKeyNames[256][8]={/* */};
Не используется, не ищите в них смысл. Я не добрался до этой части.
int FirstPressed, //0 -- none yet, 1234 -- WASD, 5678 -- PL;'
SecondPressed, //0 -- none yet, 1234 -- WASD, 5678 -- PL;'
FirstReleased; //0 -- none yet, 1 -- WASD, 5 -- PL;'
Эта часть писалась раньше всего и несовместима с требованиями, которые выдвинули остальные части. Там вот так лихо объединить первые два индекса в общий уже не катило, а рефакторить было поздно. Эти переменные хранят текущее состояние аккорда и используются как с геймпадом, так и с клавиатурной эмуляцией в режиме демонстрации и обучения.
int OperationMode = 0; //0 -- testing layout, 1 -- trying to optimise layout;
А вот и этот самый выбор режима. Переключается гуйной кнопкой и виснет так, что для выключения надо или минут 10 мышь держать нажатой (чтобы гуй заметил это), или просто снять прогу нажатием Ctrl+C в консоли. Сойдёт на данном этапе.
int DeviceMode = 1; //0 == Mobile (assuming sticks only), 1 == PC (assuming hardware Shift, Ctrl and Alt modifiers for fingers, sticks for thumbs).
int CapsLock = 0; //0 == None, 1 == Once (only for Mobile mode), 2 == Lock (does not affect Numeric keys in PC mode).
int FnMode = 0; //0 == None, 1 == Once, maybe also do 2 == Lock?
int HardwareShiftPressed = 0;
Расписано в статье. Кто есть кто — комментарии говорят сами за себя.
HWND hWndT;
static char Test_Diagram[256][512]={0};
void Test_DrawRect(int CenterX, int CenterY, int L, int D, int R, int U)
{
int X, Y;
for (X=CenterX+L; X<=CenterX+R; X++)
for (Y=CenterY+D; Y<=CenterY+U; Y+=U-D)
if (X>0&&X<512&&Y>0&&Y<256)Test_Diagram[Y][X]+=63;
for (X=CenterX+L; X<=CenterX+R; X+=R-L)
for (Y=CenterY+D; Y<=CenterY+U; Y++)
if (X>0&&X<512&&Y>0&&Y<256)Test_Diagram[Y][X]+=63;
}
Чисто отладочная вещь, нужна для рисования примерно в одном масштабе QWERTY и наложенной на неё диаграммы-подсказки.
int DiagramStickX (int LR, int F, int S, int RL) //Компактная форма диаграммы раскладки стиков. Центры "окошек" с буквами.
{
int X=1;
if (LR) X+=28;
if (F==3) X+=16;
else if (F==0 || F==2) X+=8;
if (S==3) X+=8;
else if (S==0 || S==2) X+=4;
if (RL) X+=2;
return X*2;
}
int DiagramStickY (int LR, int F, int S, int RL) //LR для галочки
{
int Y=1;
if (F==2) Y+=8;
else if (F==1 || F==3) Y+=4;
if (S==2) Y+=4;
else if (S==1 || S==3) Y+=2;
return Y*2;
}
int DiagramKeyX (int Key) //Диаграмма раскладки обычной клавиатуры (накладывается поверх диаграммы стиков).
{
int X=4;
if (Key>11)
{
Key-=12;
X++;
if (Key>10)
{
Key-=11;
X++;
}
}
X+=Key*3;
return X*2+1;
}
int DiagramKeyY (int Key)
{
int Y=6;
if (Key>11)
{
Key-=12;
Y+=2;
if (Key>10)
{
Key-=11;
Y+=2;
}
}
return Y*2;
}
А вот эти четыре друга получают на вход номер буквы (отсортированной не по алфавиту, а в порядке «ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЁ») и выдают координаты центра. Нужны не только для рисования отладочной равки, но и для оценки «фактора непривычности положения» в процессе оптимизации.
char Russian[2][34]={"йцукенгшщзхъфывапролджэячсмитьбюё", "ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЁ"};
int Spellcastings[33][4]={0}; //Соответствующие каждой букве (отсортированы не по алфавиту, а по ЙЦУКЕНГШЩЗХЪФЫ...) "движения волшебными палочками" для её набора.
//Флаг "Первым двигается правый(1) или левый(0)".
//Первое движение (0123=ULDR)
//Второе движение (то же самое)
//Который стик НЕ отпускать первым (правый=1, левый=0).
//На диаграмме слева отображены знаки, набираемые по отпускании правого стика первым
//(психологически и интуитивно знак кажется "примагниченным" к тому стику, который мы УДЕРЖИВАЕМ).
//Поэтому LR Flag (кто первый нажат) -> First -> Second -> RL Flag (кто первый отпущен).
Собственно, в комментариях всё сказано.
void InitNationalFont(char QwertyLayout[2][34]) //Для учёта оптимизации клавиш по принципу "привычности", клавиши сгруппированы в Qwerty.
{ //Для алфавитов меньшего размера придётся как-то нулями забивать. Большего -- использовать "извратный S/RL", потому что места на "клавиатуре" больше нет.
int Key=0;
for (int LR=0; LR<2; LR++)
for (int F=0; F<4; F++)
for (int S=0; S<4; S++)
for (int RL=0; RL<2; RL++)
if (KeyNames[LR][F][S][RL][0][0]=='A' && KeyNames[LR][F][S][RL][0][1]==0) //"Alphabetic"
{
KeyNames[LR][F][S][RL][0][0]=QwertyLayout[0][Key];
KeyNames[LR][F][S][RL][1][0]=QwertyLayout[1][Key];
KeyNames[LR][F][S][RL][1][1]=0;
strcpy (KeyNames[LR][F][S][RL][2], "PA"); //a "magical" value for "permutable alphabetical"
Test_DrawRect(DiagramStickX(LR,F,S,RL)*6 - 36,DiagramStickY(LR,F,S,RL)*6, -9,-12,9,12);
Test_DrawRect(DiagramKeyX (Key) *6 - 36,DiagramKeyY (Key) *6, -15,-4,15,4);
Spellcastings[Key][0]=LR;
Spellcastings[Key][1]=F;
Spellcastings[Key][2]=S;
Spellcastings[Key][3]=RL;
Key++;
}
cout<<Key<<" of 33 used"<<endl;
fstream Dia;
Dia.open ("Test512x256x8.raw", ios::out|ios::binary);
Dia.write (Test_Diagram[0], sizeof (Test_Diagram));
Dia.close();
}
Инициализация, вызывается один раз. Размечает «рыбу» из .H-файла следующими данными:
1) Реальная буква вместо «А», порядок — стартовый (т. е. от балды).
2) Ключевое значение «PA» в третьем (неиспользуемом) поле, предназначенном для неоконченных аккордов с ожиданием автоповтора (32 бонусных знака).
Кроме этого, вносит «заклинание» для набора данного знака в «книгу заклинаний» (она же — перечень аккордов), и вдобавок рисует отладочную равку с наложенной друг на друга обычной клавиатурой и шпаргалкой, чтобы можно было удостовериться, что четвёрка Диаграм-что-то-там возвращает правильные координаты.
Маниакальное использование крошечных полей «чтоб не пропадали» под тот же «PA» как бы намекает, что мысленно я уже в контроллерах клавиатуры с их единицами килобайт памяти.
BOOL Status (int First, int Second, int Released)
{
if (!FirstPressed)
{
return FALSE;
} else if (!SecondPressed) {
if (FirstPressed == First) return TRUE;
return FALSE;
} else if (!FirstReleased) {
if (FirstPressed == First && SecondPressed == Second) return TRUE;
return FALSE;
}
if (FirstPressed == First && SecondPressed == Second && FirstReleased == Released) return TRUE;
return FALSE;
}
void DrawState()
{
for (int F=1; F<=8; F++)
{
SendMessage(GetDlgItem(hWndT, F*100), BM_SETSTATE, Status(F, 0, 0), 0);
for (int S=1; S<=8; S++)
for (int R=1; R<=5; R+=4) SendMessage(GetDlgItem(hWndT, F*100+S*10+R), BM_SETSTATE, Status(F, S, R), 0);
}
}
Эти две функции — «оживлялки» для подсказки, показывают группы кнопок, которые на данный момент выбраны данным сочетанием положений стиков.
В телефоне, наверное, можно рисовать их прямо поверх текста большее или меньшее время, в зависимости от опытности пользователя (совсем опытный вслепую печатает, так что можно вообще не рисовать).
void DrawNames()
{
for (int F=0; F<8; F++)
{
SetDlgItemText(hWndT, (F+1)*100, KeyNames[F/4][F%4][4][2][0]);
for (int S=0; S<8; S++)
for (int R=0; R<2; R++)
{
if (FnMode && KeyNames[F/4][F%4][S%4][1-R][2][0] && strcmp (KeyNames[F/4][F%4][S%4][1-R][2], "PA")) //Режим Fn, вдобавок у клавиши есть Fn-значение, и это значение не является "магической константой", отличающей буквы от всего остального
SetDlgItemText(hWndT, (F+1)*100 + (S+1)*10 + 1+R*4, KeyNames[F/4][F%4][S%4][1-R][2]);
else if ( (HardwareShiftPressed||CapsLock==1) && KeyNames[F/4][F%4][S%4][1-R][1][0] || //Нажат аппаратый шифт (пека) или программный (мобила), вдобавок у клавиши есть такое значение.
CapsLock==2 && ( !strcmp(KeyNames[F/4][F%4][S%4][1-R][2],"PA") || !DeviceMode&&KeyNames[F/4][F%4][S%4][1-R][1][0] ) ) //Или включён режим Caps Lock, а клавиша или чисто буквенная, или у нас режим мобилы (в нём в верхний регистр переходит всё, что имеет таковой).
SetDlgItemText(hWndT, (F+1)*100 + (S+1)*10 + 1+R*4, KeyNames[F/4][F%4][S%4][1-R][1]);
else SetDlgItemText(hWndT, (F+1)*100 + (S+1)*10 + 1+R*4, KeyNames[F/4][F%4][S%4][1-R][0]);
}
}
}
Ещё одна «оживлялка», но рисует не то, что выбрано стиками, а то, что соответствует текущим модификаторам. В том числе Shift, Fn, Caps и так далее.
Для простоты я при наборе просто граблю из кнопки её подпись, так что никакой рассинхронизации между реальным функционалом и этими надписями не может быть в принципе. Тут меня занесло в другую сторону — пожертвовал всем ради упрощения кода и отладки.
Вызывается не только при изменении состояния модификаторов, но и при любой перегруппировке раскладки (допустим, при оптимизации).
float DistFactor=0; //Специально, чтобы с N/0 рухнуло в случае забывчивости.
float Distance (int Key) //Расстояние между положениями буквы в ЙЦУКЕНГ и на диаграмме аккордов.
{
float X=DiagramStickX(Spellcastings[Key][0],Spellcastings[Key][1],Spellcastings[Key][2],Spellcastings[Key][3]);
X-=DiagramKeyX(Key);
float Y=DiagramStickY(Spellcastings[Key][0],Spellcastings[Key][1],Spellcastings[Key][2],Spellcastings[Key][3]);
Y-=DiagramKeyY(Key);
return sqrt(X*X+Y*Y);
}
int CharsFactor=0;
float Difficulty (int Prev, int Key) //Сложность каждой буквы (в движениях), с учётом того, что могла быть нажата предыдущая.
{
float Diff = Distance (Key) / DistFactor; //Расстояние от буквы до её места в привычном ЙЦУКЕНГ оценивается по остаточному принципу, с ценой в тысячную долю.
//Это позволяет из двух раскладок, у которых суммарная сложность движений строго равна, выбрать более привычную внешне.
//Случаи, когда комбо нет (набираем с нуля): -1 == вообще нет предыдущего (слово началось с Key), или от предыдущего символа остался нажатым не тот стик, который нужен, или тот, но нажат не в ту сторону.
if (Prev < 0 || Spellcastings[Key][0]!=Spellcastings[Prev][3] || Spellcastings[Key][1] != Spellcastings[Prev][1 + (Spellcastings[Prev][0]+Spellcastings[Prev][3])%2 ] )
{
if (Spellcastings[Key][0] == Spellcastings[Key][3]) //Первый нажали, второй нажали и сразу отпустили, первый отпустили -- 3.5 движения.
{
//LRrl and RLlr costs 3.5 finger steps
Diff += 3.5;
} else { //Первый нажали, второй нажали, первый отпустили, второй отпустили -- 4 движения.
//LRlr and RLrl costs 4 finger steps
Diff += 4.0;
}
//Случаи, когда есть комбо -- от предыдущего символа остался нажатым именно тот стик, который нужен для следующего.
} else {
//Transition from LRrl/RLrl to LRrl costs 1.5 finger steps.
//Transition from RLlr/LRlr to RLlr costs 1.5 finger steps.
//Transition from LRrl/RLrl to LRlr costs 2 finger steps.
//Transition from RLlr/LRlr to RLrl costs 2 finger steps.
if (Spellcastings[Key][0] == Spellcastings[Key][3]) Diff+=1.5; else Diff+=2.0;
}
return Diff;
}
Про работу этих двух функций написана половина статьи.
void HitVKey(int Key)
{
char CurText[65536];
// if (KeyEmu)
// { //Работает чисто на уровне "показать реализуемость", ну и хрен бы с ним. Тут мы всё делаем руками над окном ввода.
int CurLen;
GetDlgItemText(hWndT, 1001, CurText, 65500);
CurLen=strlen(CurText);
GetDlgItemText(hWndT, Key, CurText+CurLen, 8);
//ToDo here: process backspace, enter etc
if (!strcmp(CurText+CurLen,"BkSp")) if (!CurLen) return; else CurLen-=2;
if (!strcmp(CurText+CurLen,"Fn"))
{
FnMode = !FnMode;
DrawNames();
} else if (FnMode && Key)
{
FnMode=0;
DrawNames();
}
if (!strcmp(CurText+CurLen,"Caps"))
{
if (DeviceMode) CapsLock = (!CapsLock)*2;
else CapsLock = (CapsLock+1)%3;
DrawNames();
} else if (CapsLock==1 && Key) //Состояние "заглавные один раз" есть только в режиме "мобильная клавиатура".
{
CapsLock=0;
DrawNames();
}
if (!strcmp(CurText+CurLen,"Space")) CurText[CurLen]=' ';
CurText[CurLen+1]=0;
SetDlgItemText(hWndT, 1001, CurText);
// } else { //Это уже более функциональная половинка -- тут мы реально с джойстика эмулируем нажатия клавиш, которые могут где-то использоваться.
// GetDlgItemText(hWndT, Key, CurText, 8);
//VOID keybd_event(
// BYTE bVk, // virtual-key code
//BYTE bScan, // hardware scan code
// DWORD dwFlags, // flags specifying various function options
// DWORD dwExtraInfo // additional data associated with keystroke
//);
// }
}
Эта функция получает на вход номер контрола в винапишном диалоге, представляющий собой тот элемент шпаргалки, на котором в конце концов завершился аккорд.
Она грабит его название и добавляет первый символ названия в окошко лога. Некоторые вещи типа бэкспейса я всё-таки реализовал, потому что без них тест уже не тест.
Кроме этого, некоторые аккорды типа Fn или Caps Lock приводят к переключению соответствующих статусов, причём по-разному в пекашном и мобильном режиме.
Тут осталась не написанной (и даже не начатой!) вторая половинка, которая позволила бы практически как-то это всё использовать. Она аналогично должна менять режимы статусных переменных, но вместо ковыряния лога просто генерировать нажатие соответствующей клавиши, понятное для любой той проги, которая сейчас держит фокус ввода. Для этого наверху была та простынка VKeyNames[256][8], которая так и не пригодилась.
Поскольку эмулировать клавиатуру с клавиатуры — очень экзотическая задача для тех случаев, когда основную её часть отгрыз няшный зверь Alot, плюс есть риск чтения сдуру собственных сгенерированных нажатий — этот режим предполагался только для работы по реальному физическому геймпаду.
int AutoRepeat;
int KeyEmu=1;
int ULDRl, ULDRr;
void ProcessKeys()
{
if (KeyEmu)
{
ULDRl=0;
if (GetAsyncKeyState(0x57)&0x8000) ULDRl=1;
if (GetAsyncKeyState(0x41)&0x8000) ULDRl=2;
if (GetAsyncKeyState(0x53)&0x8000) ULDRl=3;
if (GetAsyncKeyState(0x44)&0x8000) ULDRl=4;
ULDRr=0;
if (GetAsyncKeyState(0x50)&0x8000) ULDRr=1;
if (GetAsyncKeyState(0x4C)&0x8000) ULDRr=2;
if (GetAsyncKeyState(0xBA)&0x8000) ULDRr=3;
if (GetAsyncKeyState(0xDE)&0x8000) ULDRr=4;
}
if (DeviceMode)
{
int ShiftState;
if (GetAsyncKeyState(VK_SHIFT)&0x8000) ShiftState=1;
if (ShiftState != HardwareShiftPressed)
{
HardwareShiftPressed = ShiftState;
DrawNames();
}
}
//cout<<ULDRl<<" "<<ULDRr<<endl;
if (!FirstPressed && ULDRl) {FirstPressed=ULDRl; AutoRepeat=0;}
else if (!FirstPressed && ULDRr) {FirstPressed=ULDRr+4; AutoRepeat=0;}
else if (FirstPressed && !SecondPressed && FirstPressed<5 && ULDRr) SecondPressed=ULDRr+4;
else if (FirstPressed>4 && !SecondPressed && ULDRl) SecondPressed=ULDRl;
else if (FirstPressed && SecondPressed && !FirstReleased && !ULDRl) {FirstReleased=1; HitVKey(FirstPressed*100+SecondPressed*10+FirstReleased); AutoRepeat=0;}
else if (FirstPressed && SecondPressed && !FirstReleased && !ULDRr) {FirstReleased=5; HitVKey(FirstPressed*100+SecondPressed*10+FirstReleased); AutoRepeat=0;}
else if (FirstPressed && SecondPressed && FirstReleased == 1 && ULDRl) {if (SecondPressed>4) FirstPressed=SecondPressed; SecondPressed=ULDRl ; FirstReleased=0;} //fast re-combo
else if (FirstPressed && SecondPressed && FirstReleased == 5 && ULDRr) {if (SecondPressed<5) FirstPressed=SecondPressed; SecondPressed=ULDRr+4; FirstReleased=0;} //fast re-combo
if (!ULDRl&&!ULDRr)
{
if (!SecondPressed) HitVKey(FirstPressed*100);
FirstPressed=SecondPressed=FirstReleased=0;
}
if (FirstPressed && !SecondPressed && AutoRepeat>50) HitVKey(FirstPressed*100);
if (FirstPressed && SecondPressed && FirstReleased && AutoRepeat>50) HitVKey(FirstPressed*100+SecondPressed*10+FirstReleased);
AutoRepeat++;
//cout<<FirstPressed<<" "<<SecondPressed<<" "<<FirstReleased<<endl;
DrawState();
}
Вызывается по таймеру, так было проще. Опрашивает клавиатуру (если нет джойстика), в том числе шифт (даже если есть джойстик, но только не в режиме мобилки).
Модифицирует переменные текущего состояния аккорда и если оно «аккорд закончен», «истекло время автоповтора» и т. д. — принимает соответствующие меры по генерации символов.
Отсчитывает счётчик автоповтора (вызывается-то по таймеру, период которого известен!), вызывает перерисовывалку нажатых областей на диаграмме-подсказке (чтобы было видно текущий выбор), а ещё имеет пару отдельных веток для комбо (если аккорд уже закончен, но не отпущен второй стик — переписывает статусы так, чтобы это было начало нового аккорда).
float BestDifficulty = 1E30;
int Current[33][4];
void Permutate ()
{
float Total;
int Char, Prev; //Рассматриваемая текущая буква алфавита и предыдущая буква (предыдущая может быть -1, если её нет и слово началось с текущей).
int CastA[4], CastB[4], A, B;
memcpy (Current, Spellcastings, sizeof (Current));
for (int AtOnce = 0; AtOnce < 64; AtOnce++)
{
Total=0;
if (BestDifficulty < 100500) //Грязный, мерзкий полуночный хак. Суть: первый пуск инициализирует сложность раскладки в её изначальном виде, ничего не пермутируя.
{
//Attempting to swap two random symbols;
// int A = rand()*33/(RAND_MAX+1);
// int B = rand()*33/(RAND_MAX+1);
// while (A==B) B = rand()*33/(RAND_MAX+1);
A = (rand() + timeGetTime())%33;
B = (rand() + timeGetTime())%33;
memcpy (CastA, Spellcastings[A], 4*sizeof(int));
memcpy (CastB, Spellcastings[B], 4*sizeof(int));
memcpy (Spellcastings[A], CastB, 4*sizeof(int));
memcpy (Spellcastings[B], CastA, 4*sizeof(int));
}
//Calculating difficulty;
for (Char=0; Char<33; Char++)
{
int Monogram = Single[Char];
//Сложность состоит из "движений" (единицы) и "узнавания" (тысячные доли по остаточному принципу, если по движениям вышло баш на баш).
//Чтобы понять, насколько критична Сложность данной буквы, посмотрим все её случаи применения: все варианты 33 других букв перед ней и в качестве 34-го -- вариант, что с неё началось слово.
for (Prev=0; Prev<33; Prev++)
{
Total += Difficulty (Prev, Char) * (float)(Pairs[Prev][Char]) / (float)CharsFactor; //Сложность набора буквы после каждой другой буквы, умноженная на относительную частотность таких биграмм.
Monogram-=Pairs[Prev][Char];
}
if (Monogram<0)
{
cout<<"Колобок повесился!"<<endl;
cout<<"Произошла невозможная ошибка, которая не может происходить никогда: буква в биграммах встречается в качестве второй буквы чаще, чем она вообще встречается в языке. Ваши статистические таблицы есть хлам, найдите более достоверный источник ;)"<<endl;
for(;;);
}
Total += Difficulty (-1, Char) * (float)Monogram / (float)CharsFactor; //Оставшиеся случаи применения буквы, не вошедшие в биграммы -- как раз начальная буква слова.
}
if (Total<BestDifficulty) break; //Success!!!
}
//cout<<A<<" "<<B<<" "<<Total<<" "<<BestDifficulty<<endl;
if (Total>BestDifficulty)
{
//Revert swapped keys!
// memcpy (Spellcastings[A], CastA, 4*sizeof(int));
// memcpy (Spellcastings[B], CastB, 4*sizeof(int));
memcpy (Spellcastings, Current, sizeof (Current));
} else BestDifficulty = Total;
}
Про это написана вторая половина статьи. Обратите внимание на реликтовые следы попыток делать только одну перестановку — этот вариант тут же засел в локальном экстремуме, из которого можно выбраться только цепочкой перестановок совершенно невменяемой длины.
Если предположить, что существует только одна верная цепочка, то длина 64 — конечно, чепухня. Перебрать все 33! вариантов займёт меньше возрастов Вселенной, чем нащупать вслепую такую цепочку.
Но моё 33-мерное пространственное воображение пасует представить, как именно там могут располагаться экстремумы и какой формы 33-мерные сёдла могут вести из одного в другой.
Возможно, число пригодных вариантов тоже стремительно растёт и мы угадываем не одну цепочку, а любую из огромного списка вариантов. Во всяком случае, цепочки длиной 8 мне реально встречались!
Поэтому для страховки беру максимум 64 — это всего лишь в 8 раз медленнее, чем цепочка в 8.
BOOL __export PASCAL TimerLoop (HWND hWnd, unsigned uMsg, WPARAM wParam, LPARAM lParam)
{
if (uMsg==WM_INITDIALOG)
{
InitNationalFont(Russian);
//for (int i=0; i<1; i++) cout<<joySetCapture( hWnd, i, 1000, TRUE)<<" "; //winmm.lib
//cout<<endl<<JOYERR_NOERROR<<" "<<MMSYSERR_NODRIVER<<" "<<JOYERR_NOCANDO<<" "<<JOYERR_UNPLUGGED<<endl;
hWndT=hWnd;
if (joySetCapture( hWnd, JOYSTICKID1, 10, TRUE)) cout<<"Joystick not found! Use WASD+PL;' while keeping console (not the main window!) in focus."<<endl;
else KeyEmu=0;
DrawNames();
for (int i=0;i<33;i++)
{
DistFactor=max(DistFactor,Distance(i));
//cout<<Russian[1][i]<<" <-> "<<Distance(i)<<endl;
}
DistFactor *= 1000;
SetTimer (hWnd, 0, 1, NULL);
return FALSE;
}
else if (uMsg==WM_CLOSE)
{
if (!KeyEmu) joyReleaseCapture(0);
EndDialog (hWnd,NULL);
return FALSE;
}
else if (uMsg==WM_TIMER)
{
KillTimer (hWnd, 0);
if (OperationMode)
{
for (int i=0; i<16384; i++) Permutate();
cout<<"Achieved difficulty: "<<BestDifficulty<<endl;
//Re-generate Alphanumeric keys: place them into KeyNames array and re-init GUI controls.
for (int Key=0; Key<33; Key++)
{
KeyNames[ Spellcastings[Key][0] ] //Флаг "LR первый нажат"
[ Spellcastings[Key][1] ] //Направление первого переключения
[ Spellcastings[Key][2] ] //"Пятую колонку" занимают только стрелки и всякие энтеры-бэкспейсы, так что тут всегда 0..3
[ Spellcastings[Key][3] ] //Флаг "RL первый отпущен", причём опция "не отпускать и дождаться автоповтора" (третья колонка) не участвует в оптимизации, хотя в теории буквы выше 33-й там могут быть.
//Это настолько неудобный способ набора, что (не)счастливые обладатели алфавитов длиннее русского могут сразу вынести туда самые редкие буквы -- их не спасут никакие пары.
[0] [0] = Russian[0][Key]; //Строчная, нуль-терминатор уже инициализирован при старте.
KeyNames[ Spellcastings[Key][0] ]
[ Spellcastings[Key][1] ]
[ Spellcastings[Key][2] ]
[ Spellcastings[Key][3] ]
[1] [0] = Russian[1][Key]; //Заглавная, нуль-терминатор уже инициализирован при старте.
}
fstream Save;
Save.open ("Generated_Layout.hex", ios::out|ios::binary);
Save.write ((char*)(Spellcastings[0]), sizeof (Spellcastings));
Save.close();
DrawNames();
}
else ProcessKeys();
SetTimer (hWnd, 0, 1, NULL);
}
else if (uMsg==WM_COMMAND)
{
if (lParam)
{
if (wParam>>16==BN_CLICKED)
{
if ((wParam&0xFFFF)==1002) //Включение режима оптимизации раскладок
{
OperationMode = !OperationMode;
}
if ((wParam&0xFFFF)==1003) //Загрузка текущей раскладки ("Начните работу с нажатия этой кнопки")
{
fstream Load;
Load.open ("Current_Layout.hex", ios::in|ios::binary);
Load.read ((char*)(Spellcastings[0]), sizeof (Spellcastings));
Load.close();
for (int Key=0; Key<33; Key++)
{
KeyNames[ Spellcastings[Key][0] ] //Флаг "LR первый нажат"
[ Spellcastings[Key][1] ] //Направление первого переключения
[ Spellcastings[Key][2] ] //"Пятую колонку" занимают только стрелки и всякие энтеры-бэкспейсы, так что тут всегда 0..3
[ Spellcastings[Key][3] ] //Флаг "RL первый отпущен", причём опция "не отпускать и дождаться автоповтора" (третья колонка) не участвует в оптимизации, хотя в теории буквы выше 33-й там могут быть.
//Это настолько неудобный способ набора, что (не)счастливые обладатели алфавитов длиннее русского могут сразу вынести туда самые редкие буквы -- их не спасут никакие пары.
[0] [0] = Russian[0][Key]; //Строчная, нуль-терминатор уже инициализирован при старте.
KeyNames[ Spellcastings[Key][0] ]
[ Spellcastings[Key][1] ]
[ Spellcastings[Key][2] ]
[ Spellcastings[Key][3] ]
[1] [0] = Russian[1][Key]; //Заглавная, нуль-терминатор уже инициализирован при старте.
}
DrawNames();
}
if ((wParam&0xFFFF)==1004) //Переключение в режим мобилки
{
DeviceMode = !DeviceMode;
CapsLock = 0;
FnMode = 0;
HardwareShiftPressed = 0;
DrawNames();
}
}
}
}
else if (uMsg==MM_JOY1BUTTONDOWN || uMsg==MM_JOY1BUTTONUP)
{
if (wParam&JOY_BUTTON1) ULDRr=1;
else if (wParam&JOY_BUTTON2) ULDRr=4;
else if (wParam&JOY_BUTTON3) ULDRr=3;
else if (wParam&JOY_BUTTON4) ULDRr=2;
else ULDRr=0;
cout<<wParam<<" "<<LOWORD(lParam)<<" "<<HIWORD(lParam)<<endl;
}
else if (uMsg==MM_JOY1MOVE)
{
if (HIWORD(lParam)>45535) ULDRl=3;
else if (LOWORD(lParam)>45535) ULDRl=4;
else if (HIWORD(lParam)<20000) ULDRl=1;
else if (LOWORD(lParam)<20000) ULDRl=2;
else ULDRl=0;
cout<<wParam<<" "<<LOWORD(lParam)<<" "<<HIWORD(lParam)<<endl;
}
else return FALSE;
return TRUE;
}
В принципе, комментарии говорят сами за себя. Обратите внимание отдельно на обработчик событий от джойстика, который костылями приделан сбоку к ProcessKeys(), заменяя её родную GetAsyncKeyState в режиме работы с реальным геймпадом.
void main (void)
{/*
for(int A,b=0;b<30;b++)
{
while(!kbhit()) A=rand();
// cout<<A<<endl;
A%=(10+26+26);
if (A<10)
{
A+='0';
} else if (A<10+26)
{
A+='A'-10;
} else
{
A+='a'-10-26;
}
cout<<((char)(A));//<<endl;
while(kbhit()) getch();
}
*/
InitFreq();
/* int i,j,Max,Cap=0x7FFFFFFF; //Быстрый, эпически грязный и корявый способ проверить, что массив биграмм всосался, не трогая сам массив (не сортируя его).
while (Cap)
{
for (Max=i=0; i<33*33; i++)
{
if (Pairs[0][i] >= Cap) continue; //Does not work if array contains equal values!
if (Max<Pairs[0][i]) Max=Pairs[0][j=i];
}
cout<<Russian[1][j/33]<<Russian[1][j%33]<<" "<<Pairs[0][j]<<endl;
Cap=Max;
}
*/
for (int Sec=0; Sec<33; Sec++)
{
int Count = Single[Sec];
CharsFactor += Count;
for (int Fir=0; Fir<33; Fir++) Count -= Pairs[Fir][Sec];
cout<<Russian[1][Sec]<<": Total "<<Single[Sec]<<", "<<Count<<" word beginning"<<endl;
}
cout<<CharsFactor<<" chars total"<<endl;
DialogBoxParam(GetModuleHandle(NULL),"TEST", NULL, TimerLoop, NULL);
}
Ну, и вызывалка для диалога, предварённая всякими тестовыми и инициализирующими вызовами.
Что-то из этого можно было бы сделать и в обработчике WM_INITDIALOG, если не всё.
InitFreq определён в Freq.h (дурной стиль, я знаю), вместо нормальной таблицы.
Так было проще копипастить нагуглённые частотности, не требовалось переписывать по порядку все строки.
В одном запуске я добился 2.9482, в другом — 2.9106. В любом случае обычно получается около 2.9, что меньше трёх — а если считать обычную клавиатуру за 3 (переместить палец на клавишу, опустить палец, поднять палец), то, с поправкой на «мультипоточность» работы пальцев на обычной клавиатуре, мы уже наступаем ей на пятки!
С другой стороны, значение сложности как будто в доску Гальтона падает, причём в неаккуратно сделанную, с корявым дном. В зависимости от пути, оно прилетает в один из довольно глубоких локальных экстремумов, которые далеко друг от друга отстоят (раскладки получаются очень разные), но имеют почти одинаковую глубину (около 2.9) и перепрыгнуть от одного экстремума в другой по этим причинам шансы околонулевые (всего один раз получилось, так и добился рекорда; жаль, длину цепочки не записал). Но, может быть, где-то прячется ямка глубиной 2.5 и ниже? ;)
Отдельное спасибо всем, дочитавшим сюда, удачи!