Презентация для http://fpug.org.ua/meeting/31
Ньюансы разработки медиаплееров для мобильных устройств
четверг, 6 октября 2011 г.
воскресенье, 25 сентября 2011 г.
RealDocs для ActionScript 3.0
Редко, но все- же иногда возникает необходимость генерировать документацию по ActonScript 3.0 коду.
Если с Java в этом деле всё обстоит неплохо, с ActionScript 3.0 есть трудности: asdoc перед проверкой осуществляет синтаксический анализ кода и если находит ошибки, документации не генерирует. На практике, это означает, что при генерации кода нужно прописывать пути ко всем либам. Для флекса это ещё туда – сюда, но с флешом дело плохо. Во первых, если я хочу создать мувиклип, не создавая ассоциированный с ним файл, сделать это не удастся. Во вторых есть либы, которые вставляются в flash CS как плагин. Короче, без танцев с бубном сгенерировать не удастся.
Да и вообще, сам подход неприличен: я должен сам указывать инструменту, что мне делать, а не он мне указывать, как быть. Вот не хочу я ещё раз проверять код - я уже проверил его другими средствами, уже скомпилировал. Зачем мне ещё какой - то asdoc?
Он написан на перле, в качестве интерпретатора для винды предлагается скачать Active Perl. Вот его сайт: http://www.activestate.com/activeperl
Далее, качаем RealDocs и распаковываем его. Идем в папку, куда разархивировали RealDocs и правим предпоследнюю строчку так, чтобы получилось нечто вроде.
Далее, создаем скрипт для генерации, примерно такой
d:\install_windows\NaturalDocs\NaturalDocs -i d:\projects\hello -o html d:\outputdocs -p d:\naturaldocsproject
-o Тип документа, который будем генерировать и путь к папке, куда складывать доки
- p путь к файлу проекта, куда складывают логи
Конференция на Ciklum Game Developers Saturday
На этой конференции я рассказывал о принципах создания изометрических движков
Презентацию можно посмотреть здесь
воскресенье, 10 января 2010 г.
ТЕСТИРОВАНИЕ ИНТЕРЕСА К ИГРЕ
Введение
На сегодняшний день большое развитие получил рынок компьютерных игр, Индустрия развлечений стабильно развивается и приносит большие прибыли, что стимулирует инвесторов. Однако существует большая разница в подходе к выбору объекта инвестирования в играх и промышленном программном обеспечении. В самом деле: создав п.о. реализующее функции необходимые пользователю и отсутствующие у конкурентов можно с высокой степенью вероятности ожидать, что созданная продукция будет коммерчески успешна. Игры – же не решают бизнес – задач: их главная цель – развлечение пользователей, которые в свою очередь не склонны анализировать свой интерес к игре. Другими словами, пользователь ждет от программы не реализации конкретных требований, а увлекательного игрового процесса. Часты случаи, когда из двух игр одного и того же жанра, с примерно одинаковым сюжетом, построенные с использованием одного игрового конструктора работниками приблизительно одинаковой квалификации одна имеет ошеломляющий успех, а другая не окупает затрат на её создание.
Другим отличием от промышленного программного обеспечения является важность первого впечатления. Действительно, для решения производственной задачи пользователи выберут программу позволяющую сделать это с минимальными затратами времени, а не обладающую уникальным дизайном, или интересными звуковыми эффектами. В случае, когда, то или иное программное обеспечение применяется часто, пользователи проходят обучение его использованию, иногда довольно длительное и дорогостоящее, постоянно интересуются вновь появившимися возможностями и улучшениями. Совершенно другая картина наблюдается, когда цель использования программы – развлечение. Если игровой процесс не заинтересовал пользователя с первых минут, то он прекратит играть и, скорее всего, не заинтересуется следующими версиями данной игры, какие – бы увлекательные возможности они не предоставляли.
Поэтому очень важно тестировать игры до выхода их на суд публики, исправляя и то, что может привести к снижению интереса. С одной стороны, интерес к той или иной игре субъективен, с другой же есть объективный критерий качества, выраженный во времени проведённым за игрой. Признавая важность фактора рекламы и маркетинга вообще, тем не менее, можно сказать, что успех игры зависит от выполнения некоторых условий. Таким образом, важно определить, что это за условия и как можно проверить степень их выполнения.
1. Требования к игре
Понятно, что основное требование к игре состоит в том, чтобы она была интересной. Но интерес во многом зависит от выполнения некоторых требований, которые иногда, даже не осознаются пользователем, но, тем не менее, невыполнение их ведет к снижению качества игры.
Создание игры состоит из трех этапов: реализации механики игры(game mechanics),
игрового интерфейса(game interface) и игрового процесса(game play)
Под механикой игры понимается комбинация свойств, присущих созданной программной модели воплощённых с помощью анимации и программирования.
Под игровым интерфейсом понимается организация управляющих элементов, с помощью которых пользователь управляет программой. Это реакции на горячие клавиши, иерархические меню, механизмы отклика на действия мыши или джойстика и так далее.
Игровым процессом называется последовательность действий, которые должен проделать пользователь, чтобы достигнуть цели игры. Также к реализации игрового процесса относится создание сюжета игры, уровней, принципы начисления очков и так далее
Ниже представлены те требования, которые автор считает наиболее важными
• Управляющие клавиши и элементы меню должны соответствовать принятым в отрасли стандартам.
• Пользователю должны быть всегда доступны его очки или игровой статус
• Количество горячих клавиш должно быть минимальным
• Для предоставления обратной связи должно использоваться звуковое сопровождение
• Количество пунктов меню должно быть минимальным
• Действия, которые нужно производить должны быть понятны настолько, что нет необходимости обращаться к руководству пользователя
• Скорость отклика на действия игрока должна быть как можно большей
• Скорость отклика должна быть равномерной
• Скорость
• Цель игры должна быть понятной
• В игре должна быть возможность выбрать уровень сложности
• В каждом уровне должно быть несколько целей
• Должно существовать несколько выигрышных стратегий
• Должна присутствовать возможность сохранить начатую игру и вернуться к ней позже
• Сохранение игры должно производиться автоматически, через определённые интервалы времени или по достижению ключевых точек в игре
• У пользователя должна быть возможность автоматического создания уровней
• Присутствие определённой сложности в достижении игровых задач(Challenge). Как показывает практика, игра, прохождение которой не требует от игрока усилий, не пользуется популярностью
• Сложность уровней должна монотонно возрастать.
• Первый уровень не должен представлять особенной сложности. Его задача пояснить пользователю правила игры
•
Очевидно, что конкретное применение этих условий зависит от жанра игры.
Ясно, что некоторые из этих правил выполнить довольно просто (например, вывести на экран очки, заработанные пользователем, или предусмотреть возможность сохранения игры), но выполнение большинства из них оценить довольно трудно. В самом деле, то, на сколько правила понятны, или на сколько уровень сложен субъективно для каждого пользователя. Кроме того, понятия сложности, интереса и т.п. не формализованы, поэтому оценить их численно представляется нетривиальной задачей. Некоторые из методов такого тестирования представлены ниже.
2. Виды тестирования игр
В производстве игр применяются несколько типов тестирования, каждый из которых предназначен для выявления соответствующих данному типу недостатков. Ниже кратко рассмотрены особенности тестирования игр для тех видов, которые являются общими для всего программного обеспечения.
2.1 Тестирование функциональности (functionality testing) Цель – выявить отклонения от требуемой функциональности и ошибки так называемые «баги» (профессиональный жаргон). Этот тип тестирования, как правило, не требует от тестировщика больших технических познаний помимо понимания базовых концепций программирования и сводится к многократному прохождению игры, выявлению неполадок и условий в которых они воспроизводятся. Описание проблем производится в произвольной форме, важно лишь, чтобы текст был понятен разработчику.
Данный вид тестов является общим для всего программного обеспечения, поэтому останавливаться на нём подробно нецелесообразно.
2.2 Тестирование соответствия аппаратному обеспечению(compliance testing) Программирование игр, как и любого другого программного обеспечения, производится на персональных компьютерах: настольных или ноутбуках. В тоже время, многие игры предназначены для других типов устройств, таких как различные игровые приставки(Nintendo, Sony, Microsoft), мобильные телефоны, карманные портативные компьютеры (наладонники), коммуникаторы и другие. Первоначально разработка производится при помощи симуляторов указанных устройств, однако, как и всякая модель, они отличаются от оригинала, часто существенно. Поэтому, игра, успешно работающая на симуляторе, может иметь проблемы при запуске на устройстве. Кроме того, многие из производителей устройств, вводят лицензирование для программного обеспечения. Одним из необходимых условий успешного прохождения лицензии есть соответствие списку технических требований. Примером могут быть требования компании «Sony» для игровых приставок - Sony publishes a Technical Requirements Checklist (TRC), компании Microsoft - Microsoft publishes Technical Certification Requirements (TCR) и другие. Даже в случае незначительных отклонений от требований, в лицензии может быть отказано. В этом случае программа возвращается на доработку и таким образом теряется время, что приводит к потере и денег. Кроме того, процесс лицензирования в большинстве случаев платный. Поэтому, очень важно проверить игру на соответствие заявленным параметрам аппаратного обеспечения.
2.3 Нагрузочное тестирование(crash testing) Часто бывает, что программа, нормально работающая в большинстве ситуаций, обнаруживает проблемы при эффективных вычислениях. Этот вид проблем особенно неприятен потому, что интенсивность вычислений может не зависеть от логики игры.
Например, в программах написанных для Java – платформы, AVM2 (flash - player) и других может запускаться сборщик мусора. Принцип его работы такова, что он запускается независимо от деловой логики. В тоже время, его работа дорога в смысле вычислительных ресурсов. Кроме того, игровые ситуации с большим объёмом вычислений могут быть не замечены тестировщиками.
Поэтому, целесообразно создать тестовые ситуации, требующие большой вычислительной нагрузки. Таким образом, гораздо легче заметить и улучшить имеющиеся потенциально ненадёжные участки кода.
2.4 Тестирование локализации(Localization testing) Игры, как и некоторые другие виды развлекательной продукции, часто переводят на язык той страны, где они распространяются. Часто бывает, что переводчики не являются носителями соответствующего языка. Даже правильно переведённое словосочетание может резать слух или порождать неприятные ассоциации. Поэтому, во избежание курьёзов, после локализации полезно тестирование игры непосредственно жителями целевой страны.
3. Метод экспертной оценки в тестировании игр
Как было сказано раннее, тестирование игрового интерфейса и процесса игры нетривиальная задача из-за отсутствия чётких определений понятий свойственных человеческой психике. Поэтому, такого рода тестирование производится с помощью двух основных методов: экспертной оценки и анализа реакций пользователя на игровые события.
Метод экспертной оценки позволяет получить информацию о недостатках игры непосредственно, как мнение игрока. Хорошо для качественной оценки и выявления масштабных проблем. Однако трудно поддаётся формализации, в общем случае не подходит для установки конкретных количественных параметров (например, количество выстрелов необходимых для поражения врага, коэффициент трения скольжения игровой трассы и так далее). Часто в качестве экспертов выступают сами пользователи.
Разделяют четыре вида подобного тестирования: фокус группы, ретроспективное анкетирование, бета тестирование и метод игровых тестов. Рассмотрим их подробнее
3.1 Фокус группы (Focus Groups) Группа пользователей, обычно содержащая десять – двенадцать человек обсуждает определённый аспект игры. Такой, например, как звуковое сопровождение или реалистичность кинематики движения персонажей. Результаты дискуссии и фиксируются в протоколе. Метод хорошо подходит для выявления глобальных недостатков в концепции игры, может быть использован до завершения работы над игровой механикой.
Недостатки состоят в том, что невозможно получить конкретные численные данные, обсуждаемая концепция игры может коренным образом отличаться от концепции готового продукта, в дискуссии могут превалировать два три участника с более развитыми навыками полемики, подавляя тем самым мнение остальных.
3.2 Ретроспективное анкетирование. Чаще всего производится после выхода игры. В анкете задаются вопросы о качестве графики, звукового оформления, персонажей, сюжета и так далее. Разновидностью данного вида анкетирования являются комментарии на сайтах соответствующей тематики. В случае онлайн игр пользователю, в большинстве случаев, предлагается оценить игру непосредственно на web – странице, где она расположена. Упоминаемый выше рейтинг на игровых сайтах также можно считать видом ретроспективного анкетирования.
Этот вид тестирования позволяет непосредственно оценить игру - с его помощью можно получить объективную оценку. Данные, полученные таким образом, можно использовать как критерий качества в методе анализа пользовательских реакций, метод неприменим для улучшения вышедшей игры. Он может помочь лишь в устранении имеющихся недостатков для последующих продуктов. Также, пользователи обычно не стимулированы заполнять большие анкеты, а иногда и необъективно оценивают игру.
3.3 Бета тестирование Модификацией предыдущего метода можно считать метод бета – тестирования. После выхода бета – версии игры создатель может предложить желающим бесплатно получить программу. Взамен, тестеры указывают на существующие недостатки. Этот метод хорош тем, что позволяет проверить реакцию конечного пользователя до официального окончания работы над игрой. Кроме того, бета - тестеры в большинстве случаев являются очень опытными игроками, поэтому их замечания объективны и точны.
Для небольших и онлайн игр можно предложить тестирование посетителям тематических форумов. Так на форуме www.flasher.ru присутствует раздел обсуждения готовых flash – приложений, в том числе и игр.
3.4 Тестирование с помощью профессиональных тестеров. Описанные выше методы позволяют тестировать программное обеспечение силами пользователей, без привлечения профессиональных тестеров. Однако в основном тестирование выполняют специально обученные работники. Отличие от вышеописанных методов состоит в многократном проходе каждого уровня, стандартизированных и расширенных анкетах. Данный вид тестирования позволяет наиболее полно исследовать игру, однако его недостатком является то, что мотивация профессиональных тестеров и пользователей, играющих ради удовольствия, сильно отличается. Кроме того, профессиональное тестирование существенно увеличивает стоимость выпуска игры.
4. Тестирование игрового интерфейса и процесса с помощью записи реакций игрока.
Анкетирование и обсуждение позволяет выявить качественные проблемы игр, однако любая оценка игры субъективна. Кроме того, добровольные тестеры часто не в состоянии пояснить, что именно им не нравится в процессе игры, а профессионалы обходятся дорого. Далее, любое тестирование, основанное на фиксации мнения игрока, способно решить проблему лишь качественно. Конкретные численные характеристики приходится находить экспериментально, что увеличивает время и стоимость работы. Поэтому, принято записывать реакции игрока и путём их анализа корректировать численные параметры игры.
В качестве примера применения логирования и информации, которую можно с помощью него получить, рассмотрим такой класс игр, как головоломки.
Суть таких игр сводится к решению последовательности задач на логику, внимание, память, иногда необходимо решить задачу за определённое время. Классическими головоломками являются пазлы, шахматные и шашечные задачи, судоку, кроссворды и так далее. В последнее время появились головоломки, которые сводятся к предсказанию поведения механической системы. Такие как игры расположенные по адресам: http://www.kongregate.com/games/TheGameHomepage/red-remover, http://www.kongregate.com/games/inXile_Ent/fantastic-contraption,
http://www.kongregate.com/games/inXile_Ent/super-stacker-2 и другие. Видно, что игра состоит из последовательности логических задач повышающейся сложности.
Очевидно, что мы хотим получить игру, захватывающую пользователя с первых минут и интересом неослабевающем на протяжении всего времени использования. С постепенным увеличением сложности от уровня к уровню, качественным звуковым и музыкальным сопровождением. Мы предполагаем, что в игре реализовано автоматическое сохранение, возможность настройки элементов управления, включать и выключать звук и музыку и создавать пользовательские уровни.
Важным параметром игр – головоломок является эталонное прохождение уровня. Это прохождение, которое выполняется опытным игроком, хорошо знающим правила. Как правило, производится несколько прохождений и из них выбирается наиболее близкое к средней величине по совокупности параметров.
Ниже приведены параметры, подлежащие записи и данные, которые можно получить в процессе их анализа.
• Качество игры Время, проведённое пользователем за игрой
• Понятность правил Скорость прохождение первого уровня по отношению к эталонному прохождению. Количество обращений к помощи
• Сложность уровня Время прохождения уровня по отношению к эталонному времени. Количество проигранных игр, или уровней.
• Корректность выбранных интервалов автоматического сохранения игры Количество сохранений сделанных пользователем. Наличие большого числа сохранений на определённом участке игры говорит о том, что в этом месте необходимо сохранять данные автоматически
• Сложность уровня по отношению к другим Сравнения параметров «сложность» для каждого уровня
• Вовлечение пользователей в игру Количество пользователей, которые прошли больше определённого числа уровней. Количество пользователей прошедших последний уровень. Количество пользовательских уровней, которые были созданы.
• Качество звукового и музыкального сопровождения Количество пользователей, отключивших звук или музыку
• Удобство управления, соответствие стандартам индустрии Количество пользователей изменивших управление
• Оптимальность количества элементов управления Среднеквадратическое отклонение процентных соотношений использования конкретных элементов управления.
Используя данные характеристики можно судить о слабых местах игры и своевременно изменить их. Очевидно, что кроме представленных данных весьма любопытными представляются знания о персоне пользователя: его возраст, пол, социальный статус, профессия и так далее. Но так – как предоставление этих данных нельзя требовать, они не рассматриваются в этой статье.
Перспективы дальнейших исследований.
На данный момент актуальным является создание удобных инструментов по автоматизации тестирования игр: ведения логов и анкетирования. Следующим этапом будут исследования, относящиеся к инженерной психологии: между жанром игр, возрастной категорией, сложностью уровней и так далее существуют некоторые связи, которые могут быть выявлены с помощью технологии Data Mining
Литература
1. John P. Davis, Keith Steury, and Randy Pagulayan. A survey method for assessing perceptions of a game: The consumer playtest in game design http://www.gamestudies.org/0501/davis_steury_pagulayan/
2. Melissa A. Federoff. Heuristics and usability guidelines for the creation and evaluation of fun in video games
3. Sauli Laitinen. Better Games Through Usability Evaluation and Testing http://www.gamasutra.com/features/20050623/laitinen_02.shtml
4. David Kieras, User Interface Design for Games http://www.eecs.umich.edu/~soar/Classes/494/talks/User-interfaces.pdf
5. Sauli Laitinen. Do usability expert evaluation and test provide novel and useful data for game development?
6. Shannon Lucas and Denise Fulton What We Learned Evaluating the Usability of a Game http://www.stcsig.org/usability/newsletter/0410-gameevaluation.html
7. Martin Peterson Why Game Documentation is Essential to a Satisfying User Experience http://www.stcsig.org/usability/newsletter/0410-gamedocs.html
На сегодняшний день большое развитие получил рынок компьютерных игр, Индустрия развлечений стабильно развивается и приносит большие прибыли, что стимулирует инвесторов. Однако существует большая разница в подходе к выбору объекта инвестирования в играх и промышленном программном обеспечении. В самом деле: создав п.о. реализующее функции необходимые пользователю и отсутствующие у конкурентов можно с высокой степенью вероятности ожидать, что созданная продукция будет коммерчески успешна. Игры – же не решают бизнес – задач: их главная цель – развлечение пользователей, которые в свою очередь не склонны анализировать свой интерес к игре. Другими словами, пользователь ждет от программы не реализации конкретных требований, а увлекательного игрового процесса. Часты случаи, когда из двух игр одного и того же жанра, с примерно одинаковым сюжетом, построенные с использованием одного игрового конструктора работниками приблизительно одинаковой квалификации одна имеет ошеломляющий успех, а другая не окупает затрат на её создание.
Другим отличием от промышленного программного обеспечения является важность первого впечатления. Действительно, для решения производственной задачи пользователи выберут программу позволяющую сделать это с минимальными затратами времени, а не обладающую уникальным дизайном, или интересными звуковыми эффектами. В случае, когда, то или иное программное обеспечение применяется часто, пользователи проходят обучение его использованию, иногда довольно длительное и дорогостоящее, постоянно интересуются вновь появившимися возможностями и улучшениями. Совершенно другая картина наблюдается, когда цель использования программы – развлечение. Если игровой процесс не заинтересовал пользователя с первых минут, то он прекратит играть и, скорее всего, не заинтересуется следующими версиями данной игры, какие – бы увлекательные возможности они не предоставляли.
Поэтому очень важно тестировать игры до выхода их на суд публики, исправляя и то, что может привести к снижению интереса. С одной стороны, интерес к той или иной игре субъективен, с другой же есть объективный критерий качества, выраженный во времени проведённым за игрой. Признавая важность фактора рекламы и маркетинга вообще, тем не менее, можно сказать, что успех игры зависит от выполнения некоторых условий. Таким образом, важно определить, что это за условия и как можно проверить степень их выполнения.
1. Требования к игре
Понятно, что основное требование к игре состоит в том, чтобы она была интересной. Но интерес во многом зависит от выполнения некоторых требований, которые иногда, даже не осознаются пользователем, но, тем не менее, невыполнение их ведет к снижению качества игры.
Создание игры состоит из трех этапов: реализации механики игры(game mechanics),
игрового интерфейса(game interface) и игрового процесса(game play)
Под механикой игры понимается комбинация свойств, присущих созданной программной модели воплощённых с помощью анимации и программирования.
Под игровым интерфейсом понимается организация управляющих элементов, с помощью которых пользователь управляет программой. Это реакции на горячие клавиши, иерархические меню, механизмы отклика на действия мыши или джойстика и так далее.
Игровым процессом называется последовательность действий, которые должен проделать пользователь, чтобы достигнуть цели игры. Также к реализации игрового процесса относится создание сюжета игры, уровней, принципы начисления очков и так далее
Ниже представлены те требования, которые автор считает наиболее важными
• Управляющие клавиши и элементы меню должны соответствовать принятым в отрасли стандартам.
• Пользователю должны быть всегда доступны его очки или игровой статус
• Количество горячих клавиш должно быть минимальным
• Для предоставления обратной связи должно использоваться звуковое сопровождение
• Количество пунктов меню должно быть минимальным
• Действия, которые нужно производить должны быть понятны настолько, что нет необходимости обращаться к руководству пользователя
• Скорость отклика на действия игрока должна быть как можно большей
• Скорость отклика должна быть равномерной
• Скорость
• Цель игры должна быть понятной
• В игре должна быть возможность выбрать уровень сложности
• В каждом уровне должно быть несколько целей
• Должно существовать несколько выигрышных стратегий
• Должна присутствовать возможность сохранить начатую игру и вернуться к ней позже
• Сохранение игры должно производиться автоматически, через определённые интервалы времени или по достижению ключевых точек в игре
• У пользователя должна быть возможность автоматического создания уровней
• Присутствие определённой сложности в достижении игровых задач(Challenge). Как показывает практика, игра, прохождение которой не требует от игрока усилий, не пользуется популярностью
• Сложность уровней должна монотонно возрастать.
• Первый уровень не должен представлять особенной сложности. Его задача пояснить пользователю правила игры
•
Очевидно, что конкретное применение этих условий зависит от жанра игры.
Ясно, что некоторые из этих правил выполнить довольно просто (например, вывести на экран очки, заработанные пользователем, или предусмотреть возможность сохранения игры), но выполнение большинства из них оценить довольно трудно. В самом деле, то, на сколько правила понятны, или на сколько уровень сложен субъективно для каждого пользователя. Кроме того, понятия сложности, интереса и т.п. не формализованы, поэтому оценить их численно представляется нетривиальной задачей. Некоторые из методов такого тестирования представлены ниже.
2. Виды тестирования игр
В производстве игр применяются несколько типов тестирования, каждый из которых предназначен для выявления соответствующих данному типу недостатков. Ниже кратко рассмотрены особенности тестирования игр для тех видов, которые являются общими для всего программного обеспечения.
2.1 Тестирование функциональности (functionality testing) Цель – выявить отклонения от требуемой функциональности и ошибки так называемые «баги» (профессиональный жаргон). Этот тип тестирования, как правило, не требует от тестировщика больших технических познаний помимо понимания базовых концепций программирования и сводится к многократному прохождению игры, выявлению неполадок и условий в которых они воспроизводятся. Описание проблем производится в произвольной форме, важно лишь, чтобы текст был понятен разработчику.
Данный вид тестов является общим для всего программного обеспечения, поэтому останавливаться на нём подробно нецелесообразно.
2.2 Тестирование соответствия аппаратному обеспечению(compliance testing) Программирование игр, как и любого другого программного обеспечения, производится на персональных компьютерах: настольных или ноутбуках. В тоже время, многие игры предназначены для других типов устройств, таких как различные игровые приставки(Nintendo, Sony, Microsoft), мобильные телефоны, карманные портативные компьютеры (наладонники), коммуникаторы и другие. Первоначально разработка производится при помощи симуляторов указанных устройств, однако, как и всякая модель, они отличаются от оригинала, часто существенно. Поэтому, игра, успешно работающая на симуляторе, может иметь проблемы при запуске на устройстве. Кроме того, многие из производителей устройств, вводят лицензирование для программного обеспечения. Одним из необходимых условий успешного прохождения лицензии есть соответствие списку технических требований. Примером могут быть требования компании «Sony» для игровых приставок - Sony publishes a Technical Requirements Checklist (TRC), компании Microsoft - Microsoft publishes Technical Certification Requirements (TCR) и другие. Даже в случае незначительных отклонений от требований, в лицензии может быть отказано. В этом случае программа возвращается на доработку и таким образом теряется время, что приводит к потере и денег. Кроме того, процесс лицензирования в большинстве случаев платный. Поэтому, очень важно проверить игру на соответствие заявленным параметрам аппаратного обеспечения.
2.3 Нагрузочное тестирование(crash testing) Часто бывает, что программа, нормально работающая в большинстве ситуаций, обнаруживает проблемы при эффективных вычислениях. Этот вид проблем особенно неприятен потому, что интенсивность вычислений может не зависеть от логики игры.
Например, в программах написанных для Java – платформы, AVM2 (flash - player) и других может запускаться сборщик мусора. Принцип его работы такова, что он запускается независимо от деловой логики. В тоже время, его работа дорога в смысле вычислительных ресурсов. Кроме того, игровые ситуации с большим объёмом вычислений могут быть не замечены тестировщиками.
Поэтому, целесообразно создать тестовые ситуации, требующие большой вычислительной нагрузки. Таким образом, гораздо легче заметить и улучшить имеющиеся потенциально ненадёжные участки кода.
2.4 Тестирование локализации(Localization testing) Игры, как и некоторые другие виды развлекательной продукции, часто переводят на язык той страны, где они распространяются. Часто бывает, что переводчики не являются носителями соответствующего языка. Даже правильно переведённое словосочетание может резать слух или порождать неприятные ассоциации. Поэтому, во избежание курьёзов, после локализации полезно тестирование игры непосредственно жителями целевой страны.
3. Метод экспертной оценки в тестировании игр
Как было сказано раннее, тестирование игрового интерфейса и процесса игры нетривиальная задача из-за отсутствия чётких определений понятий свойственных человеческой психике. Поэтому, такого рода тестирование производится с помощью двух основных методов: экспертной оценки и анализа реакций пользователя на игровые события.
Метод экспертной оценки позволяет получить информацию о недостатках игры непосредственно, как мнение игрока. Хорошо для качественной оценки и выявления масштабных проблем. Однако трудно поддаётся формализации, в общем случае не подходит для установки конкретных количественных параметров (например, количество выстрелов необходимых для поражения врага, коэффициент трения скольжения игровой трассы и так далее). Часто в качестве экспертов выступают сами пользователи.
Разделяют четыре вида подобного тестирования: фокус группы, ретроспективное анкетирование, бета тестирование и метод игровых тестов. Рассмотрим их подробнее
3.1 Фокус группы (Focus Groups) Группа пользователей, обычно содержащая десять – двенадцать человек обсуждает определённый аспект игры. Такой, например, как звуковое сопровождение или реалистичность кинематики движения персонажей. Результаты дискуссии и фиксируются в протоколе. Метод хорошо подходит для выявления глобальных недостатков в концепции игры, может быть использован до завершения работы над игровой механикой.
Недостатки состоят в том, что невозможно получить конкретные численные данные, обсуждаемая концепция игры может коренным образом отличаться от концепции готового продукта, в дискуссии могут превалировать два три участника с более развитыми навыками полемики, подавляя тем самым мнение остальных.
3.2 Ретроспективное анкетирование. Чаще всего производится после выхода игры. В анкете задаются вопросы о качестве графики, звукового оформления, персонажей, сюжета и так далее. Разновидностью данного вида анкетирования являются комментарии на сайтах соответствующей тематики. В случае онлайн игр пользователю, в большинстве случаев, предлагается оценить игру непосредственно на web – странице, где она расположена. Упоминаемый выше рейтинг на игровых сайтах также можно считать видом ретроспективного анкетирования.
Этот вид тестирования позволяет непосредственно оценить игру - с его помощью можно получить объективную оценку. Данные, полученные таким образом, можно использовать как критерий качества в методе анализа пользовательских реакций, метод неприменим для улучшения вышедшей игры. Он может помочь лишь в устранении имеющихся недостатков для последующих продуктов. Также, пользователи обычно не стимулированы заполнять большие анкеты, а иногда и необъективно оценивают игру.
3.3 Бета тестирование Модификацией предыдущего метода можно считать метод бета – тестирования. После выхода бета – версии игры создатель может предложить желающим бесплатно получить программу. Взамен, тестеры указывают на существующие недостатки. Этот метод хорош тем, что позволяет проверить реакцию конечного пользователя до официального окончания работы над игрой. Кроме того, бета - тестеры в большинстве случаев являются очень опытными игроками, поэтому их замечания объективны и точны.
Для небольших и онлайн игр можно предложить тестирование посетителям тематических форумов. Так на форуме www.flasher.ru присутствует раздел обсуждения готовых flash – приложений, в том числе и игр.
3.4 Тестирование с помощью профессиональных тестеров. Описанные выше методы позволяют тестировать программное обеспечение силами пользователей, без привлечения профессиональных тестеров. Однако в основном тестирование выполняют специально обученные работники. Отличие от вышеописанных методов состоит в многократном проходе каждого уровня, стандартизированных и расширенных анкетах. Данный вид тестирования позволяет наиболее полно исследовать игру, однако его недостатком является то, что мотивация профессиональных тестеров и пользователей, играющих ради удовольствия, сильно отличается. Кроме того, профессиональное тестирование существенно увеличивает стоимость выпуска игры.
4. Тестирование игрового интерфейса и процесса с помощью записи реакций игрока.
Анкетирование и обсуждение позволяет выявить качественные проблемы игр, однако любая оценка игры субъективна. Кроме того, добровольные тестеры часто не в состоянии пояснить, что именно им не нравится в процессе игры, а профессионалы обходятся дорого. Далее, любое тестирование, основанное на фиксации мнения игрока, способно решить проблему лишь качественно. Конкретные численные характеристики приходится находить экспериментально, что увеличивает время и стоимость работы. Поэтому, принято записывать реакции игрока и путём их анализа корректировать численные параметры игры.
В качестве примера применения логирования и информации, которую можно с помощью него получить, рассмотрим такой класс игр, как головоломки.
Суть таких игр сводится к решению последовательности задач на логику, внимание, память, иногда необходимо решить задачу за определённое время. Классическими головоломками являются пазлы, шахматные и шашечные задачи, судоку, кроссворды и так далее. В последнее время появились головоломки, которые сводятся к предсказанию поведения механической системы. Такие как игры расположенные по адресам: http://www.kongregate.com/games/TheGameHomepage/red-remover, http://www.kongregate.com/games/inXile_Ent/fantastic-contraption,
http://www.kongregate.com/games/inXile_Ent/super-stacker-2 и другие. Видно, что игра состоит из последовательности логических задач повышающейся сложности.
Очевидно, что мы хотим получить игру, захватывающую пользователя с первых минут и интересом неослабевающем на протяжении всего времени использования. С постепенным увеличением сложности от уровня к уровню, качественным звуковым и музыкальным сопровождением. Мы предполагаем, что в игре реализовано автоматическое сохранение, возможность настройки элементов управления, включать и выключать звук и музыку и создавать пользовательские уровни.
Важным параметром игр – головоломок является эталонное прохождение уровня. Это прохождение, которое выполняется опытным игроком, хорошо знающим правила. Как правило, производится несколько прохождений и из них выбирается наиболее близкое к средней величине по совокупности параметров.
Ниже приведены параметры, подлежащие записи и данные, которые можно получить в процессе их анализа.
• Качество игры Время, проведённое пользователем за игрой
• Понятность правил Скорость прохождение первого уровня по отношению к эталонному прохождению. Количество обращений к помощи
• Сложность уровня Время прохождения уровня по отношению к эталонному времени. Количество проигранных игр, или уровней.
• Корректность выбранных интервалов автоматического сохранения игры Количество сохранений сделанных пользователем. Наличие большого числа сохранений на определённом участке игры говорит о том, что в этом месте необходимо сохранять данные автоматически
• Сложность уровня по отношению к другим Сравнения параметров «сложность» для каждого уровня
• Вовлечение пользователей в игру Количество пользователей, которые прошли больше определённого числа уровней. Количество пользователей прошедших последний уровень. Количество пользовательских уровней, которые были созданы.
• Качество звукового и музыкального сопровождения Количество пользователей, отключивших звук или музыку
• Удобство управления, соответствие стандартам индустрии Количество пользователей изменивших управление
• Оптимальность количества элементов управления Среднеквадратическое отклонение процентных соотношений использования конкретных элементов управления.
Используя данные характеристики можно судить о слабых местах игры и своевременно изменить их. Очевидно, что кроме представленных данных весьма любопытными представляются знания о персоне пользователя: его возраст, пол, социальный статус, профессия и так далее. Но так – как предоставление этих данных нельзя требовать, они не рассматриваются в этой статье.
Перспективы дальнейших исследований.
На данный момент актуальным является создание удобных инструментов по автоматизации тестирования игр: ведения логов и анкетирования. Следующим этапом будут исследования, относящиеся к инженерной психологии: между жанром игр, возрастной категорией, сложностью уровней и так далее существуют некоторые связи, которые могут быть выявлены с помощью технологии Data Mining
Литература
1. John P. Davis, Keith Steury, and Randy Pagulayan. A survey method for assessing perceptions of a game: The consumer playtest in game design http://www.gamestudies.org/0501/davis_steury_pagulayan/
2. Melissa A. Federoff. Heuristics and usability guidelines for the creation and evaluation of fun in video games
3. Sauli Laitinen. Better Games Through Usability Evaluation and Testing http://www.gamasutra.com/features/20050623/laitinen_02.shtml
4. David Kieras, User Interface Design for Games http://www.eecs.umich.edu/~soar/Classes/494/talks/User-interfaces.pdf
5. Sauli Laitinen. Do usability expert evaluation and test provide novel and useful data for game development?
6. Shannon Lucas and Denise Fulton What We Learned Evaluating the Usability of a Game http://www.stcsig.org/usability/newsletter/0410-gameevaluation.html
7. Martin Peterson Why Game Documentation is Essential to a Satisfying User Experience http://www.stcsig.org/usability/newsletter/0410-gamedocs.html
вторник, 25 августа 2009 г.
Раздражающие вопросы на собеседованиях
Навеяно рсдн - ом, ДОУ и другими форумами.
Итак:
1) Почему вы выбрали нашу компанию/почему вы хотите у нас работать?
Правильная стратегия поиска работы предполагает отсылать десять - двадцать резюме в день, иной раз люди проходят по три - четыре собеседования. Потом садятся, думают и из полученных предложений выбирают одно. Если предложений кроме этого больше нет, то вопрос вообще не имеет смысла, но никто ж не ответит правдиво, а на первом собеседовании он звучит как нельзя глупо
2) Что вы знаете о нашей компании
Имхо тупая калька с собеседований в Майкрософте, Гугле и др. Там это понятно, но из уст хрюши заштатной обшорки в 20 - 30 человек, у которой только и есть, что хоумпейдж, откуда соискатель может о них знать. Иногда человек приходит на собеседование чтобы узнать подходит - ли ему эта работа, т.е. выбирает он, а не контора. Т.е. и приходишь - то узнать что - нибудь об этой самой компании, насколько вы подойдёте друг - другу
3) Почему вы ищите работу. Почему - почему, деньги я люблю. Гораздо лучше звучит: чем вас не устраивало прошлое/не устраивает теперешнее место работы.
4) Пронумеруйте по степени важности десять вопросов. Ну естественно, каждый сначала выбирает интересную работу, потом деньги или коллектив, в зависимости от степени наглости, и далее по пунктам. Дальше эти бумажки кладут в папочку и выбрасываются при очередной уборке.
Итак:
1) Почему вы выбрали нашу компанию/почему вы хотите у нас работать?
Правильная стратегия поиска работы предполагает отсылать десять - двадцать резюме в день, иной раз люди проходят по три - четыре собеседования. Потом садятся, думают и из полученных предложений выбирают одно. Если предложений кроме этого больше нет, то вопрос вообще не имеет смысла, но никто ж не ответит правдиво, а на первом собеседовании он звучит как нельзя глупо
2) Что вы знаете о нашей компании
Имхо тупая калька с собеседований в Майкрософте, Гугле и др. Там это понятно, но из уст хрюши заштатной обшорки в 20 - 30 человек, у которой только и есть, что хоумпейдж, откуда соискатель может о них знать. Иногда человек приходит на собеседование чтобы узнать подходит - ли ему эта работа, т.е. выбирает он, а не контора. Т.е. и приходишь - то узнать что - нибудь об этой самой компании, насколько вы подойдёте друг - другу
3) Почему вы ищите работу. Почему - почему, деньги я люблю. Гораздо лучше звучит: чем вас не устраивало прошлое/не устраивает теперешнее место работы.
4) Пронумеруйте по степени важности десять вопросов. Ну естественно, каждый сначала выбирает интересную работу, потом деньги или коллектив, в зависимости от степени наглости, и далее по пунктам. Дальше эти бумажки кладут в папочку и выбрасываются при очередной уборке.
четверг, 20 августа 2009 г.
Сетевые игры, которые может сделать джуниор
Привет всем.
Вот что по моему будет посильно для джуна
1) Самое простое - морской бой. Делать броузерного клиента для неё не имеет смысла т.к. человеку, которому доступен броузер легко найдёт флешовую игрушку поинтереснее. Поэтому клиент лучше всего сделать мобильный использовать для этого можно J2ME, flash light, WinForms mobile, обжектив С если для айфона симбеан си и другие. Выбирай, что ближе. Сервер для игры можно сделать вебовским, используя Java + Spring + Hibernate + MySql. Должна быть авторизация юзера, выбор боёв т.е. список пользователей, которые хотят сейчас играть опционально таблица лучших игроков, чат и так далее. Прикинь, ты сидишь на скучной лекции и играешь со своим другом в морской бой, круто?
Можно ещё написать искуственный интеллект игрока, чтоб играл, когда нет других желающих. Для этого погугли журнал квант, в каком то номере за 80 - й год был алгоритм.
2) Игры типа шашек, шахмат, го и так далее. Тут уже можно сделать и броузерный клиент, делать его лучше используя флеш. Action Script 3.0 по идеологии очень похож на яву, тьюториалов туева хуча. Сервер будет состоять из тех - же частей, что и в морском бое
Дальше идут игры реального времени. Отличие их от первых двух в том, что http - сервером не обойтись, при большой частоте запросов он ляжет даже если игр и игроков мало. Нужно писать сокет - сервер, использовать что - то вроде red5, wowza или WebOrb я не советую. Во первых изучение займёт много времени, во вторых это специфические сервера, они мало где нужны, в третьих нужно понимать как работают сокет - сервера на самом низком уровне, без обёрток. Это поможет в дальнейшей работе.
Итак
3) Worms - погугли и станет ясно. Собственно, эта игра скорее пошаговая, чем риалтайм, но управлять движением червячка лучше через сокет.
4) Арканоид на шестиугольнике. Представьте себе шестиугольник по каждой грани которого ездит тележка и отражает мячик. Каждый игрок управляет своей тележкой, задача отразить мячик (их может быть и несколько) Для усложнения задачи можно поместить в центр окружность от которой мячик будет отражаться.
5) Простейшая стрелялка. По игровому полю ездят несколько танков, каждый стреляет пульками, для упрощения проблем с синхронизацией нужно, чтобы пульки и танки двигались медленно.
6) Можно придумать ещё много таких игр. Главное, чтобы они были простыми, без излишних расчётов и сложностей.
Несколько слов о общем дизайне и организации труда:
1) Никаких принятий решений на клиенте. Весь игровой алгоритм нужно реализовывать на сервере - клиент лишь отображает ситуацию на сервере и передаёт управляющие воздействия: нажатия клавиш, кнопок и т.п.
2) Не экономь на правильном решении - используй шаблоны, библиотеки, тесты везде, где только можно. Ты учишся и в спину тебя никто не гонит.
3) Нужно делать каждый день, хотябы понемногу. Не позволяйте рутине заслонить от вас процесс.
Ну вот и всё,
Владимир
Вот что по моему будет посильно для джуна
1) Самое простое - морской бой. Делать броузерного клиента для неё не имеет смысла т.к. человеку, которому доступен броузер легко найдёт флешовую игрушку поинтереснее. Поэтому клиент лучше всего сделать мобильный использовать для этого можно J2ME, flash light, WinForms mobile, обжектив С если для айфона симбеан си и другие. Выбирай, что ближе. Сервер для игры можно сделать вебовским, используя Java + Spring + Hibernate + MySql. Должна быть авторизация юзера, выбор боёв т.е. список пользователей, которые хотят сейчас играть опционально таблица лучших игроков, чат и так далее. Прикинь, ты сидишь на скучной лекции и играешь со своим другом в морской бой, круто?
Можно ещё написать искуственный интеллект игрока, чтоб играл, когда нет других желающих. Для этого погугли журнал квант, в каком то номере за 80 - й год был алгоритм.
2) Игры типа шашек, шахмат, го и так далее. Тут уже можно сделать и броузерный клиент, делать его лучше используя флеш. Action Script 3.0 по идеологии очень похож на яву, тьюториалов туева хуча. Сервер будет состоять из тех - же частей, что и в морском бое
Дальше идут игры реального времени. Отличие их от первых двух в том, что http - сервером не обойтись, при большой частоте запросов он ляжет даже если игр и игроков мало. Нужно писать сокет - сервер, использовать что - то вроде red5, wowza или WebOrb я не советую. Во первых изучение займёт много времени, во вторых это специфические сервера, они мало где нужны, в третьих нужно понимать как работают сокет - сервера на самом низком уровне, без обёрток. Это поможет в дальнейшей работе.
Итак
3) Worms - погугли и станет ясно. Собственно, эта игра скорее пошаговая, чем риалтайм, но управлять движением червячка лучше через сокет.
4) Арканоид на шестиугольнике. Представьте себе шестиугольник по каждой грани которого ездит тележка и отражает мячик. Каждый игрок управляет своей тележкой, задача отразить мячик (их может быть и несколько) Для усложнения задачи можно поместить в центр окружность от которой мячик будет отражаться.
5) Простейшая стрелялка. По игровому полю ездят несколько танков, каждый стреляет пульками, для упрощения проблем с синхронизацией нужно, чтобы пульки и танки двигались медленно.
6) Можно придумать ещё много таких игр. Главное, чтобы они были простыми, без излишних расчётов и сложностей.
Несколько слов о общем дизайне и организации труда:
1) Никаких принятий решений на клиенте. Весь игровой алгоритм нужно реализовывать на сервере - клиент лишь отображает ситуацию на сервере и передаёт управляющие воздействия: нажатия клавиш, кнопок и т.п.
2) Не экономь на правильном решении - используй шаблоны, библиотеки, тесты везде, где только можно. Ты учишся и в спину тебя никто не гонит.
3) Нужно делать каждый день, хотябы понемногу. Не позволяйте рутине заслонить от вас процесс.
Ну вот и всё,
Владимир
среда, 12 августа 2009 г.
Алгоритмы поиска пути в играх
В практике компьютерных игр часто возникает необходимость проложить курс от пункта A в пункт Б на игровом поле с отмеченными непроходимыми областями. Это может быть нужно например при движении бота к персонажу игрока. В зависимости от типа игрового мира к поиску пути применяются разные подходы.
В одном случае карту мира можно представить в виде дискретной сетки. перемещение по нему сводится к перемещению по клеткам карты. Тогда математической моделью может служить ориентированный граф вершины которого соответствуют клеткам, а рёбра возможностям перехода из одной клетки в другую. В другом - же случае мир непрерывен и положение объектов определяется их геометрической формой и взаимным расположением. Часто применяется и комбинированный подход
Если мир дискретен найти путь значит найти последовательность клеток перемещаясь по которым можно перейти из одного положения в другое. Когда — же мир непрерывен, найти путь значит найти функции линейного и углового ускорения от координат. Таким образом алгоритмы поиска пути делятся на дискретные и непрерывные. В статье [3] также предлагается деление на алоритмы локального и глобального поиска. При этом, под алгоритмами локального поиска автор понимает поиск пути в непосредственной близости от цели, соответственно, под алгоритмами глобального поиска понимается поиск на некотором протяжённом расстоянии. Однако, такое деление представляется достаточно условным так как в различных ситуациях один и тот — же алгоритм может использоваться как вблизи, так и на большом расстоянии от цели.
Алгоритм A*
Алгоритмы поиска на дискретной карте сводятся к поиску пути на графе. Существует несколько алгоритмов поиска пути. Среди них чаще всего используется алгоритм А со звездой или A* - поиск по первому наилучшему совпадению. Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).
Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. Этот алгоритм был впервые описан в 1968 году Питером Хартом Нильсом Нильсоном и Бертраном Рафаэлем. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.
A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а неf(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью. от предыдущей, как в жадном алгоритме).
В начале работы просматриваются узлы, смежные с начальной; выбирается тот из них, который имеет минимальное значение
Ввиду большой важности рассмотрим данный алгоритм более подробно. Пусть есть ориентированный граф вершинами которого являются клетки карты а рёбрами пути из клетки в клетку в случае если такой путь существует. Каждому ребру припишем некоторое число - стоимость перехода от клетки в клетку.
Алгоритм оперирует двумя списками: сортированным (далее open), в котором хранятся вершины, ребра которых еще не были обработаны (узлы сортируются по оценке расстояния до конечного узла от наиболее близкого), и не сортированный (далее close) с обработанными узлами. Изложим принцип работы данного алгоритма в виде диаграммы деятельности.
Алгоритм A* является полным в том смысле, что он всегда находит решение, если таковое существует. Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, или преемственной эвристикой. Свойство монотонности означает, что если существуют пути A—B—C и A—C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше либо равна сумме оценок путей A—B и B—C. A* также оптимально эффективен для заданной эвристики h. Это значит, что любой другой алгоритм исследует не меньше узлов, чем A* (за исключением случаев, когда существует несколько частных решений с одинаковой эвристикой, точно соответствующей стоимости оптимального пути). В то время как A* оптимален для «случайно» заданных графов, нет гарантии, что он сделает свою работу лучше, чем более простые, но и более информированные относительно проблемной области алгоритмы. Например, в некотором лабиринте может потребоваться сначала идти по направлению от выхода, и только потом повернуть назад. В этом случае обследование вначале тех вершин, которые расположены ближе к выходу (по прямой дистанции), будет потерей времени.
Проблемы возникающие при реализации A*
Скорость выполнения алгоритма
Основная сложность с реализацией A* состоит в увеличении скорости вычислений. Действительно, с ростом количества одновременных поисков и размеров карты вычисления занимают всё больше машинного времени. Как известно, основное время в поиске пути занимает работа с Open и Closed списками. Хорошо продумав алгоритмы поиска и вставки элементов можно существенно увеличить скорость работы А*. К сожалению правильной реализации собственно поиска может оказаться недостаточно в случае очень большой карты или большого количества одновременных поисков. Кроме того, следует учитывать особенности реализации структур данных для выбранной платформы. Поэтому на практике применяют ряд подходов, которые позволяют уменьшить применение А*. Некоторые из них описаны ниже.
Уменьшение точности поиска.
В случае, когда расстояние между пунктами, для которых необходимо проложить путь весьма велико, не имеет смысла находить путь с точностью до клетки. Достаточно разделить карту на непересекающиеся области или локации и в начале поиска определить последовательность локаций пройдя которые можно очутиться в исходной точке. Далее, определив необходимую локацию и соседнюю с ней, можно искать путь лишь по клеткам смежных локаций.
Остановимся подробнее на требованиях, которые налагаются на локации. В большинстве случаев путь от точки А к Б ищется для того, чтобы произвести определённые действия, к примеру бот ищет путь к персонажу игрока для того, чтобы атаковать его. Понятно, что для атаки в большинстве случаев необходимо, чтобы игроки были видимы друг другу, или говоря иными словами между ними не должно быть непроходимых областей, или клеток, если речь идёт о двумерной карте. Т.е. между центрами клеток в которых находятся персонажи A и Б можно провести прямую так, чтобы она не пересекала непроходимых клеток. Таким образом мы видим, что локация является частным случаем выпуклого множества [2] и задача разбиения карты на локации сводится к разбиению на выпуклые множества.
Предварительный расчёт пути.
Для крупных областей речь о которых шла в предидущем пункте имеет смысл расчитать оптимальные пути до начала игры. В этом случае мы экономим достаточно большое количества времени, в то — же время объем памяти необходимых для хранения матрицы путей незначителен.
Комбинирование различных алгоритмов поиска
Часто хороших результатов можно добиться используя комбинацию алгоритмов поиска. Например, найдя последовательность локаций при помощи А*. Путь внутри локации или между ними можно искать с помощью менее затратного алгоритма потенциальных полей о котором будет сказано ниже.
Проблема неестественной траектории
Хотя А* и позволяет найти путь к цели, траектория может выглядеть неестественно. Например, на рисунке
Представлена ситуация Case 1 в которой найдены два эквивалентных с точки зрения длинны поиска пути, однако очевидно, что ломаная с большим числом углов выглядит неестественно.
Далее, в ситуации Case 2 показана траектория движения соединяющая центры клеток. Понятно, что более естественной траекторией была — бы гладкая кривая обозначенная пунктиром.
В ситуации Case 3 оптимальной траекторией была — бы прямая обозначенная пунктиром. Однако, в следствие квантизации пространства, путь который нужно пройти по клеткам покрывающим её будет эквивалентен показанным сплошной линией ломаным траекториям.
Одним из путей решения проблемы естественности пути является интерполяция траектории сплайном. Другим путём решения проблемы будет предварительная проверка существуют — ли непроходимые клетки между исходной клеткой и целью. Если таких клеток нет, в использовании A* нет необходимости.
Метод потенциальных полей.
Другим часто применимым методом поиска является метод потенциальных полей. В соответствии с этим методом каждое препятствие имеет вокруг себя отталкивающее потенциальное поле сила которого обратно пропорционально расстоянию до него. Также существует однородная сила притяжения к цели. Через близкие постоянные интервалы времени вычисляется сумма притягивающих и отталкивающих векторов и объект передвигается в этом направлении.
Таким образом, отталкивающая сила будет равна
Где
- искомая ф — ция дающее направление движения в данной точке карты,
- сила притяжения к цели 
- сумма сил отталкивания от препятствия соответственно.
Очевидно, что возможны случаи, когда значение равна нулю, а значит направление движения неопределено. Эта проблема называется проблемой локальных минимумов.
Существует ряд способов её решения. Так например пытаются подобрать ф — ции, которые не имеют локальных минимумов. Другое решение состоит в том, чтобы при попадении в локальный минимум временно изменить цель, по достижении этой временной цели двигаться по направлению к главной. Данный способ выхода из локального минимума называется методом виртуальных локальных целей и изложен в [4].
Вариацией метода потенциальных полей является метод виртуальных отталкивающих клеток изложенный в [5]. Его суть состоит в том, что игровое поле разделяется на клетки (поля) и если клетка содержит препятствие, она обладает отталкивающим потенциалом. Объект, для которого нужно найти путь представляется находящимся в центре квадрата стороны которого параллельны клеткам игрового поля. Если клетка с препятствием попадает внутрь квадрата, она производит отталкивающее действие, иначе нет. Результирующая сила вычисляется как сумма отталкивающих сил от клеток с препятствиями и притягивающей к цели силе. Таким образом устраняется влияние удалённых препятствий и отдалённых частей препятствий большого размера. В следствие этого, траектория движения получается более плавной.
Иллюстрация метода представлена на рисунке.
Метод точек видимости
Данный метод всегда применяется в комбинации с методом поиска пути на графе и часто с методом потенциальных полей. Суть его в том, что вокруг неподвижных препятствий, на достаточном от них удалении чтобы избежать столкновений, расставляются точки видимости. Две точки считаются соединёнными если они видимы между собой, то есть отрезок прямой между ними не пересекает неподвижных препятствий. Математической моделью в данном случае является неориентированный граф вершины которого соответствуют точкам видимости. Две вершины соединены если соединены две соответствующие точки. Движение между двумя соседними точками можно осуществлять с помощью метода потенциальных полей. В этом случае другие объекты для которых ищется путь могут рассматриваться как препятствия. Например, когда требуется найти путь для нескольких роботов противника движущихся к роботу игрока.
Литература
1.Принцип работы алгоритма поиска пути Астар (A*) http://www.gamedev.ru/articles/?id=70121
2.Материалы сайта http://dic.academic.ru/
3.The long and short of steering in computer games Simon L. Tomlinson 2 Campden Way, Handforth, Cheshire. SK9 3JA, United Kingdom e-mail: DrSimonT@iclway.co.uk
4.ISSN 1009 - 3095 Journal of Zhejiang University SCIENCE V. 4, No. 3,P. 264-269, May- June, 2003 http://www. zju.edu.cn/jzus; http: //www. periodicals, com. en; jzus@zju. edu. en
Virtual local target method for avoiding local minimum in potential field based robot navigation ZOU Xi-yong( Ä ! )+, ZHU Jing( Ü ft ) ( College of Electrical Engineering National Laboratory of Industrial Control Technology » Zhejiang University * Hangzhou 310027» Chinai 'E- mail : zouxiyong @ 163 . net Received June 3» 2002; revision accepted Aug. 10» 2002
5.Applying an Enhanced Path Finding Avatar for a Virtual Environment Jui-Fa Chen, Wei-Chuan Lin*, Li-Hao Yang Department of Computer Science and Information Engineering, TamKang University, Danshui, Taiwan 25137, R.O.C E-mail: alpha@mail.tku.edu.tw Department of Information Technology, Tak-Ming College, E-mail: wayne@takming.edu.tw
В одном случае карту мира можно представить в виде дискретной сетки. перемещение по нему сводится к перемещению по клеткам карты. Тогда математической моделью может служить ориентированный граф вершины которого соответствуют клеткам, а рёбра возможностям перехода из одной клетки в другую. В другом - же случае мир непрерывен и положение объектов определяется их геометрической формой и взаимным расположением. Часто применяется и комбинированный подход
Если мир дискретен найти путь значит найти последовательность клеток перемещаясь по которым можно перейти из одного положения в другое. Когда — же мир непрерывен, найти путь значит найти функции линейного и углового ускорения от координат. Таким образом алгоритмы поиска пути делятся на дискретные и непрерывные. В статье [3] также предлагается деление на алоритмы локального и глобального поиска. При этом, под алгоритмами локального поиска автор понимает поиск пути в непосредственной близости от цели, соответственно, под алгоритмами глобального поиска понимается поиск на некотором протяжённом расстоянии. Однако, такое деление представляется достаточно условным так как в различных ситуациях один и тот — же алгоритм может использоваться как вблизи, так и на большом расстоянии от цели.
Алгоритм A*
Алгоритмы поиска на дискретной карте сводятся к поиску пути на графе. Существует несколько алгоритмов поиска пути. Среди них чаще всего используется алгоритм А со звездой или A* - поиск по первому наилучшему совпадению. Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).
Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. Этот алгоритм был впервые описан в 1968 году Питером Хартом Нильсом Нильсоном и Бертраном Рафаэлем. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.
A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а неf(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью. от предыдущей, как в жадном алгоритме).
В начале работы просматриваются узлы, смежные с начальной; выбирается тот из них, который имеет минимальное значение
Ввиду большой важности рассмотрим данный алгоритм более подробно. Пусть есть ориентированный граф вершинами которого являются клетки карты а рёбрами пути из клетки в клетку в случае если такой путь существует. Каждому ребру припишем некоторое число - стоимость перехода от клетки в клетку.
Алгоритм оперирует двумя списками: сортированным (далее open), в котором хранятся вершины, ребра которых еще не были обработаны (узлы сортируются по оценке расстояния до конечного узла от наиболее близкого), и не сортированный (далее close) с обработанными узлами. Изложим принцип работы данного алгоритма в виде диаграммы деятельности.
Алгоритм A* является полным в том смысле, что он всегда находит решение, если таковое существует. Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, или преемственной эвристикой. Свойство монотонности означает, что если существуют пути A—B—C и A—C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше либо равна сумме оценок путей A—B и B—C. A* также оптимально эффективен для заданной эвристики h. Это значит, что любой другой алгоритм исследует не меньше узлов, чем A* (за исключением случаев, когда существует несколько частных решений с одинаковой эвристикой, точно соответствующей стоимости оптимального пути). В то время как A* оптимален для «случайно» заданных графов, нет гарантии, что он сделает свою работу лучше, чем более простые, но и более информированные относительно проблемной области алгоритмы. Например, в некотором лабиринте может потребоваться сначала идти по направлению от выхода, и только потом повернуть назад. В этом случае обследование вначале тех вершин, которые расположены ближе к выходу (по прямой дистанции), будет потерей времени.
Проблемы возникающие при реализации A*
Скорость выполнения алгоритма
Основная сложность с реализацией A* состоит в увеличении скорости вычислений. Действительно, с ростом количества одновременных поисков и размеров карты вычисления занимают всё больше машинного времени. Как известно, основное время в поиске пути занимает работа с Open и Closed списками. Хорошо продумав алгоритмы поиска и вставки элементов можно существенно увеличить скорость работы А*. К сожалению правильной реализации собственно поиска может оказаться недостаточно в случае очень большой карты или большого количества одновременных поисков. Кроме того, следует учитывать особенности реализации структур данных для выбранной платформы. Поэтому на практике применяют ряд подходов, которые позволяют уменьшить применение А*. Некоторые из них описаны ниже.
Уменьшение точности поиска.
В случае, когда расстояние между пунктами, для которых необходимо проложить путь весьма велико, не имеет смысла находить путь с точностью до клетки. Достаточно разделить карту на непересекающиеся области или локации и в начале поиска определить последовательность локаций пройдя которые можно очутиться в исходной точке. Далее, определив необходимую локацию и соседнюю с ней, можно искать путь лишь по клеткам смежных локаций.
Остановимся подробнее на требованиях, которые налагаются на локации. В большинстве случаев путь от точки А к Б ищется для того, чтобы произвести определённые действия, к примеру бот ищет путь к персонажу игрока для того, чтобы атаковать его. Понятно, что для атаки в большинстве случаев необходимо, чтобы игроки были видимы друг другу, или говоря иными словами между ними не должно быть непроходимых областей, или клеток, если речь идёт о двумерной карте. Т.е. между центрами клеток в которых находятся персонажи A и Б можно провести прямую так, чтобы она не пересекала непроходимых клеток. Таким образом мы видим, что локация является частным случаем выпуклого множества [2] и задача разбиения карты на локации сводится к разбиению на выпуклые множества.
Предварительный расчёт пути.
Для крупных областей речь о которых шла в предидущем пункте имеет смысл расчитать оптимальные пути до начала игры. В этом случае мы экономим достаточно большое количества времени, в то — же время объем памяти необходимых для хранения матрицы путей незначителен.
Комбинирование различных алгоритмов поиска
Часто хороших результатов можно добиться используя комбинацию алгоритмов поиска. Например, найдя последовательность локаций при помощи А*. Путь внутри локации или между ними можно искать с помощью менее затратного алгоритма потенциальных полей о котором будет сказано ниже.
Проблема неестественной траектории
Хотя А* и позволяет найти путь к цели, траектория может выглядеть неестественно. Например, на рисунке
Представлена ситуация Case 1 в которой найдены два эквивалентных с точки зрения длинны поиска пути, однако очевидно, что ломаная с большим числом углов выглядит неестественно.
Далее, в ситуации Case 2 показана траектория движения соединяющая центры клеток. Понятно, что более естественной траекторией была — бы гладкая кривая обозначенная пунктиром.
В ситуации Case 3 оптимальной траекторией была — бы прямая обозначенная пунктиром. Однако, в следствие квантизации пространства, путь который нужно пройти по клеткам покрывающим её будет эквивалентен показанным сплошной линией ломаным траекториям.
Одним из путей решения проблемы естественности пути является интерполяция траектории сплайном. Другим путём решения проблемы будет предварительная проверка существуют — ли непроходимые клетки между исходной клеткой и целью. Если таких клеток нет, в использовании A* нет необходимости.
Метод потенциальных полей.
Другим часто применимым методом поиска является метод потенциальных полей. В соответствии с этим методом каждое препятствие имеет вокруг себя отталкивающее потенциальное поле сила которого обратно пропорционально расстоянию до него. Также существует однородная сила притяжения к цели. Через близкие постоянные интервалы времени вычисляется сумма притягивающих и отталкивающих векторов и объект передвигается в этом направлении.
Таким образом, отталкивающая сила будет равна
Где
- искомая ф — ция дающее направление движения в данной точке карты,
- сила притяжения к цели 
- сумма сил отталкивания от препятствия соответственно. Очевидно, что возможны случаи, когда значение равна нулю, а значит направление движения неопределено. Эта проблема называется проблемой локальных минимумов.
Существует ряд способов её решения. Так например пытаются подобрать ф — ции, которые не имеют локальных минимумов. Другое решение состоит в том, чтобы при попадении в локальный минимум временно изменить цель, по достижении этой временной цели двигаться по направлению к главной. Данный способ выхода из локального минимума называется методом виртуальных локальных целей и изложен в [4].
Вариацией метода потенциальных полей является метод виртуальных отталкивающих клеток изложенный в [5]. Его суть состоит в том, что игровое поле разделяется на клетки (поля) и если клетка содержит препятствие, она обладает отталкивающим потенциалом. Объект, для которого нужно найти путь представляется находящимся в центре квадрата стороны которого параллельны клеткам игрового поля. Если клетка с препятствием попадает внутрь квадрата, она производит отталкивающее действие, иначе нет. Результирующая сила вычисляется как сумма отталкивающих сил от клеток с препятствиями и притягивающей к цели силе. Таким образом устраняется влияние удалённых препятствий и отдалённых частей препятствий большого размера. В следствие этого, траектория движения получается более плавной.
Иллюстрация метода представлена на рисунке.
Метод точек видимости
Данный метод всегда применяется в комбинации с методом поиска пути на графе и часто с методом потенциальных полей. Суть его в том, что вокруг неподвижных препятствий, на достаточном от них удалении чтобы избежать столкновений, расставляются точки видимости. Две точки считаются соединёнными если они видимы между собой, то есть отрезок прямой между ними не пересекает неподвижных препятствий. Математической моделью в данном случае является неориентированный граф вершины которого соответствуют точкам видимости. Две вершины соединены если соединены две соответствующие точки. Движение между двумя соседними точками можно осуществлять с помощью метода потенциальных полей. В этом случае другие объекты для которых ищется путь могут рассматриваться как препятствия. Например, когда требуется найти путь для нескольких роботов противника движущихся к роботу игрока.
Литература
1.Принцип работы алгоритма поиска пути Астар (A*) http://www.gamedev.ru/articles/?id=70121
2.Материалы сайта http://dic.academic.ru/
3.The long and short of steering in computer games Simon L. Tomlinson 2 Campden Way, Handforth, Cheshire. SK9 3JA, United Kingdom e-mail: DrSimonT@iclway.co.uk
4.ISSN 1009 - 3095 Journal of Zhejiang University SCIENCE V. 4, No. 3,P. 264-269, May- June, 2003 http://www. zju.edu.cn/jzus; http: //www. periodicals, com. en; jzus@zju. edu. en
Virtual local target method for avoiding local minimum in potential field based robot navigation ZOU Xi-yong( Ä ! )+, ZHU Jing( Ü ft ) ( College of Electrical Engineering National Laboratory of Industrial Control Technology » Zhejiang University * Hangzhou 310027» Chinai 'E- mail : zouxiyong @ 163 . net Received June 3» 2002; revision accepted Aug. 10» 2002
5.Applying an Enhanced Path Finding Avatar for a Virtual Environment Jui-Fa Chen, Wei-Chuan Lin*, Li-Hao Yang Department of Computer Science and Information Engineering, TamKang University, Danshui, Taiwan 25137, R.O.C E-mail: alpha@mail.tku.edu.tw Department of Information Technology, Tak-Ming College, E-mail: wayne@takming.edu.tw
Подписаться на:
Сообщения (Atom)
Сообщения
