Marching Squares
Übersicht

![]() |
darthBetreff: Marching Squares |
![]() Antworten mit Zitat ![]() |
---|---|---|
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: ![]() Im Code sieht das so aus: BlitzBasic: [AUSKLAPPEN] Function getDirection(x, y) Und im Pfadgenerator selber ist dann dieser Teil: BlitzBasic: [AUSKLAPPEN] Repeat 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: 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 |
![]() Antworten mit Zitat ![]() |
---|---|---|
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? |
||
![]() |
hecticSieger des IS Talentwettbewerb 2006 |
![]() Antworten mit Zitat ![]() |
---|---|---|
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 |
![]() Antworten mit Zitat ![]() |
---|---|---|
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. |
Übersicht


Powered by phpBB © 2001 - 2006, phpBB Group