Разработка сетьи Петри, моделирующей процесс игры в онлайн приложение Tower Defense

Разработка сетьи Петри, моделирующей процесс игры в онлайн приложение Tower Defense

Оглавление

Введение

. Исследовательская часть

.1 Методы моделирования отличные от инструментария «сети Петри»

.2 Расширения сетей Петри  

.3 Описание инструмента моделирования

. Конструкторская часть

.1 Словесное описание моделируемого процесса

.2 Анализ сети Петри  

. Технологическая часть

.1 Программа для работы с сетями Петри

.2 Структура файла

Заключение

Список литературы

Приложение

Введение

Сети Петри - инструмент исследования систем. В настоящее время сети Петри применяются в основном в моделировании. Во многих областях исследований явление изучается не непосредственно, а косвенно, через модель. Модель - это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Манипулируя моделью системы, можно получить новые знания о ней, избегая опасности, дороговизну или неудобства анализа самой реальной системы. Обычно модели имеют математическую основу. [1]

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

Моделирование в сетях Петри осуществляется на событийном уровне. Определяются, какие действия происходят в системе, какие состояние предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнения событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы. Однако, такой анализ не дает числовых характеристик, определяющих состояние системы.

1. Исследовательская часть

.1 Методы моделирования отличные от инструментария «сети Петри»

Цепи Маркова

Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях. [4]

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

Цепью Маркова с дискретным временем называется цепь, изменение состояний которой происходит в определенные фиксированные моменты времени.

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

Пример моделирования цепями Маркова начального этапа загрузки уровня (рис.1).

Рис.1 Моделирование цепью Маркова начального этапа загрузки уровня.

Семейство стандартов IDEF

Взаимная совокупность методик и моделей концептуального проектирования IDEF разработана в США по программе Integrated Computer-Aided Manufacturing. В настоящее время имеются методики функционального, информационного и поведенческого моделирования и проектирования, в которые входят следующие IDEF-модели: IDEF0, IDEF1, IDEF2, IDEF3, IDEF4, IDEF5, IDEF6, IDEF8, IDEF9, IDEF14. [5]- Функциональное моделирование. Наиболее известной реализацией IDEF0 является методология SADT (Structured Analysis and Design Technique). Эта методика рекомендуется для начальных стадий проектирования сложных искусственных систем управления, производства, бизнеса, включающих людей, оборудование, программное обеспечение.

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

Каждая из четырех сторон функционального блока имеет своё определенное значение (роль), при этом:

Верхняя сторона имеет значение “Управление”;

Левая сторона имеет значение “Вход”;

Правая сторона имеет значение “Выход”;

Нижняя сторона имеет значение “Механизм”.

Каждый функциональный блок в рамках единой рассматриваемой системы должен иметь свой уникальный идентификационный номер. (рис.2) [4].

Рис.2 Функциональный блок.

Пример моделирования стандартом IDEF0 процесса получения запроса браузером(рис. 3)

Рис.3 Моделирование стандартом IDEF0 процесса получения запроса браузером.

Байесовские сети

Байесовские сети (Bayesian Networks) - это статистический метод описания закономерностей в данных. На основе первичной информации, содержащейся в базах данных, строится модель в виде сети, где множество вершин описывает события, а ребра интерпретируются как причинные связи между событиями. [6]

В основе байесовских сетей лежит теорема Байеса теории вероятностей для определения апостериорных вероятностей попарно несовместных событий Yi по их априорным вероятностям:

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

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

Пример моделирования Байесовскими сетями процесса проверки регистрации игрока.

Рис.4 Моделирование Байесовскими сетями процесса проверки регистрации игрока

1.2 Расширения Сетей Петри

Раскрашенные (цветные) сети Петри

Появление сетей этого класса связано с концепцией использования различных меток. Ранее все метки предполагались одинаковыми. Механизм функционирования сетей был связан только лишь с количествами меток во входных позициях переходов и определялся общими для всех меток условиями возбуждения переходов и правилами изменения различных позиций при выполнении сети. В цветных сетях каждая метка получает свой цвет. Условия возбуждения и правила срабатывания переходов для меток каждого цвета задаются независимо.[3] Множество используемых при реализации цветных сетей красок выбирается конечным или бесконечным (например, счётным). При моделировании систем цветные сети чаще всего используются для построения компактных формальных и графических представлений, в составе которых имеются однотипные по структуре и характеру функционирования группы объектов. Пример моделирования раскрашенными СП процесса проверки регистрации (рис.5).

