Schiffe versenken - Wie prüfen, ob ein Schiff genau daneben ist?

[helpplease]

@camper
Achso, ja. Das befindet sich in zufall(). Aber das ist doch nun wirklich mehr als offensichtlich, denn

time_t t;

    time(&t);
    srand((unsigned int)t);

Initialisiert ja den Zufallsgenerator.

[Nathan]

Was man ein einziges Mal tun sollte - am Beginn der main().

[LordJaxom]

helpplease schrieb:

denn [...] Initialisiert ja den Zufallsgenerator.

Genau, initialisiert. Einmal. Initial.

[helpplease]

@LordJaxom && Nathan

Stimmt, muss ich ja ändern, da ich den Zufallsgenerator in der Funktion Initialisiere.
Ich muss das auserhalb nur einmal machen, danke fürs korrigieren, doch denkt
ihr, es ist deswegen so langsam?

[LordJaxom]

helpplease schrieb:

@LordJaxom && Nathan

Stimmt, muss ich ja ändern, da ich den Zufallsgenerator in der Funktion Initialisiere.
Ich muss das auserhalb nur einmal machen, danke fürs korrigieren, doch denkt
ihr, es ist deswegen so langsam?

Da die Zufallsfunktion eine Sekunde lang immer die gleiche Zufallszahl liefert: ja. (time liefert einen Zeitstempel in Sekunden)

[helpplease]

@LordJaxom

Du hast recht. Jetzt geht es ziehmlich schnell, doch ich hab jetzt ein anderes
Problem. Jetzt setzt er nicht mehr alle Schiffe, sondern nur ein paar bestimmte.
Zum Beispiel 2 Zwei-Kästchen und den fünfer. Mehr nicht. Das einzige, was ich jetzt geändert habe, ich habe die Initialisierung des Zufallsgenerators aus
der Funktion rausgenommen und in die WinMain eingefügt, noch bevor die
Funktion zufall() das erste mal aufgerufen wird! Hast du eine Idee?

[helpplease]

Hier noch mal etwas genauer:

Funktion zufall()

int zufall()
{
	izeit = 145 + ( rand() % 100 ); 
	return izeit;
}

Ich habe allerdings schon vor ein paar stunden die SchiffPlatzieren() geändert:

Funktion SchiffPlatzieren()

void SchiffPlatzieren(short schiff, bool lage)
{
	int start, i;

	while(true)
	{
		start = zufall();
		if(lage == 0)
		{
			if(sperre[start])
				continue;
			for(i = 0; i < schiff; i++)
				if(index[start+i])
					continue;
			if(sperre[start-1] || sperre[start+schiff-1] || sperre[start-12] || sperre[start+12])
				continue;

			for(i = 0; i < schiff; i++)
			{
				index[start+i] = true;
			}
			sperre[start-1] = true;	
			sperre[start+schiff-1] = true;
			sperre[start-12] = true;
			sperre[start+12] = true;

			break;
		}
	}
}

"sperre" ist ein Bool-Array, worin ich die umliegenden Felder eines Schiffes markiere!

[volkard]

Th69 schrieb:

Hast du in deiner Zufallsfunktion srand(time(0)) drin? Dann würde es mich nicht wundern, wenn deine Routine mehrere Sekunden dauert...

Gute Kristallkugel!

[volkard]

helpplease schrieb:

Hast du eine Idee?

Meine allererste Idee ist, die Windows-Sachen wegzumachen und das Programm erstmal als Konsole-Anwendung zu bauen. Die zweite wäre, alles wegzuwerfen und neu anzufangen, diesmal mit kleineren Funktionen, lokaleren Variablen, treffenderen Bezeichnern und tatsächlich (temporär) goto, wenn du wirklich goto meinst.

[helpplease]

...tatsächlich (temporär) goto, wenn du wirklich goto meinst.

Wie kommst du jetzt auf goto? Davon hab ich nichts erwähnt!

Und wieso alles von neu machen? Jetzt, wo ich, was die Geschwindigkeit angeht
schon einen Schritt nach vorne gemacht habe! Wenn man alles von vorne beginnt,
dann leidet darunter zum einen die Motivation und zum anderen auch der Lehrerfolg.
Denn es ist doch besser, schlechten Code zu Optimieren und sich immer weiter zu
verbessern, als wieder von neu anzufangen!

[helpplease]

Gute Kristallkugel!

Was meinst du? ich hatte in srand() kein time(0) drin!

[Furble Wurble]

helpplease schrieb:

...tatsächlich (temporär) goto, wenn du wirklich goto meinst.

Wie kommst du jetzt auf goto? Davon hab ich nichts erwähnt!

Mit goto kannst Du aber bequem aus einer inneren Schleife von mehreren verschachtelten Schleifen springen.
Mit continue und break ist das nicht so einfach. Siehe zum Beispiel Deinen Code:

for(i = 0; i < schiff; i++)
  if(index[start+i])
    continue;  // quark

Gemeint hast Du wohl:

while(true){
    loop:
      start=zufall();
      //...
      for(i = 0; i < schiff; i++)
        if(index[start+i])
          goto loop;
    //...
  }

Und ganz eigentlich wolltest Du das testen der einzelnen Felder in eine eigene Funktion auslagern.

[camper]

