Automatisch organisiertes / intelligentes Inventarsystem?

11

In der letzten Woche habe ich mit Unity3D an einem Inventarsystem gearbeitet. Zuerst bekam ich Hilfe von den Jungs von Design3, aber es dauerte nicht lange, bis wir uns trennten, weil mir die Art und Weise, wie sie ihren Code machten, wirklich nicht gefiel, es roch überhaupt nicht nach OOP.

Ich habe weitere Schritte voraus gemacht - Gegenstände belegen mehr als einen Steckplatz, ein erweitertes Platzierungssystem (Gegenstände versuchen ihr Bestes, um die beste Passform zu finden), ein lokales Maussystem (die Maus bleibt im aktiven Taschenbereich gefangen) usw.

Hier ist eine Demo meiner Arbeit.

Was wir in unserem Spiel haben möchten, ist eine automatische Organisationsfunktion - keine automatische Sortierung. Wir möchten diese Funktion, da unser Inventar in Echtzeit angezeigt wird - nicht wie in Resident Evil 1,2,3 usw., wo Sie das Spiel pausieren und Dinge in Ihrem Inventar erledigen würden. Stellen Sie sich jetzt vor, Sie befinden sich in einer schwierigen Situation, umgeben von Zombies, und Sie haben keine Kugeln. Sie sehen sich um. Sie sehen, dass sich Kugeln in der Nähe auf dem Boden befinden. Gehen Sie also zu ihnen und versuchen Sie, sie aufzuheben, aber sie ziehen nicht an passt nicht! Sie sehen sich Ihr Inventar an und stellen fest, dass es passt, wenn Sie einige der Artikel neu organisieren! - Jetzt hat der Spieler - in dieser Situation keine Zeit, sich neu zu organisieren, weil er von Zombies umgeben ist und stirbt, wenn er anhält und das Inventar organisiert, um Platz zu schaffen (Inventar in Echtzeit speichern, keine Pause) - würde nicht. Ist es nicht schön, dass das automatisch passiert? - Ja!

(Ich glaube, dies wurde in einigen Spielen wie Dungeon Belagerung oder so implementiert, also sicher, dass es machbar ist.)

Schauen Sie sich dieses Bild zum Beispiel an:

Was macht die automatische Sortierung?

Ja, wenn Sie das Problem automatisch sortieren, erhalten Sie Ihre Leerzeichen, aber es ist schlecht, weil: 1- Teuer: Es ist kein ganzer Sortiervorgang erforderlich, um diese Leerzeichen freizugeben. Schieben Sie im ersten Bild einfach das rote Element an die ganz unten ganz links, und Sie erhalten die gleichen Leerzeichen, die Sie durch die automatische Sortierung erhalten haben. 2- Es ist ärgerlich für den Spieler: "Wer hat dir gesagt, dass du meine Sachen nachbestellen sollst?"

Ich frage nicht nach "Wie schreibe ich den Code?", Sondern frage nur nach einer Anleitung, wo ich suchen soll, welche Algorithmen beteiligt sind. Hat das etwas mit Grafiken und Sachen mit dem kürzesten Weg zu tun? Ich hoffe nicht, weil ich es nicht geschafft habe, mein College-Studium fortzusetzen: / Aber selbst wenn es so ist, sag es mir einfach und ich werde die damit verbundenen Dinge lernen.

Beachten Sie, dass es mehr als nur eine Lösung geben kann. Ich denke, das erste, was ich tun muss, ist herauszufinden, ob die Situation "lösbar" ist. Wenn ich weiß, wie ich feststellen kann, ob eine Situation lösbar ist oder nicht, kann ich sie "lösen". Ich muss nur die Bedingungen kennen, die es "lösbar" machen. Und ich glaube, dafür muss es einen Algorithmus / eine Datenstruktur geben.

Hier ist ein Bild für mehr als eine Lösung für den Versuch, ein 1x3-Objekt zu montieren:

Geben Sie hier die Bildbeschreibung ein

Die Pfeile zeigen nur eine der Lösungen, aber wenn Sie schauen, werden Sie mehr als eine finden. Dies ist, was ich letztendlich nicht automatisch sortiere, sondern eine Lösung finde und anwende.

Beachten Sie, dass ich, wenn ich Zeit damit verbringe, einen Weg finden werde, es zu lösen, aber es wäre nicht der beste Weg, ein Autorad mit den Füßen statt mit den Händen zu halten! XD Oder einfach nur versuchen, ein Problem zu lösen, für das Arrays erforderlich sind, dessen Existenz Sie jedoch noch nicht kennen! Was ist der richtige Ansatz dafür?

Aktualisierungen aus dem Kommentar

