php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Scripts > BRAINSTORMING PHP/SQL/HTML/JS/CSS
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


BRAINSTORMING PHP/SQL/HTML/JS/CSS Ihr habt eine Idee, aber keinen genauen Ansatz? Diskutiert mit anderen Usern des Forums über eure Gedankengänge um evtl. hilfreiche Ideen zu bekommen!
Normale Fragen bitte weiterhin in die entsprechenden Foren!

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 13-06-2009, 19:29
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard automatisches Wegfinde-Script

So hallo.
Ich bins mal wieder.
Und zwar hab ich mal wieder keinen Plan wie man folgende Sache erstellen könnte und hoffe ihr könnt mir helfen einen Ansatz zu finden:

Ich möchte auf meiner Karte (mit Straßen, Häusern, Gras, Wasser usw.) ein Script einbinden in der der User 2 Punkte anklickt und dann automatisch eine Route berechnet wird - nur über die Straßen (die kürzeste möglichst)
Nur hab ich noch keine Ahnung wie ich sowas um setzen könnte.
Hat da jemand ne Ahnung? Bzw habt ihr überhaupt verstanden was ich will?
__________________
Mess with the Besth, die like the rest!
Mit Zitat antworten
  #2 (permalink)  
Alt 13-06-2009, 19:37
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Wegsuche Algorithmus - Google Search
Mit Zitat antworten
  #3 (permalink)  
Alt 13-06-2009, 20:04
Hopka
 PHP Expert
Links : Onlinestatus : Hopka ist offline
Registriert seit: May 2003
Ort: Köln
Beiträge: 2.172
Hopka ist zur Zeit noch ein unbeschriebenes Blatt
Hopka eine Nachricht über ICQ schicken
Standard

Mit der Google Maps API kannst du sowas machen. Vorausgesetzt natürlich es geht um die reale Welt.
__________________
hopka.net!
Mit Zitat antworten
  #4 (permalink)  
Alt 13-06-2009, 23:54
PHP-Desaster
 PHP Expert
Links : Onlinestatus : PHP-Desaster ist offline
Registriert seit: Mar 2006
Beiträge: 3.105
PHP-Desaster befindet sich auf einem aufstrebenden Ast
Standard

Schau dir - falls du die Google Api nicht verwenden kannst/willst - mal den Dijkstra- bzw. den A*-Algorithmus an.
Mit Zitat antworten
  #5 (permalink)  
Alt 14-06-2009, 08:58
Benutzerbild von Berni Berni
  OWNER
Links : Onlinestatus : Berni ist offline
Registriert seit: Jan 2001
Ort: Frankfurt / Egelsbach
Beiträge: 6.306
Blog-Einträge: 6
Berni befindet sich auf einem aufstrebenden Ast
Standard

Graphentheorie! Lang lang her
__________________

php-Entwicklung | ebiz-consult.de
PHP-Webhosting für PHP Entwickler | ebiz-webhosting.de
die PHP Marktplatz-Software | ebiz-trader.de
Mit Zitat antworten
  #6 (permalink)  
Alt 14-06-2009, 09:49
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Er meldet sich gar nicht. Haben wir ihn etwa verschreckt? Nun gut, ich versuche es mal einfacher darzustellen.

2D-Karten wie diese sind meist Felder von Quadranten. Jeder Quadrant hat irgendwelche Eigenschaften, z.B. Typ "Strasse" oder "Baum". Start und Ziel sind Paare (x,y) im Feld. Zur Wegsuche schaut man alle Felder rings um den Startpunkt an. Ist ein Feld begehbar, nimmt man es in den Weg auf und führt die Suche von dort aus fort.
Dieser rekursive Algorithmus kann verschiedene Taktiken verfolgen (Breitensuche, Tiefensuche, ...) und Informationen berücksichtigen (Himmelsrichtung zum Ziel, ...) und bekommt dann einen entsprechenden Namen, damit jeder gleich weiß was gemeint ist. A*, Dijkstra und Greedy sind solche Namen.
Hier kannst du dir anschauen wie diese Algorithmen arbeiten. (Auswahl des Algorithmus durch Klick auf den Button A*)

Wenn man nach Graphentheorie googelt, findet man meist Darstellungen aus Punkten und Verbindungslinien - sog. Graphen. Auf den ersten Blick haben die nichts mit einer 2D-Karte gemeinsam. Doch die Darstellung täuscht. Eine 2D-Karte ist auch nur ein Graph. Das sieht man leicht ein, wenn man die Quadranten durch Punkte austauscht und zwischen benachbarten (begehbaren) Punkten eine Linie zieht.

