Strategie-Spiel, Nachbarländer

[Cicaro]

Hallo !

Ich programmier' gerad' ein Strategie-Spiel, bei dem ich mir eine Karte mit verschiedenen Ländern erstelle.
Folgendes ist dabei wichtig:
- ich verwende 2 Klassen, TMap und TLand
- TMap beinhaltet alle TLand-Instanzen
- in TMap kann ich herausfinden, zu welchem Land ein Bereich auf der Karte gehört

Nun möchte ich durch Zeiger (in TLand) benachbarte Länder zu dem jeweiligen Land registrieren.
Jetzt will ich wissen, wie ich ich dies am besten anstelle ?

Daneben würd' ich gern auch wissen, wie ich am besten jedes einzelne Land von sich aus zeichnen kann statt in TMap alle Bereiche ohne Rücksicht auf die TLand-Instanzen zu zeichnen ?

[Airblader]

Ohne viel von Pointeren / Klassen zu wissen sage ich mal:

Wie speicherst du denn die Instanzen der Länder in TMap?
Hast du alle in einem oder irgendwie in bspw. einem 2D-Array?

Wenn es kein 2D-Array ist, sollte man wissen, wieviele TLand nebeneinander dargestellt werden.

Ist es ein 2D-Array dann müsste es so sein:

Array[X][Y] sei die Position des MittelFelder.
Die Nachbarländer sind dann:

Zitat:

Links oben:
[X-1][Y-1]

Mitte oben:
[X][Y-1]

Rechts oben:
[X+1][Y-1]

Links:
[X-1][Y]

Rechts:
[X+1][Y]

Links unten:
[X-1][Y+1]

Mitte unten:
[X][Y+1]

Rechts unten:
[X+1][Y+1]

Natürlich müsstest du prüfen, ob X = 0 oder MaxWert bzw. Y = 0 oder MaxWert ist, da du sonst ja auf ein Fekd zugreifst, dass nicht existiert.

Hoffe, dich überhaupt richtig verstanden zu haben ;)

[Cicaro]

Also meine TMap enthält einen 2D-Array mit einzelnen Felder, die zu einem bestimmten Land gehören. Problematisch ist hierbei, dass diese Felder unabhängig davon, wo das Zentrum des Landes (in TLand angegeben) sich befindet, sind. Sie könnten einzeln irgendwo liegen.
Das versuche ich in den Griff zu kriegen.

Delphi-Quellcode:

TLand = class
  Center:TPoint;
  // andere benötigte Länderinfos
end;

TMap = class
  Land:array of TLand;
  Field:array of array of Integer;
  // ...
end;

Und wenn ich die Karte zeichnen will muss ich bis jetzt immer auf diese Felder zurückgreifen und mit zwei for-Schleifen jedes Feld einzeln zeichnen. Dabei bleibt mir nichts anderes übrig als verschiedenfarbige Rechtecke zu zeichnen.

[edit]

@Airblader:
Nach deinem Vorschlag kann ich also die Grenzen zwischen den Ländern ermitteln, wobei zunächst nur die 4 NOSW-Richtungen von Bedeutung sind. Ich dachte mir, ich erstelle einen Array in TLand mit Zeigern auf alle benachbarten Länder. So müsste das soweit klappen.
Doch das eigentliche Problem ist, dass einige Länder bestimmte Eigenschaften verlieren und nicht mehr als Nachbarn gelten dürfen (z.B.: ein Gegner hat das Land erobert). Jetzt müsste man irgendwie herausfinden können, ob ein weit entferntes Land vom aktuellen erreicht werden kann. Denn eigene Länder könnten eine Kette bilden und so zu dem Land führen.

Meine erste Idee dazu war, dass ich meine Methoden mit noch mehr for-Schleifen schmücke. Allerdings ist dieser Weg bezüglich der Rechenzeit inakzeptabel !
Was jetzt ?

[/edit]

[Cicaro]

Zum Thema Zeichnen der einzelnen Felder hier ein Screenshot.
Ich wäre dankbar, wenn mir jemand seine Ideen mitteilt, wie man die Ecken der Felder abrunden könnte.
Diese sind in einem schlichten 2D-Array verpackt.