@Stephen Ich bin wirklich kein Guru in Alogs, du hast 'Rucksack' erwähnt und @BlueRaja - Danny Pflughoeft hat ein 2D-Bin-Pack-Algo erwähnt. Sind sie irgendwie verwandt / gleich? - Ich bin immer noch verwirrt, wie ich das angehen soll.

Und ja, ich verwende bereits eine "Heuristik", aber ich wusste nicht wirklich, dass ich es bin: D Sie findet den ersten verfügbaren Steckplatz und prüft, ob der Artikel dort passt.

Ich weiß nicht, ob das Bestellen von Artikeln aufgrund ihrer "Sperrigkeit" (die ich nSlotsRequired = nRowsReq * nColsRec nenne) funktionieren würde, da Sie beispielsweise 2x2- und 1x4-Artikel haben, sie haben die gleiche Sperrigkeit, aber unterschiedliche Formen und haben ein anderer Effekt darauf, wie der Rest der Elemente als nächstes gehen wird. SO... :/

Ich habe dieses Video gesehen, die Idee mit der vollständigen Verpackung hat mir sehr gut gefallen, aber ich frage mich, wie ich vorgehen soll, da das Inventar 2D ist. Ich bin mir nicht mal sicher, ob das Verpacken von Behältern hier der Schlüssel ist, denn es stimmt, dass ich mehr als eine Tasche haben kann, aber in unserem Spiel wird es nur eine Tasche sein. Es geht also darum, Gegenstände in eine Tasche zu packen und nicht mehr. Die Beispiele in diesem Video (die Rohre und Busse) passen also nicht wirklich zu meinem Problem. Ich habe auch ein paar Sachen über diese Rucksack-Sache gesehen. Ich habe nicht gesehen, wie der 'Wert' mit meinen Gegenständen / meinem Inventar zusammenhängt, aber ich denke, 'Gewicht' ist dasselbe wie Sperrigkeit, nicht sicher.

ärgerlich
quelle
7
Dies ist eine 2D-Behälterverpackung, die NP-vollständig ist. Daher ist jeder Algorithmus, der Ihnen sagt, ob Sie alle Elemente anpassen können, ineffizient (im schlimmsten Fall). Sie können jedoch einige ziemlich gute Approximationsalgorithmen finden.
BlueRaja - Danny Pflughoeft
Genau aus diesem Grund habe ich mich stattdessen für das (heutzutage üblichere) Inventarmodell mit einem Steckplatz pro Artikel entschieden. Ich wünschte ich hätte eine Lösung für dich, ich habe dieses Problem aufgegeben ...
Ryno
@ BlueRaja-DannyPflughoeft Ich frage mich, ob ein einfacher / effizienter Algorithmus verfügbar ist, wenn die Elemente auf bestimmte Formen beschränkt waren.
Congusbongus
Das Begrenzen von Formen verringert nicht die Komplexität, sondern erleichtert nur das Nachdenken, sodass Sie der Meinung sind, dass die Komplexität gehandhabt wurde, afaik.
Patrick Hughes
@VeXe Entschuldigung, ich habe das Update für Ihre Frage verpasst. Müllverpackung und Rucksack sind nicht dasselbe. Aber beide sind Verpackungsprobleme. Der 'Wert' in Ihrem Fall ist die Form und Größe Ihrer Inventarobjekte.
Stephen

Antworten:

8

Dies ist eine Variation des Rucksackproblems. Wie Danny Pflughoeft erwähnt, ist es NP-Complete. Das heißt, es kann nicht in linearer Zeit gelöst werden, wenn ich mich richtig erinnere.

Sie können jedoch versuchen, dies in mehreren Schritten zu lösen. Es ist im Grunde ein Sortierproblem.

Ich würde damit beginnen, die "Sperrigkeit" jedes Artikels zu berechnen: Dies kann auf verschiedene Arten berechnet werden:

  • Sperrigkeit = max (Länge, Breite);

  • Sperrigkeit = Länge * Breite

  • Sperrigkeit = sqrt (Länge * Breite)

Beginnen Sie dann damit, Gegenstände mit der höchsten Punktzahl zuerst in das Inventar aufzunehmen. Da sie höchstwahrscheinlich später nicht in den verbleibenden Raum passen. Kleine Gegenstände passen immer.

Sie benötigen eine Heuristik (ein ausgefallener Name für fundiertes Raten ;-)) für Ihre Platzierungsstrategie. So etwas wie der Versuch, Gegenstände in den ersten freien Steckplatz von oben links einzupassen oder so.

Die Inventarsortierungsstrategie von Diablo II funktionierte meiner Meinung nach ähnlich. Sachen wie Schwerter und Speere landeten oben links, dann Kleidung und Rüstungen, dann Buckler und so weiter.

