Javascript kombiniert mit Vue zur automatischen Pfadfindung für jedes Labyrinthbild

Vorwort

Den Endeffekt könnt ihr direkt erleben: https://maze-vite.vercel.app/

Vor der Pfadfindung:

Nach der Pfadfindung wird automatisch ein roter Pfad auf dem Bild generiert und der blaue Bereich ist der erkundete Bereich:

Hier habe ich das Telefon absichtlich aus einem Winkel zum Fotografieren verwendet, um zu zeigen, dass das Programm die mit dem Telefon aufgenommenen Labyrinthbilder in der Realität vollständig verarbeiten kann.

Ich habe vor, das gesamte Programm mit Vue 3 + Vite zu schreiben, aber eigentlich ist es egal, ob Vue verwendet wird oder nicht. Es werden keine komplexen Schnittstellen benötigt und es ist durchaus möglich, andere Frameworks oder sogar gar kein Framework zu verwenden.

Zweidimensionales Array, Einweg

Ich sagte, wir sollten bei Null anfangen, also beginnen wir mit einem sehr einfachen Labyrinth.

Für uns Menschen ist dieses Labyrinth sehr einfach und es gibt nur einen offensichtlichen Weg. Dennoch erfordert es für einen Computer einige Anstrengungen, ein solches Labyrinth zu lösen.

Ein zweidimensionales Array ist eine gute Möglichkeit, dieses Labyrinth darzustellen:

Konstante m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

1 steht für ein begehbares Gitter, 0 für ein unbegehbares Gitter. Jedes Raster kann durch [x, y] dargestellt werden. Der Startpunkt ist beispielsweise [0, 0] und der Endpunkt ist [3, 4].

Dann sollte es eine Funktion wie diese geben: function function solveMaze (matrix, begin, end) {//...} , Matrix ist ein zweidimensionales Array, das das Labyrinth beschreibt, begin ist der Startpunkt, end ist der Endpunkt und der endgültige Rückgabewert ist eine geordnete Menge, wobei jedes Element ein Raster ist, das die richtige Routenbahn darstellt.

Die Strategie, die wir hier verwenden werden, ist sehr einfach. Beginnen Sie am Startpunkt, schauen Sie sich um, welche Gitter passierbar sind (Sie können nicht diagonal gehen), gehen Sie dann zu diesem Gitter und wiederholen Sie die obigen Schritte, bis Sie das Endgitter erreichen. Beachten Sie, dass Sie auch das Gitter aus dem vorherigen Schritt aufzeichnen und ausschließen müssen, um ein Zurückgehen zu vermeiden. Weitere Einzelheiten finden Sie im folgenden Code:

// labyrinth.js

Funktion getPoint(m, x, y) {
  wenn (x >= 0 && y >= 0 && x < m.Länge && y < m[x].Länge) {
    Rückgabewert m[x][y]
  } anders {
    Rückgabe 0
  }
}

Funktion getNextPoint(m, aktueller, letzterPunkt) {
  sei [x, y] = aktuell
  lass nächstenPunkt = [
    [x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]
  ].find(p => {
    sei r1 = getPoint(m, p[0], p[1]) > 0
    lass r2 = !isSamePoint(p, letzterPunkt)
    Rückgabewert r1 und r2
  })
  nächsten Punkt zurückgeben
}

Funktion istGleicherPunkt(p1, p2) {
  return p1[0] === p2[0] und p1[1] === p2[1]
}

Funktion solveMaze (Matrix, Anfang, Ende) {
  let Pfad = []

  // Aktueller Punkt let current = begin
  Pfad.push(aktuell)

  // Der Weg, den wir letztes Mal gegangen sind, let lastPoint = begin

  // Wähle einen zufälligen Zielpunkt, während (1) {
    wenn (istGleicherPunkt(aktuell, Ende)) {
      brechen
    }

    let validPoint = getNextPoint(Matrix, aktuell, letzterPunkt)

    Pfad.push(gültiger Punkt)
    letzterPunkt = aktuell
    aktuell = gültiger Punkt
  }
  Rückweg
}

