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

Hier gibt es zwar schon ein paar ähnliche Fragen, bei denen ich jedoch
keine Lösung gefunden habe. Sagen wir mal, ich will ein Schiff(5 Kästchen)
per Zufall platzieren. Jetzt muss ich ja zuerst prüfen, ob bei der zufällig
erstellten Koordinate platz für 5 Kästchen wären. Soweit alles klar. Jetzt muss
ich aber, bevor das Schiff platziert werden kann, ja auch noch überprüfen,
ob umliegend schon ein anderes Schiff platziert wurde. Insgesammt müsste ich
dann ja 12 Kästchen überprüfen(5 Kästchen links 5 rechts, 1 oben 1 unten). Wie
kann ich das am besten machen?

Hab mal kurz(mit Paint!) dargestellt, was ich meine.

http://s1.directupload.net/images/130603/vn26zmhw.jpg

Das Rote soll das Schiff sein. Die blaue Markierung sind die Kästchen,
die überprüft werden müssen, ob da schon ein anderes Schiff ist.

Wie kann ich das am besten machen. Wenn ich für jedes Schiff, alles einzeln
berechen, dauert es lange, da:

Berechnungen:
1. Zufällige Start-Koordinate berechnen
2. Platz berechnen
3. Umliegende Kästchen berechnen
4. Berechnen, ob das Schiff über den Rand(zwischen 10 und 11 Kästchen) kommt.

Erst nach diesen Berechnungen kann ein Schiff richtig platziert werden. Also
noch mal meine Fragen:

1. Wie kann ich die umliegenden Kästchen am besten prüfen?
2. Wie kann ich die ganzen Berechnungen so optimieren, das es wesentlich
schneller läuft?

volkard

Vorweg: Endlich mal einer, der eine klare Frage stellen kann. Da macht das Antworten gleich viel mehr Spaß. Daran sollten sich einige eine Scheibe abschneiden.

helpplease schrieb:

Wie kann ich das am besten machen?

Hab mal kurz(mit Paint!) dargestellt, was ich meine.

http://s1.directupload.net/images/130603/vn26zmhw.jpg

Das Rote soll das Schiff sein. Die blaue Markierung sind die Kästchen,
die überprüft werden müssen, ob da schon ein anderes Schiff ist.

Das Bildchen ist toll. Nur sind die Roten Kreise dort ein tatsächliches Schiff im Speicher und die Blauen Tupfen sind nicht im Speicher, aber warum eigentlich nicht? Dir wären supi hilfreich!

helpplease schrieb:

Wie kann ich das am besten machen. Wenn ich für jedes Schiff, alles einzeln
berechen, dauert es lange, da:

Och, die Laufzeit würde mich da eher weniger jucken. Das ist alles sauschnell. Aber ich hätte Lust, mir hier und da ein wenig Programmierarbeit zu ersparen. Und wenn's dadurch sogar nebenher schneller wird, warum nicht?

helpplease schrieb:

10. Zufällige Start-Koordinate berechnen
20. Platz berechnen
30. Umliegende Kästchen berechnen
40. Berechnen, ob das Schiff über den Rand(zwischen 10 und 11 Kästchen) kommt.
Erst nach diesen Berechnungen kann ein Schiff richtig platziert werden.

5. Ich gehe davon aus, daß die Schiffe der Länge nach gesetzt werden, die langen zuerst.
10. Zufällige Start-Koordinate und Richtung würfeln. ^(Fußnote)
20. entfällt
30. entfällt
~~40. Zielkorrdinate berechnen und wenn sie außerhalb ist, gehe zu 10.~~
50. Laufe über die Plätze, wo ein Roter Kreis hinsoll, und schau jedesmal, ob da ein Blauer Tupfen ist, wenn ja, gehe zu 10.
60. Laufe nochmal über die Plätze, wo ein Roter Kreis hinsoll, und setze ihn und
-----Laufe über die vier Nachbarfelder des Roten Kreises und
~~--------Wenn das Nachbarfeld innerhalb des Spielfeldes ist, dann~~
------------Wenn da kein Roter Kreis ist, setze da einen Blauen Tupfen.

Besser noch, Du machst das Spielfeld nicht 10x10 groß, sondern 12x12 und setzt ganz zu Anfang rundherum einen "Todesrand" aus Blauen Tupfen. Dadurch entfallen die gestrichenen Zeilen.

helpplease schrieb:

1. Wie kann ich die umliegenden Kästchen am besten prüfen?

Das war eigentlich die falsche Frage, weil es mit dem Blaue-Tupfen-Trick vermeidbar ist, für jedes gewürfelte Schiffsprojekt erst noch die umliegenden Kästchen zu prüfen. Es reicht, die Blauen Tupfen immer erst zu setzen, wenn ein Schiff tatsächlich gebaut werden kann.

helpplease schrieb:

2. Wie kann ich die ganzen Berechnungen so optimieren, das es wesentlich
schneller läuft?

Das war auch die falsche Frage. Laufzeit ist hier völlig irrelevant. Ob der Benutzer 100 oder 500 Mikrosekunden warten muss, er kann es nicht bemerken. Die Blauen Topfen und der Todesrand machen den Code einfacher, er wird kleiner, alle Vorausspeicherungen und alle Randberechnungen fallen weg, weniger Fehler können sich drin verstecken.

^(Fußnote) Startkoordinate als zwei ints x|y und Richtung als zwei ints dx|dy (lies delta-x und delta-y) und die Rote-Kreis-Schleife als

for(int i=0;i<laenge;++i){
   //tuwas mit dem Roten Kreis auf x|y
   x+=dx;
   y+=dy;
}

Dann fallen sogar alle Code-Duplikationen weg, wo man an sich den selben Code für die vier Richtungen viermal hinschreiben müsste.

hustbaer

@helpplease
Wenn du es machst damit du es dann hast, dann mach es so wie volkard geschrieben hast.
Wenn du es aber machst primär um dabei was zu lernen, könnte es Sinn machen die ganzen Corner-Cases ohne Tricks zu lösen.

Hi, erstmal danke an euch beiden. Vor allem dir volkard für deine
ausführliche Antwort, zu der ich jetzt mal genauer drauf eingehen möchte.

Erstmal, ich hab vergessen zu erwähnen, dass ich es mit der WinAPI programmiere.
Vielleicht sollte ich es lieber im WinApi-Forum posten, also bitte verzheit.

Och, die Laufzeit würde mich da eher weniger jucken. Das ist alles sauschnell.

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

Das ist bei mir leider nicht so der Fall. Beim starten muss ich mehrere Sekunden
warten, bis das Spielfeld + die Schiffe des Gegners gesetzt wurden. Das liegt
wahrscheinlich an folgendem Code, den ich benutze, um die Schiffe zusetzen:

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

	while(test != true)
	{
		start = zufall();
		if(lage == 0)
		{
			if(index[start-1] == false && index[start-10] == false  && index[start+10] == false)
				test = true;
			else
				continue;

			for(i = 0; i <= schiff; i++)
			{
				if(index[start+i] == false)
					test = true;
				else
					continue;
			}
		}
		else
		{
			if(index[start-10] == false && index[start-1] == false && index[start+1] == false)
				test = true;
			else
				continue;

			for(i = 0; i <= schiff*10; i += 10)
			{
				if(index[start+i] == false)
					test = true;
				else
					continue;
			}
		}
	}

	if(test == true)
	{
		if(lage == 0)
		{
			for(i = 0; i < schiff; i++)
				index[start+i] = true;
		}
		else
		{
			for(i = 0; i < schiff*10; i += 10)
				index[start+i] = true;
		}
	}
}

Kurz erklärt:
start -> Zufällig generierte Start-Koordinate
i -> Hilfsvariable für Schleifen
test -> Wenn test am Ende true ist, wird das Schiff platziert.
lage -> Die lage soll die Lage beschreiben(0 = Horizontal, 1 = Vertikal)

Ich bin kein Profi, von daher würde ich mich freuen, wenn eure Kritik schonend
rüberkommen würde

Ich benutze diese Funktion, um die Schiffe zufällig zu platzieren, und dabei
die erforderlichen abfragen zu machen. Das mit den blauen Tupfen, sollte
in dem Bild eigentlich nur zeigen, welche Kästchen gemeint sind, aber deine
Idee

Laufe über die vier Nachbarfelder des Roten Kreises und
wenn da kein Roter Kreis ist, setze da einen Blauen Tupfen.

wäre nicht schlecht. Genauso, wie das mit dem "Todesrand".

@hustbaer
Ich mache das, um das gelernte in einem kleinen Programm umzusetzen und zu vertiefen.

Ich bitte euch nochmals, ich bit kein Profi, also bitte Kritik schonend
äußern ;), danke!

Oh, habe eine kleinigkeit vergessen, folgendes zu erklären:

...start+1 -> Der Button, der rechts neben dem Startbutton ist(Horizontal).
...start+10 -> Der Button, der unter dem Startbutton ist(Vertikal).

Die index[] Variable ist ein Bool-Array, -> True = Schiff, False = Kein Schiff

Th69

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

@Th69
Nein, hab kein time(0) drin. Hab es so:

time_t t;

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

camper

in zufall() ?

camper schrieb:

in zufall() ?

Wieso? Verstehe nicht ganz!

camper

Th69 schrieb:

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

helpplease schrieb:

@Th69
Nein, hab kein time(0) drin. Hab es so:
time_t t;

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

camper schrieb:

in zufall() ?

==> Befindet sich dieser Code in der Zufallsfunktion zufall?

@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.

@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)

@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?

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.

...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!