Pathfinding - Contest [Beendet]

Übersicht Sonstiges Projekte

Gehe zu Seite Zurück  1, 2

Neue Antwort erstellen

 

Matthias

 BeitragSo, Aug 03, 2008 15:29
Antworten mit Zitat
Benutzer-Profile anzeigen
OK. Aber drozdem würde ich mir wünschen das die Testmap schon offengelegt wird.

Denn ich bin der Meinung das mann bei großen Maps. Andere Methoden anwenden muß als bei
Kleinen. Also wie groß ist das Map Maximal??.
 

Ava

Gast

BeitragSo, Aug 03, 2008 15:56
Antworten mit Zitat
Integrier doch einfach eine Abfrage und verwende unterschiedliche Funktionen, wenn Du meinst, es wäre angebrachter, dies für die jeweiligen Map-Grössen zu unterscheiden. Rolling Eyes

Ein guter Pathfinder sollte schon in der Lage sein, mit einer unbekannten Map klarzukommen ... *räusper* ... wie auch immer er dies bewerkstelligt ...
 

Dreamora

 BeitragSo, Aug 03, 2008 16:32
Antworten mit Zitat
Benutzer-Profile anzeigen
Das ist unrealistisch Ava

Immerhin die Grössenordnung der Map sollte bekannt sein. 32x32? 256x256? 1024x1024?
Denn während für ersteres etwas funktionieren mag, so kann man eigentlich garantieren das es bei letzterem nimmer funktionieren wird.


Eine andere Frage: Ich nehme an das in der gleichen map einige dutzend verschiedene Pfade berechnet werden, mehrfach (wegen CPU Variationen), richtig? Nicht nur einer und gut ist.
Denn Caching ist ein "normaler Vorgang" für Wegfindung, macht aber keinen Sinn wenn pro Map nur eine Berechnung erfolgt.
Besonders bei grossen Maps macht es einen recht extremen Unterschied.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.
 

Ava

Gast

BeitragSo, Aug 03, 2008 16:38
Antworten mit Zitat
Verstehe ich nicht, warum das unrealistisch ist, sorry. Ich habe in meinem ganzen Leben noch keine einzige Pathfinder-Funktion programmiert, die nur auf einer einzigen Map bzw. bei konstanter Map-Grösse funktioniert hat - auf so eine blöde Idee wäre ich nie gekommen...

Das die Karten-Dimensionierung übergeben werden bzw. abrufbar sein muss, ist denke ich selbstverständlich ...

Aber wenn ein Pathfinder ne 512x512 Map schafft und dann bei 256x256 nur Grütze auswirft oder sich erhängt, weil plötzlich mal ne Wand woanders steht, als wie er das "gelernt" hat ... dann ist das schon sehr bedenklich und auch traurig ...
 

Dreamora

 BeitragSo, Aug 03, 2008 16:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Das Problem ist eher umgekehrter Natur.

In normalen Situationen wirst du nichts mit ner 1024er map befeuern ausser du hast das Path Finding System (das ist nicht mit einer einzelnen Funktion zu meistern) darauf ausgelegt und speicherst entsprechende "Toplevel Pfade" zwischen Zellen der Map

Von daher ist es unerlässlich die Grösse der Map zu wissen, damit man in etwa abschätzen kann wieviel "Management Overhead" sinnvoll ist zu implementieren. Denn wenn alle maps 64x64 und kleiner sind ist es total sinnlos dafür komplexere Algorithmen zu nutzen, denn die werden vom Overhead dann ausgenockt.

Eher Dijkstra, A*, Hierarchie basierende Ansätze, Potenzfelder, ... ??


Ich hoffe das Problem leuchtet jetzt ein.
Es geht nicht drum obs geht, es geht drum wie ineffizient es wird aufgrund von Overheads die bei grösseren Maps ausgeglichen werden und anderen Faktoren.


Von daher würde ich mir folgende Spezifikationen wünschen:

1. Wird es auf einer Map mehr als 1 Pfad berechnet? (-> Caching und ähnliche Mechanismen)
2. Wie viele Maps wird es geben, welche Grossen sind dabei zu erwarten?
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.
 

Ava

Gast

BeitragSo, Aug 03, 2008 17:07
Antworten mit Zitat
Nein, ich verstehe Dein Problem nicht bzw. warum meine Aussage unrealistisch war, da Du ansich nur meinen Denkansatz wiederholst.

