После прочтения статьи про
выбор объектов в OpenGL, мне особенно понравился метод выбора, используя буфер цвета. Идея метода заключается в следующем: каждом объекту, который может быть выбран присваивается уникальный id и уникальный цвет(на самом деле достаточно только цвета), затем все эти объекты помещаются в некоторую структуры данных. При попытки выделить объект, строится двумерная проекция картинки. Строить надо лишь объекты, которые можно выделить и строить их надо без текстур, однотонные с указанным цветом. Затем считывается цвет пикселя под курсором мышки и ищется объект соответствующего цвета. Затем он и становится выделенным объектом.
За идентификатор рационально использовать сам объект, если такое возможно(например, если все объекты, которые могут быть выделены предоставляют собой потомков некоторого класса, то можно использовать механизм позднего связывания).
Явный минус такого алгоритма - он позволяет выделить только одного юнита. Если больше не надо использовать стоит именно его, если же надо выделить более одного, то алгоритм можно расширить. Я могу предложить два способа, как это сделать, они похожи, отличия у них, правда, небольшие.
Нам понадобится ещё одна структура данных, где мы будет хранить выделенных юнитов. Оба способа заключается в обходе выделанного прямоугольника, считывании пикселей, поиске фигур в буфере цвета(первая структура данных) и помещение их в буфер выделения(вторая структура данных). Отличите простое: в первом случае я предлагаю сделать обработку буфера выделения так, чтобы в нём не возникало коллизий(если юнит уже есть, то его не добавлять). Второй способ заключается в том, чтобы если юнит попадет в буфер выделения, то он удаляется из буфера цвета. Главный минус первого способа - каждый раз при добавлении в буфер выделения необходимо проверять все уже выделенные фигуры, главный минус второго способа - каждый раз при выделении необходимо заново строить буфер цвета(или "перекидывать" из буфера выделения обратно).
Следующий вопрос, не менее важный, это - как выбрать эти структуры данных. Начну с конца. Буфер выделения, выбирать лучше исходя из особенностей выделяемых объектов и самого выделения. Если выделить можно некоторое конечное количество фигур, то подойдёт ограниченный линейный список(реализованный с помощью массива, т.к. это позволяет производить прямой и обратный обход памяти, что даёт существенный выигрыш во времени), если можно выделять потенциально бесконечное множество объектов, то тут уже надо "смотреть на месте".
Для буфера цвета строить общую теорию проще, т.к. его вид его элементов и назначение сразу определенно. Буду рассматривать ситуацию, когда идентификатор включен в буфер. Назначение буфера цвета - это хранение всех объектов, которые могут быть выделены, а так же возможность поиска в нём. Из необходимости поиска и будем исходить. В статье, ссылку на которую я дал вышел, в виде буфера цвета используется статический массив и линейный поиск(просматриваются подряд все элементы массива). При небольшом количество объектов это, пожалуй лучшее решение. Причина всё та же - возможность прямого и обратного обхода памяти. Однако когда количество элементов превышает уже, где-то 256 это не очень удобно, т.к. время обхода будет компенсировать выигрыш.
Проблема в построении структуры данных для поиска, в данном случае, заключается в том, что величина, по которой мы ведём поиск - векторная, состоящая из минимум трёх компонент: (r, g, b). Однако, задачу можно очень просто свести к задачи поиска по скалярной величине. Множество значений каждой из переменных ограниченно, и можно построить отображение из множества цветов во множество натуральных чисел следующим образом:
Пожалуй, это самый просто способ решения. Построив такое отображение, мы можем искать вместо цвета, простое чисто. В силу ограниченности отображения, у него существует обратное, которая находится достаточно легко(одна из учебных задач - разить число на части), числа в разрядах 0-2 будут означать красную составляющию цвета, 3-5 - зелёную и 6-8 - синюю. Теперь, для буфера цвета, в качестве структуры данных можно использовать бинарное дерево поиска. Поиск в такой структуре один из самых быстрых(собственно, для этого она и предназначена) и кодированние/декодированние цвета тоже занимает мало количество времени. Минус использования дерева поиска - это удаление элемента из дерева может привести к перестройке всего дерева, поэтому второй, из предложенных мной, способов реализации выделения большого числа юнитов не подходит.
В общем, это достаточный теоретический минимум, чтобы реализовать выделение юнитов. Особенно это полезно в играх-стратегиях. Однако применение возможно и в других областях, например, взаимодействие пользователя с некоторыми предметами, посредством мышки(например некоторая физическая система и её элементы можно двигать, щёлкая на них мышкой).
