Wie verteile ich Ressourcen fair auf Fabriken, wenn die Ressourcen nahezu erschöpft sind?

12

Die Hauptressource in meinem Spiel ist Masse , die als Gleitkommazahl gespeichert wird und sich mit der Zeit ändert. Ressourcenknoten erhöhen die Masse und Fabriken entleeren sie. Wenn ich zum Beispiel einen Ressourcenknoten habe, der 5 Masse pro Sekunde liefert, werde ich bei 5 * deltaTjedem Spielschritt Masse gewinnen . Die Masse wird auf die nächste ganze Zahl gerundet angezeigt, und die Gewinn- / Verlustindikatoren werden in Zehnteln angezeigt.

Wie soll ich mit einer Masse umgehen, die auf Null trifft? Dies schafft eine Race-Bedingung, wenn mehrere Fabriken versuchen, gleichzeitig zu bauen: Fabriken, die sich zuerst in der Warteschlange befinden oder die weniger Ressourcen verbrauchen, erhalten Priorität, sobald mehr Ressourcen eingehen, und werden so schneller als die anderen gebaut.

Wie kann ich damit umgehen? Soll ich den Schritt komplett überspringen?

Mob
quelle
Bah, mein Kommentar wurde nicht gespeichert. Ich hatte eine bessere Erklärung. Grundsätzlich habe ich eine Ressource, auf die jedes Objekt bei jedem Schritt zugreift. Jedes Objekt addiert oder subtrahiert von der Ressource. Mein Problem ist, dass ich nicht weiß, was ich tun soll, wenn die Ressource 0 erreicht. Soll ich eine Art Warteschlange aufbauen? Soll ich den Schritt eines Objekts überspringen? Was?
Mob
3
Round Robin. Problem gelöst.
Patrick Hughes
Die Antwort von Roy unten in Verbindung mit dem Kommentar dazu beschreibt ein anständiges, leicht zu wartendes und zu optimierendes Round-Robin-System. Solange Ihr unmittelbares Designproblem gelöst ist, ist alles in Ordnung =)
Patrick Hughes

Antworten:

9

Ich stimme Petr zu: Es gibt keinen festen Weg, dies zu tun. Wie Sie dies tun möchten, hängt davon ab, wie Sie Ihr Spiel gestalten möchten.

Unter diesen Umständen ist es jedoch sofort offensichtlich, auf welche Art von Mechanik Sie abzielen: Sie möchten nur, dass die Dinge so schnell wie möglich produziert werden, und zwar in dem Maße, wie Sie Masse zur Verfügung haben.

Produzieren innerhalb der Kapazität

Ich werde das Buch von Supreme Commander durchblättern, da Sie ein System verwenden, das dem von Supreme Commander sehr ähnlich ist. Das Verringern der Produktionskapazität ist eigentlich ziemlich einfach.

Ein Mechaniker für Produktionsgeschwindigkeit

In jedem Aktualisierungsschritt produzieren Ihre Fabriken nicht nur eine festgelegte Menge: Sie arbeiten mit einer Produktionsgeschwindigkeit , die bestimmt, wie viel Fortschritt sie in jedem Schritt machen und wie viel Masse sie verbrauchen. Wenn Sie mit 75% Kapazität produzieren, machen Ihre Fabriken in jedem Schritt 75% mehr Fortschritte und verbrauchen 75% der Masse im Vergleich zu 100% Kapazität.

Um die Produktionsgeschwindigkeit zu berechnen, sollten Sie Ihre Fabriken abfragen, bevor Sie überhaupt etwas bauen, um die Gesamtressourcen zu ermitteln, die in diesem Schritt bei voller Kapazität verbraucht würden. Dann führen Sie eine einfache Berechnung durch:

production speed = (total mass capacity / mass required this step)
if (production speed > 1.0) production speed = 1.0

Nehmen wir an, Sie benötigen in diesem Schritt 125 Masse, um mit voller Kapazität zu produzieren, haben aber in diesem Schritt nur 100 Masse. Diese Gleichung liefert Ihnen eine Produktionsgeschwindigkeit von 0,8 (die dezimale Darstellung von 80%). Wenn Sie Ihren Fabriken anweisen, ihre Bauarbeiten tatsächlich auszuführen , geben Sie ihnen diesen Wert, um ihnen mitzuteilen, mit welcher Geschwindigkeit sie bauen: und jetzt wird Ihre Produktion auf ganzer Linie verlangsamt.