Geändert von onemorenerd (14-06-2009 um 09:54 Uhr)
Mit Zitat antworten
  #7 (permalink)  
Alt 14-06-2009, 10:39
Benutzerbild von Berni Berni
  OWNER
Links : Onlinestatus : Berni ist offline
Registriert seit: Jan 2001
Ort: Frankfurt / Egelsbach
Beiträge: 6.306
Blog-Einträge: 6
Berni befindet sich auf einem aufstrebenden Ast
Standard

5 Semester Informatik ?
__________________

php-Entwicklung | ebiz-consult.de
PHP-Webhosting für PHP Entwickler | ebiz-webhosting.de
die PHP Marktplatz-Software | ebiz-trader.de
Mit Zitat antworten
  #8 (permalink)  
Alt 14-06-2009, 10:48
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

icke? mehr
Mit Zitat antworten
  #9 (permalink)  
Alt 14-06-2009, 13:07
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

ne verschreckt nicht - ich bin erst jetzt wieder hierzu gekommen ^^
Es war doch Freitag abend
Da muss man doch nicht immer vorm PC hocken *g*

Also um nochmal klar zu stellen: Ich suche kein Suchsystem ala Google für die Weltkarte. Meine karte ist etwas einfacher.
Ich hab eine 2D Karte wie wahrscheinlich
Zitat:
Zitat von onemorenerd
2D-Karten wie diese sind meist Felder von Quadranten
meinte. (Leider kann man den Link nicht aufrufen.)
EDIT:
ja genau so sieht meine karte aus (bisschen einfacher)


Also es gibt auf jeder Koordinate entweder ein Haus, Wald, Gras, Wasser oder eben Straße.

Also rein vom logischen hab ich mir schon gedacht das ich sozusagen jedes angrenzende Feld untersuchen muss ob dort ein Weg möglich ist. Nur meine Frage ist eher wie ich die Priorität mit einbaue.
Sonst findet er ja bestimmt irgendwann nen Weg aber der ist auf jedenfall nicht der kürzeste.
Aber wahrscheinlich ist dieser A* das was ich suche oder?
Zitat:
Zitat von onemorenerd
Hier kannst du dir anschauen wie diese Algorithmen arbeiten.
Ist bei der Seite das was gerade ausgewählt ist das was oben links in der Ecke steht? Oder wenn ich drauf klick spirngt er zu dem jeweiligen?
Die Seite ist echt gut.

Mir haperts grad noch wie ich das dann in PHP umsetz ^^
Und ist die Ladezeit dann nicht enorm?
__________________
Mess with the Besth, die like the rest!

Geändert von Besth (14-06-2009 um 13:22 Uhr)
Mit Zitat antworten
  #10 (permalink)  
Alt 14-06-2009, 14:19
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Du kennst die Koordinaten von Start und Ziel, also kannst du vom Start aus bevorzugt in Richtung Ziel gehen, Feld für Feld. Wenn ein Feld nicht begehbar ist, nimmst du das Nachbarfeld, was noch am ehesten in Richtung des Ziels liegt.
Rennst du in eine Sackgasse, machst du Backtracking. Eine Sackgasse erkennst du daran, dass du alle Felder um deinen Standort bereits erkundet hast (bis auf das von dem du gekommen bist natürlich) und nirgendwo einen Weg fandest. Also gehst du einen Schritt zurück auf das Feld von dem du gekommen bist und probierst dort eine Alternative, also ein Feld, das du bisher noch nicht probiert hast. Auch hier gilt wieder: Wähle zuerst das Feld, welches am meisten Richtung Ziel liegt.

Wahrscheinlich kannst du dir den Ablauf des Algorithmus inzwischen ganz gut vorstellen (falls nicht ...), aber du weißt nicht wie du das in Code gießen kannst. Nun, ich würde mit einer 10x10 Felder großen Karte beginnen, auf der zunächst alle Felder begehbar sind.
Du brauchst eine Repräsentation dieser Karte (Klasse oder Array), falls du das noch nicht hast. Außerdem brauchst du eine Repräsentation des aktuellen Standorts und des Ziels (Koordinatenpaare x,y) und Hilfsfunktionen wie istBegehbar(x,y), istAufDerKarte(x,y), geheNach(x,y) usw.
Wenn das alles steht kannst du anfangen:

Standort = geheNach(Start);
Nachbarfeld = ermittleBestesNachbarfeld(Standort, Ziel);
wenn istBegehbar(Nachbarfeld) Standort = geheNach(Nachbarfeld);