[Lukaro]

Du könntest doch gucken, ob an dem aktuellen Feld Land ist oder nicht.
Wenn kein Land dann eventuell abgerundete Bilder einfügen oder selber zeichnen.
Möglicherweise hilft auch eine Linie, die von den Eckpunkten der Nachbarfelder gezogen wird.

Viel Erfolg noch!
Lukaro

[Khabarakh]

Erstmal: Nimm für "Land" eine TObjectList. Die Nachbarländer würde ich auch in eine TObjectList einfügen, natürlich AOwnsObjects = false.
Zum Abrunden: Ist wahrscheinlich übertrieben, aber ein Subdivision Surfaces-Algorithmus sollte gute Ergebnisse bringen :wink: .

[Cicaro]

Zitat:

Zitat von Khabarakh

Erstmal: Nimm für "Land" eine TObjectList. Die Nachbarländer würde ich auch in eine TObjectList einfügen, natürlich AOwnsObjects = false.

Mein Problem ist eigentlich der Nachbarländer-Such-Algorithmus selbst. Zuerst hab' ich einfach jedes Feld meiner Arrays überprüft, ob diese an einer Grenze liegen. Dabei benötigt man 2 For-Schleifen (Screenshot-Beispiel: 80x60) + Überprüfungscode. Damit hat man aber nur die unmittelbaren Nachbarländer ermittelt. Ich will aber ein weit entferntes Land, das noch über andere Nachbarländer (also über eine Kette von solchen) mit dem aktuellen verbunden ist. Wenn alle Länder der Kette einem bestimmten Spieler angehören, kann der Spieler aus dem aktuellen Land in das 'weit entfernte' reisen. Ist die Kette gerissen ( sprich ein Land aus der Kette gehört dem gegnerischen Spieler ), dann kann man aus dem aktuellen Land nicht in das 'wei entfernte'.

Wenn ich also die 2 for-Schleifen in weitere for-Schleifen lege, dauert die Berechnung dieser Kette Minuten. Es soll aber kaum eine Sekunde Berechnungszeit benötigen.
Da dachte ich mir Berechne für jedes Land die unmittelbaren Nachbarn zur OnCreate-Zeit und zur Spiel-Zeit müsste das irgendwie über Zeiger ablaufen. Doch wie ?

[negaH]

Ist doch relativ einfach :)

Du hast deinen 2 Schleifen Algortihmus, korrekt ?
Du benötigst noch in jedem TLand Objekt eine Liste von TLand Objekten, nennen wir sie mal "NachbarLaender". In deiner Suchschleife erkennst du nun den Fall das du auf ein Grenz-Kästchen gestoßen bist. In diesem Moment hast du ermittelt welches TLand auf ein anderes trifft. In beiden "NachbarLaender" Listen dieser beiden TLand Objekte fügst du nun wechselseitig das jeweils angenzende TLand ein, aber nur wenn es noch nicht eingetragen wurde.
Am Ende deiner Suchschleife hast du nun zu jedem TLand in dessen "NachbarLaender" Liste eine Verlinkung auf alle angrenzenden Länder.

Gruß Hagen

[Cicaro]

So weit bin ich ja auch schon, aber

Zitat:

Ich will aber ein weit entferntes Land, das noch über andere Nachbarländer (also über eine Kette von solchen) mit dem aktuellen verbunden ist. Wenn alle Länder der Kette einem bestimmten Spieler angehören, kann der Spieler aus dem aktuellen Land in das 'weit entfernte' reisen. Ist die Kette gerissen ( sprich ein Land aus der Kette gehört dem gegnerischen Spieler ), dann kann man aus dem aktuellen Land nicht in das 'wei entfernte'.

// Rechtschreibfehler !

Das hier muss ich noch mit einem möglichst geringen Speicherplatz- und Zeitverbrauch realisieren. :gruebel:

[Ruppi]