Рис.5 Моделирование раскрашенными СП процесса обработки параметров.

Временные Сети Петри

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

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

Пример моделирования дискретно-временными СП процесса запроса таблицы рекордов. (рис.6).

Рис.6 Моделирование дискретно-временными СП процесса запроса таблицы рекордов

1.3 Описание инструмента моделирования

Сеть Петри представляет собой двудольный ориентированный граф <#"577528.files/image008.gif">

Рис.7 Участок сети, моделирующий процесс входа в игру

По завершению загрузки (t13), игрок окажется в главном меню (p13), в котором есть несколько вариантов: 1)переход (t14) в меню игры (р14), либо- 2) переход (t27) в меню настроек (р22).   Из этих меню можно вернуться обратно в главное (t15, t28 соответственно). Из меню игры (р14) пользователь может попасть в (t16) меню режима кампании (р15), либо (t18) в меню режима «удержание» (р19), из которых может вернуться (t17, t 19 соответственно) обратно в меню игры (р14).       Из меню режима «кампании» игрок может попасть либо (t20) в меню «улучшений» (р16), либо в меню покупок (p17) , либо (t24) перейти к загрузке игры (p18). Из меню «удержания» (р19) игрок может либо (t25) запросить таблицу рекордов, либо (t26) перейти к загрузке игры (р21).

Это представлено на рис.2

Рис.8 Моделирование процесса нахождения игрока в системе меню

Оказавшись в меню настроек (р22), пользователь имеет возможность перейти к настройкам звука (р23), видео (р24) или ввода (р25), запустив переходы t29, t31, t33 соответственно. Вернуться назад можно запустив переходы t30, t32, t34 соответственно. Находясь в меню настроек звука, видео или ввода, пользователь может изменить (соответственно t35, t36, t37) их. Изменённые настройки (р26) могут быть либо сохранены (t38), либо сброшены (t39). Если пользователь выберет второй вариант, он окажется (t39) в главном меню настроек, иначе, после завершения процесса сохранения (р27), он окажется (t40) в главном меню настроек. Этот процесс представлен на рис.3.

Рис.9 Моделирование процесса нахождения игрока в системе меню

Процесс игры начинается с анализа уровня сложности (р28). Затем программа переходит (t42) к инстанировке моделей окружения (р29), после этого к (t43) инстанировке игрока (р30). Когда игрок появился (t44), вычисляется длительность раунда (р31) и запускается таймер (t45). Сеть, моделирующая этот процесс, показана на рис. 4.

Рис.10 Моделирование процесса начального этапа игры

Далее параллельно выполняются два процесса - наступление врагов и защита игрока от них. Рассмотрим каждый в отдельности.

Защищаясь, игрок осуществляет перемещение (р32) по местности. Выбрав нужную позицию, он при необходимости начинает (t46) перезарядку (р33), а затем (либо сразу) переходит (t47 (либо (t48))) к прицеливанию (р34). Прицелившись (t49), игрок выполняет стрельбу (р35). При промахе игрок снова переходит (t53) к смене позиции (р32). Если выстрел произведён удачно (t50), врагу наносится урон (р36). Если противник остался жив (t54), снова возвращаемся к смене позиции (р32), иначе (t51) добавляем очки (р37) и при необходимости (t52) добавляем бонусы (р38), а затем возвращаемся (t56) к перемещению (р32), либо сразу возвращаемся (t55). Процесс защиты изображен на рис. 5.

        Рис.11 Моделирование процесса защиты игрока

Атакующие действия противников происходят по сигналам таймера. Анализируется оставшееся время раунда (р39), и, если оно закончилось (t65), уведомляем игрока о победе (p44), иначе, либо (t57) рождаются новые враги (p40), либо (t59) приближаются уже существующие (41). Если враги подобрались достаточно близко (t61), они начинают атаковать (p42), иначе возвращаемся (t60) к анализу таймера (р39). После атаки врага (p42) начинаем (t62) считать нанесённый им урон (p43), и, если ущерба достаточно (t64), уведомляем игрока о поражении (p48). Иначе переходим (t63) к анализу таймера (р39).