Alternativen

Sie könnten auch damit beginnen, Fabriken vorübergehend außer Betrieb zu setzen, bis die Produktionskapazität frei wird, und es könnte sehr interessant sein, zu beobachten, dass Fabriken, die von Generatoren weit entfernt sind, extrem ausgelastet sind.

Mehrere Ressourcen?

Wie Sie damit umgehen, bleibt Ihnen überlassen. Es gibt viele Möglichkeiten. Am einfachsten ist es wahrscheinlich, eine Produktionskapazität für jede Ressource zu berechnen und dann die niedrigste auszuwählen , sodass Ihre schwächste Ressource für den Rest zum Engpass wird.

doppelgreener
quelle
Ich glaube, Sie müssen der Fabrik nicht einmal sagen, dass sie mit einer Geschwindigkeit von 80% produzieren soll, denn was auch immer Ihre Fabrik erzeugt, verbraucht eine feste Menge an Masse. Zum Beispiel: Sie bauen einen Panzer, für dessen Bau 100 Massen benötigt werden. Normalerweise kann die Fabrik 2 Massen pro Zyklus verbrauchen. Dies bedeutet, dass es 50 Zyklen dauert, bis der Tank fertig ist, und jeder Zyklus, den Sie ausführen, addiert 2 zur aktuellen Masse des Tanks. Jetzt steht Ihnen nur noch 1 Masse zur Verfügung. Dies bedeutet, dass in diesem Zyklus die derzeit verbrauchte Panzermasse um 1 anstatt um 2 erhöht wird. Überprüfen Sie nach jedem Zyklus einfach die aktuelle Masse im Vergleich zur erforderlichen Gesamtmasse, um festzustellen, ob der Panzer vollständig gebaut ist oder nicht.
Thomas
Wenn Sie 0 Masse zur Verfügung haben, fügen Sie dem Tank einfach keine Masse hinzu. Die Zeit, die benötigt wird, um etwas auf diese Weise aufzubauen, hängt von Ihrem Masseneinkommen ab. Wenn Sie 2 Fabriken haben, die 2 Massen / Zyklus und nur 3 Einnahmen verbrauchen können, wird Tank 1 in 50 Zyklen und Tank 2 in 100 gebaut aktiv etwas bauen). Die Gesamtmenge an Masse, die eine Fabrik verwenden kann, kann durch Hinzufügen von Ebenen zur Fabrik verbessert werden. Zum Beispiel können sie auf Stufe 1 2 Masse ausgeben, auf Stufe 2: 3 Masse usw. usw.
Thomas
@Thomas Das Hinzufügen von Masse zu einem Produkt bei der Herstellung scheint eine übermäßig komplexe Methode zu sein, verglichen mit der einfachen Vervollständigung eines Prozentsatzes des Produkts. Zumal Ihre Fabrik alles über Ihr Ressourcensystem wissen muss, anstatt über eine einfache Eigenschaft "Produktionsrate". Wenn das Ergebnis für den Spieler dasselbe ist, halten Sie die Implementierung so einfach wie möglich. Dies erleichtert auch das Vornehmen zukünftiger Änderungen, beispielsweise beim Hinzufügen / Entfernen von Ressourcen.
Hackworth
@ Hackworth Ich bin eher anderer Meinung, die Fabrik muss nichts über das Ressourcensystem wissen. Die Fabrik weiß nur, was sie baut und wie weit es ist. Das Ressourcensystem teilt der Fabrik lediglich mit, dass dem Build ein X-Betrag hinzugefügt werden soll. Auf diese Weise müssen Sie nicht den Prozentsatz des Ressourceneinkommens berechnen, den diese Fabrik hat, und Sie müssen das Ressourceneinkommen nicht in einen zusätzlichen Prozentsatz für die Fertigstellung umwandeln.
Thomas
6

Obwohl ich die Antwort von Jonathan Hobbs gut finde, finde ich ein Warteschlangensystem noch einfacher:

Queue<Factory> queue = ...;
int numFactories = ...;

