Прохождение игры-числового паззла в виде нахождения оптимального пути в графе

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

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

А теперь постараюсь по возможности максимально кратко объяснить всё по порядку.
1. О чём речь? Есть такая игра DORD RPG (в качестве жанра заявлен resourse management). Суть игры заключается в том, что игрок может выбирать, в каком порядке продвигать в разных направлениях, при этом один и тот же выбор всегда имеет одинаковый результат (нет элемента случайности). По началу выбор кажется достаточно простым, но в итоге оказывается, что многие действия стоит надолго откладывать или вовсе игнорировать для того, чтобы в дальнейшем получить большее преимущество или, просто, пройти очередной этап. Поскольку по мере прохождения свободы выбора становится всё больше, а отдельно взятые решения принимают неожиданно бОльшую значимость (особенно ранние), я решил, что проще (но при этом достаточно интересно) будет составить карту игры-граф и скрипт для поиска оптимальных путей, и по мере продвижения расширять карту.

2. На основе чего строится граф? При максимальном упрощении игры получается следующее: по миру игры разбросано множество монстров, победа над которыми сопровождается некоторой наградой. Каждый монстр имеет уникальные параметры, которые при столкновении сопоставляются с параметрами игрока (которые можно повысить по мере прохождения) и определяют, сколько единиц здоровья теряет игрок (если это число падает ниже единицы, то это считается поражением). Награда от побед бывает двух видов: повышение параметров игрока, получение некоторых ресурсов, необходимых для продвижения по определённым путям. И ещё один момент - по некоторым путям можно перемещаться только в одном направлении.
Также примечательно, что игра поделена на уровни, которые последовательно связаны между собой одним ребром.

3. Как выглядит граф (в моём представлении)? При максимальном упрощении получится следующее. Вершины графа - награда, получаемая при достижении некоторого участка. Рёбра - наличие связи между участками. Каждое ребро имеет вес в виде некоторого числа монстром (обычно 1) и/или цены в определённых ресурсах. Если ребро пройдено хотя бы раз, то его вес становится нулевым. При этом часть рёбер могут быть пройдены только в одном направлении (у некоторых из них это ограничение снимается при прохождении).
Немного неопрятный пример можно увидеть на первом рисунке.

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

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

Миниатюры

   

0

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

Добавлено через 3 минуты
И да, не уверен по поводу более поздних уровней, но несколько последующих имеют ненамного более сложную структуру.

0

Сообщение от InferernumDeus но как при этом правильно учесть веса в этом случае?

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

0

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

0

Сообщение от InferernumDeus Только сохранять планирую лишь состояние игрока.

Странновато. Что тогда помешает делать одно и то же несколько раз? Или оно просто получится невыгодно? Кстати, можно в место графа включать в состояние определённые маркеры о выполнении некоторых действий.

Сообщение от InferernumDeus А с графом делать так: держать 2 графа - рабочий и исходный.

А зачем нужен исходный? Или ты планируешь как-то bfs прикрутить?

0

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

Сообщение от Qwertiy Странновато. Что тогда помешает делать одно и то же несколько раз? Или оно просто получится невыгодно? Кстати, можно в место графа включать в состояние определённые маркеры о выполнении некоторых действий.

В зависимости от состояния игрока некоторый путь может быть:
- непроходим
- проходим
- проходим без затрат

0

Сообщение от InferernumDeus В зависимости от состояния игрока некоторый путь может быть:

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

0

Прошу прощения.
От состояния игрока зависит результат первого прохождения по ребру.

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

А само состояние игрока определяется характеристиками (которые повышаются при посещении определённых вершин графа) и ресурсами, требуемыми для продвижения по рёбрам (здоровье, ключи).

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

0