Strategie-Spiel, Nachbarländer

[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