Update()
{
    int resources = GetAllResourcesForThisStep();
    for(int i = 0; i < numFactories; i++)
    {
        if(queue.Peak().RequiredResources <= resources)
        {
            Factory f = queue.Pop();
            resources -= f.RequiredResources;
            queue.Push(f);
        }
        else
        {
            break;
        }
    }
}

Dies wird wahrscheinlich im Durchschnitt genauso funktionieren wie die Implementierung von Jonathan. Jonathans Lösung kann jedoch Probleme bereiten, wenn die Arbeitsgeschwindigkeit sehr niedrig eingestellt ist und meine Implementierung eine Fabrik mit einer sehr hohen Ressourcenanforderung für diesen Frame haben könnte, die andere Fabriken für mehrere Frames blockiert.

Roy T.
quelle
+1 Ich entwickle ein Spiel mit doppelten Ressourcen, ähnlich wie in der Frage, und wenn ich das Problem mit der Versorgungssperre lösen will, habe ich vor, etwas Ähnliches zu verwenden. Nicht der genaue Code, aber die Idee dahinter. Verbraucher, die in der Lage sind, Ressourcen in einem Tick zu nutzen, erhalten im folgenden Tick eine niedrigere Priorität. Ich plane auch, ein Flag hinzuzufügen, um anzuzeigen, ob dieser Verbraucher eine hohe Priorität hat, und dem Benutzer die Kontrolle über dieses Flag zu übertragen.
John McDonald
Hüten Sie sich vor Hunger, wenn Sie ihnen separate Prioritäten geben. :)
Roy T.
Hunger mit getrennten Prioritäten wäre jedoch das Ziel. Hast du jemals Siedler 4 oder Knights & Merchants gespielt? Wenn Sie Gebäude überbauen, gehen die begrenzten Ressourcen an zufällige Gebäude und es dauert ewig, bis alles fertig ist. Sie können aber auch auswählen, ob ein Gebäude wichtig ist oder nicht. In diesem Fall werden die Ressourcen zuerst an diese wichtigen Gebäude gesendet. Der Schlüssel ist, niemals so wenig wie möglich zu überkonstruieren oder zu überkonstruieren.
John McDonald
5

Ich entwickle ein ähnliches Versorgungssystem in meinem eigenen Spiel, daher habe ich auch darüber nachgedacht, wie ich das Problem der Versorgungssperre und die Bevorzugung lösen kann. Um das Problem zu veranschaulichen, werde ich ein einfaches Beispiel erstellen:

Wenn Sie eine Liste haben: [Produzent1, Konsument1, Konsument2, Konsument3] und die Aktualisierung in der angegebenen Reihenfolge ab Angebot = 0 durchführen, erhalten Sie Folgendes:

producer1 produces 5 mass. You now have 5 mass
consumer1 wants 3 mass. Success, you now have 2 mass
consumer2 wants 3 mass. Fail
consumer3 wants 3 mass. Fail
[next tick]
producer1 produces 5 mass. You now have 7 mass
consumer1 wants 3 mass. Success, you now have 4 mass
consumer2 wants 3 mass. Success, you now have 1 mass
consumer3 wants 3 mass. Fail
etc...

consumer1 macht den ganzen Spaß, während consumer 2 und 3 hungern, bis consumer 1 zufrieden ist. Abhängig von Ihrem Spiel ist dies möglicherweise nicht wünschenswert. Ich weiß, in meinem Spiel ist es nicht. Wenn ich damit fertig bin, erstelle ich eine Warteschlange, in der Verbraucher, denen ein Tick eingegeben wurde, für den nächsten Tick an den hinteren Bereich der Warteschlange verschoben werden, an den Roy T. meiner Meinung nach gelangt. Das obige Beispiel würde so aussehen:

producer1 produces 5 mass. You now have 5 mass
consumer1 wants 3 mass. Success, you now have 2 mass. <-- Move to end of queue
consumer2 wants 3 mass. Fail
consumer3 wants 3 mass. Fail
[next tick]
producer1 produces 5 mass. You now have 7 mass
consumer2 wants 3 mass. Success, you now have 4 mass  <-- Note the order change
consumer3 wants 3 mass. Success, you now have 1 mass
consumer1 wants 3 mass. Fail
etc...

