Ненормальное программирование
Разработка игр
Комментарии 47
+3

Это безумно интересно! Неожиданное и изящное применение мат.аппарата.

+3
Я уверен, что подобный метод можно применить и для гейм-дизайна. Например, вычислять cost/benefit для квестов, выявляя недостатки в балансе. Находить недоиспользуемые области мира. Определять по метрикам квесты с неудачным дизайном (много гринда или бесполезных перемещений по миру), прогрессию и pacing в течение игры или квестовых цепочек, и так далее.
0

А игроки потом прыгают по горам и бегают голышом по полям нетчей.

+3
В Kingdom Come чтобы не чиниться бегал голый и одевался перед дракой )
+4
Вы походу плохо понимаете смысл перемещений по миру в квестах.
Если не надо никуда бежать, то все квесты проходятся в 100500 раз быстрее и соответсвенно быстрее надоедают/их надо больше.
Как бы разнесены в пространстве они СПЕЦИАЛЬНО.
0
Позволю себе не согласиться. Ничто не надоедает больше, чем бессмысленная беготня с одного конца карты на другой. Для этого и вводят механизмы типа fast travel или порталов в Diablo, например.
+1
Ага, а также ничто не надоедает больше, чем бить 100 монстров на 100 шкурок.

Только вот квесты типа перейти через улицу, отнести письмо, вернутся назад и полочить 1опыта еще быстрее надоедают.

А фаст тревел делаются для смены локаций квестов, а не для «более быстрого прохождения».
+2
Беготня по пустому миру, да по одним и тем же маршрутам — конечно надоедает. Но если мир наполнен секретами и случайными событиями путешествия и исследование становятся чуть ли не самой интересной частью игры. Потому разумно распределять сюжетную нагрузку по миру так чтобы игроку не приходилось проходить по одним местам больше пары раз и чтобы на пути обязательно встречались какие-то «точки интереса».
0
Ничто не надоедает больше, чем бессмысленная беготня с одного конца карты на другой.

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

0
А если читернуть — добраться туда до взятия квеста, оставить там метку, а после взятия квеста применить «возврат»? Не помню, считается ли прочтение свитков за разговор, но заклинания «из памяти» там делаются руками.
0

Я так и делал. Главное узнать о точке назначения раньше, чем взять квест.

+2
У вас для расчёта расстояний учитывается только геометрическое расстояние между локациями? В Morrowind много мгновенных перемещений кроме mark/recall, например силтстрайдеры. Задача уровня nightmare: добавьте в мат. модель расчёта расстояний кольцо данмерских крепостей и поиск ключей для них. :)
0
В тексте же написано, что с учетом мгновенных перемещений, кроме mark/recall.
0
А еще заклинание прыжка и бонусы акробатики (свиток Икара...)
-6
Уважаемый Нирован, подскажите Каким кратчайшим путем и как обуздать Министерство справедливости?
0
Интересно, сколько времени занимает такое оптимизированное прохождение без учета требований к навыкам? Например, если до этого герой уже прокачался по полной…
P.S. На карте не отмечено побережье Шеогората.
0
Шигорада. Названо в честь Принца Безумия Шеогората, но не точно также. В том числе и на английском: Prince Sheogorath, но Sheogorad region.
0
помнится там была жутко недоработанная система параметров. Например прокачав только интеллект и алхимию, можно делать бутылки которые будут добавлять интеллект, и снова делать бутылки которые будут добавлять интеллект еще больше… В результате чего мы быстро-быстро можем поднять параметры до заоблачных высот. И после чего перемещение из одной области в другую ограничивается только скоростью компа который пытается загружать эти самые области ))
0
1. А можно пояснить каким образом задача о получении всех правильных нумераций (или как вы говорите топологических сортировок) сводится к задаче коммивояжера?
2. Дано: ациклический граф квестов. Найти: кратчайшие пути из заданного источника (у нас 0 фракций) в набор стоков (мы во всех фракциях). Зачем отжиг, если эта задача решается за O(M)? Поправьте, если не понял Вашу формулировку задачи.

PS: про морроувинд почти ничего не знаю
0
Вы, видимо не поняли, что речь не о пути в графе квестов, а о пути в игровом мире.
Граф квестов — это граф зависимостей — правил, что можно делать после чего. Но набор этих правил не полный, поэтому есть варианты и их много.
Каждое действие происходит в какой-то локации. Несколько действий могут быть в одной локации, локации могут быть далеко и близко (по времени перемещения).
Не уверен, что ясно выразился. Узлы графа квестовых зависимостей можно обходить не по рёбрам этого графа. И таких обходов очень много. Тут и появляется задача коммивояжера.
+1
Узлы графа квестовых зависимостей можно обходить не по рёбрам этого графа.

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

Тут и появляется задача коммивояжера.

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