Konstante m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

konsole.log(
  löseMaze(m, [0, 0], [3, 4])
)

getNextPoint ruft das nächste befahrbare Gitter ab, solveMaze ruft den endgültigen befahrbaren Pfad ab und die Konsolenausgabe lautet:

Diese Koordinaten stellen die endgültige Gehstrecke dar und scheinen korrekt zu sein.

Mapping der Basisschnittstelle

Um Tests und Beobachtungen zu erleichtern, müssen wir unsere Datenstruktur auf die Webseite abbilden.

// labyrinth.js
// ...

// Exportiere die Funktion „solveMaze“ und lasse die Vue-Komponente „export {“ aufrufen.
  Labyrinth lösen
}

<Vorlage>
  <div>
    <div Klasse="div-Matrix">
      <div v-for="(Zeile, x) in Matrix" :key="x">
        <div Klasse="Zelle" 
          :Klasse="{ schwarz: p <= 0, Pfad: istPfad(x, y) }"
          v-for="(p, y) in Zeile" :key="y" :style="{ links: `${y * 2.5}em`, oben: `${x * 2.5}em` }">
          {{ begin[0] === x && begin[1] === y ? 'B' : '' }}
          {{ end[0] === x && end[1] === y ? 'E' : '' }}
        </div>
      </div>
    </div>
  </div>
</Vorlage>

<Skript>
importiere {solveMaze} aus './maze'

Standard exportieren {
  Daten () {
    zurückkehren {
      Beginn: [0, 0],
      Ende: [3, 4],
      Matrix: [],
      Pfade: []
    }
  },
  Methoden: {
    istPfad(x, y) {
      const p = this.paths.find(Pfad => Pfad[0] === x && Pfad[1] === y)
      Rückkehr p
    }
  },
  erstellt () {
    const m = diese.matrix = [
      [1, 1, 0, 0, 0],
      [0, 1, 1, 1, 0],
      [0, 0, 0, 1, 0],
      [0, 0, 0, 1, 1]
    ]
    diese.Pfade = löseMaze(m, dies.beginnen, dies.ende)
  }
}
</Skript>

<Stil>
.Spitze {
  Rand unten: 1em;
}
.div-Matrix {
  Position: relativ;
}
.Zelle {
  Rand: 1px schwarz durchgezogen;
  Breite: 2em;
  Höhe: 2em;
  Position: absolut;
  Textausrichtung: zentriert;
}
.Zelle.Pfad {
  Rand: 1px rot durchgezogen;
}
.Schwarz {
  Hintergrund: schwarz;
}
</Stil>

Endergebnis:

Tatsächlich wird das entsprechende Div durch die zweidimensionale Array-Matrix generiert, und der Elementwert im Array bestimmt Schwarz und Weiß. Das Pfad-Array speichert die resultierenden Pfade und die Pfade sind mit einem roten Rand markiert. Dadurch können die Testergebnisse später leichter eingesehen werden.

Breitensuche, flächendeckende Suche

Schauen Sie sich das folgende Labyrinth an:

const m = diese.matrix = [
  [1, 1, 0, 0, 0],
  [1, 1, 1, 1, 1],
  [0, 1, 0, 1, 0],
  [0, 1, 0, 1, 1]
]

Wenn Sie es auf den obigen Code anwenden, werden Sie feststellen, dass die Seite hängen bleibt. Dies liegt daran, dass das Labyrinth Gabeln enthält, wodurch der Algorithmus im Kreis läuft. Wir brauchen eine Methode, die uns den Weg merkt, den wir genommen haben, damit wir ihn nicht noch einmal gehen müssen. Die Methode ist nicht schwierig. Wir müssen nur die Gitter, die im Moment gegangen werden können, in eine Warteschlange stellen. Dann müssen wir mit den Gittern in der Warteschlange dasselbe tun, bis wir das Endgitter erreichen.

