Gra w Statki - Rozmieszczenie okrętów

upychasz statki od największego do najmniejszego.
losujesz pozycję i orientację bieżącego statku
sprawdzasz poprawność i jeśli się nie da to losujesz pozycję orientację statku na nowo aż do skutku.

Myślałem o standardowym losowaniu jednego punktu i potem na jego podstawie wylosować jeden z kierunków w którym dodać kolejne punkty, ale to raczej mało praktycznie, bo okręt mógłby wyjść za planszę, lub wejść jeden na drugi.

Dla mnie to dobre rozwiązanie. Losujesz punkt, losujesz kierunek - sprawdzasz czy na kolejnych polach nie byłoby to już poza planszą, lub czy nie ma tam innego statku - jak jest - to sprawdzasz inny losowy kierunek - jak w żadnym kierunku się nie da to losujesz inny punkt i sprawdzasz to wszystko jeszcze raz.

Nie jest to najwydajniejszy algorytm zapewne, ale - różnica pomiędzy najlepszym z możliwych algorytmów a czymś takim będzie i tak niezauważalna - plansza ma 100 pól, a nawet Nokia 3310 poradzi sobie z takim algorytmem w ułamku sekundy - więc na etapie nauki i pisania gry w statki - bym go zaimplementował. Potem ew. bedziesz mogł go ulepszyć.

edit: tak jak @MarekR22 napisał - losując od największego do najmniejszego masz mniejszą szansę na trafianie w niedozwolone pola = wydajniejszy algorytm.

No tak, na to, żeby losować od największego już wpadłem, ale jak rozwiązać to losowanie kierunku ułożenia statku? Bo mamy jedną z 4 możliwości.

masz tylko 2 możliwości kierunku, poziomo lub pionowo. A możliwości pozycji masz rozmiarPlanszy*(rozmiarPlanszy-rozmiarStatku+1) (nie licząc kolizji).

@MarekR22: Jemu chodzi o to, że po wylosowaniu punktu losuje kierunek w którym stawiać kolejne punkty, nie, że od razu stawia statek w całości (a więc nie robi tak, że np. mając statek na 4 pola losuje pozycje X = <0,5>). To jest chyba lepsze rozwiązanie niż stawiać w całości - bo i tak musi przelecieć po punktach w poszukiwaniu kolizji.

dzek69, dokładnie. Losujemy punkt i od niego idziemy, albo do góry, albo w dół, albo w lewo, albo w prawo. Tylko nie wiem jak zrobić losowanie tego ułożenia. No i jest jeszcze problem z tą kolizją. Bo dajmy na to mam 2 statki ustawione równolegle i między nimi 2 kolumny przerwy. Wylosuje mi między nimi punkt i zacznie ustawiać w poprzek. Postawi 2 punkty i co dalej? Jakiś warunek jest potrzebny, żeby wtedy losowało od nowa punkt, tylko nie wiem jak to rozwiązać kodowo.

pętla while i przede wszystkim rozbicie tego na funkcje realizujące konkretne zadania.

@dzek69, Ogólniki, ogólniki... Problem w tym, że nie mam pomysłu na jakie zadania mam to rozbić. Liczyłem na pomoc w wykombinowniu algorytmu.

co to jest "or"?

Mógłbyś mi jeszcze wytłumaczyć te linijki?

 while (jestKolizjaDla(x, y, or, statek.rozmiar));
    dodajStatek(x, y, or, statek.rozmiar); 

Poza tym, nie za bardzo rozumiem roli or... On ustawia pionowo, albo poziomo?

Ja bym zrobił dwie bliźniacze tablice: główną i pomocniczą. Losujesz dowolny punkt na tablicy pomocniczej i sprawdzasz po kolei w każdym z czterech kierunków czy zmiescisz statek. Jak stwierdzisz, że się zmiesci to nakładasz statek na obie mapy ,a na tablicy pomocniczej zaznaczasz jeszcze okolicę statku.

Łączne mam w programie aż 4 tablice, dla przejrzystości, ale wciąż nie o to się rozchodzi. Nie rozumiem tego fragmentu co mi @MarekR22 podesłał. Nie wiem jak mam zrobić to losowanie.

bool jestKolizjaDla(int x, int y, int or, int rozmiar) {
     if (or==0) {
           for (int i=y; i<y+rozmiar)
                if (plansza[x][i]!=PustePole)
                     return true;
           return false;
     } 
     for (int i=x; i<x+rozmiar)
         if (plansza[i][y]!=PustePole)
             return true;
     return false;
};

To sprawdza tylko czy dodanie nowego statku powoduje nakładanie się z innym statkiem, więc musisz to poprawić jeśli chcesz mieć inny warunek kolizji.
Dodanie statku powinno wyglądać prawie identycznie.

