Einfache Pathfinding in PHP

Weiß jemand, ob es eine einfache Möglichkeit gibt, Pathfinding in PHP zu tun?Einfache Pathfinding in PHP

Ich habe im Grunde eine Liste von Zahlen, z.

{origin:11485,outboundDirections:"11486,11487,11488"}
{origin:11487,outboundDirections:"11485,11676,94185"}

und 11.485-94.185 immer in 11485>11487>94185 Wege mit zu „exit“ führen würde, und ich versuche, herauszufinden, wie dies zu tun (es doesn‘ t haben wirklich kürzesten Weg oder etwas AI artig sein, nur einen Weg von A nach B zu gelangen)

ich habe keine Ahnung, wo überhaupt zu starten, leider

Quelle

2011-01-05 pdx

Sie können für dieses Problem auf oder Dijkstra's algorithm lesen. Diese sind beide gut etablierte (und ziemlich unkomplizierte) Algorithmen zum Auffinden von kürzesten Wegen (Breite-zuerst-Suche, um die Anzahl von Hops zu minimieren, Dijkstra-Algorithmus, um die Gesamtdistanz zu minimieren).

Quelle

2011-01-05 20:51:40 templatetypedef

Ich bin bei bfs suchen, aber ich kann keine Basisklasse zu finden scheinen, oder was auch immer es in PHP (ich ziemlich viel habe nur Hallo Welt darin geschrieben), und ich habe ein paar tausend Knoten nur. Was wäre die beste Vorgehensweise dafür? Speichern Sie jeden einzelnen in einer SQL-Tabelle mit den Spalten Origin und ExitRoute oder geben Sie jeder Exit-Route eine Spalte (sie sind nicht konsistent und einige haben eine, einige können fünf oder sechs haben) – pdx

Wie vertraut sind Sie mit der Warteschlangendatenstruktur? Wenn Sie das vorher nicht gesehen haben, würde ich empfehlen, es nachzuschlagen: http://en.wikipedia.org/wiki/Queue_(data_structure). Sobald Sie mit dieser Struktur vertraut sind, ist es vielleicht einfacher zu verstehen, wie BFS funktioniert. Wahrscheinlich wirst du es selbst schreiben müssen; Ich kenne keine PHP-Bibliotheken, die das für Sie tun. – templatetypedef

Ich bin ein Designer von Beruf, ich habe keine Ahnung, was Schlange ist. Python anstelle von PHP könnte auch akzeptabel sein, aber ich habe gleiche Mengen an Wissen in beiden (keine). Der Server, mit dem ich arbeiten muss, hat nur Python 2.5, 2.6 und PHP5/6. – pdx

Wenn diese einer Grafik ähnlich sind, kann die A* algorithm funktionieren. Es ist ein sehr grundlegender AI-Algorithmus für Spiele, aber auch Labyrinthe, Navigation, optimale Pfade.

Quelle

2011-01-05 20:55:26

Er will nur einen Weg, kümmert sich nicht um die Länge, also ist das Overkill. – marcog

Wahr, aber es ist schneller als Dijkstra Algo und ist einer der grundlegendsten Wegfindung Algorithmen um. –

Ich habe vor kurzem begonnen und opensourced ein flexibles Pathfinding-Skript in PHP, hauptsächlich mit dem A * -Algorithmus. Die Idee besteht darin, ein Knotengraphobjekt mit den grundlegendsten Methoden zu versehen, die der Algorithmus benötigt, um das Knotendiagramm zu untersuchen und H- und G-Kosten zu erhalten.

Es würde sehr einfach mit Ihrer Liste von Zahlen arbeiten, da es auch Ganzzahlen verwendet, um auf Knoten verweisen.

See: https://github.com/Nexii-Malthus/phpPathfinding

Quelle

2011-09-10 15:50:40

Einfache Pathfinding in PHP

Antwort

Verwandte Themen