Um die Verarbeitung unseres Algorithmus zu erleichtern, müssen wir zum Ausdruck eine neue Datenstruktur verwenden, nämlich die Graphstruktur.

Die Graphstruktur ist einer verknüpften Liste sehr ähnlich. Der größte Unterschied besteht darin, dass jeder Knoten mehrere Zeiger haben kann, die auf verschiedene Knoten zeigen.

Reduzieren Sie gleichzeitig die Dimensionalität des zweidimensionalen Arrays auf eine Dimension:

Konstante m = [
  1, 1, 0, 0, 0,
  1, 1, 1, 1, 1,
  0, 1, 0, 1, 0,
  0, 1, 0, 1, 1
]

Obwohl dieser Zugriff nicht ganz so direkt ist, erfordert er nur eine Adressierung und das Kopieren und Übertragen ist viel bequemer als bei einem zweidimensionalen Array.

Erstellen Sie dann eine Node-Klasse zur Darstellung des Knotens und eine NodeGraph-Klasse zur Darstellung der gesamten Graphstruktur.

Klasse Knoten {
  Konstruktor (x, y, Wert) {
    dies.x = x
    dies.y = y
    dieser.Wert = Wert
    dies.geprüft = falsch
    dies.nearNodes = []
  }
}

Klasse NodeGraph {
  Konstruktor (Matrix, Breite, Höhe) {
    diese.knoten = []
    diese.matrix = matrix
    this.width = Breite
    this.height = Höhe
  }

  buildNodeGraph () {
    let { Breite, Höhe } = dies
    
    für (lass y = 0; y < Höhe; y++) {
      für (lass x = 0; x < Breite; x++) {
        lass Knoten = this.getNode(x, y)
  
        nachlassen = this.getNode(x, y - 1)
        im Stich lassen = this.getNode(x, y + 1)
        lass links = this.getNode(x - 1, y)
        rechts lassen = this.getNode(x + 1, y)
        node.nearNodes = [oben, unten, links, rechts].filter(node ​​=> node && node.value === 1)
      }
    }
  }

  getNode (x, y) {
    let { Knoten, Breite, Matrix } = dies
    wenn (x >= 0 und y >= 0) {
      let node = Knoten[y * Breite + x]
      wenn (!Knoten) {
        let Wert = Matrix [y * Breite + x]
        if (Wert !== undefiniert) {
          Knoten = neuer Knoten(x, y, Wert)
          Knoten[y * Breite + x] = Knoten
        }
      }
      Rückgabeknoten
    } anders {
      return null
    }
  }
}

buildNodeGraph konvertiert das Matrix-Array in eine Graphstruktur. Die NearNodes jedes Knotens entsprechen dem Rastersatz, der als nächstes untersucht werden kann. „Checked“ gibt an, ob der Knoten untersucht wurde.

Um die Statusänderungen jedes Schritts bequem anzeigen zu können, müssen Sie das aktuelle Raster und das Raster in der Warteschlange auf dem Bildschirm markieren. Ich werde den vollständigen Code nicht veröffentlichen, Sie können ihn nach Belieben in Codesandbox lesen:

Der blaue Rand ist das Gitter in der Warteschlange und der kleine Mann ist das aktuelle Gitter. Es stoppt, wenn es die untere rechte Ecke erreicht.

Was wir jetzt getan haben, ist, den kleinen Mann reibungslos zum Endpunkt zu bewegen, aber wie erhalten wir den gewünschten Pfad? Die Methode besteht darin, dem Knoten ein zusätzliches übergeordnetes Attribut hinzuzufügen, um den vorherigen Knoten aufzuzeichnen. Weisen Sie beim Abrufen von NearNodes den aktuellen Knoten dem übergeordneten Knoten jedes NearNodes zu:

// ...
für (let node von current.nearNodes) {
  wenn (node.checked === false) {
	Knoten.übergeordnet = aktuell
	Warteschlange.Push(Knoten)
  }
}
// ...

Lesen Sie dann einfach die übergeordneten Knoten vom aktuellen Knoten und verfolgen Sie sie einzeln zurück:

Funktion BuildPath (Endknoten) {
  let Pfad = []
  let node = endNode

  während (Knoten) {
    Pfad.push(Knoten)
    Knoten = Knoten.übergeordnet
  }

  Rückweg
}

Wirkung:

Wenn der kleine Mann das Ende erreicht, ist das rote Quadrat der kürzeste Weg.

KarteBearbeiten

Durch eine geringfügige Änderung des Codes können wir das Labyrinth in Echtzeit bearbeiten, was das Testen komfortabler macht.

Bedienung: Klicken Sie auf das Quadrat, um den Schwarz-Weiß-Zustand zu ändern, halten Sie die Alt-Taste gedrückt und klicken Sie, um einen neuen Zielpunkt festzulegen.

Verschieben Sie lokale Variablen in SolveMaze schrittweise in die NodeGraph-Klasse, um den externen Zugriff bequemer zu gestalten. Beachten Sie, dass Sie die Funktion nicht beenden dürfen, wenn die Pfadfindung abgeschlossen ist. Verwenden Sie stattdessen eine While-Schleife, um auf die Festlegung des neuen Zielpunkts zu warten:

// ...

    wenn (gleich Knoten (aktuell, Knotengraph.Endknoten)) {
      während (equalsNode(current, nodeGraph.endNode)) {
        warte auf Schlaf (1000)
      }
      weitermachen
    }
// ...

Optimierung von Pfadfindungsalgorithmen

Stellen Sie sich dieses Szenario vor:

Der Start- und der Endpunkt liegen auf einer geraden Linie ohne Hindernisse dazwischen, aber dieser kleine Mann rennt überall hin und es dauert eine Weile, bis er den Endpunkt erreicht. Das funktioniert nicht und muss optimiert werden.

Fügen Sie der Node-Klasse ein Attribut endDistance hinzu, um die Distanz von jedem Knoten zum Endpunkt aufzuzeichnen. Die Funktion getDistance kann die Distanz direkt anhand der Koordinaten berechnen. Diese Distanz berücksichtigt zwar keine möglichen Hindernisse in der Mitte, ist aber auch für die Routenbewertung sehr nützlich:

Klasse Knoten {
  Konstruktor (x, y, Wert) {
    dies.x = x
    dies.y = y
    dieser.Wert = Wert
    this.endDistance = 0 // Distanz zum Endpunkt, Hindernisse in der Mitte werden ignoriert this.checked = false
    this.parent = null
    dies.nearNodes = []
  }
}

Funktion getDistance(KnotenA, KnotenB) {
  const x = Math.abs(KnotenB.x - KnotenA.x)
  const y = Math.abs(nodeB.y - nodeA.y)
  Rückgabewert (x + y)
}

Jedes Mal wird der Knoten mit der kleinsten Enddistanz durch die Methode popBestNextNode aus der Warteschlange genommen:

Klasse NodeGraph {
// ...

  popBestNextNode () {
    let { queue } = dies
    let bestNode = Warteschlange[0]
    let bestNodeIndex = 0
    let { Länge } = Warteschlange

    für (sei i = 0; i < Länge; i++) {
      lass Knoten = Warteschlange[i]
      wenn (node.endDistance < bestNode.endDistance) {
        bestNode = Knoten
        besterNodeIndex = i
      }
    }

    Warteschlange.splice(besterNodeIndex, 1)
    bestNode zurückgeben
  }
// ...
}

Da es eine „endDistance“ gibt, muss es auch eine „beginDistance“ geben, um die Anzahl der vom Startpunkt aus zurückgelegten Schritte aufzuzeichnen. Dieser Wert wird nicht direkt aus den Koordinaten berechnet, sondern beim Voranschreiten akkumuliert, so dass beginDistance keine Schätzung, sondern ein tatsächlicher Wert ist:

// ...
für (let node von current.nearNodes) {
  wenn (node.checked === false && node.value) {
	Knoten.übergeordnet = aktuell
	node.checked = wahr
	node.endDistance = getDistance(Knoten, nodeGraph.endNode)
	node.beginDistance = aktuelle.beginDistance + 1
	Knoten.Kosten = Knoten.Enddistanz + Knoten.Beginndistanz
	nodeGraph.queue.push(Knoten)
  }
}
// ...

Da in Zukunft möglicherweise neue Faktoren hinzugefügt werden, wird direkt ein Kostenattribut hinzugefügt, um die Kosten auszudrücken. Derzeit betragen die Kosten EndDistance + BeginnDistance. Je geringer die Kosten, desto höher die Priorität.

In einer solchen Situation versuchte das Männchen zunächst, sich von oben zu nähern, doch je weiter es vorwärtskam, desto mehr Schritte musste es machen und so kam es zu dem Schluss, dass es besser wäre, nach unten zu gehen und gab den Weg nach oben auf.

Nun werden die Handlungen des Bösewichts glaubwürdiger:

Pfadfindung für ein Bild

Nehmen Sie dieses zufällige Bild, das ich gezeichnet habe, als Parameter:

Das Ziel besteht darin, von Punkt B zu Punkt E zu gelangen. Wir müssen nur die Pixel dieses Bildes lesen, sie in ein Array basierend auf den Farben Schwarz und Weiß umwandeln und sie in die Funktion „solveMaze“ einfügen.

Dazu benötigen Sie ein Eingabetag mit Typ „file“, um das Bild auszuwählen, eine URL über URL.createObjectURL(File) zu generieren und dann mit new Image() ein img-Tag zu erstellen, das nicht zum Textkörper hinzugefügt werden muss, und die URL an img.src weiterzugeben. Kopieren Sie es über CanvasRenderingContext2D.drawImage() in Canvas und rufen Sie dann CanvasRenderingContext2D.getImageData() auf, um das Pixel-Array zu erhalten.

Derzeit können wir Div nicht mehr zum Rendern verwenden, da dieses Bild Zehntausende von Pixeln hat. Wenn es für jedes Pixel ein Div gibt, kann der Browser es nicht verarbeiten und die Bilder werden in Zukunft noch größer.

Hier verwenden wir also Canvas zum Rendern und ordnen drei Canvas an, eines zur Anzeige des Originalbilds des Labyrinths, eines zur Anzeige der erkundeten Knoten und eines zur Anzeige des aktuell kürzesten Pfads, d. h. der Knoten im Pfadarray, und stapeln diese drei Canvas dann zusammen. Schließlich müssen wir nur noch die letzten beiden Canvas im Rückruf aktualisieren.

Laden Sie das obige Bild auf Ihren Computer herunter, klicken Sie auf die Schaltfläche „Datei auswählen“, um das Bild auszuwählen. Anschließend können Sie den Effekt sehen. Sie können auch andere Bilder auswählen, aber meine Start- und Endpunktkoordinaten sind fest codiert und der Code wurde nicht optimiert. Daher kann es schwierig sein, mit zu großen Bildern umzugehen.

Hinweis: Wenn bei Ihnen Probleme mit mehreren Domänen auftreten, müssen Sie die Bilder selbst hochladen.

Passen Sie Ihren Startpunkt an und ändern Sie Ihre Route jederzeit

Die Klickkoordinaten können durch Verwendung von offsetX und offsetY im Klickereignis ermittelt werden, und die Koordinaten der Start- und Endpunkte können gespeichert werden. Sobald eine Änderung erfolgt, wird die vorherige Pfadfindungsfunktion gestoppt und die aktuelle Pfadfindungsfunktion erneut ausgeführt. Daher muss in der Schleife eine Entscheidung getroffen werden, ob die Funktion beendet werden soll. Dies kann im Rückruf durchgeführt werden.

Stellen Sie dann ein Eingabefeld bereit, um die Anzahl der Zyklen vor der Aktualisierung des Bildschirms frei anzupassen, sodass die Geschwindigkeit der Pfadfindung angepasst werden kann.

Farbbilder verarbeiten

