Algorithmus 'Insel(n) im Meer'

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo Community

gegeben ist ein beliebig großes, zweidimensionales Array „map(x, y)“ vom Typ „Zahl“ (integer o.ä.). Dieses Array soll eine Seekarte darstellen, wobei folgende Zahlenwerte relevant sind:
0 - an der Koordinate ist Meer
1 - an der Koordinate ist Land

Ich suche nun einen Algorithmus (oder ein fertiges Tool, welches einen ASCII-Output erzeugen kann, in dem nur zwei Werte vorkommen), der solche eine Karte „per Random“ erzeugt, sprich: das Array mit Wasser füllt (0 setzt) und dann zufällig geformte Inseln an zufälligen Positionen setzt.

Ich hoffe, Ihr habt geistreiche und hilfreiche Kommentare dazu :smile:)

Liebe Grüsse

#2

Hi,

also, ein Algorithmus dafür ist wirklich trivial:

Du brauchst zwei geschachtelte Schleifen, wobei eine die Spalten im Array abzählt und die andere die Zeilen. Dann prüft man, ob im Array an der aktuellen Zeile/Spalte eine 0 steht oder eine 1 und gibt an der aktuellen Zeile/Spalte auf dem Ausgabegerät das gewünschte Zeichen aus.

In Pseudocode könnte das so aussehen:

for zeile = 1 to N\_zeilen {
 for spalte = 1 to N\_spalten {
 if map[spalte, zeile] == 0 then {
 Ausgabe(spalte, zeile, "X")
 } else {
 Ausgabe(spalte, zeile, " ")
 }
 }
}

N_zeilen und N_spalten sind die Anzahl Zeilen und Spalten, die dein Array hat. Die Funktion „Ausgabe“ steht für eine Funktion, welche an einer x- und y-Koordinate einen Text ausgibt.

LG
Jochen

#3

hallo mindshape,

nun … eigentlich ist ja alles wasser :smile:)
also braucht es „nur“ die anzahl und koordinaten der inseln und größe der karte ( x und y)

var x=200
var y=200
var anzahl=5

var x\_kor = new Array(anzahl)
var y\_kor = new Array(anzahl)


for (var i = 1; i \< anzahl; i++){
 var nr=Math.round(Math.random() \* x) + 1;
 x\_kor[i] = nr

 var nr=Math.round(Math.random() \* y) + 1;
 y\_kor[i] = nr
}


var inseln ="Insel-Koordinaten: \<br\> ";

for (var i = 1; i \< anzahl; i++){
inseln=inseln + i+". Insel = x:" + x\_kor[i] +" y:"+ y\_kor[i] +"\<br\>"
}

document.write(inseln)

gruß
klaus

#4

Hallo,

also die Ausgabe lässt sich wirklich recht einfach bewältigen, wie dir im anderen Beitrag berreits gezeigt wurde. Das generieren der Landschaft ist natürlich etwas komplizierter.

Einfach das Array zu durchlaufen und den Zufall entscheiden zu lassen, wann eine 1 oder eine 0 gesetzt wird finde ich nicht sehr ansehlich.

Ich würde mir abhängig von der Größe der Karte eine Zufallszahl generieren lassen, die die Anzahl der Inseln angibt. Dann würde ich für jede Insel (als kreisförmig angenommen) den Radius ebenfalls durch Zufall generieren. Als letztes noch zufällig die Position der Inseln auf der Karte und dann kannst du alle Inseln in deinem Array eintragen.

Unterschiedliche Formen ergeben sich dann dadurch, dass ein paar Inseln sich überlappen werden. Andernfalls könntest du auch alternative Formen für die Inseln vorgeben und die Form auch per Zufall auswählen lassen.

Dann hätte ich noch eine Idee für ein Verfahrens der wirklich zufällige Formen erzeugt. Dazu einfach zufällige Punkte auf deiner Karte generieren und diese durch Linien verbinden. Wenn die Form geschlossen ist dann auch das innere ausfüllen. Das ist allerdings etwas komplizierter.
Man könnte hier auch die größe der Insel eindämmen. Der Code für die umsetzung in das ASCII-Array ist sicherlich etwas komplizierter aber bestimmt machbar.

In welcher Sprache bräuchtest du es denn?

MfG IGnow

#5

Ich würde mir abhängig von der Größe der Karte eine
Zufallszahl generieren lassen, die die Anzahl der Inseln
angibt. Dann würde ich für jede Insel (als kreisförmig
angenommen) den Radius ebenfalls durch Zufall generieren. Als
letztes noch zufällig die Position der Inseln auf der Karte
und dann kannst du alle Inseln in deinem Array eintragen.

Unterschiedliche Formen ergeben sich dann dadurch, dass ein
paar Inseln sich überlappen werden. Andernfalls könntest du
auch alternative Formen für die Inseln vorgeben und die Form
auch per Zufall auswählen lassen.
In welcher Sprache bräuchtest du es denn?

Ich hab das mal in MS SmallBasic gemacht.

GraphicsWindow.BackgroundColor = "Aqua"
GraphicsWindow.Show()
GraphicsWindow.Title = "Inseln im Meer"
GraphicsWindow.Width = 1280
GraphicsWindow.Height = 1024
GraphicsWindow.MouseDown = Zeichnen

Sub Zeichnen
 GraphicsWindow.Clear()
 i = 0
 While i 
Und hier in VB.NET(ist nur der Code konvertiert)


    
    Module Inseln\_im\_MeerModule
     Dim i, n, h, w, m As Primitive
     Sub Main()
     GraphicsWindow.BackgroundColor = "Aqua"
     GraphicsWindow.Show()
     GraphicsWindow.Title = "Inseln im Meer"
     GraphicsWindow.Width = 1280
     GraphicsWindow.Height = 1024
     AddHandler GraphicsWindow.MouseDown, AddressOf Zeichnen
    
     End Sub
     Sub Zeichnen()
     GraphicsWindow.Clear()
     i = 0
     While i 
    Lg der einzigware
#6

Hallo!

Eine andere Möglichkeit dafür wäre, Perlin-Noise zu verwenden. Hier ein Beispiel, das das Resultat in einer Textbox ausgibt. Je nach Kartengröße dauert die Berechnung aber sehr lange (die 50x50-Karte im Beispiel dauert bei mir etwa 4 Sekunden, aber das Ergebnis ist doch ganz gut.

Public Class Form1
 Const W As Integer = 50
 Const H As Integer = 50
 Dim arrStatic(W, H) As Single

 Private Sub Form1\_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
 Randomize()
 For x As Integer = 0 To W
 For y As Integer = 0 To H
 arrStatic(x, y) = Rnd()
 Next
 Next
 For x As Integer = 0 To W
 For y As Integer = 0 To H
 TextBox1.Text = TextBox1.Text & IIf(GetNoise(x, y) 
Die Ausgabe kannst du modifizieren, indem du einerseits die Gewichtungen in der Noise()-Funktion anpasst (aber aufpassen, dass insgesamt eine 1 rauskommt) oder die Konstante in der IIf-Anweisung änderst.

Nico