Auf diese Weise erhält jeder seinen angemessenen Anteil an den Ressourcen.

Ich plane auch, eine zusätzliche Warteschlange zu implementieren, die als Prioritätswarteschlange verwendet werden soll, damit der Benutzer bestimmte Strukturen mit Ressourcenpriorität auswählen kann. Die Prioritätswarteschlange wird immer vor der Standardwarteschlange bedient. Stellen Sie sicher, dass zuerst alle Produzenten aktualisiert werden und anschließend alle Ressourcen verbraucht werden. Anderenfalls bricht die Warteschlange zusammen, wenn Sie Ressourcen auf halbem Weg durch einen Haken produzieren und einige Konsumenten bereits ausgehungert sind.

Um es noch einmal zusammenzufassen: Aktualisieren Sie die Produzenten, dann die Prioritätswarteschlange, und verschieben Sie gefütterte Verbraucher an das Ende der Prioritätswarteschlange. Aktualisieren Sie dann die Standardwarteschlange und verschieben Sie gefütterte Verbraucher an das Ende der Standardwarteschlange.

John McDonald
quelle
Im Endeffekt könnte dies bedeuten, dass kein Verbraucher fertig wird, bis jeder Verbraucher fertig werden kann. In einem realistischen Szenario für die Produktionskette ist dies ziemlich unwahrscheinlich und kann ziemlich katastrophal sein, wenn jemand eine Warteschlange für eine massive Armee haben möchte. Er wird die ganze Zeit, in der die Armee gebaut wird, praktisch ohne Truppen sein.
Cardin
Diese Antwort war mein erster Gedanke, als ich die Frage las. Es sollte auch beachtet werden, dass die pro Tick verbrauchte Masse nicht unbedingt die Masse ist, um eine vollständige Einheit zu erstellen, sondern vielmehr die Kosten der Einheit über die erforderliche Zeit, sodass ich nicht sicher bin, ob die Bedenken von @ Cardin gültig sind, es sei denn, Ihre Einheit Die Kosten pro Tick liegen sehr nahe an Ihrer Gesamtsammelquote. Ich würde einfach die Prioritätswarteschlange explizit vom Spieler verwalten lassen, damit er entscheiden kann, wer hungert.
Brice
@Cardin, du bist ganz richtig, aber es kann auch als Spielmechaniker verwendet werden. Siedler 4, Knights & Merchants, Total Annihilation und Supreme Commander sind Spiele, von denen ich weiß, dass sie dies getan haben. Der Trick besteht darin , diese Versorgungssperre nicht zu erreichen. Wenn Sie dies tun, stellen Sie sicher, dass Sie die Versorgungssperre so schnell wie möglich verlassen. Durch das Hinzufügen einer Prioritätswarteschlange können Benutzer einfacher aussteigen.
John McDonald
3

Nun, ich werde auf Johns Idee näher eingehen, da wir dies ein wenig im Chat besprochen haben .

Bearbeiten: Diese Lösung ist eigentlich nur dann vorzuziehen, wenn der Verbrauchsartikel-Betrag davon abhängt, wie oft die Fabrik einen Stapel von Ressourcen erhalten soll. Wenn es egal ist, können Sie in der Tat nur eine Warteschlange verwenden.

Meine Lösung: Alle Fabriken in einer Prioritätswarteschlange. Die Priorität wird erhöht, da eine Fabrik unter Hunger leidet. Hunger, Priorität, auf Null gesetzt, wenn die Fabrik Ressourcen verbraucht hat. Oberste Priorität hat immer die Beschaffung der nächsten Ressourcen.

Bei der Bestimmung, welche Fabrik welche Ressourcen in einer Art Pseudocode erhält:

iterator i = factoryqueue.start()
bool starvation = false
while(i.next())
  if(i.ready)
    if (!starvation) 
      if (i.consumeAmount < resource.count) starvation = true
      else 
        i.consume(resource)
        i.priority = 0
    if (starvation)
      i.priority += 1

Auf diese Weise stellen Ihre Fabriken nacheinander jeweils 1 Produkt her. Wenn Sie die Anzahl der verbrauchten Produkte berücksichtigen möchten, damit billigere Produkte häufiger hergestellt werden, können Sie beispielsweise die Priorität um 1 / verbrauchte Menge erhöhen.

