Denkanstoss, wie geht's eleganter?
Übersicht
BlitzBasic Allgemein
|
TravisBetreff: Denkanstoss, wie geht's eleganter? |
 Mi, Apr 16, 2008 20:57Antworten mit Zitat 
|
|---|---|---|
|
https://www.blitzforum.de/upload/file.php?id=2856 (Blitz2D/3D)
Folgende Situation: Ein Array (x,y), freie Felder, blockierte Felder, Start und Ziel. Jetzt möchte ich (NUR) die Wegkosten vom Start zum Zielpunkt haben. Bewegungen in allen 8 Richtungen erlaubt. Habe bereits ein voll Funktionsfähiges Programm erstellt, was auch seinen Zewck erfüllt - ist aber nicht gerade elegant. Kann man das nicht irgendwie rekursiv mit einer Funktion lösen? Steh da echt auf'm Schlauch. Ihr merkt, es geht um Pathfinding. Das hat ja sicherlich schon mal jemand gemacht ... 
|
||
judos |
Mi, Apr 16, 2008 21:17 Antworten mit Zitat
|
|
|---|---|---|
|
Hmm wie meinst du Wegkosten??
Naja wenn du das PathfindingProgramm schon hast, dann wäre das wohl einfach: kosten= weglänge * kosten pro Feld mfg judos /edit: beim "füllen" in deinem Programm würde ich mal "if map(x,y)=n" gleich nach "for x=0 to 12" nehmen und das endif dann wiederum ganz am schluss vor "next" schreiben, damit überprüfst du nicht 8mal ob map(x,y) wirklich gleich n ist 
da du beim Ziel die Anzahl der Schritte hast, wäre das ungefähr gleich der länge. Allerdings solltest du beachten, dass wenn man diagonale Schritte macht dies eigentlich der Länge Sqr(2) entsprechen würde... Wird also nicht exakt sein wenn du es mit der Zahl beim Ziel, berechnest... /edit2: wenn du es elegant machen willst, tue die pathfinding funktion doch in eine Funktion
Und noch eine Frage an dich, der Weg den du suchst, wie kannst du den so ansprechen? Ich meine du hast ja nicht die Koordinaten in einem Dim-Feld wo du nacheinander hingehst. Du hast vielmehr welches Feld bei welchem Schritt eventuell betreten würde werden... :S Ach und kennst du dich mit Types von Blitzbasic aus? Habe ein Problem mit denen ebenfalls beim Pathfinding. Wenn sich das löst kann ich dir vielleich besser weiter helfen... |
||
|
BladeRunnerModerator |
Mi, Apr 16, 2008 21:39 Antworten mit Zitat
|
|---|---|---|
|
1. Auf www.blitzbase.de gibt es ein Tutorial zum A*-Algo.
2. Forensuche Codearchiv BMax, dort ist eine A*-Implementation meinerseits drin die ich auch recht ausführlich dokumentiert hatte. BMax ist zwar kein BB aber vielleicht hilft es prinzipiell beim Verständnis. 3. gibt es sicher auch in den BB-Codearchiven passende und rekursive Ansätze 
|
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
judos |
Mi, Apr 16, 2008 21:44 Antworten mit Zitat
|
|
|---|---|---|
|
wo genau auf www.blitzbase.de findet man dieses tutorial? habe echt die ganze Seite abgekämmt aber nichts gefunden....
mfg judos |
||
|
|
BladeRunnerModerator |
Mi, Apr 16, 2008 21:49 Antworten mit Zitat
|
|---|---|---|
|
http://www.blitzbase.de/quellcode/pathfinding.zip
sowie http://www.blitzbase.de/artikel/path_1.htm
|
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
RallimenSieger des 30-EUR-Wettbewerbs |
Mi, Apr 16, 2008 22:05 Antworten mit Zitat
|
|---|---|---|
|
Was ich beim groben gucken gesehen habe...
Das benutzen von And in einer If ... then geht immer auf die Geschwindigkeit, da immer beide vergleiche überprüft werden, selbst wenn das erste schon nicht zutrifft. |
||
|
[BB2D | BB3D | BB+]
|
||
|
|
Travis |
Do, Apr 17, 2008 18:19 Antworten mit Zitat
|
|---|---|---|
|
@judos
Ich brauche ja kein komplettes Pathfinding. Es geht nur darum zu ermitteln, ob ein Ziel mit einer bestimmten Anzahl von Schritten erricht werden kann oder nicht. Der eigentliche Weg ist egal, es muss nur möglich sein (oder eben nicht). Zitat: if map(x,y)=n ...oops! das steht da wirklich 'n paarMal zu oft. Danke.
|
||
|
www.funforge.org
Ich hasse WASD-Steuerung. Man kann alles sagen, man muss es nur vernünftig begründen können. |
||
|
|
BladeRunnerModerator |
Do, Apr 17, 2008 19:26 Antworten mit Zitat
|
|---|---|---|
|
Travis, dann brauchst du komplettes Pathfinding, denn nur wenn du den Pfad gehst siehst du ob er frei ist.
Ansonsten kannst du nur Entfernungsbestimmungen a la Pythagoras machen, aber das sagt ja nichts über die Gangbarkeit des Weges aus. |
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
|
Travis |
Fr, Apr 18, 2008 19:05 Antworten mit Zitat
|
|---|---|---|
|
Stimmt. Wenn der Weg blockiert ist, würde er in der Schleife hängen bleiben.
Code: [AUSKLAPPEN] Repeat .... Until Map(TarX,TarY) <> -2 Or KeyHit(1) Das könnte ich aber umgehen, indem ich vom Startpunkt aus eine Rekursive "Füllfunktion" anwende. Kommt die "Füllung" am Ziel an, dann ist der Weg frei und die Entfernung kann berechnet werden. |
||
|
www.funforge.org
Ich hasse WASD-Steuerung. Man kann alles sagen, man muss es nur vernünftig begründen können. |
||
|
|
RallimenSieger des 30-EUR-Wettbewerbs |
Fr, Apr 18, 2008 20:58 Antworten mit Zitat
|
|---|---|---|
|
Ich habe auch mal so eine Function geschrieben und bin da etwas anders rangegangen...
Ich habe mir ein zweites Array erstellt und das Ziel mit -1 und start mit 1 eingetragen Danach habe ich ein Type erstellt mit x und y vom Startpunkt. In der For =Each Schleife habe ich um den Startpunkt neue erstellt bis ich am Ziel war oder die Schleife verlassen wurde da es kein Weg gab. Code: [AUSKLAPPEN] Data 0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,1,0,0,0,0,0,0,0,1,0,0 Data 0,0,1,0,0,0,0,0,0,0,1,0,0 Data 0,0,1,0,0,0,0,0,0,0,1,0,0 Data 0,0,1,0,0,0,0,0,0,0,1,0,0 Data 0,0,1,0,0,0,1,0,0,0,1,0,0 Data 0,0,1,1,1,1,1,1,1,1,1,0,0 Data 0,0,1,0,0,0,1,0,0,0,1,0,0 Data 0,0,1,0,0,0,0,0,0,0,1,0,0 Data 0,1,1,0,0,0,0,0,0,0,1,0,0 Data 0,0,1,0,0,0,0,0,0,0,1,0,0 Data 0,0,0,0,0,0,0,0,0,0,0,0,0 Data 0,0,0,0,0,0,0,0,0,0,0,0,0 Const MAPX=12 , MAPY=12 Dim Map(MAPX,MAPY),PatFind(MAPX,MAPY) ;map einlesen For y= 0 To 12:For x= 0 To 12:Read Map(x,y):Next:Next ;########## Speed Test Time = MilliSecs() For t= 0 To 1000 StartZiel(0,0,12,12) Next Print (MilliSecs() - time)/ 1000.0 + " Millisec" ;########################## b= StartZiel(0,0,12,12) Print StartZiel(0,0,12,12) WaitKey ;######## Cls For y= 0 To 12 For x= 0 To 12 Text 25*x,22*y,Patfind (x,y) Next Next WaitKey End Type NaechstesFeld Field x,y End Type Function StartZiel(x1,y1,x2,y2) Dim PatFind(MAPX,MAPY) PatFind(x1,y1)= 1; 1 = Start PatFind(x2,y2)= -1;-1 = Ziel T.NaechstesFeld = New NaechstesFeld T\x=x1:T\y=y1 For T.NaechstesFeld = Each NaechstesFeld For x1 = T\x-(T\x>0) To T\x+(T\x<MAPX) For y1 = T\y-(T\y>0) To T\y+(T\y<MAPY) ;If x1 => 0 And x1 <= 12 And y1 => 0 And y1 <= 12 Then ; Array out of Range If Patfind (x1,y1) = -1 Then; Ziel gefunden wert = Patfind (T\x ,T\y ) Delete Each NaechstesFeld Return wert EndIf If Map (x1,y1) = 0 Then ; alles was =1 ist wird als Mauer If Patfind (x1,y1) = 0 ; leeres Feld ; noch nicht benutzt Patfind (x1,y1) =Patfind (T\x ,T\y ) +1 T1.NaechstesFeld = New NaechstesFeld T1\x=x1:T1\y=y1 EndIf EndIf ;EndIf Next Next Next Delete Each NaechstesFeld Return -1 End Function hab das mal mit deinem Feld getestet und die Function gleich noch verbessert Edit : habs nochmal verbessert |
||
Übersicht
BlitzBasic Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group