Игровой дизайн, гейм дизайн (game design)
GameDev.ru / Игровой Дизайн / Статьи / Математическая модель игры Доббль (4 стр.)

Математическая модель игры Доббль (4 стр.)

Страницы: 1 2 3 4 5 Следующая

Автор:

Как построить проективную плоскость?

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

Например, для проективной плоскости 7 порядка можно посетить такую страницу: https://www.uwyo.edu/moorhouse/pub/planes/pg27.txt 
Там представлена матрица из чисел. Строки - это карточки (точки) в понятиях Доббля. Числа в строках - это порядковые номера символов (линий), начиная с нуля, которые нарисованы на каждой карточке (проходят через данную точку).

Также можно воспользоваться услугами математических пакетов, таких, как Matlab, чтобы построить матрицу инцидентности проективной плоскости. [2] [3]

Матрицы инцидентности

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

Одним из простейших примеров матрицы инцидентности может служить матрица размером 2х1 для неориентированного графа из двух вершин, соединённых одним ребром:

1 | Математическая модель игры Доббль
Рис. 14. Неориентированный граф из двух вершин, соединённых одним ребром, и его матрица инцидентности.

Более сложный пример графа и его матрицы инцидентности:

1 | Математическая модель игры Доббль
Рис. 15. Неориентированный граф с 4-мя вершинами и его матрица инцидентности.

Как видно из последнего примера, в матрице инцидентности графа в каждом столбце ровно две единицы, т.к. одно ребро соединяет две вершины. 

Проективная плоскость является гиперграфом, так как одна прямая (ребро) соединяет несколько точек (вершин). Поэтому в матрице инцидентности проективной плоскости единицы в каждом столбце встречаются [cht]n+1[/cht] раз, где [cht]n[/cht] - порядок проективной плоскости.

Для плоскости Фано, изображённой на рис. 9, матрица инцидентности будет иметь следующий вид:

1 | Математическая модель игры Доббль
Рис. 16. Матрица инцидентности плоскости Фано.

Для упрощения восприятия нули не показаны, а единицы заменены на символ Х.
В таком представлении проективной плоскости хорошо заметен принцип двойственности точек и прямых - прямая проходит ровно через 3 точки, и, в то же время, точка принадлежит ровно трём прямым.

Построение проективной плоскости перебором

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

Для всех столбцов
    Для всех строк
        Если в столбце стоит n+1 единиц, то перейти к следующему столбцу
        Если в строке стоит n+1 единиц, то перейти к следующей строке
        Для каждого предыдущего столбца Х
            Если в столбце Х на текущей строке стоит единица
            и
            Если уже есть совпадения в строках для столбца Х и текущего столбца,
                то перейти к следующей строке
        Поставить единицу
    Перейти на следующую строку
Перейти на следующий столбец

Следуя этому алгоритму, мы получим симметричную матрицу для плоскости Фано:

1 | Математическая модель игры Доббль
Рис. 17. Матрица инцидентности плоскости Фано, построенная по алгоритму псевдокода.

Эта матрица не совпадает с предыдущей. На самом деле, это неважно. 
Перестановка любых двух строк матрицы инцидентности равносильна перенумерации вершин графа. 
Перестановка любых двух столбцов матрицы инцидентности равносильна перенумерации рёбер графа (если их заранее пронумеровать).

Страницы: 1 2 3 4 5 Следующая

5 мая 2017

#геймдизайн, #Доббль


Обновление: 21 мая 2017

2001—2017 © GameDev.ru — Разработка игр