Toni
quelle
Ich würde dies gerne unterstützen, bin mir aber nicht sicher, was damit gemeint ist - es verfolgt den Hunger, aber ansonsten dreht es sich (vermutlich) genau wie normal durch die Warteschlange, und sowohl der Hunger als auch die Priorität werden nie angezeigt etwas zu tun.
Doppelgreener
Der Unterschied wird deutlich, wenn Sie die Priorität um + = 1 / amountThisFactoryConsumes erhöhen. Diejenigen, die mehr Ressourcen für die Erstellung eines Produkts benötigen, bleiben etwas zurück, sodass kostengünstigere Unternehmen proportional mehr Ressourcen in Anspruch nehmen können. Dies würde das Ressourcenverhältnis pro Fabrik ausgleichen. Dies ist jedoch immer noch kein Kinderspiel, da die Hungernummer jedes Mal auf die magische Zahl 0 gesetzt wird, wenn Ressourcen von der Fabrik verbraucht werden. Es wird also nicht garantiert, dass sie exakt gleichmäßig verteilt sind, wenn die Ressourcenerneuerung stark schwankt.
Toni
Eigentlich bin ich mir jetzt nicht so sicher, ob es tatsächlich nicht garantiert ist. Ich müsste ein paar Grafiken zeichnen und es testen, um sicherzugehen.
Toni
oh, und die Priorität ist die Qualität der Prioritätswarteschlange. Ich werde nicht erklären, wie man einen baut. Die Prioritätswarteschlange selbst ist immer nach dem Prioritätswert ihrer Mitglieder sortiert.
Toni
+1 Da es sich um eine Prioritätswarteschlange handelt, sieht die Funktionsweise jetzt einfach aus: Durchsuchen Sie die Warteschlange und suchen Sie das früheste Element aus, das Ressourcen verbrauchen könnte. Wenn die Kapazität stark aufgeteilt ist (Sie haben 1.000 Ressourcen, aber hundert 100 Ressourcen), sollte dies kein Problem sein, und die Dinge werden ziemlich gut gefüttert. Selbst wenn etwas über Ihren Ressourcen liegt, könnte es irgendwann genug sparen, um ein bisschen Fortschritt zu machen - was den Effekt hat, es zu verlangsamen oder große Dinge ganz zugunsten kleinerer Dinge auszuschalten, was eine gute Sache ist. Ich mag das sehr. :)
doppelgreener
2

Komische Frage.

Mein Problem ist, dass ich nicht weiß, was ich tun soll, wenn die Ressource 0 erreicht. Soll ich eine Art Warteschlange aufbauen? Soll ich den Schritt eines Objekts überspringen? Was?

Was Sie tun müssen, hängt von der von Ihnen erstellten Spiellogik ab . Sie können eine Warteschlange machen, Sie können überspringen. Kommt darauf an, wie du denkst, dass sich dein Spiel verhalten soll. Korrigieren Sie mich, wenn ich mich in Ihrer Frage geirrt habe.

Petr Abdulin
quelle
1

Sie können für alle Konstruktionen eine Anzahl des gesamten Ressourcenbedarfs pro Tick behalten. Wenn ein Ressourcenspeicher weniger als diese erforderliche Menge erreicht, wird der gesamte Aufbau vollständig gestoppt, bis sich der Speicher so weit angesammelt hat, dass er mindestens einen Tick Produktion unterstützt. Dann kann die Produktion wieder aufgenommen werden.

Anstatt die Produktionsrate als Float zu speichern, ist sie binär - entweder produziert Ihre Fabrik mit voller Geschwindigkeit oder nicht.

Abgesehen davon ist dieser Ansatz im Wesentlichen der gleiche wie die Antwort von Jonathan für die Produktionsraten-Sonderfälle 0,0 und 1,0 - ein beliebiger Gleitkommawert f mit 0,0 <= f <= 1,0 ist wahrscheinlich eleganter, da Sie keine ruckeligen Bewegungen der Speichermenge erhalten , aber die Logik sollte etwas einfacher sein.

Hackworth
quelle