Рис.12 Моделирование процесса наступления противников

После уведомления (p44) о победе (t66) подсчитываются набранные очки (p45) и программа переходит (t67) к формированию запроса на сервер с информацией о завершенном раунде (p46). Когда отчет сформировался (t68) начинается его отправка (p47), а игрок возвращается (t69) в меню игры (р15). Это представлено на рисунке 7

Рис.13 Моделирование процесса уведомления игрока о результатах уровня

Оказавшись (t17) в меню магазина (p17), пользователь может выбрать тип предмета для покупки: оружие (р74), здания (р75), турели (р76), что соответствует переходам t105, t107, t109. Вернутся можно используя переходы t106, t108, t110 соответственно. Выбрав тип предмета, игрок покупает конкретную модель (t111, t112, t113). Затем формируется запрос серверу на покупку (p77, p78, p79). Когда запрос будет сформирован (t114, t115, t116), программа совершит (p80) отправку и перейдёт (t117) к ожиданию ответа (p81). Когда ответ придёт (t118), его необходимо проанализировать (p82), и затем (t119) выдать пользователю уведомление о результатах запроса (p83). После прочтения уведомления (t120) игрок вернётся к выбору следующего элемента для покупки (p17). Рисунок 8 отражает написанное выше.

Рис.14 Моделирование процесса нахождения игрока в магазине

При запросе (t25) таблицы рекордов из меню режима «удержание» (p19), сформируется запрос к серверу (p20), затем (t100) отправится (p70), и программа перейдёт (t101) к ожиданию ответа (p71). Когда ответ придёт (t102), выведем результаты на экран (p72). Посмотрев желаемые сведения, игрок вернёт (t103) в меню режима удержание. Сеть, моделирующую этот процесс, можно увидеть на рисунке 9.

Рис.15 Моделирование процесса запроса таблицы рекордов

Игра в режиме удержания начинается сразу с инстанса моделей окружения (p51), затем (t71) игрока (p52). Когда все модели инстанируются, запустится таймер (t73).

Рис.16 Моделирование процесса начала игры

Снова рассмотрим две модели поведения - игрок и враги.

Защищающийся игрок осуществляет те же действия: перемещение (р53) , перезарядку (р54), прицеливание (р55) и стрельбу (р56). За попадания(p57) начисляются очки (p58) и бонусы (p59). Рисунок 11:

Рис.17 Моделирование процесса защиты игрока

Враги неизменно рождаются (p62), приближаются (p63) и атакуют (p65). Также по сигналу таймера (t85) периодически увеличивается уровень сложности (p61). Когда враги одержат верх (t95), игра закончится.

Рис.18 Моделирование процесса наступления противника

По завершению игры (t95) игроку покажется уведомление о набранных очках (p66). Затем (t96) сформируется (p67) и пошлётся (t97) запрос к серверу с результатами игры. Программа дождётся ответа (p68) и затем (t98) уведомит игрока о том, установил ли он новый рекорд (p69). После чего игрок вернётся в меню (p19)

Рис.19 Моделирование процесса уведомления игрока о результатах уровня

2.2 Анализ сети Петри

Для оценки модели игры в приложении необходимо провести анализ сети Петри, моделирующей этот процесс

Процесс игры промоделирован стандартными средствами сетей Петри.

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

Безопасность позволяет интерпретировать позицию как условие.

Проверим на достижимость ключевые маркировки получившейся СП.

Из исходной маркировки Kµ =(p1) достижимы, например, маркировкиµ =(p13), Kµ =(p17) и Kµ =(p28), что свидетельствует о том, что игрок может оказаться в главном меню, меню покупок и зайти в саму игру. Недостижимы маркировки Kµ=(p13, р15) и Kµ=(p28, р51), что говорит о невозможности одновременного нахождения в разных разделах меню или разных типах игры.

Сеть не содержит переходов с уровнем активности 0, а значит, все реализованные функции могут быть выполнены.

3. Технологическая часть

.1 Программа для работы с сетями Петри

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

При запуске программы открывается главная форма (рис.14).

Рис.21 Главная форма редактора сетей Петри.

сеть петри игра программа

На главной форме размещены три таблицы:

Таблица входов (количество входов из i-ой позиции в j-ый переход).

Таблица выходов (количество выходов из j-ого перехода в i-ую позицию).