Niko0 napisał(a):

Łączne mam w programie aż 4 tablice, dla przejrzystości, ale wciąż nie o to się rozchodzi. Nie rozumiem tego fragmentu co mi @MarekR22 podesłał. Nie wiem jak mam zrobić to losowanie.

Jesteśmy w dziale algorytmy [...] a nie w Newbie czy też c++. Na tym polega właśnie robienie na początku np. przez ciebie tej gry żebyś sam ją zrobił, żebyś nauczył się rozwiązywać problemy, szukać w googlu, helpie, dokumentacji itd. Jak ktoś Ci da cały kod to co ci to da?

@Nitro Cee. Ja nie chciałem kodu, tylko algorytm. Może myć opisany słownie. :)

Sprawdzanie kolizji i inne rzeczy wiem jak zrobić. Jedyne czego nie umiem to losowanie ułożenia i orientacji statku.

No to dostałeś odpowiedzi na temat algorytmu.

Najlepiej:

1. losujesz od 1 do 100
2. potem sprawdzasz czy zmiesci się 5 w góre bez kolizji jak nie to potem np. prawo, dól, lewo
3. jak git to ustawiasz a jak nie do wróc do 1

a może troszke inaczej? Każdy statek może mieć tylko kilka reprezentacji na planszy, każda reprezentacja ma swoją "otoczkę" - obszar na którym nie może być żadnego innego statku.
Na początku zdefinuj sobie kolekcję możliwych reprezentacji i otoczek dla każdego statku i potem próbuj rozmieszczać statki na planszy, a jak już go postawisz, "zamaluj" na planszy całą otoczkę dla tej reprezentacji statku.

Jak chcesz ustawić statek skłądający się z 4 pkt, to wybierasz losowo jedną z jego reprezentacji. Następnie szukasz na planszy wystarczająco dużych obszarów aby w nie wstawić tą wybraną reprezentację. Po ułożeniu statku zaznaczasz na planszy jego otoczkę, aby nie można było wstawić na niej innego statku.
Ponieważ zaznaczasz na planszy otoczki, nie musisz sprawdzać kolizji, a dlatego że szukasz miejsca dla statku nie musisz martwić się że otoczka wyjdzie poza mapę/wejdzie na już istniejącą otoczkę.
I tak powtarzasz dla wszystkich statków.
Tak jakbyś rozmieszczał figury na kwadratowej planszy.

Problem pewnie się pojawi jak nie da się wstawić wybranej reprezentacji bo nie ma miejsca - wtedy np wyżucasz tą wybraną reprezentację i szukasz dla innej.

Moźliwe położenia statków możesz sobie na początku wygenerować, albo ręcznie napisać.

Mam jeszcze taki problem, że nie wiem jak przekazać tablicę dwuwymiarową jako argument funkcji, tak, aby można ją było modyfikować wewnątrz tej funkcji. To tak jakby przekazywać przez referencję, ale normalny zapis referencji się nie kompiluje. Mógłby mi ktoś coś doradzić?

Nie wiem czy to jest dobra praktyka, ale mógłbyś ją opakować w klasę, albo użyć vector<vector<whatever>>

Może jakoś prościej? Po najciekawsze jest to, że w jednej funkcji tablica przesłana bezpośrednio jest edytowalna, a w drugiej nie zapamiętuje nic. Przy próbie wpisania jej jako referencji wyskakuje mi błąd. Jest na to jakiś patent?

Podstawy programowania w C++: wszystkie tablice przesyłane są zawsze PREZ WSKAŹNIK. Nie ma możliwości przesłania normalnej tablicy przez wartość!

Jakiś czas temu robiłem a'la sapera i też robiłem coś podobnego. Może wrzucę kod komuś się przyda.

 
      for(int i=0; i<LiczbaMin; i++)
      {
			do
			{
              a=rand()%7;
              b=rand()%7;
			} while(tab[a][b]==mina || (a==0 && b==0)||(a==6 && b==6));
     
              tab[a][b]=mina;     
              a=0;
              b=0;
      }

Chodziło o to, żeby wylosować podaną liczbę min. Mina nie mogła pokrywać się z inną, nie mogła być na początku trasy sapera i na mecie sapera.

Myślałem, żeby zrobić losowanie liczby "kierunek" z przedziału od 0 do 3 i na tej podstawie wybrać kierunek. Jeśli zwróci 1 to losujemy "kierunek" od nowa. Pierwsze losowanie generowałoby współrzędne d i e. Nie wiem tylko jak zrobić kolejne losowanie tych współrzędnych, w przypadku, gdy wszystkie 4 kierunki nie dadzą pożądanego efektu.