void SchiffPlatzieren(short schiff, bool lage) // schiff == Länge,  lage == horizontal/vertkal?
{
	int start, i; // Definition besser erst später

	while(true)
	{
		start = zufall();
		if(lage == 0)
		{
			if(sperre[start])
				continue;
// prüft, ob Schiffsfelder schon durch anderes Schiff belegt
// was ist, wenn es sich um benachbarte Felder (sperre) handelt?
			for(i = 0; i < schiff; i++)
				if(index[start+i])
					continue;  // wurde schon kritisiert
// im Allg. mehr als 4 benachbarte Felder
// und warum genau sollte die Belegung fehlschlagen, wenn ein freies Feld zufällig schon Nachbar eines anderen Schiffes ist?
			if(sperre[start-1] || sperre[start+schiff-1] || sperre[start-12] || sperre[start+12])
				continue;
			for(i = 0; i < schiff; i++)
			{
				index[start+i] = true;
			}
// das ist seltsam: ein Schiff hat ja in der Regel mehr als 4 benachbarte Felder eher: 2*Länge+2 od 2*Länge+6 falls Ecken zählen
			sperre[start-1] = true;	
			sperre[start+schiff-1] = true;
			sperre[start-12] = true;
			sperre[start+12] = true;

			break;
		}
	}
}

Die Verwendung zweier Felder scheint nicht besonders sinnvoll. Ein einzelnes Feld mit 3 Zuständen je Feld (leer, benachbart, belegt) dürfte sinnvoller sein. Das vereinfacht auch die Logik: damit ein Schiff gesetzt werden kann, müssen alle Felder, die es belegt, leer sein.

[hustbaer]

und warum genau sollte die Belegung fehlschlagen, wenn ein freies Feld zufällig schon Nachbar eines anderen Schiffes ist?

Weil das nunmal die Regeln sind

[camper]

hustbaer schrieb:

und warum genau sollte die Belegung fehlschlagen, wenn ein freies Feld zufällig schon Nachbar eines anderen Schiffes ist?

Weil das nunmal die Regeln sind

Gemeint ist, das ein Feld ja durchaus Nachbar zweier Schiffe sein kann (also z.B. zwei Schiffe parallel mit dem Abstand 2). Etwas anderes kann ich aus der Beschreibung nicht herauslesen.

[algofrieg]

volkard schrieb:

Laufzeit ist hier völlig irrelevant. Ob der Benutzer 100 oder 500 Mikrosekunden warten muss, er kann es nicht bemerken.

Also interessiert der Algo nicht, der für n Schiffe nur O(1) pro Setzen benötigt (unabhängig von Schifflänge und Feldgrösse) und dabei O(n) Speicher benötigt.

[hustbaer]

camper schrieb:

hustbaer schrieb:

und warum genau sollte die Belegung fehlschlagen, wenn ein freies Feld zufällig schon Nachbar eines anderen Schiffes ist?

Weil das nunmal die Regeln sind

Gemeint ist, das ein Feld ja durchaus Nachbar zweier Schiffe sein kann (also z.B. zwei Schiffe parallel mit dem Abstand 2). Etwas anderes kann ich aus der Beschreibung nicht herauslesen.

Ah
Ja, dass er das doppelt macht, und dadurch 2 freie Felder zwischen Schiffen sein müssten hab' ich übersehen.
(Abgesehen von dem "das ist seltsam" Fehler)

[volkard]

camper schrieb:

Die Verwendung zweier Felder scheint nicht besonders sinnvoll. Ein einzelnes Feld mit 3 Zuständen je Feld (leer, benachbart, belegt) dürfte sinnvoller sein. Das vereinfacht auch die Logik: damit ein Schiff gesetzt werden kann, müssen alle Felder, die es belegt, leer sein.

Jo, schon.
Andererseits wird das sperre-Feld nur ganz kurz mal während des Schiffe-Platzierens gebraucht und dab dann für den Rest des Spiels ist der dritte Zustand ein Bißchen störend.

[Swordfish]

...

[camper]

volkard schrieb:

camper schrieb:

Die Verwendung zweier Felder scheint nicht besonders sinnvoll. Ein einzelnes Feld mit 3 Zuständen je Feld (leer, benachbart, belegt) dürfte sinnvoller sein. Das vereinfacht auch die Logik: damit ein Schiff gesetzt werden kann, müssen alle Felder, die es belegt, leer sein.

Jo, schon.
Andererseits wird das sperre-Feld nur ganz kurz mal während des Schiffe-Platzierens gebraucht und dab dann für den Rest des Spiels ist der dritte Zustand ein Bißchen störend.

Im Prinzip ändert das ja nichts an der Komplexität des Problems. Der Algorithmus sollte im Prinzip so aussehen

1. würfle Position
2. Falls nicht jedes Feld des Schiffskörpers frei ist (frei==kein anderes Schiff und auch kein Nachbarfeld eines anderen Schiffes), gehe zu 1.
3. Markiere Schiffsfelder als belegt
4. Markiere Nachbarfelder als solche

Zwei Felder bedeutet doppelte Arbeit im 2. Schritt aber sicher keinen wesentlichen Nachteil.
Oder aber man verzichtet auf die Erfassung der Nachbarfelder und prüft eben intensiver im 2. Schritt

1. würfle Position
2. Falls nicht jedes Feld des Schiffskörpers als auch jedes benachbarte Feld frei ist (frei==kein anderes Schiff), gehe zu 1.
3. Markiere Schiffsfelder als belegt

Offenbar bedeutet diese Variante mehr Arbeit, falls eine gewürfelte Position nicht verwendbar ist. Dafür wird der Algorithmus kürzer.