Die Suche nach der perfekten Quest

Jetzt ist es Zeit, sich einer schwierigen Herausforderung zu stellen, und hier beginnt es, ein wenig knifflig zu werden.

Ich habe lange nach der richtigen Herausforderung gesucht, da die meisten Probleme, auf die ich gestoßen bin, nur Aufbereitungen der früheren arraybasierten Probleme waren, wenn auch mit leichten Variationen, um mehr Effizienz in weniger Codezeilen herauszuholen. Ich denke, man kann mit Sicherheit sagen, dass wir das nicht wirklich tun können mit Mendix und das ist sicherlich nicht der Punkt dieser Artikel.

Die nächste Reihe von Problemen, auf die ich stieß, betraf mehrdimensionale Arrays. Ein relativ einfaches Konzept in grundlegenden Programmiersprachen und eine schnelle Möglichkeit, Datenraster zu speichern. In einem tabellenbasierten System wie Mendix, es ist nicht so elegant. Allerdings ist mir ein Problem aufgefallen, das praktisch gelöst werden konnte und zudem ein interessantes Konzept darstellte. Herausforderung einhundertvierundsiebzig: „Dungeon-Spiel“.

Betrete den Kerker

Die Hauptelemente unserer Suche:

• Der tapfere, unerschrockene Ritter. 🛡
• Der Gefangene wartet auf seine Rettung. ⛓
• Der Kerker 🚨

In dieser Herausforderung werden wir einen Kerker erschaffen, durch den sich unser tapferer Ritter wagen muss, um den Gefangenen im letzten Raum zu retten. Der Kerker besteht praktischerweise aus einem quadratischen Raster von Räumen und in jedem Raum befindet sich eines der folgenden Dinge:

1. Gar nichts – eine Null und tut nichts.
2. Ein Dämon 👿 – eine negative Zahl und reduziert den Gesundheitswert unseres Ritters.
3. Eine magische Kugel 🔮 – eine positive Zahl und erhöht den Gesundheitswert unseres Ritters.

Unser tapferer Ritter muss sich von oben links nach unten rechts durch den Kerker bewegen und darf dabei nur nach rechts oder unten gehen, da er eine krankhafte Angst davor hat, nach links und oben zu gehen. Den letzten Teil habe ich mir vielleicht ausgedacht, es ist nur eine willkürliche Regel, damit wir nicht in einer Schleife stecken bleiben.

Unsere Aufgabe als Dungeon Master besteht darin, herauszufinden, mit wie viel Gesundheit unser Ritter zu Beginn mindestens auskommen muss, um den letzten Raum zu erreichen und zu überleben, und am Ende mit einem Gesundheitspunkt abzuschließen.

In dem wir einen Dungeon erstellen

Als Erstes brauchen wir eine Möglichkeit, die Daten zu speichern, die den Dungeon darstellen. Es bieten sich einige Optionen an:

Erstens gibt es den einfachen Ausweg, bei dem wir einfach eine Liste von Räumen haben können. Um zu navigieren, würden wir uns einfach von einem Raum zum nächsten bewegen, indem wir eine Reihe nach rechts und n Räume nach unten bewegen, wobei n die Anzahl der Zellen in unserem Quadrat ist. Das fühlt sich allerdings ein bisschen wie Schummeln an, da die Herausforderung darin besteht, ein mehrdimensionales Array aufzunehmen.

Als nächstes gibt es mehr Mendix Möglichkeit, dies zu tun, bei der wir weiterhin jeden Raum in einer Liste mit den Zeilen- und Spaltenindizes als Referenz speichern und einen Link von jedem Raum zum Raum rechts davon und zum Raum darunter speichern können. Dies erleichtert das Wechseln von einem Raum zum nächsten über Assoziationen. Es ist jedoch immer noch keine wirklich faire Darstellung eines mehrdimensionalen Arrays.

Schließlich beginnen wir diese Übung, indem wir zunächst eine Entität „Zeile“ erstellen, die eine Reihe von Zellen mit einem Indexattribut darstellt, um sie in der richtigen Reihenfolge zu halten. Als Nächstes erstellen wir eine untergeordnete Entität namens „Zelle“, die jeden Raum in dieser Reihe darstellt, wieder mit einem Index, um sie in der richtigen Reihenfolge zu halten. Dies wird in der Praxis viel mehr wie ein mehrdimensionales Array wirken. Die Navigation wird nicht so effizient sein wie die echte Mendix Ansatz, aber wir versuchen, so nah wie möglich an der Vorgabe zu bleiben.

