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

Методы моделирования, отличные от инструментария "сети Петри". Пример моделирования стандартом IDEF0 процесса получения запроса браузером. Раскрашенные (цветные) сети Петри. Моделирование процессов игры стандартными средствами сетей Петри, ее программа.
Краткое сожержание материала:

Размещено на

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

Заключение

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

Приложение

Введение

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

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

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

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

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

Цепи Маркова

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

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

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

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

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



матрица вероятностей переходов
0	1	0	0	0
0	0	1	0	0
0	0	0	1	1

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

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

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

IDEFO - Функциональное моделирование. Наиболее известной реализацией 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]

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

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