Berechnung der Nachbarländer

[Guest]

Hallo!

Ich will so eine Art Spiel wie Risiko machen. Jetzt bin ich gerade dabei die Nachbarländer zu berechnen. Es sollte möglichst schnell und einfach zu implementieren sein. Über bessere Algorithmen, etc. kann ich mir ja nachher noch mehr gedanken machen.

Ich hätte mir gedacht, ob folgendes vielleicht möglich wäre.

Ich speichere mir in irgendeiner Collection für jedes Land, seine Nachbarländer. Wenn ich die Nachbarn brauche, dann frag ich einfach die Länder in der Collection ab.

Ist das zu realisieren, oder sollte ich da etwas anderes nehmen?

mfg,
Christian.

 

[Campino]

natürlich ist das zu realisieren, nur arbit is es...

 

[Guest]

Jetzt bin ich gerade dabei die Nachbarländer zu berechnen.

hm... "berechnest" oder hardcodest du?

ein Array tuts doch auch pro Land statt einer Collection, oder?
ich hab das "brerechnen" so gemacht: für jeden Pixel des Landes [Grenzbreite] Pixel in alle Richtungen geschaut, ob ich auf einem anderen Land lande. Das dauert zwar ein paar Millisekunden, muss man aber ja nur einmal machen.

 

[Verraffer]

Kannst Du genauer beschreiben was Du brauchst?

Du willst zu jedem Land, in dem Du dich gerade befindest, eine Lste seiner Nachnarn erhalten? Habe ich jetzt so richtig verstanden? Bzw. verstehe ich nicht wie man Nachbarländer "berechnet".

 

[SBehnen27]

wie wärs denn mit ner matrix?
gibts einfach jedem land ne id und in die Matrix schreibste dann deine länder rein. dann musste jeweils nur den angrenzenden Index anschaun: (Da Länder nicht alle gleich gross sind und versch. formen haben, bekommt nicht jedes land nur eine pos im array, sondern ggf. mehrere. so kann man auch schön die karte "darstellen")

1 - 1 - 2 - 3 - 4 - 5
1 - 2 - 2 - 2 - 4 - 6
7 - 7 - 8 - 9 - 9 - 9


wenn du nu wissen willst, an welches land das lad 1 angrenzt, schaust du einfach, wo überall die 1 steht und guckst dann nach, welche da angrenzen. in diesem fall wärs dann ja die 2 und die 7.

hoffe, ich hab das prob richtig verstanden.
das würde ich als eine lösung mit relativ wenig aufwand bezeichnen.

 

[Hansdampf]

wenn du nu wissen willst, an welches land das lad 1 angrenzt, schaust du einfach

naja, das einfach schauen ist dann gar nicht so einfach. Das einfachste ist ein Array vom Typ Land[] pro Land, dann kann man sich bequem durchhangeln. Am schnellsten isses auch.
Dazu noch eine globale Enfernungsmatrix/Erreichbarkeitsmatrix einmal berechnen und man hat alles, was man braucht.

 

[Sanix]

Wenn man so Länder wie die Schweiz hat, wie findet man dann die einzelnen Pixel des Randes, der Schweiz aus? Also jede Position eines Punktes der auf dem Umfang liegt.

 

[Hansdampf]

prüfe, ob links, rechts, oben und unten von jedem Pixel auch noch Schweiz ist. Falls nicht -> Pixel ist Grenzland. Ich verstehe aber nicht, wozu man so eine Liste verwenden könnte.

 

[Sanix]

um die Nachbarländer zu prüfen

 

[Hansdampf]

aber bei dem Prozess, diese Pixel zu bestimmen, bekommst Du doch schon die Nachbarländer. Wozu brauchst Du dann noch so eine Liste?

 

[Sanix]

sorry ich kapiere deine Frage nicht ganz, sagen wir Mal wir listen 20 Länder beliebig an. Jetzt will ich wissen von welchen Ländern Land 10 umgeben ist.

 

[Hansdampf]

kopiert von oben:

ich hab das "brerechnen" so gemacht: für jeden Pixel des Landes [Grenzbreite] Pixel in alle Richtungen geschaut, ob ich auf einem anderen Land lande. Das dauert zwar ein paar Millisekunden, muss man aber ja nur einmal machen.

bei [lande auf neuem Land]-> ist Land schon in Liste? ja-> weiter; nein-> tus rein

dazu musst Du natürlich wissen, welche LandID ein Pixel hat.

 

[Gast]

Das geht ganz einfach mit Graphentheorie...
Ein gerichteter Graph für die Länder ...
Verbinde darin die Länder die verbunden sind...
Mach dir für den Graphen eine Linked List anstelle von Arrays
(sin unbegrenz füllbar)
Den Rest machst du mit Tiefensuche und Breitensuche