Wir haben unseren Datenspeicher, also füllen wir ihn mit Zahlen. Bei diesem Teil machen wir uns keine Gedanken über die Effizienz, also werden ein paar verschachtelte Schleifen den Job erledigen. Ich habe der Dungeon-Entität auch Attribute für die Rastergröße und den maximalen Zellenwert hinzugefügt, damit sie für verschiedene Bereiche konfiguriert werden kann. Im Moment sind beide standardmäßig auf 10 eingestellt. Der Hauptteil der Datenladung sieht so aus, ganz einfach.

Wenn wir das auf dem Bildschirm ausgeben und den Galerie-Widgets ein wenig SASS-Styling hinzufügen, erhalten wir etwas, das dem Kerker aus dem Beispiel sehr ähnlich sieht:

In dem wir unsere Route planen

Jetzt müssen wir den Kerker durchqueren und dabei bedenken, dass sich unser Ritter nur nach rechts und unten bewegen kann. Wir beginnen in der oberen linken Ecke, bei der Gitterreferenz Null-Null, und prüfen von dort aus, welcher der nächste optimale Schritt ist. Im obigen Beispiel wäre es ein Schritt nach rechts. Wir möchten den Schritt machen, der uns den jeweils höchsten Wert gibt, der in diesem Fall Null ist. Wir müssen auch daran denken, dass wir die Gesundheit des Ritters und ihren Rückgang im Auge behalten müssen, also lohnt es sich wahrscheinlich, unserem Kerker ein weiteres Attribut für die aktuelle Gesundheit und die niedrigste Gesundheit hinzuzufügen.

Unser mutiger Ritter beginnt seine Reise in der ersten Zelle. Das ist kein guter Start, da er bereits einen Gesundheitspunkt verloren hat. Wir beginnen unseren Ablauf also, indem wir ihn in die erste Zelle setzen und seine Startgesundheit berechnen.

Wenn wir dies ausführen, wird die erste Zelle aktualisiert, um anzuzeigen, wo er sich befindet, und sein Gesundheitswert wird aktualisiert.

Lassen Sie uns nun einen Weg durch den Dungeon finden, der den nächstbesten Schritt beinhaltet. Eine Möglichkeit hierfür ist die Verwendung eines rekursiven Microflow-Aufrufs, der die Optionen rechts und darunter vergleicht und diejenige mit der besten Auswirkung auf die Gesundheit auswählt.

Mit dieser Funktion können wir diesen Weg abbilden. Es ist nicht unbedingt der beste Weg, aber zumindest ein gangbarer. Wir können auch sehen, wo der Gesundheitsabfall am geringsten ist. Wenn wir also mit einem Punkt mehr beginnen, haben wir einen geeigneten Gesundheitswert, mit dem wir beginnen können. Für das folgende Beispiel müssten wir unseren Ritter mit 10 Gesundheitspunkten beginnen lassen.

Wir haben jetzt einen Weg durch das Verlies und einen Gesundheitswert, der unseren Ritter zum Gefangenen bringt. Woher wissen wir, dass dies der beste Weg ist – der, der die wenigsten Gesundheitspunkte erfordert? Die Antwort ist: Nein. Um das zu verstehen, müssten wir einen Bottom-up-Ansatz ausprobieren, der den optimalen Schritt an jedem Punkt ermittelt und das Ausmaß des Gesundheitsdefizits verfolgt, das der Ritter auf seiner Reise erleiden wird.

In dem wir einen besseren Weg finden

Dazu beginnen wir am Ende mit dem Gefangenen und arbeiten uns das Raster nach außen und wieder nach oben. Bei jedem Schritt müssen wir die relativen Kosten berechnen, die es kostet, von dem Feld, in dem wir uns befinden, zum nächsten zu gelangen. Nehmen wir ein Beispiel aus dem Raster:

1. Wir berechnen die relativen Kosten für die Änderung von 0 unten rechts auf 5 oder -4.
2. Der Wechsel auf -4 kostet uns 4 Gesundheit.
3. Der Wechsel auf 5 kostet uns keine Gesundheit, wir gewinnen sogar Gesundheit, also betragen die relativen Kosten 0.
4. Schließlich berechnen wir die Kosten des besten Schritts aus dem Quadrat -2, also von -2 bis 0, sodass die endgültigen Kosten dieses Quadrats -2 betragen.

Von einem Mendix Aus unserer Sicht bedeutet dies, dass wir einen Microflow benötigen, um das Raster rückwärts, Zeile für Zeile und Zelle für Zelle zu durchlaufen. In Schritt eins fügen wir jeder Zelle ein Attribut hinzu, in dem wir die relativen Kosten der Zelle speichern und auf dem Bildschirm anzeigen können.

Als Nächstes holen wir uns die Zeilenliste, die wir brauchen, und richten eine Schleife ein, um jede Zeile in umgekehrter Reihenfolge zu durchlaufen. Das bedeutet, wir brauchen einen Index zum Verfolgen der Zeile und eine While-Schleife, damit sie weiterläuft, bis wir bei der ersten Zeile (oder der letzten Zeile, je nachdem, wie man es sieht!) ankommen.

Wie Sie sehen, können wir auch ein paar leere Listen erstellen. Eine zum Aufzeichnen aller Änderungen an Zellen, wenn wir die relativen Kosten aktualisieren, damit wir am Ende eine Massenaktualisierung durchführen können, und eine zum Speichern der Zellen aus der vorherigen Iteration, damit wir nicht zwei Abrufe durchführen müssen.

In dieser neuen Schleife geschieht die wahre Magie. Wir holen uns die Zellenliste für die aktuelle Zeileniteration und durchlaufen alle Zellen darin. Für jede dieser Zellen prüfen wir, wo sie im Raster positioniert ist, denn wenn sie sich unten oder rechts befindet, müssen wir sie anders behandeln als Zellen mit zwei möglichen Ausstiegspunkten.

Für jede Zelle müssen wir die relativen Kosten basierend auf dem besten Ausstiegspunkt aktualisieren. Im Fall der untersten Zeile und der letzten Spalte wird einfach die Zelle rechts oder darunter zum Wert der aktuellen Zelle addiert. In allen anderen Zellen ist es der Wert der aktuellen Zelle plus der Wert des größten Ausstiegspunkts. Denken Sie daran, dass wir den Wert einfach auf Null zurücksetzen, wenn der Endwert größer als Null ist, da seine relativen Kosten nichts sind. Im kompliziertesten Fall erhalten wir eine Berechnung wie diese:

Diese Schleifen führen uns durch das gesamte Raster und verschieben unsere relativen Kosten nach oben und nach links, bis wir die erste Zelle erreichen und beide Schleifen verlassen. An diesem Punkt berechnen wir die minimale Startgesundheit, die den relativen Kosten der ersten Zelle plus eins entspricht, und speichern sie im Dungeon.

An diesem Punkt habe ich auch die Möglichkeit hinzugefügt, die Größe des Dungeons zu konfigurieren und ihn neu zu generieren, damit ich ihn an einem kleineren Dungeon testen konnte. Er sieht jetzt so aus und Sie können sehen, dass es anscheinend die richtige Antwort gibt!

In dem wir unsere Erfolge feiern

Das war's also! Technisch gesehen haben wir diese schwierige Aufgabe abgeschlossen – jetzt kann es losgehen! Ich habe die Leistung nicht verfolgt und bezweifle, dass sie so leistungsfähig ist wie einige der Standardcodelösungen, aber soweit ich das beurteilen kann, reagiert sie ziemlich schnell und sieht nach einer eleganten Lösung aus. Wenn wir weitermachen würden, würde ich wahrscheinlich wieder den optimalen Weg verfolgen und den Weg markieren wollen, den unser edler Ritter durch dieses heimtückische Verlies nehmen sollte, um unseren Gefangenen in Gefahr zu retten! Wenn das jemand sehen möchte, lasst es mich wissen.

Vielen Dank, dass Sie mitgelesen haben, während wir verschiedene Herausforderungen in Low-Code testen. Haben Sie ein Problem, das Sie als nächstes in Angriff nehmen möchten? Melden Sie sich gerne und machen Sie einen Vorschlag!