Ich denke, Sie müssen dies wirklich ausprobieren und den Algorithmus optimieren (unterschiedliche Bulkiness-Berechnung, unterschiedliche Heuristik), bis er vernünftig genug funktioniert.

Stephen
quelle
1
NP-vollständig ist eine Reihe von Problemen mit einer höheren Komplexität als das Polynom. Für ein relativ kleines Inventar (weniger als tausend Artikel würde ich sagen :)) würde sogar ein exponentieller Algorithmus ziemlich schnell funktionieren, da ein Schritt eines solchen Algorithmus sehr wenig Zeit in Anspruch nimmt. Trotzdem sollte die Verwendung Ihrer Idee gut genug und einfacher sein als die Implementierung eines dynamischen Programmieralgorithmus -> +1
MartinTeeVarga
Danke für die positive Abstimmung. Ja, das Inventar sollte nicht potenziell unendlich sein, also sollten exponentielle Algorithmen gut funktionieren ^^
Stephen
@ sm4: Tausend ist normalerweise eine enorme Zahl für NP-Complete-Probleme. Denken Sie daran, diese Probleme sind O (2 ^ n) - sogar nur 2 ^ 64 sind rechnerisch nicht realisierbar!
BlueRaja - Danny Pflughoeft
3

Haha, @Jeder, der geholfen hat, danke. Ich habe es endlich geschafft, es zu lösen. Folgendes habe ich im Grunde getan:

IEnumerator AddItem_Sorted (Item item)
  1. Trivialer Zustand: Überprüfen Sie, ob wir die minimalen nRequiredSlots für den Artikel erhalten haben. Wenn wir ihn haben, fahren Sie fort ...
  2. Wir werden die ganze Tasche leeren - die Gegenstände in einen Platzhalter legen (Liste oder so)
  3. Fügen Sie das gewünschte Objekt zu dem SEHR letzten Steckplatz / Platz hinzu, in den es passen könnte, und stellen Sie sicher, dass es in seiner horizontalen Form sicher ist
  4. Mit dem abnehmenden First-Fit-Algo fügen wir den Rest unserer Artikel hinzu
  5. Während des Hinzufügens verwenden wir die dynamische Programmierung (Memoisierung), um uns an den Index zu erinnern, an dem wir hinzufügen (Index des nächsten verfügbaren Slots).
  6. Wenn alles Hinzufügen erfolgreich ist, haben wir es geschafft, unseren gewünschten Artikel zu montieren und die Tasche irgendwie zu sortieren - von großen bis zu kleinen Artikeln
  7. Wenn wir nicht alle Elemente hinzufügen konnten, bedeutet dies, dass dies keine lösbare Situation war. Daher müssen wir die Tasche in den vorherigen Zustand versetzen
  8. Eine Möglichkeit, dies zu tun (kam aus der Oberfläche meines Geistes heraus), besteht darin, den Zustand der Tasche vor dieser ganzen Operation zu kopieren. Wenn dies fehlschlägt, werden wir während des '. Wenn wir den Beutel leeren, merken wir uns, wo sich die einzelnen Elemente befanden. Wenn die Operation fehlschlägt, erhalten wir sie mithilfe von AddItem (Element, Index) an den vorherigen Indizes zurück :)
  9. Dieser ganze Prozess könnte einige Zeit dauern, also könnten wir die Last auf separate Frames verteilen, wobei ich meine schöne Ausbeute verwende :)
  10. FERTIG ! \ m / (@ ~ 9: 00)

AKTUALISIEREN:

  1. Ich habe ein Array erstellt, in dem die Indizes aller hinzugefügten Elemente gespeichert sind. Auf diese Weise muss ich nicht nach den belegten Slots suchen, um sie freizugeben - ein großer Schub.

  2. Keine Notwendigkeit, am letzten Steckplatz hinzuzufügen, in der Tat funktioniert es manchmal nicht so. Ich habe das gewünschte Element zu den anderen Elementen hinzugefügt und es mit ihnen sortiert.

Wie Sie dem Video entnehmen können, muss es ein wenig optimiert werden. Die Sortierung ist nicht perfekt. Ich würde gerne eine vollständige Behälterverpackung verwenden, aber sie ist bereits leistungsgierig. Ich bin offen für Optimierungsvorschläge, nochmals vielen Dank :)

ärgerlich
quelle
Bitte! :) Ich möchte BlueRaja - Danny Pflughoeft für die Erwähnung von Bin Packing, @Stephen für die sperrige Idee und Richard Buckland für seine dynamische Programmiervorlesung und alle Vorlesungen danken.
Vexe