Schiffe zufällig setzen!

[TNA329]

Hallo
brauche mal wieder hilfe, wie wohl sogut wie jeder, der ein neues Thema schreibt :P

Also mein Problem ist folgendes:

Ich programmiere momentan ein Schiffeversenken Spiel...alles soweit so gut bis jetzt keine größeren Probleme gehabt, bis es zur zuälligen Schiffsverteilung kam (vom NPC-Gegner)!

Hatte mal ausprobiert, dass er eben zufällige Koordinaten auswählt und dann überprüft, ob man das schiff setzten kann.
Das überprüfen lief so ab: erstma geguckt, ob Horizontal oder Vertikal -> geprüft, dass Schiff nicht über´n Rand hinaus ragt -> und zuletzt, dass es natürlich nicht auf einem schon besetzten Feld liegt bzw in einem Feld neben eines Schiffes (Ein Feld muss jeweils neben eines anderen Schiffes frei bleiben.)
Selbst das überprüfen ist kein Problem, das ich genau das selbe jeweils prüfe, wenn ich selbst die Schiffe verteile, ABER
wenn der PC das selbst machen soll hängt der sich auf, weil er ja teils ewig suchen muss, bis alle faktoren erfüllt sind, besonders wenn schon Schiffe gesetzt wurden.
Habe die Koordinaten des Feldes in einem Array gespeichert (Array[1..10,1..10] of integer;) und in einer dynamischen Liste.

Könnt ihr mir also evtl einen Code liefern oder zumindest "mündliche" Lösungen anbieten, wie das problem des aufhängens gelöst werden könnte??
Habe mir schon stunden darüber gedanken gemacht, aber komme zu keinem erfolgreichen ergebnis!

Hoffe ihr versteht das Problem :P

LG Jochen

---Edit:

Das Feld ist 10x10 groß und es sind folgende Schiffe vorhanden: 1x 5er, 1x 4er, 2x 3er und 1x 2er

[Medium]

Die wichtigste Frage ist zunächst mal: Kann man N-n Schiffe so platzieren, dass ein weiteres an keiner Stelle mehr kollisionsfrei platziert werden kann. Danach entscheidet sich dann ob man mit einem einfachen Randomisierer + Prüfung (was du jetzt im Grunde machst) vorgehen kann, oder ob das schon zu einem kleinen Optimierungsproblem ausartet.

[TNA329]

also egal mit welchem Schiff man anfängt und egal wie man es schlieslich legt, gibt es immer eine Variante, so dass alle schiffe plaziert werden können, wenn du das meintest, mit deiner Aussage...

[patti]

Hab das auch schonmal vor einigen Jahren gemacht, den Source hab ich jetzt leider nicht bei der Hand, sonst hätte ich ihn dir gegeben. Aber wie wäre folgendes?

Code:

1. Zufälliges Feld auswählen (--> "AusgangsFeld")
2. Richtung bestimmen (horizontal oder vertikal --> "Richtung")
3. Erstmal schauen, ob das Schiff überhaupt auf dem Spielfeld liegt:

Delphi-Quellcode:

case Richtung of
0 : // nach rechts
    Passt := AusgangsFeld.x + Groesse -1 <= 10;
1 : // nach unten
    Passt := AusgangsFeld.y + Groesse -1 <= 10;
end;

Code:

4. Wenn das Schiff auf dem Spielfeld liegt, dann überprüfen, ob es nirgends "aneckt"

Delphi-Quellcode:

var x1,x2,y1,y2 : integer;
//...
if Passt then
begin
x1 := Max(AusgangsFeld.x-1,1); // aus der Unit Math
x2 := Min(Ausgangsfeld.x+Groesse-1,10);
y1 := Max(AusgangsFeld.y-1,1);
y2 := Min(Ausgangsfeld.y+Groesse-1,10);
//
repeat
   repeat
      Passt := not(Felder[x2,y2]) // je nachdem wie du deine Felder halt speicherst
      //
      dec(y2);
   until (y2 < y1) or not(Passt);
   //
   dec(x2);