Ein gutes Pathfinding-System muss meiner Aufassung nach klug genug sein, die optimale Methode anhand der übergeben Parameter auszuwählen und so dann auch gegebenfalls auf unterschiedliche Lösungswege / Algorythmen zurückzugreifen.

Aber wahrscheinlich denke ich schon wieder viel zu überdimensional ... zumal ich es zeitlich wohl doch nicht schaffen werde, am Contest teilzunehmen. Confused
 

Dreamora

 BeitragSo, Aug 03, 2008 18:06
Antworten mit Zitat
Benutzer-Profile anzeigen
Eigentlich hast du recht. Aber eben, der contest ist nicht so ausgelegt, das etwas derart komplexes sinn macht, da der entwicklungsaufwand dann easy 100 stunden überschreitet und das ist es definitiv net wert wenn die sources dann "frei raus gehen" zumindest nicht für mich und vermutlich auch sonst nur wenige die eine flexible effiziente lösung implementieren könnten in Blitz3D
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.
 

BIG BUG

 BeitragSo, Aug 03, 2008 23:25
Antworten mit Zitat
Benutzer-Profile anzeigen
Dreamora hat schon recht.
Gut möglich dass der eine Algo bei 32*32 und ein anderer Algo bei 512*512 der schnellste ist. Wer gewinnt?
Es sollte also entweder ein gewisser Rahmen vorgegeben oder eben über diverse Map-Größen getestet und Punkte vergeben werden.
Aber wenn es wieder nur bei einem Teilnehmer bleibt, hat sich das Problem sowieso erübrigt Smile
B3D-Exporter für Cinema4D!(V1.4)
MD2-Exporter für Cinema4D!(final)

Noobody

 BeitragMo, Aug 04, 2008 0:02
Antworten mit Zitat
Benutzer-Profile anzeigen
Testen werde ich die Funktionen auf Mapgrössen von 32x32 bis 256x256 - sprich 4 verschiedene Maps (alles mit Seitenlängen von Zweierpotenzen).
Es werden auf jeder Map 3 verschiedene Pfade abgefragt - Caching und ähnliche Methoden seien erlaubt, wer dies für nötig hält.

StepTiger: Die Arraygrösse ist gegeben durch die Globalen MapWidth und MapHeight. Zitat:
Das Array beginnt bei 0, hat also die Grösse MapWidth - 1, MapHeight - 1.


BIG BUG: Wie bereits erwähnt, werden die Ergebnisse zusammengezählt; der Algorithmus, der im Durchschnitt am schnellsten ist, gewinnt also.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

Dreamora

 BeitragMo, Aug 04, 2008 0:03
Antworten mit Zitat
Benutzer-Profile anzeigen
Jut jut, danke Smile
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Noobody

Betreff: Ende Gelände

 BeitragDi, Sep 02, 2008 8:16
Antworten mit Zitat
Benutzer-Profile anzeigen
*tsching*
Mit einiger Verspätung läute ich hiermit den Schlussgong für den Contest.
Eine Auswertung war diesmal nicht nötig, da unglücklicherweise (trotz der grossen Resonanz) nur ein einziger teilgenommen hat.
Hiermit überreiche ich den Preis des "King of Pathfinding 2008" an Lobby!

Sein abgegebener Code: [AUSKLAPPEN]
;Vorbereitungen
Graphics 400,300,32,2
SetBuffer BackBuffer()

Global MapWidth%=20,MapHeight%=10
Dim MapData(MapWidth-1,MapHeight-1)
Dim Array(MapWidth-1,MapHeight-1)

;Mauer erstellen
MapData(7,5)=1
MapData(7,6)=1
MapData(7,7)=1

;Punkte festlegen
StartX%=2
StartY%=2
EndX%=8
EndY%=6

timer=CreateTimer(48)