Таблица маркировки (отображает текущее количество фишек в позициях сети).

Меню программы имеет следующую структуру:

Файл

Создать

Открыть

Сохранить

Информация

Запустить

Верхняя панель содержит инструменты для добавления и удаления позиций и переходов.

При выборе команды Файл - Создать, появляется форма с полями для ввода количества позиций и переходов новой сети (Рис.15).

Рис.22 Форма для задания параметров новой сети.

Выбрав команду Файл - Открыть, пользователь видит диалоговое окно, с предложением выбрать файл, содержащий сохранённую ранее сеть Петри (Рис.16). После чего в редактор загружается сеть Петри.

Рис.23 Диалоговое окно для загрузки файла с СП.

Для сохранения созданной или измененной сети Петри в редакторе предусмотрена команда Файл - Сохранить, в результате выполнения которой откроется диалоговое окно, в котором необходимо либо выбрать уже существующий файл для его перезаписи, либо создать новый файл для сохранения сети.

Для удаления позиции (перехода) необходимо выбрать тип удаляемого элемента на панели редактирования, указать номер этого элемента и нажать кнопку удаления (Рис.17).

Рис.24 Форма удаления позиции (перехода).

Для осуществления запуска необходимо выбрать команду меню Запустить, в результате чего отобразится форма (Рис. 20).

Рис. 25 Запуск переходов.

На данной форме расположен список с разрешенными переходами. Для запуска перехода необходимо нажать кнопку Запустить. Внизу расположена таблица с текущей маркировкой СП, которая меняется в процессе запусков переходов. Так же имеется возможность «обратного» запуска переходов - кнопка Откат (для контроля корректности работы введено поле с указанием последовательности запущенных переходов).

При выборе команды Информация о позициях (Сеть - Информация о переходах) выводится форма со списком позиций (переходов). При клике на одном из элементов списка в двух полях напротив отображается информация о данном элементе - имена и количество входящих/выходящих переходов (позиций). При показе информации о позиции внизу отображается количество фишек в данной позиции. (Рис. 22).

Рис.26 Информация о позициях (переходах)

Структура файла

При выборе команды Файл-Сохранить формируется файл с расширением .txt .

Файл содержит описание каждой таблицы. Данные о каждой строке разделяются символом переноса строки, о каждом столбце - символом «|».

Перед каждым описанием таблицы стоит строка с указанием того, какая это таблица (input - таблица входов, output - таблица выходов, trans - таблица текущей маркировки)

Пример

Для сети, изображенной на рис.23, текстовый файл будет иметь следующий вид:

|1||

||1|

|||

Рис.27 Пример сети Петри

Заключение

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

В ходе выполнения курсовой работы был произведен анализ методов моделирования, отличных от сетей Петри: сети Маркова, IDEF0, байесовские сети. В результате анализа был сделан вывод, что сеть Петри плохо подходит для моделирования данной системы, т.к. нельзя в полном объеме описать параметры и данные, которые будут передаваться, что является неотъемлемой функцией. Так же он не позволяет вводить различные типы ресурсов, что могло бы значительно сократить и упростить модель, а так же приблизить ее к реальному функционированию системы. Также были рассмотрены некоторые расширения сетей Петри: раскрашенные СП, дискретно временные СП. Моделирование процесса игры в приложение лучше реализовать с помощью цветных сетей Петри, так как она позволяет подробно проследить за основными этапами работы и учесть различные параметры запросов и условия алгоритма.

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

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

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

Список литературы

Лескин А.А., Мальцев П.А., Спиридонов А.М. Сети Петри в моделировании и управлении Л., Наука, 1989.-135с.

Питерсон Дж. Теория сетей Петри и моделирование систем. - М. Мир,1983.-264с.

http://habarov.spb.ru/new_es/exp_sys/es06/es6.htm <http://www.habarov.spb.ru/new_es/exp_sys/es06/es6.htm>

<http://idefinfo.ru/content/view/12/27/>                

<http://itmu.vgta.vrn.ru/Subjects/Matmodel-pk/Seti-Petri.htm>

<http://klax.tula.ru/~spm/index.html>

<http://www.iacp.dvo.ru/lab_11/otchet/ot2000/pn3.html>://is.ifmo.ru/books/switch_pdf/_switch11.pdf

Приложение

Позиции