4. Schiffe versenken

Schiffe versenken

  • I

    Hallo,

    ich versuche gerade, meine Funktion, die auf einem 7x7 Feld 6 Schiffe (1x 5, 1x 4, 2x 3, 2x 2 lang) platziert dahingehend zu verbessern, dass sie die Schiffe nicht alle auf einen Haufen nebeneinander schmeißt. Zurzeit entscheidet der Zufall über die Position, aber das führt oft zu besagten Haufen:

    void KI::createShip(unsigned shipCategory)
{
	static bool rotated;
	rotated = !rotated;
	std::random_shuffle(mPossiblePositions.begin(), mPossiblePositions.end());
	for(const auto& position : mPossiblePositions)
	{
		if (mPlayer.addShip(mPlayerCategory, rotated, shipCategory, position) ||
			mPlayer.addShip(mPlayerCategory, !rotated, shipCategory, position))
			return;
	}
	throw std::logic_error("Ship could not be placed!");
}

    Fallen euch irgendwelche Ideen ein, wie man das verhindern kann? Oder kann man das sogar vernachlässigen?

    0
  • Mod

    Du musst halt erst einmal mathematisch formulieren, was "nicht auf einen Haufen" bedeuten soll. Und dann setzt du dies eben als Voraussetzung an, ob ein Satz angenommen wird oder nicht.

    Eine Idee wäre, dass der mittlere quadratische Abstand aller Schiffe voneinander einen gewissen Mindestwert haben muss.

    0

  • Oder du nimmst einfach eine Halton-Sequenz:

    https://en.wikipedia.org/wiki/Halton_sequence

    Die vermeidet die Haufenbildung.

    0

  • @Incocnito
    Wäre interessant wie das generierte Bild aussieht. MMn. dürfte nämlich mit deinem Code auch nicht immer alles auf einem Haufen landen. Vorausgesetzt der Name mPossiblePositions hält was er verspricht - d.h. du befüllst mPossiblePositions korrekt (und vor allem vollständig). Und natürlich auch vorausgesetzt du seedest den Generator irgendwo mit einem "nicht-konstanten" Seed.

    Ansonsten kannst du mal versuchen nen besseren Zufallszahlengenerator zu verwenden. Für deine Anwendung sollte Mersenne-Twister OK sein (und da gibt's ne fertige Implementierung in der Boost und IIRC auch in der STL - ab C++11). Bzw. kannst du auch z.B. einen Xorshift oder Multiply-With-Carry Generator probieren:
    https://en.wikipedia.org/wiki/Xorshift
    https://en.wikipedia.org/wiki/Multiply-with-carry
    K.A. ob's da was fertiges gibt, aber beide derart einfach, die 2-3 Zeilen schreibst du schnell selbst bzw. kopierst sie aus dem Netz.

    0
  • I

    Erstmal danke für die Antworten. Das mit der Halton Sequenz sieht interessant aus, werd mir mal anschauen ob man das so einfach umsetzen kann.

    @hustbaer: Hier mal ein paar Beispiele mit der Zufallsfunktion:
    https://picload.org/view/rwiwwalw/zwischenablage.jpg.html
    Es landen irgendwie immer ein paar Schiffe direkt nebeneinander, das würd ich schon gern vermeiden. Das mit mPossiblePositions ist ja auch ziemlich straightforward

    void KI::fillPossiblePositions()
{
	mPossiblePositions.clear();
	for(int i = 1; i <= 7; ++i)
	{
		for(int j = 1; j <= 7; ++j)
			mPossiblePositions.push_back(sf::Vector2i(i, j));
	}
}

    und dazu halt das übliche

    std::srand(std::time(0));

    müsste doch eigentlich reichen. Sieht jedenfalls recht zufällig aus.

    Edit: ach ja, dieser logic_error wird hin und wieder tatsächlich mal geschmissen. Hab ich irgendwo Mist gebaut oder kann es per Zufall tatsächlich vorkommen, dass die Schiffe so ungünstig platziert wurden, dass es keine freien Plätze mehr fürs letzte/vorletzte gibt? Wüsste jetzt nicht, wie man das auf die schnelle ausrechnen kann 😃

    0
  • R
    Mod

    Incocnito schrieb:

    Edit: ach ja, dieser logic_error wird hin und wieder tatsächlich mal geschmissen. Hab ich irgendwo Mist gebaut oder kann es per Zufall tatsächlich vorkommen, dass die Schiffe so ungünstig platziert wurden, dass es keine freien Plätze mehr fürs letzte/vorletzte gibt? Wüsste jetzt nicht, wie man das auf die schnelle ausrechnen kann 😃

    Wieso schaust du dir nicht einfach den zustand an bei dem das schiff nicht positioniert werden konnte? benutzt du einen debugger?

    0
Anmelden zum Antworten