Snake - problem z losowaniem współrzędnych owoca

Hej,
z powodu tematu na forum, który dotyczył umiejętności zrobienia Snake'a, zaklepałem sobie na szybko prostą, konsolową implementacje. Zachciało mi się jednak trochę rozbudować projekt i dodałem parę rzeczy.
Potrzebowałem między innymi metody, która mi losowo ustawi miejsce owocu, więc napisałem coś takiego.

void setFruit()
     {
         using randoms = std::uniform_int_distribution<std::mt19937::result_type>;
         std::random_device rd;
         std::mt19937 rng(rd());
         randoms dist(1, width - 1);
         randoms dist2(1, height - 1);
         auto x1 = dist(rng);
         auto x2 = dist2(rng);
         fruitX =  static_cast<int>(x1);
         fruitY = static_cast<int>(x2);
     }

Niestety nie rozwiązało to problemu do końca, ponieważ czasem owoc pojawiał się w miejscu, gdzie aktualnie znajdował się wąż(dajmy na to wąż to - - - - -, a owoc &, czasem po losowaniu pojawiało się coś takiego --&----.

Skorzystałem z biblioteki standardowej i pojawiło się coś takiego:

void setFruit()
     {
         using randoms = std::uniform_int_distribution<std::mt19937::result_type>;
         std::random_device rd;
         std::mt19937 rng(rd());
         randoms dist(1, width - 1);
         randoms dist2(1, height - 1);
         auto x1 = dist(rng);
         auto x2 = dist2(rng);
        
         while (std::find(tailsX.begin(), tailsX.end(), x1) != tailsX.end())
             x1 = dist(rng);

         while (std::find(tailsY.begin(), tailsY.end(), x2) != tailsY.end())
             x2 = dist2(rng);
             
         fruitX =  static_cast<int>(x1);
         fruitY = static_cast<int>(x2);
     }

powyższego bugu już nie ma i losowanie odbywa się prawidłowo - natomiast teraz w pewnym momencie program się wysypuje i gra stoi w miejscu, wciskanie dowolnego klawisza sprawia, że jest on wypisany na konsoli, a wąż pozostaje bez ruchu. Zastanawiam się gdzie może tkwić problem?

Oczywiśćie tailsX i tailsY to std::vector.

Czy Twój program zawiesza się w momencie, gdy wąż zajmuje całą wysokość lub szerokość planszy i zjesz owoc?

No właśnie nie - nie ma reguły. Raz jest to przy długości 5(startujemy od 1, z każdym zjedzeniem owocu dlugosc zwiększa się o 1), a raz przy 20.

Przykładowy screen:

Problem rozwiązany. Dziękuję @Burmistrz

zmiana pętli na

while (std::find(tailsX.begin(), tailsX.end(), x1) != tailsX.end() &&
                std::find(tailsY.begin(), tailsY.end(), x2) != tailsY.end()) {
                
             x1 = dist(rng);
             x2 = dist2(rng);
         }

przyniosła efekt. :)

E: jednak problem dalej jest obecny:

Powinieneś porównywać obie współrzędne owocu po kolei z każdym fragmentem węża. Wydaje mi się, że teraz po prostu wykluczasz cały prostokąt, w którym znajduje się wąż. Na obrazku ze zrzutem ekranu prostokąt, który zajmuje wąż, zajmuje całą planszę, więc owoc nie może się nigdzie pojawić.

Napisałem prostą klasę dla punktu:

struct Point {
    int x,y;
    Point() : x(0), y(0){}
    Point(int _x, int _y) : x(_x), y(_y){}
    bool operator ==(const Point& p) const {
        return x == p.x && y == p.y;
    }
    void set(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

a potem zmieniłem funkcję losującą tak:

void setFruit()
     {

         using randoms = std::uniform_int_distribution<std::mt19937::result_type>;
         std::random_device rd;
         std::mt19937 rng(rd());
         randoms dist(0, width - 1);
         randoms dist2(0, height - 1);
         auto x1 = dist(rng);
         auto x2 = dist2(rng);
         Point p(static_cast<int>(x1),static_cast<int>(x2));
         std::vector<Point> points(tailsX.size());
         for (vSize i = 0; i != tailsX.size(); ++i) {
             points[i] = Point(tailsX[i], tailsY[i]);
         }
         while ((std::find(points.begin(), points.end(), p) != points.end())) {
             x1 = dist(rng);
             x2 = dist2(rng);
             p.set(static_cast<int>(x1),static_cast<int>(x2));
         }


         fruitX =  static_cast<int>(x1);
         fruitY = static_cast<int>(x2);
     }

i wszystko działa jak należy. :)

Edit: Oczywiście, klasa Point jest totalnie zbędna, bo to samo można uzyskać przy użyciu std::pair<int,int>. No i właśnie przy tej wersji pozostałem.

Łatwiej by Ci było, gdybyś miał dodatkowo wektor punktów z wolnymi miejscami na planszy. Wiele ich nie będzie – w końcu konsola to niewielka siatka znaków. Zamiast w pętli na pałę losować punkt i sprawdzać czy wskazuje na puste miejsce czy nie, losuj indeks punktu w wektorze, następnie pobierz te współrzędne i usuń punkt z wektora.

Aby to zadziałało, po każdym ruchu usuwaj z tego wektora nowy punkt głowy i dodawaj do niego stary punkt ogona. Wyjątkiem jest klatka, w której wąż zjada owoc – wtedy nie modyfikuj wektora w ogóle.

Tradycyjne losowanie współrzędnych na planszy w większej części pokrytej przez węża, może równie dobrze trwać w nieskończoność, zawieszając grę. Sposób opisany wyżej zapewni stałą złożoność losowania, nie dopuszczając do takich zwiech. Będziesz mógł pokryć wężem calutką planszę, bez żadnych strat czasowych.

To już na jutro, ciężka głowa po weselu nie sprzyja przesiadywaniu nad nowymi rozwiązaniami.

Tak swoją drogą, napomknę jeszcze, że odchudziłem kod, po przez pozbycie się dwóch vectorów dla X i Y, std::vector<std::pair<int,int>> jest dużo lepszym rozwiązaniem. :)

Skoro problem rozwiązany to dorzucę od siebie:

klasa Point jest totalnie zbędna, bo to samo można uzyskać przy użyciu std::pair<int,int>

Dla czytelności zdecydowanie lepsza jest nazwana klasa, a nie generyczna para.

using randoms = std::uniform_int_distribution<std::mt19937::result_type>;

Klasy uniform_x_distribution liczą na docelowy typ, źródłowy dedukują sobie z podanego im rng/prng.

kq napisał(a):

Dla czytelności zdecydowanie lepsza jest nazwana klasa, a nie generyczna para.

ale więcej kodu, a w założeniu było uszczuplenie tego. :D

kq napisał(a):

using randoms = std::uniform_int_distribution<std::mt19937::result_type>;

Klasy uniform_x_distribution liczą na docelowy typ, źródłowy dedukują sobie z podanego im rng/prng.

Racja. Nie wiem czemu się tak samoistnie zjadłem tym. Poprawione, dzięki. :)