Граф невероятно простой концептуально объект, но который открывает нам множество возможностей. Знали ли вы, что такие задачи, как поиск пути, вывод древовидных комментариев и динамические структуры данных – это поле теории графов?
Если вы умеете грамотно обращаться с графом, перебирать его и, конечно же, искусно представлять его в объектной модели, то перед вами откроется много дверей, ранее закрытых.
С точки зрения математики, графы изучаются как более абстрактные объекты с какими-то отличительными свойствами. Например, есть ли направление у связи? Есть ли циклы на графе? Какие алгоритмы мы можем применять к тем или иным графам?
Но больше толку для вас, конечно же, будет представлять чисто практический опыт применения этих знаний. И чаще всего граф будет спрятан под абстракцией, и вам нужно будет грамотно представить его с инкапсуляцией, и это, зачастую, бывает очень не просто.
Что можно представлять графом?
Граф G – это два множества. Первое множество состоит из вершин (ноды, node, индексы, vertices, вертиксы). А второе множество из пар (рёбра, edges), которые определяют отношения.
Например: G = (V, E), где
V – Множество вершин;
E – Множество рёбер (пар).
Что можно описать таким графом? Например, у нас есть в игре танки. Танки разбиты на ветки, и, допустим, если мы хотим получить танк КВ-2, нам изначально нужно получить танк КВ-1.
Тогда мы могли бы сказать, что множество V содержит танки:
V = (КВ-1, КВ2, ИС-1, ИС-2, ИС-3)
А множество E содержит отношения танков, например, представлено как множество (родитель, [потомки]):
E = ((КВ-1, КВ-2), (ИС-1, ИС-2), (ИС-2, ИС-3))
Такой граф бы очертил две ветки танков, чтобы получить ИС-3 мне сначала нужно было бы открыть ИС-2,а чтобы открыть его, нужно открыть ИС-1.
Вершины бы содержали, вероятно, не только сами танки, но и дополнительные состояния: открыт\закрыт, куплен\не куплен, исследован\не исследован.
Т.е. танк открыт (доступен для исследования; на исследование тратится валюта). Следующий танк считается открытым, если исследован один из предыдущих.
Рёбра тоже могут содержать данные, например, если бы ИС-3 был доступен из другой ветки (например, исследование одного танка открывает нам два других танка), то исследование из одной ветки стоило бы одно количество валюты, а из другой другое.
У нас получился ориентированный граф, в таком графе очень важно откуда и куда лежат связи. Так связь (ИС-2, ИС-3) лежит от первого ко второму. Т.е. первый танк открывает для исследования второй, и если у нас открыт второй (в результате какой-то акции пользователь получил этот танк), то это не означает доступность первого. Допустим игрок купил за реальные деньги ИС-3, при этом, чтобы получить ИС-2, ему сначала нужно открыть ИС-1.
Инкапсуляция графа
Графы являются структурами данных – они помогают организовать связи между различными данными системы. С точки зрения объектно-ориентированного программирования – это ужас и большой вызов. Объекты должны обладать инкапсуляций – защитой внутреннего состояния. Графы в этом плане дают большое поле для творчества.
Если представлять граф, как полноценный объект, то мы уже не можем работать с ним как хотим. К структуре начинает примешиваться модель приложения и бизнес-правила. Например, если мы представим граф квестовой системы, где выполнение одного квеста может давать игроку ряд других квестов, то мы можем иметь следующие правила:
- У нас не должно быть циклов, когда, например, квест A открывает доступ к квесту B, а тот, в свою очередь, опять к квесту A.
- Открываемые квесты можно выполнить на ближайших локациях (явное выражение такого геймдизайн-правила в коде – это очень полезный трюк).
В таком случае мы уже не сможем описать граф влоб, и он будет красиво скрываться в объектной модели. Дальше мы рассмотрим как это сделать.