Gra Bingo Na Arduino Uno R4 i nie tylko

[fReLpl]

To świetna rozrywka i wspólna zabawa z przyjaciółmi oraz rodziną — bez wszechobecnego telefonu na stole. Wystarczy mała płytka Arduino, zasilacz i odrobina miejsca, a klasyczna gra wraca do łask w wersji „retro-tech”.

Kilka słów o zasadach Bingo (wariant 75)

W tej wersji Bingo losuje się liczby od 1 do 75. Gracze mają karty 5×5 z nagłówkiem B-I-N-G-O, gdzie każda kolumna ma przypisany zakres: B: 1–15, I: 16–30, N: 31–45, G: 46–60, O: 61–75. Zwykle środkowe pole jest „FREE” (pole darmowe). Prowadzący losuje kolejne liczby, a gracze je zakreślają. Wygrywa osoba, która jako pierwsza ułoży ustalony wzór (np. linia pozioma/pionowa/ukośna).

Na czym polega projekt?

Projekt to generator liczb Bingo uruchamiany na Arduino UNO R4 WiFi, wykorzystujący wbudowaną matrycę LED 12×8 do wyświetlania wylosowanych liczb.
Kod źródłowy (na podstawie repozytorium):
https://github.com/MariuszFerdyn/Bingo-Game-For-Arduino-UNO-R4

Najważniejsze cechy działania:

• losowanie liczb 1–75 bez powtórzeń (każda liczba może paść tylko raz w danej grze),
• efekty wizualne przejść (miganie, „fade in/out”), przewidziany jest też sygnał ostrzegawczy na diodzie przed zmianą liczby,
• animacje przewijanych napisów na starcie oraz komunikat końcowy w kilku językach po wylosowaniu wszystkich liczb.

Od strony implementacji logika jest prosta i niezawodna: program prowadzi tablicę stanów (zajętości) dla liczb 1–75, a każdorazowe losowanie wybiera tylko te liczby, które nie zostały jeszcze użyte. Dzięki temu odpada ręczne pilnowanie „czy to już było”.

Co ważne: tytuł „…i nie tylko” nie jest przypadkowy. Mechanizm losowania i kontroli powtórzeń jest przenośny, natomiast na innych płytkach trzeba jedynie zmienić warstwę prezentacji (np. użyć wyświetlacza OLED/LCD zamiast wbudowanej matrycy UNO R4).

Przebieg gry na urządzeniu

Po uruchomieniu układ przechodzi sekwencję startową (powitanie i odliczanie), a następnie wyświetla kolejne liczby w cyklu czasowym. Domyślnie jedna liczba jest prezentowana przez ok. 13 sekund z etapami „fade in”, stanem stałym i „fade out”, a pomiędzy liczbami jest krótka przerwa z wygaszoną matrycą. Parametry czasu można łatwo dostroić stałymi w kodzie (czas wyświetlania, przerwy, długość efektów).

Użyte podzespoły

Arduino UNO R4 WiFi

Zasilacz justPi 12V/2,5A do Arduino

(Opcjonalnie, dla lepszego „klimatu” gry) Moduł z buzzerem aktywnym z generatorem

Dla innych Arduino wyswietlacz LED

Jeden film dostarczy więcej informacji niż tysiące słów i zdjęć: 

Kod projektu: https://github.com/MariuszFerdyn/Bingo-Game-For-Arduino-UNO-R4/tree/main

Karty Bingo do wydruku: https://github.com/MariuszFerdyn/Bingo-Game-For-Arduino-UNO-R4/blob/main/bingo_100_cards.md

[borabora]

Pokazałeś, że te wyświetlacze w nowych Arduino jednak do czegoś się nadają 

Patrząc na kod, można pokusić się o jego optymalizację.

int getNextNumber() {
  if (numbersRemaining == 0) return 0;
  
  // Generate random number that hasn't been used
  int num;
  do {
    num = random(1, 76);
  } while (usedNumbers[num]);
  
  usedNumbers[num] = true;
  numbersRemaining--;
  
  // Store the number in draw order
  drawnNumbers[drawCount] = num;
  drawCount++;
  
  return num;
}

W funkcji pseudolosującej, gdy zostało np. 4 wolne numery, prawdopodobieństwo, że zostaną trafione wynosi 1 do 19, czyli może się zdarzyć, że pętla do-while wykona się 20 razy. Niby to niewiele, ale można łatwo to zoptymalizować, żeby trafiać zawsze za pierwszym razem używając 

random(1, numbersRemaining);

następnie iterując po tablicy znajdywać i-ty wolny numer. 

Edytowano 3 lutego przez borabora

[H1M4W4R1]

39 minut temu, borabora napisał:

W funkcji pseudolosującej, gdy zostało np. 4 wolne numery, prawdopodobieństwo, że zostaną trafione wynosi 1 do 19, czyli może się zdarzyć, że pętla do-while wykona się 20 razy. Niby to niewiele, ale można łatwo to zoptymalizować, żeby trafiać zawsze za pierwszym razem używając 

random(1, numbersRemaining);

następnie iterując po tablicy znajdywać i-ty wolny numer. 

Nadal wolno... tym razem w przypadku losowania początkowych numerów (jak wylosujesz np. 50, 51 i 49 w trzech losowaniach to policz sobie cykle, które zmarnujesz na iterację).

Lepiej zrobić tablicę bajtów i przetasować ją na starcie. Potem odczytać pierwszy numer i przenieść na "koniec" tablicy (swap z numerem numbersRemaining-1), a jak licznik zejdzie do zera możemy też przetasować tablicę ponownie i zresetować licznik do pełnej wartości tym samym usuwając przypadek gdy zużyliśmy wszystkie numery. Czas dostępu O(1) dla 74/75 przypadków i O(n) dla pozostałych.

[borabora]

9 minut temu, H1M4W4R1 napisał:

Nadal wolno... tym razem w przypadku losowania początkowych numerów (jak wylosujesz np. 50, 51 i 49 w trzech losowaniach to policz sobie cykle, które zmarnujesz na iterację).

Funkcja random() nie zajmuje jednego cyklu maszynowego, jak to wygląda w praktyce możesz zobaczyć tutaj. Dodatkowo w funkcji random(1, n) używany jest operator modulo, który jest jednym z kosztowniejszych.
Ile dokładnie może to zajmować, nie wiem, ale intuicja mi mówi, że nawet pesymistyczny przypadek w postaci Iteracji po całej tablicy będzie bardziej optymalny niż "losowanie do skutku".

 

14 minut temu, H1M4W4R1 napisał:

Lepiej zrobić tablicę bajtów i przetasować ją na starcie.

 Samo się nie przetasuje i w każdym przypadku sprowadza się to do wygenerowania permutacji bez powtórzeń. Tej jednej, (pseudo)losowo wybranej ze wszystkich n!.

[ethanak]

21 minut temu, borabora napisał:

Samo się nie przetasuje

No i dlatego @H1M4W4R1 napisał żeby przetasować. A to akurat jest proste, coś w stylu:

void init_t(uint8_t t, int cnt)
{
  int i,n;
  for (i=0;i<cnt;i++) t[i]=i+1;
  for (i=0;i<cnt;i++) swap(t[i],t[random(cnt)]);
}

...

#define COUNT 75
uint8_t tablica[COUNT];

 init_t(tablica, COUNT);

czy jakoś tak - przykład ze starego dobrego podręcznika Icona:

every !t :=: ?t;

 

Edytowano 3 lutego przez ethanak

[borabora]

Tylko co takie wstępne przetasowanie wprowadza? To jest ta sama złożoność tylko rozłożona w czasie. 
I pojawia się istotne pytanie o rozkład prawdopodobieństwa takiego tasowania, bo losujesz za każdym razem element z całego zbioru.

Jak iterowanie po tablicy 76-elementowej jest problemem, można użyć struktury zbioru, np implementując na liście opartej o tablice statyczne.

Edytowano 3 lutego przez borabora

[ethanak]

12 minut temu, borabora napisał:

I pojawia się istotne pytanie o rozkład prawdopodobieństwa takiego tasowania, bo losujesz za każdym razem element z całego zbioru.

No i co z tego? 

[fReLpl]

Ale w ten sposób co jest liczby są bardziej losowe;)   Aczkolwiek zgadzam się można optymalizować. Proponuję pull-request.

[borabora]

24 minuty temu, ethanak napisał:

No i co z tego? 

To, że raz zrobisz swapa 1 z 5 i za chwile zrobisz swapa 5 z 1, taki "przypadek" 

[ethanak]

No i co z tego? Czy w losowym ciągu liczba n nie może wystąpić na pozycji n? Czy jeśli tasujesz karty to dwójka trefl nie może być na dole?

[borabora]

6 minut temu, ethanak napisał:

No i co z tego? Czy w losowym ciągu liczba n nie może wystąpić na pozycji n?

Oczywiście, że może. Tylko w metodzie którą pokazałeś, jest szansa, że swapowane będą ciągle te same indeksy przez to nie dostaniesz poprawnego rozkładu.

[ethanak]

Udowodnij to.

[borabora]

Przed chwilą, ethanak napisał:

Udowodnij to.

Co mam udowadniać?

[ethanak]

No to że mój algorytm jest niepoprawny bo to mi zarzucasz.

[borabora]

Porównaj sobie z Knuth Shuffle, tam jest ograniczenie losowania - nie powinieneś losować za każdym razem z zakresu cnt tylko do i.