Zusammenhängende Flächen

Übersicht

BlitzBasic

Allgemein

	BBPro2 Betreff: Zusammenhängende Flächen	So, Sep 06, 2009 14:51 Antworten mit Zitat
hi, ich habe folgendes problem es geht um eine 2 dimensionale spielwelt, dargestellt durch ein 2 dimensionales array. nun hat jedes team (bis zu 10 teams) eine basis, dargestellt durch in teamfarbe gefärbte felder. gespeichert werden die maps in einem einfachen byte-format in einer .txt datei. nun zu meinem problem: ich möchte zu beginn der map eine überprüfung haben ob folgendes für die datei gilt: - jedes team hat -genau- eine basis - eine basis ist definiert als eine zusammenhängende fläche von basisfeldern - die welt ist torusförmig -> wenn 0,0 ein basis feld ist, 1,0 kein basisfeld ist, 99,0 ein basisfeld ist bei einer 100x100 map handelt es sich um eine basis (also überlauf an den kartenrändern möglich( nun fällt mir leider kein geeigneter algorithmus zu dem problem ein, der keine exponentielle laufzeit mit sich bringen wüde. hat jemand von euch so etwas ähnliches vlt schonmal gelöst und hat etwas code für mich ? oder ne gute idee vielen dank im voraus !

BBPro2

Betreff: Zusammenhängende Flächen

So, Sep 06, 2009 14:51
Antworten mit Zitat

hi,
ich habe folgendes problem

es geht um eine 2 dimensionale spielwelt, dargestellt durch ein 2 dimensionales array.
nun hat jedes team (bis zu 10 teams) eine basis, dargestellt durch in teamfarbe gefärbte felder.
gespeichert werden die maps in einem einfachen byte-format in einer .txt datei.
nun zu meinem problem: ich möchte zu beginn der map eine überprüfung haben ob folgendes für
die datei gilt:
- jedes team hat -genau- eine basis
- eine basis ist definiert als eine zusammenhängende fläche von basisfeldern
- die welt ist torusförmig -> wenn 0,0 ein basis feld ist, 1,0 kein basisfeld ist, 99,0 ein basisfeld ist
bei einer 100x100 map handelt es sich um eine basis (also überlauf an den kartenrändern möglich(

nun fällt mir leider kein geeigneter algorithmus zu dem problem ein, der keine exponentielle laufzeit mit sich
bringen wüde.
hat jemand von euch so etwas ähnliches vlt schonmal gelöst und hat etwas code für mich ?
oder ne gute idee Smile

vielen dank im voraus !

	Kruemelator	So, Sep 06, 2009 17:34 Antworten mit Zitat
Code: [AUSKLAPPEN] [EINKLAPPEN] Dim map(99,99) For x=0 To 99 For y=0 To 99 If map(x,y) = 1 Then If map(x+1,y) = 1 And map(x,y+1) = 1 And map(x+1,y+1) = 1 Then ;Basis liegt in der Map Else If map(99,y) = 1 And map(x,y+1) = 1 And map(99,y+1) = 1 Then ;Basis auf senkrechtem Rand Else If map(x+1,y) = 1 And map(x,99) = 1 And map(x+1,99) = 1 Then ;Basis auf waargerechtem Rand Else If map(99,0) = 1 And map(0,99) = 1 And map(99,99) = 1 Then ;Basis auf der Eck Else ;Basis ist nicht vorhanden EndIf EndIf EndIf EndIf EndIf Next Next Sollte gehen Gruß Kruemelator

Kruemelator

So, Sep 06, 2009 17:34
Antworten mit Zitat

Code: [AUSKLAPPEN]

Dim map(99,99)

For x=0 To 99
For y=0 To 99
If map(x,y) = 1 Then
If map(x+1,y) = 1 And map(x,y+1) = 1 And map(x+1,y+1) = 1 Then
   ;Basis liegt in der Map
Else
   If map(99,y) = 1 And map(x,y+1) = 1 And map(99,y+1) = 1 Then
      ;Basis auf senkrechtem Rand
   Else
      If map(x+1,y) = 1 And map(x,99) = 1 And map(x+1,99) = 1 Then
         ;Basis auf waargerechtem Rand
      Else
         If map(99,0) = 1 And map(0,99) = 1 And map(99,99) = 1 Then
            ;Basis auf der Eck
         Else
            ;Basis ist nicht vorhanden
         EndIf
      EndIf
   EndIf
EndIf
EndIf
Next
Next

Sollte gehen

Gruß Kruemelator

	Hip Teen	So, Sep 06, 2009 19:56 Antworten mit Zitat
Öh, versteh ich es richtig, dass eine Basis aus mehreren Feldern bestehen kann? Dann würd ich es so machen: Du erstellst als erstes eine Kopie von dem Array Dann suchst du das erste Basisfeld in dem Array. Gibts keins, weißte schon dass die Map nicht in Ordnung ist. Wenn du eins gefunden hast, löschst du alle Basisfelder, die mit dem ersten Basisfeld verbunden sind. Wenn du fertig bist damit, suchst du das Array ab, ob noch so ein Basisfeld in dem Array vorhanden ist. Wenn ja, gibt es mehrere Basen. Wenn nicht, ist alles paletti. Laufzeit ist dann linear zur Mapgröße.
Spruch der Woche: "Ahh, ein neues Gesicht?!" - "Nein, das hab ich schon länger"

Hip Teen

So, Sep 06, 2009 19:56
Antworten mit Zitat

Öh, versteh ich es richtig, dass eine Basis aus mehreren Feldern bestehen kann?
Dann würd ich es so machen:
Du erstellst als erstes eine Kopie von dem Array
Dann suchst du das erste Basisfeld in dem Array. Gibts keins, weißte schon dass die Map nicht in Ordnung ist. Wenn du eins gefunden hast, löschst du alle Basisfelder, die mit dem ersten Basisfeld verbunden sind. Wenn du fertig bist damit, suchst du das Array ab, ob noch so ein Basisfeld in dem Array vorhanden ist. Wenn ja, gibt es mehrere Basen. Wenn nicht, ist alles paletti.
Laufzeit ist dann linear zur Mapgröße.

Spruch der Woche: "Ahh, ein neues Gesicht?!" - "Nein, das hab ich schon länger"

	BBPro2	Mo, Sep 07, 2009 15:33 Antworten mit Zitat
hi, @kruemel ich verstehe deinen ansatz zwar nicht ganz aber ich fürchte dass er auf keinen fall funktionieren wird. eine basis kann aus mehreren feldern bestehen. nach deinem ansatz wären 2 getrennte aber jeweils zusammenhängende flächen z.b. ebenfalls "ok", was sie aber nicht sind @hip der ansatz gefällt mir schon besser, hatte ne ähnliche idee das problem liegt in "mit dem 1. feld verbunden'" das ist nicht so einfach und zieht eine exponentielle laufzeit nach sich, da ich für jedes angrenzende feld wieder jedes angrenzende feld überprüfen muss. oder habe ich dich vlt falsch verstanden ? danke!

BBPro2

Mo, Sep 07, 2009 15:33
Antworten mit Zitat

hi,

@kruemel
ich verstehe deinen ansatz zwar nicht ganz aber ich fürchte dass er auf keinen fall funktionieren wird.
eine basis kann aus mehreren feldern bestehen.
nach deinem ansatz wären 2 getrennte aber jeweils zusammenhängende flächen z.b. ebenfalls "ok", was sie aber nicht sind

@hip
der ansatz gefällt mir schon besser, hatte ne ähnliche idee
das problem liegt in "mit dem 1. feld verbunden'"
das ist nicht so einfach und zieht eine exponentielle laufzeit nach sich, da ich für jedes angrenzende feld wieder jedes angrenzende feld überprüfen muss.
oder habe ich dich vlt falsch verstanden ?

danke!

	Philon	Mo, Sep 07, 2009 17:26 Antworten mit Zitat
hi! mach es am besten wie in der ersten Antwort beschreiben. So lange dauert das gar nicht, ein computer ist schneller als du denkst! außerdem wird das ganze ja nur einmal beim laden durchlaufen, da tuts nicht weh, wenn man eine halbe sekunde(?) warten muss. gruß kleiner_philip

Philon

Mo, Sep 07, 2009 17:26
Antworten mit Zitat

hi!

mach es am besten wie in der ersten Antwort beschreiben.

So lange dauert das gar nicht, ein computer ist schneller als du denkst!
außerdem wird das ganze ja nur einmal beim laden durchlaufen, da tuts nicht weh, wenn man eine halbe sekunde(?) warten muss.

gruß
kleiner_philip

	Hip Teen	Mo, Sep 07, 2009 18:46 Antworten mit Zitat
Zitat: So lange dauert das gar nicht, ein computer ist schneller als du denkst! Wenn du exponentielle Laufzeit hast, kann dein Computer der schnellste der Welt sein und er schafft die Berechnung ab einer bestimmten, gar nicht so großen, Mapgröße es nicht in der Zeit, in der das Universum existiert. So viel mal dazu. @BBPro2 Seh grad, hab meine Idee nicht so genau erklärt mit dem verbunden sein. Also, du hast jetzt das erste Feld gefunden. Jetzt gehst an die benachbarten Basisfelder und löscht diese. Das ganze machst du rekursiv und schon sind alle Felder gelöscht, die mit dem ersten verbunden sind. Da du jedes Feld nur einmal betrachtest (wichtig hier: Erst das Feld löschen und dann die Rekursion anwenden!), hast du eine lineare Laufzeit. Hoffe das ist jetzt verständlicher, wenn nicht kann ich auch noch etwas Pseudocode erstellen.
Spruch der Woche: "Ahh, ein neues Gesicht?!" - "Nein, das hab ich schon länger"

Hip Teen

Mo, Sep 07, 2009 18:46
Antworten mit Zitat

Zitat:

So lange dauert das gar nicht, ein computer ist schneller als du denkst!

Wenn du exponentielle Laufzeit hast, kann dein Computer der schnellste der Welt sein und er schafft die Berechnung ab einer bestimmten, gar nicht so großen, Mapgröße es nicht in der Zeit, in der das Universum existiert. So viel mal dazu.
@BBPro2
Seh grad, hab meine Idee nicht so genau erklärt mit dem verbunden sein. Also, du hast jetzt das erste Feld gefunden. Jetzt gehst an die benachbarten Basisfelder und löscht diese. Das ganze machst du rekursiv und schon sind alle Felder gelöscht, die mit dem ersten verbunden sind. Da du jedes Feld nur einmal betrachtest (wichtig hier: Erst das Feld löschen und dann die Rekursion anwenden!), hast du eine lineare Laufzeit. Hoffe das ist jetzt verständlicher, wenn nicht kann ich auch noch etwas Pseudocode erstellen.

Spruch der Woche: "Ahh, ein neues Gesicht?!" - "Nein, das hab ich schon länger"

	BBPro2	Mo, Sep 07, 2009 21:01 Antworten mit Zitat
Zitat: Wenn du exponentielle Laufzeit hast, kann dein Computer der schnellste der Welt sein und er schafft die Berechnung ab einer bestimmten, gar nicht so großen, Mapgröße es nicht in der Zeit, in der das Universum existiert. So viel mal dazu. yop kann ich nur zustimmen.. ich hab ne map die bis zu 1024x1024 groß werden kann. wenn ich jetzt für jedes feld anfange jedes andere feld zu überprüfen mit exponentieller laufzeit (und das wäre exponentielle laufzeit.) würde ich das ende der routine bei maximaler mapgröße nichtmal auf einem 20ghz computer miterleben (es sei denn ich würde rund 10^30 jahre alte oder so^^) 1brd mal >nichts< tun dauert übrigens 1 std auf meinem rechner (habs ausprobiert mit weniger und hochgerechnet) 1brd mal >if keydown(1) then end< dauert 10 std wie du siehst sind pcs gar nicht mal so schnell wie du dachtest edit: ok ich sehe grad "es geht sogar noch" es wären "nur" etwas über 1 billion aufrufe. je nachdem was in einem aufruf so passiert könnte es innerhalb weniger stunden oder tage vlt sogar schon fertig sein. bei einer etwas größeren map oder einem sehr zeitaufwendigen aufwand pro aufruf würde jedoch keiner von usn das ende miterleben Zitat: @BBPro2 Seh grad, hab meine Idee nicht so genau erklärt mit dem verbunden sein. Also, du hast jetzt das erste Feld gefunden. Jetzt gehst an die benachbarten Basisfelder und löscht diese. Das ganze machst du rekursiv und schon sind alle Felder gelöscht, die mit dem ersten verbunden sind. Da du jedes Feld nur einmal betrachtest (wichtig hier: Erst das Feld löschen und dann die Rekursion anwenden!), hast du eine lineare Laufzeit. Hoffe das ist jetzt verständlicher, wenn nicht kann ich auch noch etwas Pseudocode erstellen. vielen dank das sollte auf jeden fall helfen, wenn nicht melde ich mich nochmal. aber die idee ist auf jeden fall gut und müsste gut und effizient funktionieren. anstatt das array vorher jedoch zu kopieren werde ich versuchen es über ein 2. neues array zu lösen in dem ich einfach nur einzelne bits setze für "gelöscht" und "nich gelöscht". so spar ich mir das rüberkopieren (immerhin > 1 mio einträge bei 1024x1024) und komme mit bit arrays statt byte arrays aus (im prinzip egal, da das array danach ohnehin redundant wird, aber besser ists trotzdem) verfügt blitz basic eigentlich über eine automatische speicherbereinigung ? wenn ja - zur laufzeit oder erst nach beendigung des programms ? vielen dank !

BBPro2

Mo, Sep 07, 2009 21:01
Antworten mit Zitat

Zitat:

yop kann ich nur zustimmen.. ich hab ne map die bis zu 1024x1024 groß werden kann.
wenn ich jetzt für jedes feld anfange jedes andere feld zu überprüfen mit exponentieller laufzeit (und das wäre exponentielle laufzeit.) würde ich das ende der routine bei maximaler mapgröße nichtmal auf einem 20ghz computer miterleben (es sei denn ich würde rund 10^30 jahre alte oder so^^)
1brd mal >nichts< tun dauert übrigens 1 std auf meinem rechner (habs ausprobiert mit weniger und hochgerechnet)
1brd mal >if keydown(1) then end< dauert 10 std
wie du siehst sind pcs gar nicht mal so schnell wie du dachtest Wink

edit:
ok ich sehe grad "es geht sogar noch"
es wären "nur" etwas über 1 billion aufrufe. je nachdem was in einem aufruf so passiert könnte es innerhalb weniger stunden oder tage vlt sogar schon fertig sein.
bei einer etwas größeren map oder einem sehr zeitaufwendigen aufwand pro aufruf würde jedoch keiner von usn das ende miterleben Smile

Zitat:

@BBPro2
Seh grad, hab meine Idee nicht so genau erklärt mit dem verbunden sein. Also, du hast jetzt das erste Feld gefunden. Jetzt gehst an die benachbarten Basisfelder und löscht diese. Das ganze machst du rekursiv und schon sind alle Felder gelöscht, die mit dem ersten verbunden sind. Da du jedes Feld nur einmal betrachtest (wichtig hier: Erst das Feld löschen und dann die Rekursion anwenden!), hast du eine lineare Laufzeit. Hoffe das ist jetzt verständlicher, wenn nicht kann ich auch noch etwas Pseudocode erstellen.

vielen dank das sollte auf jeden fall helfen, wenn nicht melde ich mich nochmal.
aber die idee ist auf jeden fall gut und müsste gut und effizient funktionieren.

anstatt das array vorher jedoch zu kopieren werde ich versuchen es über ein 2. neues array zu lösen in dem ich einfach nur einzelne bits setze für "gelöscht" und "nich gelöscht".
so spar ich mir das rüberkopieren (immerhin > 1 mio einträge bei 1024x1024) und komme mit bit arrays statt byte arrays aus (im prinzip egal, da das array danach ohnehin redundant wird, aber besser ists trotzdem)
verfügt blitz basic eigentlich über eine automatische speicherbereinigung ?
wenn ja - zur laufzeit oder erst nach beendigung des programms ?

vielen dank !

	Kruemelator	Di, Sep 08, 2009 20:52 Antworten mit Zitat
Ich weis jetzt nicht was du damit meinst: Zitat: nach deinem ansatz wären 2 getrennte aber jeweils zusammenhängende flächen z.b. ebenfalls "ok", was sie aber nicht sind Um das Prüfen von allen Feldern kommt man nicht rum. @Hip Teen Wir haben eigendlich das selbe: Also ich würde auch nicht die ganze Map abspeichern, sondern nur Koordinaten der Basen etc.

Kruemelator

Di, Sep 08, 2009 20:52
Antworten mit Zitat

Ich weis jetzt nicht was du damit meinst:
Zitat:

nach deinem ansatz wären 2 getrennte aber jeweils zusammenhängende flächen z.b. ebenfalls "ok", was sie aber nicht sind

Um das Prüfen von allen Feldern kommt man nicht rum.

@Hip Teen
Wir haben eigendlich das selbe:

Also ich würde auch nicht die ganze Map abspeichern, sondern nur Koordinaten der Basen etc.

	Hip Teen	Mi, Sep 09, 2009 1:42 Antworten mit Zitat
Kruemelator, ganz ehrlich, dein Code macht nicht viel sinnvolles. Mir ist zwar klar, dass der nur die grobe Struktur vorgeben soll, aber in deinem Code kann ich ehrlich gesagt weder eine Ähnlichkeit zu meiner Idee erkennen, noch eine Idee, die auch nur annähernd das Problem löst. Dein Code stellt nur für jedes einzelne Feld fest, in welchem Bereich ein bestimmtes Feld liegt, wenn es denn ein Basisfeld ist. Und weiter? Du musst die Informationen für jedes einzelne Feld verknüpfen, sonst macht deine Code ja nichts sinnvolles. Aber egal, BBpro2 scheint ja das Problem soweit gelöst zu haben.
Spruch der Woche: "Ahh, ein neues Gesicht?!" - "Nein, das hab ich schon länger"

Hip Teen

Mi, Sep 09, 2009 1:42
Antworten mit Zitat

Kruemelator, ganz ehrlich, dein Code macht nicht viel sinnvolles. Mir ist zwar klar, dass der nur die grobe Struktur vorgeben soll, aber in deinem Code kann ich ehrlich gesagt weder eine Ähnlichkeit zu meiner Idee erkennen, noch eine Idee, die auch nur annähernd das Problem löst. Dein Code stellt nur für jedes einzelne Feld fest, in welchem Bereich ein bestimmtes Feld liegt, wenn es denn ein Basisfeld ist. Und weiter? Du musst die Informationen für jedes einzelne Feld verknüpfen, sonst macht deine Code ja nichts sinnvolles.
Aber egal, BBpro2 scheint ja das Problem soweit gelöst zu haben.

Spruch der Woche: "Ahh, ein neues Gesicht?!" - "Nein, das hab ich schon länger"

	Kruemelator	Mi, Sep 09, 2009 13:49 Antworten mit Zitat
Zitat: durch in teamfarbe gefärbte felder Wäre: Code: [AUSKLAPPEN] [EINKLAPPEN] If map(x,y) = 1 Then ... müsste er anpassen. Vielleicht mit Select. Zitat: - jedes team hat -genau- eine basis wird er woll selber schaffen Zitat: - eine basis ist definiert als eine zusammenhängende fläche von basisfeldern - die welt ist torusförmig -> wenn 0,0 ein basis feld ist, 1,0 kein basisfeld ist, 99,0 ein basisfeld ist Hab ich drin: Code: [AUSKLAPPEN] [EINKLAPPEN] If map(x+1,y) = 1 And map(x,y+1) = 1 And map(x+1,y+1) = 1 Then ;Basis liegt in der Map Else If map(99,y) = 1 And map(x,y+1) = 1 And map(99,y+1) = 1 Then ;Basis auf senkrechtem Rand Else If map(x+1,y) = 1 And map(x,99) = 1 And map(x+1,99) = 1 Then ;Basis auf waargerechtem Rand Else If map(99,0) = 1 And map(0,99) = 1 And map(99,99) = 1 Then ;Basis auf der Eck Else ;Basis ist nicht vorhanden EndIf EndIf EndIf EndIf @Hip Teen Aber das unsere Idee nicht gleich sind, da hast du doch Recht, hatte es so verstanden das bei dir das komplette Array mehrmals nach Basen durchsucht wird, wäre bei meinem Code dann aber nicht. @BBPro2 Du schriebst das du das in einer Datei gespeichert hast, wolltest du prüfen ob die Map in Ordnung ist bevor du sie überhaupt lädst? Gruß Kruemelator

Kruemelator

Mi, Sep 09, 2009 13:49
Antworten mit Zitat

Zitat:

durch in teamfarbe gefärbte felder

Wäre:
Code: [AUSKLAPPEN]

If map(x,y) = 1 Then ...

müsste er anpassen. Vielleicht mit Select.

Zitat:

- jedes team hat -genau- eine basis

wird er woll selber schaffen

Zitat:

- eine basis ist definiert als eine zusammenhängende fläche von basisfeldern
- die welt ist torusförmig -> wenn 0,0 ein basis feld ist, 1,0 kein basisfeld ist, 99,0 ein basisfeld ist

Hab ich drin:
Code: [AUSKLAPPEN]

If map(x+1,y) = 1 And map(x,y+1) = 1 And map(x+1,y+1) = 1 Then
;Basis liegt in der Map
Else
If map(99,y) = 1 And map(x,y+1) = 1 And map(99,y+1) = 1 Then
;Basis auf senkrechtem Rand
Else
If map(x+1,y) = 1 And map(x,99) = 1 And map(x+1,99) = 1 Then
;Basis auf waargerechtem Rand
Else
If map(99,0) = 1 And map(0,99) = 1 And map(99,99) = 1 Then
;Basis auf der Eck
Else
;Basis ist nicht vorhanden
EndIf
EndIf
EndIf
EndIf

@Hip Teen
Aber das unsere Idee nicht gleich sind, da hast du doch Recht, hatte es so verstanden das bei dir das komplette Array mehrmals nach Basen durchsucht wird, wäre bei meinem Code dann aber nicht.

@BBPro2
Du schriebst das du das in einer Datei gespeichert hast, wolltest du prüfen ob die Map in Ordnung ist bevor du sie überhaupt lädst?

Gruß Kruemelator

	BBPro2	Mi, Sep 09, 2009 18:55 Antworten mit Zitat
hi @kruemel nein dein code funktioniert nicht, da du die aufgabe falsch verstanden hast glaube ich ein feld in der map kann ein basisfeld sein dies sei dargstellt durch eine 1 für team 1, bzw eine 2 für team 2 etc eine basis ist nun eine zusammenhängende fläche aus diesen feldern beispiel: ...1111... ...1111... .............. ....222.... wäre gültig. team 1 hätte eine 8feld-basis, team 2 eine 3feld-basis dein code überprüft dies leider nicht im übrigen sind solche if-konstrukte eigentlich nie eine saubere lösung, sondern furchtbarer spaghetti-code. auch select-statements sind, zwar nicht ganz so krass wie if, aber trotzdem, furchtbar. und nein, ich lade zuerst die map ein und überprüfe dann ob es eine korrekte map ist. ander lässt sich das problem vermutlich kaum lösen, fürchte ich. trotzdem vielen dank für eure hilfe, gelöst hab ichs jetzt wie hip teen gesagt hat nur mit der bereits erwähnten änderung.

BBPro2

Mi, Sep 09, 2009 18:55
Antworten mit Zitat

hi

@kruemel
nein dein code funktioniert nicht, da du die aufgabe falsch verstanden hast glaube ich
ein feld in der map kann ein basisfeld sein
dies sei dargstellt durch eine 1 für team 1, bzw eine 2 für team 2 etc
eine basis ist nun eine zusammenhängende fläche aus diesen feldern
beispiel:
...1111...
...1111...
..............
....222.... wäre gültig. team 1 hätte eine 8feld-basis, team 2 eine 3feld-basis

dein code überprüft dies leider nicht

im übrigen sind solche if-konstrukte eigentlich nie eine saubere lösung, sondern furchtbarer spaghetti-code.
auch select-statements sind, zwar nicht ganz so krass wie if, aber trotzdem, furchtbar.

und nein, ich lade zuerst die map ein und überprüfe dann ob es eine korrekte map ist.
ander lässt sich das problem vermutlich kaum lösen, fürchte ich.

trotzdem vielen dank für eure hilfe,
gelöst hab ichs jetzt wie hip teen gesagt hat nur mit der bereits erwähnten änderung.

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Zusammenhängende Flächen

Betreff: Zusammenhängende Flächen