Marching Squares

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

darth

Betreff: Marching Squares

BeitragSo, Apr 18, 2010 20:44
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,

ich bin gerade beim Versuch einen Marching Squares Algorithmus zu schreiben. Damit werden i.A. Ränder für 2D Felder bestimmt (die entweder true oder false sind). Um die Felder zu generieren benutze ich die Metaball-Formel.

Für die Richtungsbestimmung nutze ich folgende Regeln von Wikipedia:
user posted image

Im Code sieht das so aus:
BlitzBasic: [AUSKLAPPEN]
Function getDirection(x, y)
Local d1, d2, d3, d4

d1=getDataField(x-1,y-1)
d2=getDataField(x,y-1)
d3=getDataField(x-1,y)
d4=getDataField(x,y)

Local sum=d1+d2+d3+d4

Local N=1 ; NORTH
Local E=2 ; EAST
Local S=3 ; SOUTH
Local W=4 ; WEST

Select sum
Case 0
Return E
Case 1
If d2
Return E
ElseIf d4
Return S
ElseIf d1
Return N
ElseIf d3
Return W
EndIf
Case 2
If d2 And d4
Return S
ElseIf d1 And d2
Return E
ElseIf d1 And d3
Return N
ElseIf d3 And d4
Return W
ElseIf d1 And d4
Return N
ElseIf d2 And d4
Return W
EndIf
Case 3
If Not d2
Return N
ElseIf Not d1
Return W
ElseIf Not d3
Return S
ElseIf Not d4
Return E
EndIf
Default
Return -1
End Select
End Function


Und im Pfadgenerator selber ist dann dieser Teil:
BlitzBasic: [AUSKLAPPEN]
	Repeat
iter=iter+1
If iter>maxIter
;Dies hier ist ein Problem!
Return newPath(initialX, initialY, directions)
EndIf

Select getDirection(X, Y)
Case 1
dir=newDirection(North)
Case 2
dir=newDirection(East)
Case 3
dir=newDirection(South)
Case 4
dir=newDirection(West)
Default
Return Null
End Select

X=X+dir\dirX
Y=Y+dir\dirY

previous\succ=dir
previous=dir
Until X=initialX And Y=initialY


So, für den Grossteil aller Fälle funktioniert das ohne Probleme. Aber es gibt mindestens einen Sonderfall, der mir aufgefallen ist, in diesem Beispiel hier:

user posted image

Der rote Pfad funktioniert ohne weiteres. Der folgt dem Punkt da hinauf und geht dann weiter bis zum Urpsrung. Das Problem ist dann, dass er beim grünen Pfad auch hochgeht und dann "unendlich lang" den roten umkreist.
Wenn ich die Antwort ändere, also bei der Stelle da nach Süden gehe statt nach Norden, dann habe ich das Problem, dass er "unendlich" oft um den grünen Part kreist (weil er immer wieder an dieser Stelle vorbeikommt, und sich nach Süden entscheidet).
Rein theoretisch würde ich sagen, dass der rote Pfad den grünen beinhalten müsste (also dort nach Süden gehn, nicht nach Norden) - was aber wie gesagt zum selben Problem führt.

Ich hoffe ihr versteht mein Problem. Sonst muss ich wohl versuchen das umzuformulieren :/ Meh.

Falls jemand sich damit auskennt oder sonst eine Idee hat, wie man das lösen könnte, wäre ich dankbar.

MfG,
Darth
Diese Signatur ist leer.

Ana

BeitragSo, Apr 18, 2010 21:16
Antworten mit Zitat
Benutzer-Profile anzeigen
Versteh ich das richtig dass das Problem nur bei den Diagonal 2 weiß 2 schwarz auftritt und er eigentlich dann in das kleine Feld einmal rum und dann wieder im großen weiter soll?

Also es ist sicherlich keine allzu saubere Lösung aber vielleicht einen type erzeugen ansolchen stellen der sich merkt in welche richtung gegangen wurde und dann wann immer so ein Feld auftaucht überprüft wird ob es für das feld schon einen type gibt und dann die von dem angegebene richtung verboten ist?

hectic

Sieger des IS Talentwettbewerb 2006

BeitragMo, Apr 19, 2010 2:12
Antworten mit Zitat
Benutzer-Profile anzeigen
Deine Filteregeln sind nicht sauber. In der einen und selben Situation wo entsprechend aber die Kommen-Richtung unterschiedlich ist - wird diese jedoch nicht berücksichtigt, sondern - wird einfach pauschal wieder in die eine vorgegebene Richtung geschaltet. Du musst nur einen Weg finden, einen bereits besuchten Weg als solches zu markieren und entsprechend dann eine 180° Wende zur Ziel-Richtung bestimmen.

Da kann es einfach helfen, wenn man die Kommen-Richtung mit berücksichtig und in so einem Fall (10/01) oder (01/10) entsprechend 180° die Ziel-Richtung zu bestimmen oder nicht. Das würde zumindest ein Type oder eine zweite Array-Maske ersparen.
Download der Draw3D2 V.1.1 für schnelle Echtzeiteffekte über Blitz3D

darth

BeitragMo, Apr 19, 2010 15:40
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,

ich habe gestern im Chat noch über das Ding diskutiert, und auch da wurde mir gesagt, ich solle die alte Richtung mit einbeziehen.

Die Methode von wegen "da war ich schon" (mit einer weiteren Array-Mask) funktioniert nicht, weil er beim Kreuzungspunkt einfach abbrach (-> die Maske sollte Loops verhindern, auch im Chat diskutiert). Ausserdem löste dies das Wegproblem nicht.

Ich habe dann mal beide Lösungsvorschläge (von hier) umgesetzt und eigentlich funktionieren beide. Allerdings finde ich die Lösung mit den Types (wie von Khalantes erwähnt) etwas unsauber, also habe ich mich für die alte Richtung entschieden.
Das macht auch Sinn denn, wenn er zweimal aus der gleichen Richtung an den selben Punkt kommt, muss schon vorher ein Fehler passiert sein.

Komisch finde ich nur, dass dieses Problem scheinbar nirgends angesprochen wird, wenn der Algorithmus vorgestellt wird :/ Ich vermute mal, die rechnen nicht-kompakten (nicht zusammenhängenden) Feldern, sondern nur mit einem einzelnen.. Allerdings fällt mir gerade kein Fall ein, wo eine solche Konstellation eintreffen könnte..

Es hat sich dann noch herausgestellt dass der andere Fall (also die Diagonale in die andere Richtung) auch zum ähnlichen Fehler führt, aber da kann man die gleiche Lösung übernehmen.
Von daher ist das Problem gelöst, ich danke für die Ratschläge.

MfG,
Darth
Diese Signatur ist leer.

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group