until (x2 < x1) or not(Passt);
end;

Das ganze machst du für jedes Schiff sooft, bis du ein "Passt" hast.
Hoffe, ich hab keine allzu großen Fehler gemacht ;-)

Patti

Edit: Hab gesehen, dass dein Felder-Array von 1 bis 10 und nicht von 0 bis 9 geht. Hab mal den Code von mir etwas angepasst...

[Medium]

Zitat:

Zitat von TNA329

also egal mit welchem Schiff man anfängt und egal wie man es schlieslich legt, gibt es immer eine Variante, so dass alle schiffe plaziert werden können, wenn du das meintest, mit deiner Aussage...

Eigentlich meinte ich das Gegenteil: Kann es eine Variante geben, in der eben das nicht der Fall ist. Sobald du nämlich weniger als alle Schiffe (daher N-n) so platzieren kannst, dass die verbleibenden noch zu setzenden auf dem Feld keinen Platz mehr haben, kann vorgenannter Weg zu Endlosschleifen führen (da dann für kein weiteres Schiff jemals mehr ein zufälliges Plätzchen gefunden werden kann).

Ich kann mir gut vorstellen, dass das bei 10x10 und den von dir genannten Schiffen nicht vorkommen kann, aber theoretisch müsste man dies beweisen bevor man zufälliges "piece-by-piece"-Verteilen bedenkenlos anwenden kann.

[p80286]

Zitat:

Zitat von TNA329

..wenn der PC das selbst machen soll hängt der sich auf, weil er ja teils ewig suchen muss, bis alle faktoren erfüllt sind, besonders wenn schon Schiffe gesetzt wurden.

Das "ewige Suchen" muß ja nicht sein. Wenn das erste Schiff eingetragen ist, werden dadurch ja schon einige Positionen belegt. Je nach Größe und Spielregeln mehr oder weniger. Z.B. das erste "U-Boot" (1 Kästchen) liegt auf postion 1/1. Die nächste Position deines Zufallszahlengenerators ist 1, dann nimm die erste freie Position (2/1), richte Dein Schiff aus und gut ist. Damit solltest Du einiges an Zeit herausschinden können. Wenn Du dann z.B freie Positionen hast, in die keines Deiner Schiffe mehr passt, dann solltest Du diese auch aus der Verfügbarkeitsliste streichen.

Gruß
K-H

[TNA329]

Also ersteinmal ein großes Danekeschön für alle, die sich die Zeit genommen haben mir zu meine Frage zu beantworten! =)

Habe nun das Problem gelöst! Dabei haben mir eure Ideen schöne Denkanstöße gegeben.

Für alle die es interessiert erkläre ich kurz wie ich dies umgesetzt habe:

0. Die liste komplett neu füllen!
1. Horizontal oder nicht
2. die Koordinaten aus der Liste gelöscht, die ich nicht verwenden kann(kommt halt auf die größe des schiffes an)
3. dann werden zufällige koordinaten rausgesucht, welche verwendet werden
3.1 diese punkte überprüfen mit hilfe einer function
3.1.1 diese Koordinaten funktionieren nicht--> aus der liste löschen und Punkt 3 wiederholen
3.1.2 die funktionieren --> schiff setzen

Diese vorgehnsweise hat den vorteil, dass keine Koordinaten zweimal abgefragt werden und dieser durchlauf auf jeden fall kleiner als 100 ist, da anfangs schon koordinaten raus gelöscht werden!

habe damit nun keine probleme mehr die schiffe zufällig zu setzten...
man beachte aber, welche schiffe ich verwende...sollten mehrere größere schiffe hinzukommen müsste da wohl einiges umgeschrieben werden!!

nungut also bis zur nächsten frage ;)
lg