Я делаю небольшую игру на Java, чтобы попрактиковаться в программировании, и натолкнулся на эту маленькую проблему, которую я не могу решить самостоятельно.
В этой игре я хочу создать виртуальный магазин, в котором я могу покупать и продавать предметы.
Большинство предметов можно получить только в игре, создав их из других предметов, следуя тому, что я назвал «рецептами». Рецепт - это просто набор предметов, необходимых для создания нового предмета. Предмет может иметь несколько рецептов. Результатом рецепта может быть более одного экземпляра новой суммы. Я буду обозначать такие рецепты как [предмет, предмет, ..., предмет] (итоговая сумма).
Таким образом, существуют базовые предметы, которые не могут быть созданы, но должны быть получены другими способами, и существуют созданные предметы, которые могут быть получены только по одному из его рецептов.
Я хочу попытаться смоделировать спрос и предложение, и я придумала это свойство, которое я называю «сумма сделки», которая устанавливается равной 0 для каждого элемента. Сумма сделки показывает, сколько товара продается или покупается. Если я продам X количества предмета, его объем торговли увеличится на X, а если я куплю Y количества предмета, его объем торговли уменьшится на Y.
Теперь мне нужно определить цену на мои товары.
Всем базовым предметам присваивается фиксированное значение. Затем стоимость и сумма сделки включаются в функцию f (v, t), которая выплевывает цену. Эта цена всегда> = 0. Одним из свойств этой функции является то, что если сумма сделки t равна 0, то итоговая цена равна входному значению v. Так что, если один игрок покупает заданное количество товара, сумма сделки идет вниз на x, и цена становится ближе к 0. Если затем другой игрок продает такое же количество того же предмета, сумма сделки возвращается к 0, и цена возвращается к первоначальному значению.
Теперь, когда все базовые предметы имеют значение, мне нужно вычислить значения всех созданных предметов, чтобы иметь возможность рассчитать их цену с помощью f. Я хочу, чтобы их ценность основывалась на самом дешевом рецепте, необходимом для их создания. Поэтому я должен проанализировать все рецепты, сложить цены всех предметов, использованных в каждом рецепте, и определить минимальную цену рецепта. Это значение созданного предмета.
Я могу смоделировать эту настройку в виде графика с вершинами, представляющими предметы, которыми можно торговать в магазине, а направленные ребра соединяют предмет с другим предметом, который можно создать из исходного предмета. Таким образом, у меня есть направленный край («источник -> пункт назначения»), где источник является ингредиентом в одном из рецептов пункта назначения. Исходя из этого, я создаю случайный ориентированный граф из 600 вершин.
Этот график меняется каждый раз при загрузке игры, и генератор должен специально разрешать циклы внутри графика.
Вот пример:
Элементы A и B являются базовыми элементами со значениями 10 и 2 соответственно. Их торговые суммы изначально равны 0, поэтому их цены равны их значениям 10 и 2.
Элемент C - это созданный элемент с двумя рецептами R1 = A, A, B и R2 = B, B, B. Теперь я определяю R1 по цене 22, а R2 по 6, что является минимальной ценой рецепта. , Таким образом, позиция C имеет значение 6 (и изначально сумма сделки равна 0, поэтому цена также равна 6).
В этом случае график будет выглядеть примерно так: (A) -> (C) <- (B) </p>
До этого момента все прекрасно и идеально работало.
Теперь у меня возникает проблема, когда зависимости цена-значение являются циклическими.
Вот 3 типа дел, в которых мне нужна помощь:
(1) - 0 вершинный цикл
Проще говоря, предмет A имеет фиксированную цену, и предмет B можно создать по рецепту [A, B]. Если цена B изменяется, то все элементы, созданные B, должны быть пересчитаны. В этом случае B состоит из A и B, поэтому я также должен пересчитать цену B. Это снова вызывает пересчет B и так далее, и так далее ...Я знаю, что предпосылка странная, но думаю, что это перекраска двери (B).Он сделан из той же двери (B) плюс краска (A).Я называю это циклом с 0 вершинами, потому что при прохождении цикла вы пропускаете 0 вершин, чтобы вернуться к тому, с чего начали.
(2) - 1 цикл вершин
Если мы возьмем те же предметы A и B из самого первого примера и добавим элемент C с рецептами R1 = A, B и R2 = D, D, D и пункт D с рецептом R3 = C.Таким образом, C можно «разбить» на 3 D, а 3 D можно объединить в один C. Если я теперь снизу цену C, продавая ее много, мне следует также снизить цену D, поскольку можно сделать DC. Но поскольку C также может быть сделан из D, и, предполагая, что R2 становится дешевле, чем R1, я должен также понизить цену C, таким образом снова вызывая снижение цены D и так далее, и так далее.Это будет продолжаться до тех пор, пока значение не приблизится где-либо в зависимости от ингредиентов рецептов.Я называю это циклом из 1 вершины, потому что при прохождении цикла вы проходите только одну вершину.
(3) - n циклов вершин
Это общий случай,и я думаю, что если я решу это, два конкретных случая выше также будут решены.Если элемент A сделан из B, B из C, C из D и т. Д. До элемента Z, который состоит из A, то изменение цены одного вызовет изменение цены следующего, что вызоветцена следующая и тд и тп.Эта цепочка может быть практически произвольной длины. **
Я ищу алгоритм, который может решить мою проблему.Я хочу иметь возможность рассчитать все значения и цены для всех предметов с начальным объемом торговли, равным 0. Когда игроки покупают и продают предметы, изменения цен должны распространяться по графику.Я рассмотрел вопрос об изменении алгоритма Дейкстры, A *, алгоритма Беллмана-Форда и алгоритма Флойда-Варшалла, но не смог получить удовлетворительный результат ни с одним из них.
Может кто-нибудь направить меня в правильном направлении?