Algorithmus für Längste Handelsstrasse bei Siedler

[¦square²¦]

Hi,

wir müssen gerade ein kleines Spiel programmieren und das wird eine Abwandlung von die Siedler von Catan. Wie prüfe ich welcher Spieler die längste Handelsstrasse hat. Möchte gar nicht den Quellcode wiissen, sondern den Ablauf wie ich bei jedem Spieler die längste Handelsstrasse herausfinde.
Das Spielbrett besteht aus Sechsecken, somit können sechs Strassen an ein Spielfeldteil angelegt werden. Das schwierige ist eventuelle Abzweigungen von einer Strasse zu berücksichtigen. Da dadurch wieder mehrere mögliche Handelsstrassen entstehen. Das Spiel muß in Lingo programmiert werden, falls einer davon Ahnung hat.
Hoffe es ist einigermaßen verständlich. Vielen Dank

MfG

 

[Green Mamba]

Ich würde nicht die Sechsecke verwalten, sondern sozusagen die Knotenpunkte. Das ganze ist ja verallgemeinert ein Netz, oder auch Graph genannt. Wenn du jetzt alle Knotenpunkte auf der einen Achse einer zweidimensionalen Matrix abträgst, und das gleiche nochmal auf der anderen, dann kannst du alle Einzelstrassen in dieser Matrix auf den Zeilen, bzw. Spalten (die Treffpunkte der Zeilen und Spalten) eintragen. Soviel nur mal dazu wie ich diese Daten speicher würde.
Zu Graphenproblemen gibts etliche alte Algorithmen zu allen möglichen Problemen. Ich denke auch nicht dass es mit dem Graphen sehr schwer sein dürfte einen Brute-Force-Algorithmus zu entwickeln, der einfach alle möglichen Strassen abfährt, und dadurch herausfindet welche die längste ist.

 

[¦square²¦]

Thx a lot Green Mamba.

MfG

 

[Boron]

Mein Stichwort an dich wäre dabei: Backtracking.

Die Idee ist dabei, dass du ein Strasse von einem Knotenpunkt zum nächsten baust. Wenn du an einen Kreuzungspunkt kommst, wo du keine Strasse bauen kannst, dann gehst du wieder zur vorherigen Kreuzung zurück, und probierst in einer anderen Richtung eine Strsse zu bauen.

Hierfür ist eine rekursive Funktion nötig. Informier dich mal über Rekursion im Netz.

Wenn du das schaffst, gar sooooo schwer, dann ist der Lehrer definitiv beeindruckt .

 

[Limit]

Ich kenne das Spiel nicht, aber da es auf einem Spielbrett gespielt wird, gehe ich mal davon aus, dass die Anzahl der Felder sehr begrenzt ist und alle Felder gleich groß sind. Dann ist es wohl wirklich am einfachsten für jeden Spieler eine 2D-Matrix aufzustellen, in der dann für jedes Feld eine 1 (heißt Straße vorhanden) oder 0 (heißt Straße nicht vorhanden) eingetragen werden. Dann brauchste nur noch mit Hilfe zweier Schleifen die 1er zählen und hast die Straßenlänge jedes Spielers. Backtracking-Algorithmus find ich für dieses Problem ein wenig übertrieben und ist wohl auch langsamer.

 

[Green Mamba]

@Limit
Da hast du was falsch verstanden, das Problem liegt darin dass die Straßenelemente auch zusammengehören müssen. Also eine lange Strasse am Stück, nicht z.B. 3 kleine.