Nie czytalem calego tematu, ale czy naprawde nie wystarczy cos takiego:

{dir, pos[2]} = rand()
if(pos[abs(dir)&1]+ship_size*dir in plansza)
	return {pos[2], dir}
else
	return {}

Wylosuje, sprawdzi i zwroci wszystkie potrzebne dane do narysowania.

Rozwiązałem problem, więc dodam mój pomysł. Może komuś się kiedyś przyda:

1. Tworzę czteroelementową tablicę, gdzie na każdą pozycję losuje liczbę z zakresu <0, 3>, po czym sprawdzam, czy ona już jest na liście. Jeśli tak to dodaję, jeśli nie, to losuję do skutku.
   Mam Losowo wygenerowany ciąg liczb.
2. Losuję współrzędne do tablicy dwuwymiarowej
3. Biorę pierwszy element z listy, który odpowiada jednemu z 4 możliwych kierunków rozmieszczeń (dół, góra, prawo, lewo od wylosowanych współrzędnych) i przesyłam do funkcji, która sprawdza, czy mogę rozmieścić statek w pierwszym
   • Jeśli tak, to układa statek w tym kierunku
   • Jeśli nie (wychodzi za plansze, lub jest tam juz statek), to bierze następny kierunek.
4. Jeśli wszystkie kierunki nie dadzą pożądanego efektu to losujemy współrzędne od nowa

Teraz zostaje najtrudniejsza część, czyli inteligentne strzelanie przez komputer :). Chodzi o to, żeby po trafionym strzale dalsze trafienia szły jeden po drugim, w danym kierunku. Jeśli ktoś ma jakieś sugestie to z chęcią wysłucham :)

Uwzględnianie zwrotów nie ma sensu. Interesują nas tylko kierunki, które mamy dwa. To czy jakiś statek ustawi się od lewej, czy od prawej nie ma najmniejszego znaczenia!
Poza tym, aby oderwać się na chwilę od tego, co robię aktualnie, napisałem taki kod, korzystając z Twojego @Niko0 pomysłu

Niko0 napisał(a):

poszczególne komórki wypełniać jedynkami - tam gdzie jest statek, ale w tej grze statki nie mogą się stykać burtami, więc statek oznaczyłbym jako 2, a jedynkami otoczył każdy z okrętów.

Sam na początku myślałem o używaniu po prostu booli i sprawdzaniu czy kolejny okręt nie koliduje. ale w przypadku robienia graficznie mapy statki mogą być otoczone inna grafiką, więc przychyliłem się do tej wersji. Kod wymaga poprawek, ale niewiele da się zrobić w piętnastominutową przerwę.

#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

class plansza //jednego gracza
 {
  static const unsigned int liczba_statkow,statki[],bok;
  short unsigned int** const pola;
  void uzupelnij(void); //uzupelnianie planszy statkami
  bool dodaj_statek(unsigned int); //dlugosc statku
  public:
   plansza(void);
   void narysuj(void);
   bool sprawdz_trafienie(unsigned int,unsigned int);
   ~plansza(void);
 };

int main(void)
 {
  srand(time(NULL));
  plansza komputera;
  komputera.narysuj();
  return 0;
 }

const unsigned int plansza::liczba_statkow = 5,plansza::statki[liczba_statkow] = {5,4,3,3,2},plansza::bok = 10;

plansza::plansza(void) : pola(new short unsigned int*[bok])
 {
  for(unsigned int i = 0;i<bok;++i)
   pola[i]=new short unsigned int[bok];
  for(unsigned int i = 0;i<bok;++i)
   for(unsigned int j=0;j<bok;++j)
    pola[i][j]=0;
  uzupelnij();
 }
void plansza::uzupelnij(void)
 {
  //tutaj mozna dodac opcje recznego uzupelniania
  for(unsigned int i=0;i<liczba_statkow;++i)
   while(!dodaj_statek(statki[i]));
 }
bool plansza::dodaj_statek(unsigned int dlugosc_statku)
 {
  bool kierunek = rand()%2; // 1 - pionowy, 0 - poziomy
  unsigned int x = rand() % (( kierunek ? bok : (1+bok-dlugosc_statku))),y=rand() % ( kierunek ?(1+bok-dlugosc_statku) : bok);
  
  for(unsigned int i=0;i<dlugosc_statku;++i)
   if(pola[x+(kierunek?0:i)][y+(kierunek?i:0)]>0)
    return false;

  if(kierunek?y:x!=0)
   pola[x-(!kierunek)][y-kierunek]=1;
  if((kierunek?y:x) + dlugosc_statku < bok)
   pola[x+(kierunek?0:dlugosc_statku)][y+(kierunek?dlugosc_statku:0)]=1;
  for(unsigned int i=0;i<dlugosc_statku;++i)
  {
   pola[x+(kierunek?0:i)][y+(kierunek?i:0)] = 2;
   if(kierunek?x:y > 0)
    pola[x-(kierunek)+(kierunek?0:i)][y-(!kierunek)+(kierunek?i:0)] = 1;
   if((kierunek?x:y)+1<bok)
    pola[x+(kierunek)+(kierunek?0:i)][y+(!kierunek)+(kierunek?i:0)] = 1;
  }
  return true;
 }