Вы, видимо не поняли, что речь не о пути в графе квестов, а о пути в игровом мире.

Это как раз понятно, что мы хотим сократить время прохождения в итоге. Но для этого нужно выполнить квесты! Напишу как я понимаю эту задачу в постановке автора. Каждый квест переводит персонажа в некоторое состояние описываемое числовым вектором. У автора есть два графа. Один геометрический и описывает локации и расстояния между ними, второй граф зависимостей по квестам. Автор пытается осуществить одновременное перемещение по обоим графам так, чтобы на втором прийти в целевую вершину, а в первом пройти минимальный путь. Такая формулировка задачи понятна, исходя из моих знаний о ММОРПГ. Но в такой постановке ее решать сложно и странно. Я уверен, что могу переформулировать задачу так, что она будет решаться алгоритмом Дейкстры, т.е. детерминировано без ML, отжигов и пр. Но сначала я хочу убедиться, что правильно понимаю задачу, и автор понимает о чем пишет.
0
Начну отвечать с конца. Вы описали проблему именно так, как её понимаю и я. Я тоже имел в виду два графа и одновременное перемещение по обоим.
Как я понял, автор считает эту задачу задачей коммивояжера с дополнительными ограничениями.
Также автор отмечает, что эти дополнительные ограничения сокращают пространство решений NP-полной задачи коммивояжера недостаточно сильно. Кроме того. для упрощения задачи автор неоднократно вводил упрощения и условности, которые, строго говоря, могли оставить за пределами рассмотрения ряд претендентов на оптимальное решение.

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

Единственная сложность — как раз с заклинанием телепортации, но именно его-то автор еще не рассматривал.
0

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

0
Не все так плохо: квестовые линии же больше вытянутые чем широкие. Будет (количество локаций)*(длина квестовой линии)^(количество линий).

В любом случае, искать кратчайший путь на этом графе намного проще чем решать задачу коммивояжера на нем же.
0
Я по прежнему не вижу на каком графе автор планировал решать задачу коммивояжера. У игрока нет цели обойти все, как у коммивояжера. У него есть цель: выполнить набор линеек квестов, которые пересекаются, за минимальное время. Можете пояснить где тут гамильтонов цикл?
0
Нет, не могу — но другого графа у автора в любом случае нет :-)
0
Я по прежнему не вижу на каком графе автор планировал решать задачу коммивояжера. У игрока нет цели обойти все, как у коммивояжера.

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

0
Задача коммивояжера с ограничениями может быть совсем даже полиномиальной. Приведу вырожденный пример не про спидран: пусть требуется построить гамильтонов путь так, чтобы в нем вершины с меньшими номерами предшествовали вершинам с большими номерами. Таким образом, нужно либо доказывать, что эта задача сводится к коммивояжеру на полном графе, либо оговорится, что она видится таковой.

В любом случае, спасибо за разъяснения. Теперь вижу коммивояжера, но я бы так не решал эту задачу.
0
Задача коммивояжера с ограничениями может быть совсем даже полиномиальной.

Это все зависит от конкретного множества ограничений. Может, у вас останется всего один возможный путь (и считать уже, собственно, нечего), а может — множество пустое, и тогда мы получаем неограниченную задачу. Поскольку никакой информации о характере множества ограничений у нас нет, то мы остаемся в ситуации общего положения, то есть NP-complete.


Теперь вижу коммивояжера, но я бы так не решал эту задачу.

А как? В том и смысл NP-complete задач, что единственный способ их решения — это перебор. Других вариантов просто не существует.

0
Поскольку никакой информации о характере множества ограничений у нас нет, то мы остаемся в ситуации общего положения

Если Вы не смогли доказать, что ограничения достаточно строгие, чтобы она перестала быть NP-complete, то это не значит что это не так. Если докажете, что она сводится к любой NP-полной задаче, то соглашусь, а пока ничего не доказано, спорить бесполезно.
0
Если Вы не смогли доказать, что ограничения достаточно строгие, чтобы она перестала быть NP-complete, то это не значит что это не так.

Вы, видимо, не в курсе, как считается сложность. Именно что значит. Любая задача имеет сложность Х, пока не доказано, что она может быть решена быстрее. То есть это, наоборот, надо доказывать, что любые ограничения будут достаточно строгими, чтобы задачу упростить.И если существует хоть одно ограничение, которое сводит к задачу к NP-complete — то она NP-complete. И у нас такое ограничение есть — это пустое ограничение, так что все доказано математически строго :)


Ну а если говорить о практике, а не о математической теории — задача коммивояжера нерешаема уже для 20 локаций (по крайней мере на домашнем пека за разумное время). То есть нам во время выполнения надо иметь 20 локаций с независимыми посещениями, чтобы показать, что беда. У нас в практически любом прохождении будет заведомо больше таких локаций.