Vorschau: https://codesandbox.io/s/maze-vite-8-h845p?file=/src/App.vue (Beachten Sie, dass Sie das Bild selbst hochladen müssen, wenn ein domänenübergreifender Fehler auftritt)

Ich werde keine Iframes mehr einfügen. Ich habe das Gefühl, dass es zu viele davon gibt, wodurch die Seite ziemlich blockiert wird.

Bisher wurde angenommen, dass weiße Pixel begehbare Bereiche sind. Versuchen Sie jetzt, nahegelegene Pixel mit ähnlichen Farben als begehbare Bereiche zu verwenden. Das wird einen besseren Effekt haben.

Übergeben Sie die RGBA-Farbdaten direkt an SolveMaze und berechnen Sie dann den Farbunterschied zwischen den benachbarten Knoten und dem aktuellen Knoten in der Schleife. Wenn der Unterschied zu groß ist, wird er nicht in die Warteschlange gestellt.

Um die Kanäle einer RGBA-Ganzzahl zu trennen, können wir schreiben:

/**
 * Holen Sie sich den RGB-Wert des Knotens * @param {Node} Knoten 
 * @returns 
 */
Funktion getNodeRGB (Knoten) {
  let { Wert } = Knoten
  sei r = Wert & 0xFF
  sei g = Wert >> 8 & 0xFF
  sei b = Wert >> 16 & 0xFF
  Rückgabe [ r, g, b ]
}

Der einfachste Weg, die Ähnlichkeit von RGB-Farben zu ermitteln, besteht darin, die beiden Farben als zwei Punkte mit dreidimensionalen Koordinaten zu betrachten und dann ihren euklidischen Abstand zu ermitteln. Dies entspricht jedoch nicht dem Wahrnehmungsmodell des menschlichen Auges. Die detaillierte Methode ist bereits im Wiki verfügbar: https://zh.wikipedia.org/wiki/ColorDifference

Die Berechnungen in diesem Bereich sind etwas kompliziert und ich habe sie in color.js geschrieben.

Ergebnis:

Achten Sie im Code auf den colorDiffThreshold. Ich verwende derzeit 2,25. Wenn er zu hoch ist, führt er dazu, dass die Wand durchgeht. Wenn er zu niedrig ist, findet er leicht den Weg nicht.

Leistungsoptimierung

Nachdem Sie zweimal auf den Bildschirm geklickt haben, müssen Sie eine Weile warten, bevor die Pfadsuche beginnt. Dies sollte viel CPU verbrauchen. Öffnen Sie den Leistungsanalysator in DevTools, um zu analysieren, wo die meiste Leistung verbraucht wird:

Offensichtlich nimmt die Funktion „solveMaze“ die meiste Zeit in Anspruch. Erweitern Sie den Aufrufbaum unten:

buildNodeGraph und getNode sind die Schlüsselpunkte der Optimierung. Öffnen Sie den Code und Sie können direkt die von jedem Satz verbrauchte CPU-Zeit sehen:

if (!node) {...} in Zeile 57 ist eine einfache Entscheidung, die aber viel Zeit in Anspruch nimmt. Versuchen Sie, es in node === undefined zu ändern, und der Wert muss nicht mehr entschieden werden. Auch der Zugriff auf und das Lesen des Nodes-Arrays nimmt viel Zeit in Anspruch. Versuchen Sie, es am Anfang mit new Array(length) zu initialisieren. Das sollte besser sein. Der optimierte Code:

Sieht etwas besser aus.

Leistungsüberwachung während der Pfadfindung:

Ich habe festgestellt, dass buildPath ziemlich zeitaufwändig ist, was vernünftig ist. Schließlich wird es jedes Mal durch die Schleife aufgerufen und durchläuft die gesamte Kette vollständig. Die Lösung ist auch einfach. Rufen Sie es einfach auf, wenn das Endergebnis ausgegeben wird. Basierend auf früheren Erfahrungen wird while (node) in while (node ​​!== null) geändert.