While 1
   ams=MilliSecs()
   
   ;Funktionsaufruf
   fp$=FindPath$(StartX,StartY,EndX,EndY)
   
   ms=MilliSecs()
   fps#=(1000.0/(ms-ams))*0.5+fps*0.5
   
   ;Grafische Darstellung
   Cls
   For y=0 To MapHeight-1
      For x=0 To MapWidth-1
         If MapData(x,y)=0 Then
            Color 155,155,155
            Rect x*20,y*20,19,19
         Else
            Color 255,255,255
            Rect x*20,y*20,19,19
            Color 55,55,55
            Rect x*20+1,y*20+1,18,18
            Color 88,88,88
            Rect x*20+1,y*20+1,17,17
            Color 55,55,55
            Text x*20+5,y*20+3,"M"
         EndIf
      Next
   Next
   x=StartX
   y=StartY
   t$=fp
   While t$<>""
      nt$=Mid(t,1,1)
      ax=x
      ay=y
      Select nt
         Case 6
            x=x+1
         Case 2
            y=y+1
         Case 4
            x=x-1
         Case 8
            y=y-1
         Case 3
            x=x+1
            y=y+1
         Case 1
            x=x-1
            y=y+1
         Case 7
            x=x-1
            y=y-1
         Case 9
            x=x+1
            y=y-1
      End Select
      Color 255,255,255
      Rect x*20,y*20,19,19
      Color 155,155,0
      Line ax*20+10,ay*20+10,x*20+10,y*20+10
      t=Mid(t,2)
   Wend
   Color 255,255,255
   Rect StartX*20,StartY*20,19,19
   Color 0,155,0
   Rect StartX*20+1,StartY*20+1,18,18
   Color 0,255,0
   Rect StartX*20+1,StartY*20+1,17,17
   Color 0,155,0
   Text StartX*20+5,StartY*20+3,"S"
   Color 255,255,255
   Rect EndX*20,EndY*20,19,19
   Color 155,0,0
   Rect EndX*20+1,EndY*20+1,18,18
   Color 255,0,0
   Rect EndX*20+1,EndY*20+1,17,17
   Color 155,0,0
   Text EndX*20+5,EndY*20+3,"E"
   Color 255,255,255
   Text 0,220,"Weg: "+fp
   t$=fps
   If t="Infinity" Then
      t=">1000"
      fps=0
   EndIf
   Text 0,240,t+" FPS("+nms+"ms)"
   Text 0,260,"LMT um den Startpunkt zu setzen"
   Text 0,272,"RMT für den Endpunkt und MRT für Mauer;-)"
   Flip 0
   nms=(ms-ams)
   mx=MouseX()-10
   my=MouseY()-10
   x=Int(mx/20.0)
   y=Int(my/20.0)
   If MouseDown(1) Then
      StartX=x
      StartY=y
      EndIf
   If MouseDown(2) Then
      EndX=x
      EndY=y
   EndIf
   If MouseHit(3) Then
      If x<=MapWidth-1 And y<=MapHeight-1 Then
         MapData(x,y)=1-MapData(x,y)
      EndIf
   EndIf
   WaitTimer timer
Wend







;Funktionen & Types_________________________________________________________

Function FindPath$(StartX%,StartY%,EndX%,EndY%)
   If StartX<0 Or StartY<0 Or EndX>MapWidth-1 Or EndY>MapHeight-1 Or StartX>MapWidth-1 Or StartY>MapHeight-1 Or EndX<0 Or EndY<0 Then Return ""
   If MapData(StartX,StartY)>0 Or MapData(EndX,EndY)>0 Then Return ""
   ClearAll()
   TypeAdd EndX,EndY,Null,""
   hz%=MapWidth*MapHeight
   For z%=0 To hz
      tw$=TypeWork$(StartX,StartY,EndX,EndY)
      If tw<>"" Then Return tw
   Next
   Return ""
End Function

Function ClearAll()
   For Feld.TFeld=Each TFeld
      Delete Feld.TFeld
   Next
   For y=0 To MapHeight-1
      For x=0 To MapWidth-1
         Array(x,y)=0
      Next
   Next
End Function

Function TypeAdd(x%,y%,ch.TFeld,name$)
   If x<0 Or y<0 Or x>MapWidth-1 Or y>MapWidth-1 Then Return
   If MapData(x,y)<>0 Or Array(x,y)<>0 Then Return
   Feld.TFeld=New TFeld
   Feld\x=x
   Feld\y=y
   Feld\ch=ch
   Feld\c=0
   Feld\movename=name
   Array(x,y)=1
   Return
End Function