void plansza::narysuj()
 {
  for(unsigned int i = 0;i<bok;++i,printf("\n"))
   for(unsigned int j=0;j<bok;++j)
    printf("%c ",(pola[i][j])==2?'X':'-');
 }
bool plansza::sprawdz_trafienie(unsigned int x,unsigned int y)
 {
  return (pola[x][y]==2);
 }
plansza::~plansza(void)
 {
  for(unsigned int i = bok;i--;)
   delete[] pola[i];
  delete[] pola;
 }

Jak widać nie skupiałem się tutaj na wykorzystaniu za wszelką cenę wylosowanego punktu. Nie ma to większego sensu, każda pozycja (dopuszczalna przez grę) jest dobra. Jeśli nie trafiłem, losowałem ponownie, a nie przekształcałem to, co już miałem.

Niko0 napisał(a):

Teraz zostaje najtrudniejsza część, czyli inteligentne strzelanie przez komputer :). Chodzi o to, żeby po trafionym strzale dalsze trafienia szły jeden po drugim, w danym kierunku. Jeśli ktoś ma jakieś sugestie to z chęcią wysłucham :)

Nie jest to wcale takie trudne. Ogólnie to robisz planszę graczowi (komputerowi), na której zaznacza gdzie już strzelił. Na początku te strzały odbywają się w pełni losowo, ale jeśli trafią na już użyte pole, jest losowane kolejne (komputer nie zgłasza, że chce strzelać ponownie w użyte miejsce). Dodatkowo, gdy już trafisz jakiś statek to sprawdzasz (kolejnymi strzałami), w którym kierunku jest on ustawiony i strzelasz, aż go zatopisz. Możesz sprawdzać, czy zakończyłeś zadanie poprzez upewnienie się, że strzały na jedną i na drugą stronę trafiają w wodę, ale lepszym rozwiązaniem (jeśli to możliwe) jest upewnianie się na podstawie statków będących w grze. Jeśli najdłuższy grający aktualnie statek przeciwnika ma długość 4 i Ty właśnie trafiłeś 4. sektor, wiesz, że cały okręt zatonął. Ponadto, jeżeli statek zetknie się z polem, na którym statku nie ma (wiesz to już, np. strzeliłeś tam) to też nie ma sensu ciągnąć w tą stronę tego okrętu. Dodatkowo należy pamiętać, że na około statków (przed, za i obok, w sumie 2(n+1) pól wody) nie może być innych statków, więc i tam nie należy oddawać strzałów (jak już zestrzelisz statek to otaczasz go polami, w które też nie będziesz strzelał). Może jak znajdę chwilę to i to napiszę.
Komunikację "komputera z planszą" przeprowadzałbym tylko przez taką funkcję jak w moim kodzie sprawdz_trafienie.
PS
Oczywiście przeciwnik nie powinien mieć możliwości wyświetlania sobie planszy (nieswojej) ;). Po fazie testów ta opcja powinna zniknąć.

Zauważ jak ja to robię: Używam 4 różnych stron, gdyż losuję jeden punkt i później dopiero idę od tego punktu w jedną ze stron. Można by było zrobić tylko 2 kierunki, ale wtedy trzeba częściej losować współrzędne, bo zakładając, że na przykład wypadnie 1 rząd i 5 kolumna, a ustawiałbym począwszy od tego punktu do góry, to trzeba by było losować jeszcze raz, a tak mogę pójść jeszcze od tego w dół.

Zrobiłem to w ten sposób i rozmieszczenie działa dość sprawnie.

Co do strzałów, to opisałeś mi zasady gry. To wszysto wiem jak ma działać. Problem jest z rozwiązaniem programowym, np. z tym, żeby strzelał w tym samym kierunku, aż do zatopienia. Trochę się trzeba będzie z tym pobawić.

Nie koniecznie rozwiązanie @Tacet'a jest mniej wydajne - najpierw dajmy na to losując 4-masztowca wybierasz kierunek (w prawo lub górę) np. prawo i zwróć uwagę, że nie musisz losować x od 0-9 tylko od 0-6 w ten sposób nie musisz sprawdzać czy statek nie wyszedł poza mapę, y dla kierunku poziomego losujesz już dla całości czyli 0-9.