Мир аниматов. Первые дни творения (стр. 2 )

Создание структуры данных

Одним из путей к оптимизации расчетов является грамотная организация данных.

Мало удобные системы данных серьёзно усложняют решение задачи. Так, например задача прессование элемента массива имеет линейную сложность (~n), а прессование списка константную, что по своей сути весьма выгодно.

По этой причине мы занялись разработкой новой структуры организации ячеек памяти.

Первым (и на сей день единственным) пунктом нашего плана действий стала организация данных о карте (ландшафте и расположении объектов).

Простой трёхмерный массив не удовлетворяет нашим потребностям по следующим причинам:

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

2.  Размерные ограничения на массив. Крайние размеры массива задаются до компиляции, минимальная граница всегда 0, что-то не очень соответствует идеалу для хранения бесконечного мира. Конечно, чаще всего можно просто описать массив с «запасом», но это откровенное растранжиривание памяти и не всегда можно угадать потребности программы. Посему весьма желательна возможность динамического расширения карты (У массива такая функция отсутствует)

Нами были созданы специализированные структуры данных более подходящие для конкретной задачи. Это классы Net, Net3D и Polost.

Теперь о каждом из них поподробнее.

Net

Структура Данных представляет собой подобие прямоугольной сетки с данными в узлах

По этой структуре данных удобно перемещается в соседние клетки, что нам собственно и нужно. Расширение сети доступно и осуществляется добавлением слоёв.

MinChek и MaxChek это крайние узлы ссылки, на которые хранятся всегда, от них и производится добавление, перебор и поиск элементов.

Помимо простой навигации реализованы функции:

1.  Поиска (Поиск по индексу, Поиск по данным, Поиск с определённой стартовой точки)

2.  «Выборки»:

·  ReturnLine Возвращает N Клеток в K сторону от L клетки

 

·  ReturnRect возвращает прямоугольник шириной W, высотой H вниз от L клетки

·  ReturnRound Возвращает квадратную спираль радиуса R от точки L

ReturnLine

·  ReturnAll Возвращает все клетки сети.

Так же есть функции Расширения и уменьшения сети.

Net3D

Это трёхмерный вариант простой сетки состоит как бы из нескольких Net расположенных слоями, причем каждый элемент связан с соответствующим ему элементом на слой выше и на слой ниже.

Она содержит все функции Net

О структуре Polost будет рассказано в следующей главе.

Оптимизация рендеринга или предрендеринг[8]

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

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

Мы решили разбить процесс предрендеринга на два этапа, пока разработан и реализован только первый. Вот его суть:

Специально для предрендеринга была разработана структура данных Polost. Так как мир, в конечном счете, имеет форму прямоугольного параллелепипеда, представим его кусочком сыра, воздух воздухом и останется, а все другие материалы будут сыром. Получился сыр с дырками, эти дырки назовём полостями. (Причем если сыр распространяется не до края, есть воздушная прослойка, то она тоже будет полостью). Очевиден факт что, находясь в любой полости, мы можем видеть только её стенки и ничего более. Именно для записи стенок полости используется наш новый класс.

Polost в полости имеется «двусторонняя очередь»[9] переменных типа Layer и ряд процедур для её формирования.

Layer содержит Списки[10] «Крышечек», «Бортиков» и объектов на данном слое[11].

Крышечка – верхняя часть блока пример -

Бортики бывают трёх видов

1.  Правый

2.  Левый

3.  Двойной

Главное условие, что Layer содержит только те объекты, которые граничат с воздухом полости. Более того, списков бортиков на слое четыре по соответствующим ракурсам обзора.

Логика, в общем-то, элементарна - видеть то, что не граничит с воздухом, мы не можем, априори.

Формируются слои при помощи применения метода волновой трассировки[12].

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

По итогам этих размышлений нами написана программа GraphicEngeine3D основная её функция разовое проведение процедуры предрендеринга и последующая реализация цикла постоянного вывода на экран (рендеринга) картинки. В программе доступны функция осмотра ландшафта с четырёх сторон (рис. 15) (для получения ясного представления о его структуре) и функция отключения вывода «крышечек»/«бортиков» (Рис.16) (для доказательства эффекта предрендеринга.). Обычный скриншот из программы представлен на рисунке 17.

Программа Colution Test

По разработанному алгоритму проверки на столкновения была создана программа Colution Test, предназначенная для отладки и анализа его эффективности.

Программа работает следующим образом, имеются три класса объектов Маленькие(1/4 клетки), Средние (В клетку), Большие (В 16 клеток). По команде пользователя генерируются экземпляры этих классов. Объекты летают по полю, абсолютно упруго рикошетят от стен и проверяется их взаимодействия. Имеется два режима работы программы Просмотр (Рис. 12, скриншот №1, и отладка скриншот №2)

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

На рисунке (рис.13) представлен пример обозначения. На большом объекте стоит красный маркер, показывающий, что он взаимодействует с красным (средним) объектом. На одном из красных зелёный маркер, на другом маркера нет.

Во время работы программы можно переключатся с оптимизированного алгоритма проверки взаимодействий на классический. Также программа отображает частоту кадров в секунду, это позволяет оценивать соотношение производительности оптимизированного и не оптимизированного алгоритмов. Был проведён ряд экспериментов, их результаты представлены ниже на графике (рис.14). Из графика видна однозначная выгода оптимизации (нового алгоритма) для средних и малых тел. Для больших тел выгода есть но незначительная.

Создание первого анимата

Первый анимат… Первый житель мира созданного нами. Первый шаг на пути к созданию искусственного интеллекта. Теперь пара слов о глобальном стержне нашего подхода к созданию ИИ.

Однажды моё рассуждение об искусственном интеллекте было прервано вопросом, вы хотите создать интеллект[13] или разум[14]? Я задумался.… Позже, в ходе литературного обзора, был получен ответ, конечной целью является разум. Разум не может существовать вне интеллекта и на наш взгляд является его более высокой степенью развития. Мы мечтаем развить наш интеллект до уровня разума, и потому основываем подход к созданию алгоритма мышления на следующем утверждении. «Действие разума, как осмысления всеобщего, теснейшим образом связано с человеческой речью (языком)».

Более четко это выражается так. Мы выдвигаем гипотезу, что прийти к истинно интеллектуальной и разумной деятельности возможно лишь путем, связанным с естественным языком (речью), и будем далее следовать из сего предположения.

Обоснование необходимости мира. Первые идеи по созданию виртуального мира возникли из следующих рассуждений. Достаточно актуальная проблема современных разговаривающих программ: О чем говорить? Как может ответить на вопрос «Как дела?» Существо без тела, у которого дел не может быть в принципе? Значит нужно тело. Далее мы узнали о том, что одним из наиболее популярных методов для обучения ИИ является метод проб и ошибок. Созрел план следующего рода, мы поместим наше существо в некий мир, где оно сможет жить и общаться с другими, подобными существами. Дальнейшим аргументом вползу мира, стало то, что интеллекта является следствием борьбы за выживание, следовательно, нужны условия, в которых будет проходить эта борьбы.