Wenn du weißt welches land welche Nachbarländer hat, dann kannst du jedem land je einen Pointer auf jedes der Nachbarländer geben.
Dann fütterst du einen Wegsuchalgorithmus (vgl A*) mit den kanten Knoten und der puckt dann geschwind aus ob es eine Verbundung gibt oder nicht. wenn du nicht die schnellste verbindung suchst dann reicht auch ein einfacherer WegSuchAlgo.

mfg Ruppi

pS : wird das ein Risikoklon? Klingt so ... von wegen reisen etc...

[negaH]

A* brauchst du nicht, du benötigst noch nichtmal einen Suchalgorithmus sondern nur die richtigen Datenstrukturen.

Also oben erklärte ich dir wie du die Map=TLand->TNachbarlisten Objekte zum start des Spieles initialisierst.
Mehrere zusammenhängende Länder die EIN Spieler erobert hat verhalten sich technisch gesehen wie EIN Land. Erobert ein Spieler ein Land so wird es sehr wahrscheinlich eines der Nachbarländer sein das vorher nicht diesem Spieler gehört hat. In dem Moment wo ein Spieler ein neues Nachbarland sein eigen nennt vermischst du einfach die TNachbarländerListen des eroberten Landes mit allen Listen der schon angrenzenden Ländern, fertig. Denn wenn dieser Spieler ALLE Länder erobert hat so enthalten ALLE Länder in ihren TNachbarländerListen automatisch alle anderen Länder, also alle die direkt erreichbar sind. Denk mal drüber nach und zeichne es dir auf.

Jedes TLand hat eine Liste mit TNachbarländern, fest initialisiert um die Original Map zu erhalten.
Jedes TLand hat eine Liste mit TEroberteNachbarländern die dem Spieler gehören.
Erobert ein Spieler ein TLand so wird die Liste der TEroberteNachbarländer des eroberten TLands und aller angrenzenden eroberten TLand Objekten geupdatet.

Somit steht zb. im TLand(A).TEroberteNachbarländer autom. das TLand(Z) falls es eine direkte Landbrücke gibt.

Du kanst aber auch recht simpel einen "Suchalgo." schreiben. Möchtest du wissen ob ein Spieler von TLand(A) nach TLand(Z) reisen kann so beginnst du die TNachbarLänderList von TLand(A) rekursiv zu durchsuchen. Alle dort eingetragenen Nachbarländer die ebenfalls diesem Spieler gehören werden durch die Rekursive Suche ebenfalls durchsucht. Die Abbruchbedingung der Rekursiven Suche ist entweder TLand(A) oder TLand(Z). Trifft man auf TLand(Z) so gibt es eine Landbrücke, trifft man auf TLand(A) so ist man fertig mit der Suche. Allerdings kann eine solche Suche bei sehr vielen Ländern und Mitspielern schon ziemlich zeitaufwendig werden. Natürlich sind Maps mit 100 Ländern noch kein Problem.

Ein dritter Algorithmus verwaltet zu jedem Spieler eine Liste der eroberten Ländern. Willst du von TLand(A) nach TLand(Z) so müssen diese Länder zwangsweise auch in der Liste TEroberteLänder enthalten sein, logisch. Nun durchsuchst du die TNachbarländerListe von TLand(A) nach einem Land das in TEroberteLänder enthalten ist. Sollte es keines geben so gibt es keinen Weg nach TLand(Z). Sollte es eines geben so durchsuchst du nun rekursiv mit der gleichen Methode dessen TNachbarländerListe(). Dabei wird TLand(A) logischerweise ignoriert und trifft man dort auf TLand(Z) so gibt es eine Landbrücke zwischen A und Z. Diese Landbrücke ist sogar durch die Rekursion nachvollziehbar.

Ich würde denoch den Weg der "richtigen" Datenstrukturen gehen und direkt bei der Eroberung/Änderung der Map die Liste der erreichbaren Nachbarländer jedes Spielers und Land updaten.

Du hast also verschiedene Möglichkeiten: entweder Speed = mehr Speicher, oder höhere Komplexität in der Suche = weniger Speicher.

Gruß Hagen