0
Ну а если говорить о практике, а не о математической теории — задача коммивояжера нерешаема уже для 20 локаций (по крайней мере на домашнем пека за разумное время).


Вы очень плохо информированы. Если откроете работу Костюка 2013г., то у него вроде написано про 100 вершин за минуту. Ну, и посмотрите работу 2017г, начиная с 8 слайда (за минуту 150 вершин последовательный алгоритм).
0
Вы очень плохо информированы. Если откроете работу Костюка 2013г., то у него вроде написано про 100 вершин за минуту. Ну, и посмотрите работу 2017г, начиная с 8 слайда (за минуту 150 вершин последовательный алгоритм).

Это все эвристики.

0
mayorovp чуть выше описал именно то, то я имел ввиду. Сначала построим Декартово произведение графов. Т.е. строим граф состояний, в котором вершина соответствует географической локации, набору выполненных и взятых квестов, а дуга связывает две вершины, если можно выполнить элементарное действие (перемещение, сдача квеста, взятие квеста и пр), которое позволит перейти из одного состояния в другое. Дальше Дейкстра на новом графе.
0
Т.е. строим граф состояний, в котором вершина соответствует географической локации

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

0
Проблема заключается в том, что поиск в графе состояний — NP-complete

Утверждение в целом не верно, могу привести примеры задач, где все вполне полиномиально. Для задачи коммивояжера — верно. Но посмотрите на мою формулировку задачи: я решаю не задачу коммивояжера.

Вижу ваш комментарий выше, в котором говорится почему автор решает коммивояжера. Буду думать.
0
Утверждение в целом не верно

Оно в целом верно.


Но посмотрите на мою формулировку задачи: я решаю не задачу коммивояжера.

Именно ее вы и решаете. От того, что вы переформулировали задачу коммивояжера в задачу поиска кратчайшего пути в графе состояний, как выше я сделал в моем посте — ее сложность не меняется.


Задача состоит в том, что вам дано N вершин, и вы должны найти кратчайший вариант их обхода. И как не меняй формулировку — это задача, эквивалентная задаче коммивояжера.

-1
Задача состоит в том, что вам дано N вершин, и вы должны найти кратчайший вариант их обхода. И как не меняй формулировку — это задача, эквивалентная задаче коммивояжера.


Даже если рассмотреть ваш подход к решению задачи, то цитируемая мной фраза ошибочна. На самом деле, у вас серия из K задач коммивояжера на подграфах исходного графа с размерностями N1, N2,… ,NK. И, совершенно очевидно, что для каждого следующего подграфа будут пути, которые вы уже рассматривали.

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

Поэтому я настаиваю, что если правильно организовать перебор, то решение полиномиально.
0
На самом деле, у вас серия из K задач коммивояжера

Но К задач коммивояжера не может быть проще, чем одна единственная. А одна единственная решается перебором. Даже если все остальные вообще решать не нужно, пусть они решаются хоть за константу — это уже не важно.


Ее можно решать полным перебором, но если делать это правильно (динамикой), т.е. повторно не рассматривать уже рассмотренные частичные решения, то вы получаете полиномиальный алгоритм.

Нет, не получите.


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

Вы говорите о том, что если у вас уже есть решение задачи, то эту задачу можно не решать. Это очевидно. Но чтобы решение было, его нужно получить. Это первое. Второе — решение кусочка коммивояжера никак вам не поможет при решении более широкой задачи. Если вы сперва решили задачу для 20 точек, потом одну единственную (!) точку поменяли, то придется решать целиком заново. Никакой динамики для коммивояжера (ну и для рюкзака, конечно же) не существует.


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

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

Я вам уже несколько раз сказал, что я решаю не задачу коммивояжера, а ту задачу которая описана в этой статье. И она задачей коммивояжера не является. Но, видимо, мне действительно стоит прекратить писать здесь, т.к. мы с вами друг друга не слышим.

Никакой динамики для коммивояжера (ну и для рюкзака, конечно же) не существует.

Для рюкзака существует. Смиритесь.
0
Я вам уже несколько раз сказал, что я решаю не задачу коммивояжера, а ту задачу которая описана в этой статье.

А в статье решается задача коммивояжера.


И она задачей коммивояжера не является.

Как это не является? Вам дано n вершин, вам надо найти кратчайший обход. Что это если не задача коммивояжера?


Для рюкзака существует. Смиритесь.

Динамики, про которую вы говорили (позволяющую решить рюкзак за полиномиальное время) не существует. Читайте внимательнее материал, на который ссылаетесь.

0
Для рюкзака существует.

Вот только сложность линейно зависит от размера рюкзака.
Таким образом увеличение входа на один бит удваивает время решения.

Только полноправные пользователи могут оставлять комментарии. , пожалуйста.