Function TypeWork$(sx%,sy%,zx%,zy%)
   For Feld.TFeld=Each TFeld
      If Feld\x=sx And Feld\y=sy Then
         t$=""
         Feld2.TFeld=Feld.TFeld
         While Feld2.TFeld<>Null
            t$=t$+Feld2\movename
            Feld2.TFeld=Feld2\ch.TFeld
         Wend
         Return t
      ElseIf Feld\c=0 Then
         TypeAdd Feld\x+1,Feld\y,Feld.TFeld,4
         TypeAdd Feld\x,Feld\y+1,Feld.TFeld,8
         TypeAdd Feld\x-1,Feld\y,Feld.TFeld,6
         TypeAdd Feld\x,Feld\y-1,Feld.TFeld,2
         TypeAdd Feld\x+1,Feld\y+1,Feld.TFeld,7
         TypeAdd Feld\x+1,Feld\y-1,Feld.TFeld,1
         TypeAdd Feld\x-1,Feld\y+1,Feld.TFeld,9
         TypeAdd Feld\x-1,Feld\y-1,Feld.TFeld,3
         Feld\c=1
      EndIf
   Next
End Function

Type TFeld
   Field x%
   Field y%
   Field ch.TFeld
   Field c%
   Field movename$
End Type


Wenn er will, kann er gerne einen neuen Contest starten, jedoch ist die Beteiligung jeweils eher gering (leider).
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

da_poller

 BeitragDi, Sep 02, 2008 15:46
Antworten mit Zitat
Benutzer-Profile anzeigen
ich will nciht kritisieren aber der code erzeugt bei mir einen mav in folgender zeile:

Code: [AUSKLAPPEN]
If MapData(StartX,StartY)>0 Or MapData(EndX,EndY)>0 Then Return ""


Array index out of bounds

liegts an mir oder gewinnt ein verbuggter code?

Lobby

 BeitragSa, Sep 06, 2008 1:43
Antworten mit Zitat
Benutzer-Profile anzeigen
Ja da_poller, da is nen Bug drinn Confused (Ich verzichte u.a. daher auf den Titel)

Ich bin dafür diese Titelwettbewerbe in Zukunft mit 'echten' Titeln zu machen
(die dann unter dem Nick des Siegers stehen), dazu wäre jedoch zuerst
eine Absprache mit den entsprechenden Personen (Admins/Mods) nötig.
An dieser Stelle beende ich diese Wettbewerbe vorerst einmal, ihr könnt
ja wieder einen mit Absprache organisieren für den Fall das ihr das hinkriegt Wink

Hier noch der funktionierende Code(für die die den Fehler nochnicht entdeckt haben):
Code: [AUSKLAPPEN]
;Vorbereitungen
Graphics 400,300,32,2
SetBuffer BackBuffer()

Global MapWidth%=20,MapHeight%=10
Dim MapData(MapWidth-1,MapHeight-1)
Dim Array(MapWidth-1,MapHeight-1)

;Mauer erstellen
MapData(7,5)=1
MapData(7,6)=1
MapData(7,7)=1

;Punkte festlegen
StartX%=2
StartY%=2
EndX%=8
EndY%=6

timer=CreateTimer(48)


While 1
ams=MilliSecs()

;Funktionsaufruf
fp$=FindPath$(StartX,StartY,EndX,EndY)

ms=MilliSecs()
fps#=(1000.0/(ms-ams))*0.5+fps*0.5

;Grafische Darstellung
Cls
For y=0 To MapHeight-1
For x=0 To MapWidth-1
If MapData(x,y)=0 Then
Color 155,155,155
Rect x*20,y*20,19,19
Else
Color 255,255,255
Rect x*20,y*20,19,19
Color 55,55,55
Rect x*20+1,y*20+1,18,18
Color 88,88,88
Rect x*20+1,y*20+1,17,17
Color 55,55,55
Text x*20+5,y*20+3,"M"
EndIf
Next
Next
x=StartX
y=StartY
t$=fp
While t$<>""
nt$=Mid(t,1,1)
ax=x
ay=y
Select nt
Case 6
x=x+1
Case 2
y=y+1
Case 4
x=x-1
Case 8
y=y-1
Case 3
x=x+1
y=y+1
Case 1
x=x-1
y=y+1
Case 7
x=x-1
y=y-1
Case 9
x=x+1
y=y-1
End Select
Color 255,255,255
Rect x*20,y*20,19,19
Color 155,155,0
Line ax*20+10,ay*20+10,x*20+10,y*20+10
t=Mid(t,2)
Wend
Color 255,255,255
Rect StartX*20,StartY*20,19,19
Color 0,155,0
Rect StartX*20+1,StartY*20+1,18,18
Color 0,255,0
Rect StartX*20+1,StartY*20+1,17,17
Color 0,155,0
Text StartX*20+5,StartY*20+3,"S"
Color 255,255,255
Rect EndX*20,EndY*20,19,19
Color 155,0,0
Rect EndX*20+1,EndY*20+1,18,18
Color 255,0,0
Rect EndX*20+1,EndY*20+1,17,17
Color 155,0,0
Text EndX*20+5,EndY*20+3,"E"
Color 255,255,255
Text 0,220,"Weg: "+fp
t$=fps
If t="Infinity" Then
t=">1000"
fps=0
EndIf
Text 0,240,t+" FPS("+nms+"ms)"
Text 0,260,"LMT um den Startpunkt zu setzen"
Text 0,272,"RMT für den Endpunkt und MRT für Mauer;-)"
Flip 0
nms=(ms-ams)
mx=MouseX()-10
my=MouseY()-10
x=Int(mx/20.0)
y=Int(my/20.0)
If MouseDown(1) Then
StartX=x
StartY=y
EndIf
If MouseDown(2) Then
EndX=x
EndY=y
EndIf
If MouseHit(3) Then
If x<=MapWidth-1 And y<=MapHeight-1 Then
MapData(x,y)=1-MapData(x,y)
EndIf
EndIf
WaitTimer timer
Wend







