Gra w Statki - Rozmieszczenie okrętów

0

Postanowiłem dla treningu jako początkujący programista napisać grę w statki. Nie mam jednak pomysłu jak rozwiązać problem z losowym rozmieszczaniem okrętów na planszy przez komputer. Plansza do gry to tablica [10][10] początkowo wypełniona zerami. Początkowo myślałem, żeby 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. Jednak punkt byłby przyznawany tylko przy trafieniu w pole z 2. Okręty mają wymiary [5][1], [4][1], [3][1], [3][1], [2][1].
Nie mam zbyt logicznego pomysłu jak to rozmieścić losowo. 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.
Zastanawiałem się też czy ręcznie nie napisać np. 20 przykładowych rozmieszczeń i komputer wybierałby tylko jedną z nich.

Czekam na wasze sugestie i pomysły.

EDIT: Sorry, za poprzednie posty, był jakiś błąd na serwerze i pisało, że post nie został wrzucony.

3

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.

0

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.

0

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.

0

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

0

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

0

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.

0

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

0

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

0
for(statek in statki) {
    int x,y,orientacja;
    do {
        orientacja = rand()%2;
        x = rand()%(orientacja==0?RozmiarPlanszy:(RozmiarPlanszy-statek.rozmiar+1));
        y = rand()%(orientacja!=0?RozmiarPlanszy:(RozmiarPlanszy-statek.rozmiar+1));
    } while (jestKolizjaDla(x, y, orientacja, statek.rozmiar));
    dodajStatek(x, y, orientacja, statek.rozmiar);
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0