Das funktioniert bereits, weil die Karte überall begehbar ist.
Nun fügst du eine Wand zwischen Start und Ziel ein und passt den Algorithmus so an, dass er einen Weg drumherum findet. Dabei sind nur zwei Dinge zu beachten:
1. Code wiederverwenden! So entsteht die Rekusion.
2. Keine Annahmen über die Umwelt (Größe der Karte, Zielpunkt, Form der Wand) im Code verankern.
Mit Zitat antworten
  #11 (permalink)  
Alt 14-06-2009, 17:56
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Ja das Prinzip hab ich verstanden. Danke für deine anschaulichen Erklärungen.
Ich mein eher wie rechne ich denn zb aus welches das beste nachbarfeld ist ^^
muss ich da die luftlinie nehmen zwischen dem zu ermitteltem feld und dem ziel - und wenns am kleinsten ist - ist das das beste feld?
ich test es mal so
__________________
Mess with the Besth, die like the rest!
Mit Zitat antworten
  #12 (permalink)  
Alt 15-06-2009, 00:27
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Nehmen wir mal an dein Standort ist (2,1) und das Ziel (4,5). Das Feld sieht also so aus:
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   |   |   |   |
---------------------------
2 |   |   |   |   |   |   |
---------------------------
1 |   |   | S |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Du bildest die Differenzen der x-und y-Werte (Schritt 1)
x = 4-2 = 2
y = 5-1 = 4
halbierst diese Werte und rundest das Ergebnis (Schritt 2)
x = round(2/2) = 1
y = round(4/2) = 2
und addierst sie zu den Koordinaten deines Standortes (Schritt 3).
So erhältst du den Punkt (3,3), der auf der Hälfte des Weges zwischen Standort und Ziel liegt:
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   | P |   |   |
---------------------------
2 |   |   |   |   |   |   |
---------------------------
1 |   |   | S |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Solange nicht beide Ergebnisse aus dem zweiten Schritt 1 sind, wiederholst du das ganze, nimmst aber immer den Punkt P als Ziel an.
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   |   |   |   |
---------------------------
2 |   |   |   | P |   |   |
---------------------------
1 |   |   | S |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Wenn beide Ergebnisse 1 sind erhältst du durch Addition zum Standort die Koordinaten eines Nachbarfelds.

Dahinter steckt die Idee eines rechtwinkligen Dreicks SZR mit R = (xZ, yS) und dessen Verkleinerung Richtung S durch Hypthenusenhalbierung.
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   |   |   |   |
---------------------------
2 |   |   |   |   |   |   |
---------------------------
1 |   |   | S |   | R |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Die Komplexität der Schleife mit den o.g. drei Schritten ist logarithmisch in der Größe des Feldes. Bei 1000x1000 Felder wird sie also nur maximal 10 Mal durchlaufen. Schick, aber gaanz großer Käse! Es geht nämlich auch in O(n). Denn es gibt auch eine Möglichkeit das Nachbarfeld direkt aus den Koordinaten von Standort und Ziel abzuleiten. Dazu betrachtet man die relative Lage der Punkte zueinander. Liegt Z rechts von S, kommen auch nur die rechten Nachbarfelder von S in Betracht. Liegt Z zudem über S, kommen nur Nachbarfelder rechts über S in Frage. Davon gibt es nur eins. Rums bums Nikolaus.
Mit Zitat antworten
  #13 (permalink)  
Alt 15-06-2009, 10:19
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Also das klingt für mich jetzt doch etwas verwirrend
ich habs etwas anders gelöst.
ich hab diese formel genommen:

damit rechne ich immer den weg der luftlinie zwischen den nachbarfeldern meines standortes und des ziels aus.
wo der wert am kleinsten ist, ist das beste feld.

sackgassen hab ich auch rausgefiltert. sollte einmal ein weg eingeschlagen werden wo es nicht weiter geht - wird ein feld zurück gegangen und nach alternativen gesucht.

mein prob is derzeit noch das er nur eine route findet aber es ist NICHT die kürzeste
muss das mit den kosten da noch reinbekommen.
naja ich bau mal noch weiter

EDIT:
bei deinem beispiel ist aber das problem wenn nun eine wand (hier die X) so ist:
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   | X | X | X | X | X |
---------------------------
3 |   | X |   |   |   |   |
---------------------------
2 |   | X |   | S |   |   |
---------------------------
1 |   | X |   |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
dann rennst du ja nur nach norden und dann wirds mist, weil er irgendwann nich mehr weiter kommt.

__________________
Mess with the Besth, die like the rest!