;Funktionen & Types_________________________________________________________

Function FindPath$(StartX%,StartY%,EndX%,EndY%)
If StartX<0 Or StartY<0 Or EndX>MapWidth-1 Or EndY>MapHeight-1 Or StartX>MapWidth-1 Or StartY>MapHeight-1 Or EndX<0 Or EndY<0 Then Return ""
If MapData(StartX,StartY)>0 Or MapData(EndX,EndY)>0 Then Return ""
ClearAll()
TypeAdd EndX,EndY,Null,""
hz%=MapWidth*MapHeight
For z%=0 To hz
tw$=TypeWork$(StartX,StartY,EndX,EndY)
If tw<>"" Then Return tw
Next
Return ""
End Function

Function ClearAll()
For Feld.TFeld=Each TFeld
Delete Feld.TFeld
Next
For y=0 To MapHeight-1
For x=0 To MapWidth-1
Array(x,y)=0
Next
Next
End Function

Function TypeAdd(x%,y%,ch.TFeld,name$)
If x<0 Or y<0 Or x>MapWidth-1 Or y>MapHeight-1 Then Return
If MapData(x,y)<>0 Or Array(x,y)<>0 Then Return
Feld.TFeld=New TFeld
Feld\x=x
Feld\y=y
Feld\ch=ch
Feld\c=0
Feld\movename=name
Array(x,y)=1
Return
End Function

Function TypeWork$(sx%,sy%,zx%,zy%)
For Feld.TFeld=Each TFeld
If Feld\x=sx And Feld\y=sy Then
t$=""
Feld2.TFeld=Feld.TFeld
While Feld2.TFeld<>Null
t$=t$+Feld2\movename
Feld2.TFeld=Feld2\ch.TFeld
Wend
Return t
ElseIf Feld\c=0 Then
TypeAdd Feld\x+1,Feld\y,Feld.TFeld,4
TypeAdd Feld\x,Feld\y+1,Feld.TFeld,8
TypeAdd Feld\x-1,Feld\y,Feld.TFeld,6
TypeAdd Feld\x,Feld\y-1,Feld.TFeld,2
TypeAdd Feld\x+1,Feld\y+1,Feld.TFeld,7
TypeAdd Feld\x+1,Feld\y-1,Feld.TFeld,1
TypeAdd Feld\x-1,Feld\y+1,Feld.TFeld,9
TypeAdd Feld\x-1,Feld\y-1,Feld.TFeld,3
Feld\c=1
EndIf
Next
End Function

Type TFeld
Field x%
Field y%
Field ch.TFeld
Field c%
Field movename$
End Type
 

da_poller

 BeitragSo, Sep 07, 2008 19:38
Antworten mit Zitat
Benutzer-Profile anzeigen
lobby wollte dich damit nicht kritisieren obwohl dein code fehler haft war(hab den neuen nicht getestet) hab ich riesen respekt da das thema pathfinding für mcih noch ein buch mit 7 siegeln ist.. bin froh das ich netztwerk erstmal soweit hinbekomme Smile

Gehe zu Seite Zurück  1, 2

Neue Antwort erstellen


Übersicht Sonstiges Projekte

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group