Jetzt ist er überhaupt nicht mehr präsent.

Als nächstes folgt die for...of-Anweisung. Es wird empfohlen, sie in die traditionelle Array-Index-Selbstdekrementierung zu ändern, die am schnellsten ist. Natürlich ist for...of im täglichen Gebrauch besser lesbar.

Dann popBestNextNode:

Hier wird jedes Mal das gesamte Array durchlaufen, um den Knoten mit den geringsten Kosten zu finden. Außerdem erfolgt am Ende eine Operation zum Entfernen von Array-Elementen. Für mich ist es wirklich schwierig zu sagen, ob JavaScript-Arrays im Dauerspeicher oder verstreut gespeichert sind, aber in jedem Fall kann stattdessen ein binärer Heap verwendet werden, um eine bessere Leistung zu erzielen. Ich werde es nicht selbst implementieren, sondern einfach das vorhandene verwenden: https://www.npmjs.com/package/heap-js. Beachten Sie, dass ein benutzerdefinierter Komparator an den neuen Heap() übergeben wird und dann die Implementierung von popBestNextNode geändert wird, um this.queue.pop() zurückzugeben.

Entfernen Sie abschließend die beiden For-Schleifen in buildNodeGraph, initialisieren Sie nicht länger alle Nodes vorab und fügen Sie NodeGraph eine neue Methode hinzu:

  getNearNodes (Knoten) {
    sei { x, y } = Knoten
    nachlassen = this.getNode(x, y - 1)
    im Stich lassen = this.getNode(x, y + 1)
    lass links = this.getNode(x - 1, y)
    rechts lassen = this.getNode(x + 1, y)
    return [hoch, runter, links, rechts].filter(node ​​=> node !== null)
  }

In der nachfolgenden Pfadfindungsschleife wird getNearNodes aufgerufen, um benachbarte Knoten zu erhalten, was die anfängliche Verzögerung erheblich reduziert.

Abschließend werden zwei Strategien vorgeschlagen:

• Streng: Wenn der Farbunterschied zwischen benachbarten Pixeln kleiner als ein bestimmter Wert ist, werden sie der Warteschlange hinzugefügt. Bei Bildern mit geringen Farbänderungen im Gehbereich ergibt sich nahezu der kürzeste Weg.
• Fuzzy: Benachbarte Pixel werden unabhängig vom Farbunterschied zur Warteschlange hinzugefügt und ihr Differenzwert wird mit bestimmten Koeffizienten als Kosten des Knotens multipliziert. Passt in jedes Bild und findet am Ende immer einen Weg. . .

let nearNodes = nodeGraph.getNearNodes(aktuell)
für (let i = nearNodes.length - 1; i >= 0; i--) {
  lass Knoten = nearNodes[i]
  wenn (node.checked === false) {
	node.checked = wahr

	let colordiff = getNodeColorDiff(Knoten, aktuell)
	const colorDiffThreshold = 2 // Zulässiger Farbunterschied, Bereich 0~100

	Knoten.übergeordnet = aktuell
	node.endDistance = getDistance(Knoten, nodeGraph.endNode)
	node.beginDistance = aktuelle.beginDistance + 1

	if (mode === "1") { // Streng node.cost = node.endDistance + node.beginDistance

	  wenn (Farbdifferenz < Farbdifferenzschwelle) {
		nodeGraph.queue.push(Knoten)
	  }
	} sonst wenn (Modus === "2") { // Unschärfe node.cost = node.endDistance + node.beginDistance + (Farbunterschied * Breite * Höhe)
	  nodeGraph.queue.push(Knoten)
	}
  }
}

Quellcode: https://gitee.com/judgeou/maze-vite

Dies ist das Ende dieses Artikels über die Kombination von Javascript mit Vue, um eine automatische Pfadfindung für jedes Labyrinthbild zu erreichen. Weitere relevante Inhalte zur automatischen Pfadfindung von Javascript in Kombination mit Vue-Labyrinthen finden Sie in früheren Artikeln auf 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!