Geändert von Besth (15-06-2009 um 10:54 Uhr)
Mit Zitat antworten
  #14 (permalink)  
Alt 15-06-2009, 13:19
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Ja klar gehe ich erstmal nach Norden.
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   | X | X | X | X | X |
---------------------------
3 |   | X |   | S |   |   |
---------------------------
2 |   | X |   |   |   |   |
---------------------------
1 |   | X |   |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Nun würde ich gern auf (4,4) gehen. Dieses Feld ist aber nicht begehbar. Erst jetzt erkenne ich, dass ich auf ein Hindernis zugelaufen bin.
Ich versuche (3,4), weil es ebenso gut Richtung Z führt. Aber auch dieses Feld ist nicht begehbar.
Nun versuche ich (4,3), das ist begehbar, also mache ich diesen Schritt.
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   | X | X | X | X | X |
---------------------------
3 |   | X |   |   | S |   |
---------------------------
2 |   | X |   |   |   |   |
---------------------------
1 |   | X |   |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Jetzt würde ich gern nach (5,4), aber das geht nicht. Ich erkenne, dass mich jeder andere Schritt weiter von Z wegbringen würde (lokales Optimum) und beginne, das Hindernis zu umgehen. Hindernisumgehung bedeutet "gehe so lange an der Wand entlang, bis es günstiger wäre, Richtung Z zu gehen, statt weiter an der Wand lang". Ich starte Richtung Osten.
Code:
---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   | X | X | X | X | X |
---------------------------
3 |   | X |   |   |   | S |
---------------------------
2 |   | X |   |   |   |   |
---------------------------
1 |   | X |   |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Am Rand der Karte ändere ich die Richtung - ich gehe nun andersrum an der Wand lang. Hier der Weg, den ich schließlich zurücklege.
Code:
---------------------------
5 |   | S |   |   | Z |   |
---------------------------
4 | . | X | X | X | X | X |
---------------------------
3 | . | X | . | . | . | . |
---------------------------
2 | . | X | . |   |   |   |
---------------------------
1 | . | X | . |   |   |   |
---------------------------
0 |   | . |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |
Ab diesem Moment ist es günstiger, wieder direkt auf Z zuzulaufen. Deshalb höre ich auf an der Wand entlang zu gehen.

Geändert von onemorenerd (15-06-2009 um 13:22 Uhr)
Mit Zitat antworten
  #15 (permalink)  
Alt 15-06-2009, 21:48
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

jojo is schon klar soweit

aber mal noch ne andere sache. bei den seiten die du gelinkt (zb hier) hast reden die immer von einer offenen liste und einer geschlossenen liste.
gibt es sowas in php? also listen?
oder muss man das über mehrdimensionale arrays lösen? oder gar direkt über die db? was geht denn am schnellsten bei der verarbeitung?
__________________
Mess with the Besth, die like the rest!
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
[Script] Automatisches Eintragen von Videos auf Seite Pitchriddick Apps und PHP Script Gesuche 0 19-05-2007 00:16
[Script] automatisches ausfüllen eines externen formulars crok74 Apps und PHP Script Gesuche 4 22-11-2006 10:11
[Perl] Automatisches script / dateien umbenennen radio-dreamwave Apps und PHP Script Gesuche 0 30-11-2005 23:03
automatisches script mastahjay PHP Developer Forum 9 23-11-2002 12:26
automatisches Löschen Argus SQL / Datenbanken 1 26-10-2001 21:41

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

PHP Server Monitor

PHP Server Monitor ist ein Skript, das prüft, ob Ihre Websites und Server betriebsbereit sind.

11.09.2018 Berni | Kategorie: PHP/ Security
PHP WEB STATISTIK ansehen PHP WEB STATISTIK

Die PHP Web Statistik bietet Ihnen ein einfach zu konfigurierendes Script zur Aufzeichnung und grafischen und textuellen Auswertung der Besuchern Ihrer Webseite. Folgende zeitlichen Module sind verfügbar: Jahr, Monat, Tag, Wochentag, Stunde Folgende son

28.08.2018 phpwebstat | Kategorie: PHP/ Counter
Affilinator - Affilinet XML Produktlisten Skript

Die Affilinator Affilinet XML Edition ist ein vollautomatisches Skript zum einlesen und darstellen der Affili.net (Partnerprogramm Netzwerk) Produktlisten und Produktdaten. Im Grunde gibt der Webmaster seine Affilinet PartnerID ein und hat dann unmittelb

27.08.2018 freefrank@ | Kategorie: PHP/ Partnerprogramme
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 08:35 Uhr.