Witam mam gre 2D i chce zrobić system kolizji (wejście na pole jest zablokowane) i mam problem ze za nic nie moge tego zrobić więc pomyślałem ,że zapytam się tutaj więc tak, mam baze mysql o nazwie kolizje a w niej pola

mapa | x | y |
1 | 5 | 4 |
1 | 6 | 4 |

i teraz mam mape :

( x y)

x x x x x x
y 1x1 | 1x2 | 1x3 | 1x4 | 1x5 | 1x6 .... 1x15
y 2x1 | 2x2 | 2x3 | 2x4 | 2x5 | 2x6 .... 2x15
y 3x1 | 3x2 | 3x3 | 3x4 | 3x5 | 3x6 .... 3x15
y 4x1 | 4x2 | 4x3 | 4x4 | 4x5 | 4x6 .... 4x15
y 5x1 | 5x2 | 5x3 | 5x4 | 5x5 | 5x6 .... 5x15
y 6x1 | 6x2 | 6x3 | 6x4 | 6x5 | 6x6 .... 6x15

i w bazie chce zablokowac aby nie można bylo wejsc na x-5 y-4 oraz x-6 i y-4

jeszcze aby nei było dam to co zrobiłem ostatnio

[PHP] pobierz, plaintext 
if($row['x'] + 1 == $user['x'] and $row['y'] == $user['y']){
 // funkcja nei zostanie wykonana
}else{
 // funkcja jest wykonana
}
[PHP] pobierz, plaintext 

prosze o pomoc =]

Jest wiele rozwiązań Twojego problemu.
Na przykład:
Gracz jest na pozycji 5x3 i wykonuje ruch w dół - następna pozycja to 5x4 (jeszcze gracza tam nie przemieszczasz). Wiesz, że numer mapy na której się znajduje to 1, więc mając potrzebne dane pierw odpytujesz bazę danych [np. SELECT * FROM kolizje WHERE x=5 AND y=4 AND map=1], jeśli wynik będzie pozytywny (czyli odnajdzie w spisie kolizji szukane pole) to po prostu nie zmieniaj pozycji gracza. Analogicznie, kiedy nic nie znajdzie w bazie - zmień jego pozycję.

Innym przykładem może być mapa w bazie danych opisana jakimiś symbolami - coś na styl gier rougelike. Wtedy na podstawie symbolu określasz czy może na niego stanąć, czy nie.

Ja miałem podobny zgryz z kumplem gdy robiliśmy na algorytmy genetyczne, kilka dobrych lat temu, ruch konia szachowego (może stanąć na każdym polu tylko raz) i wynikł nam problem krzyżowania oraz mutacji. Nie mogliśmy kodować pól, ponieważ po tych operacjach ruch konia nie był zachowany. Rozwiązaliśmy więc to kodując ruch konia, a więc cały genotyp składał się z 63 posunięć konia, które zawierały się w 8 możliwościach ruchu z każdego pola. Jak widać, czasem koń nie miał możliwości ruchu, bo trafiał na pole już odwiedzone lub chciał wyskoczyć poza plansze.

Tu nam pomogło odpowiednie przemyślenie sytuacji. Potraktowaliśmy całe pole szachownicy jako macierz i "dołożyliśmy" poza krawędziami pola tak, by teoretycznie można było je ruchem konia odwiedzić, ale dopisaliśmy do funkcji celu, że są one z automatu zabronione i odwiedzenie ich kończy obliczanie wyniku dla owej funkcji. W ten sposób powstała nam szachownica 12x12 gdzie środkowe 8x8 było odwiedzalne i ponumerowaliśmy, idąc wierszami, od 1 do 144, licząc od górnego lewego. Każdy z 8 dostępnych skoków koniem opisaliśmy jako operację dodawania lub odejmowania określonej liczby od obecnego pola, która to dawała pole na które skacze się. W ten sposób plansza dwuwymiarowa, stała się wektorem, a ruchy prostym dodawaniem lub odejmowaniem.

Ty w swoim przypadku masz planszę 6x15, więc zrobiłbyś 8x17 ze skrajnymi wierszami i kolumnami zablokowanymi. Popatrz jak wygląda skok na pola sąsiednie, a zauważysz ile trzeba dodawać lub odejmować by uzyskać określony ruch. Możesz teraz pewne pola "zablokować". Przykładowo x-5, y-4 to 17*4+5*1+1 = 74 i teraz jeśli ruch z jakiegoś pola ma się zakończyć na polu 74, uznajesz ten ruch za niedozwolony. Co ciekawe... Nie musisz nigdzie trzymać "obrazu" mapy Znasz bowiem jej matematyczny model i wiesz że pewne pola są niedostępne, na innych coś tam masz, a na określonym stoisz. Jedyne więc co Ci jest potrzebne to... numer pola na jakim stoisz, operacje sumowania lub odejmowania odpowiedzialne za ruchy w każdym kierunku (też masz ich 8, bo w 4 strony świata i 4 na ukos) oraz tablica pól niedostępnych, lub jeśli tych jest więcej niż połowa -> tablica pól dostępnych.

W ten sposób możesz w zasadzie całą główną planszę wrzucić do cache'u. Rzeczy dostępne globalnie też możesz łatwo tam wrzucać lub usuwać, a jeśli coś jest tylko dla konkretnej osoby, to zapisujesz tylko numer pola na mapie (i co to jest) jako widoczne tylko w instancji gry gracza i niejako jego własnym "wektorze". Likwidujesz masę zapytań, a masz dostęp niemal w czasie rzeczywistym i ograniczeniem jest jedynie szybkość łącza.

Grę w ten sposób sprowadzasz z 2D do 1D, a ruchy do banalnego dodawania i odejmowania, których możesz w ciągu sekundy przeprowadzić tysiące. To jest właśnie coś, czego trzeba się z czasem nauczyć. Widzieć rzeczy trudne w sposób prostszy. Do tego jednak już spryt, logika i szczypta matematyki jest potrzebna oprócz pomysłu.

@thek, bardzo ciekawe (choć nie bardzo wiem skąd w tym x-5, y-4 to 17*4+5*1+1 = 74 jest 5*1), to jednak najprostrze rozwiązanie zaproponował @ethann. A jeżeli danego pola nie ma w bazie (np 16-1) to można uznać domyślnie że jest zablokowane.

Skąd? Popatrz na swoje współrzędne. Skoro x = 5, y = 4, wielkość planszy w poziomie to 15 kolumn, poziomie to 6 wierszy, to wychodzi nam plansza o faktycznej wielkości 17 kolumn i 8 wierszach. Teraz punkt (5,4) . Wiersz 4 ma pod sobą 3 wiersze realne i jeden zablokowany, wszystkie o szerokości 17 kolumn, z kolei 4 kolumna to 4 kolumny + 1 kolumna dodatkowa. Z tego wychodzi nam, że numer pola to zawsze według wzoru:

gdzie:
x - numer kolumny,
y - numer wiersza.
Podstawiając więc do wzoru przykładowo:
Pole w grze ma:
- 20 kolumn x 30 wierszy
- punkt postaci to (5,9)
Co nam to daje? Wszystko co chcemy.
Plansza realna zamienia się nam na 22 kolumny i 32 wiersze, czyli możemy policzyć pozycję startową
nr = 9 *22 + 5 + 1 = 204

Jeśli przypatrzymy się numeracji pól wokół niego to uzyskamy taki widok:

A z tego można łatwo zauważyć jaki ruch to jaka operacja, gdyż zawsze to końcowe pole odjąć startowe:

W lewo w górę: 181 - 204 = -23
W górę: 182 - 204 = -22
W prawo w górę: 183 - 204 = -21
W lewo: 203 - 204 = -1
W prawo: 205 - 204 = 1
W lewo w dół: 225 - 204 = 21
W dół: 226 - 204 = 22
W prawo w dół: 227 - 204 = 23

Popatrz na to, na wielkości planszy i zauważ prostą rzecz...

W lewo w górę => - ilość_kolumn_w_wierszu - 1
W górę => - ilość_kolumn_w_wierszu
W prawo w górę => - ilość_kolumn_w_wierszu + 1
W lewo => -1
W prawo => +1
W lewo w dół => ilość_kolumn_w_wierszu - 1
W dół => ilość_kolumn_w_wierszu
W prawo w dół => ilość_kolumn_w_wierszu + 1

Masz zdefiniowane wszystko: operacje będące ruchami, wielkość planszy, numeracje pól. Czego chcieć więcej? Jedyne co potrzebujesz do wygenerowania plansz to:
- znać ich wielkość bazową,
- wiedzieć co jest na jakim polu,
- jakie numery pól są zablokowane.

Dlaczego tak? Ponieważ w bazie nie musisz już rozwalać wszystkiego na macierze.
Zamiast zapisywać punkty w formie układu współrzędnych w postaci (x,y) masz jedną liczbę. Możesz mieć ogrom plansz, które przechowują informacje w postaci: numer_planszy, numer_pola, id_obiektu zamiast rozbijać numer_pola na dwie składowe.

Co nam to daje przykładowo? Zaprezentuję prostym przykładem. Mamy już wygenerowaną "mapę" i teraz pewne pola wrzucamy do tablicy $forbidden, która przechowuje pola na które nie można wejść. Sposób sprawdzenia banalny... Próbujemy wykonać "operację ruchu" i sprawdzamy czy wynik jest w tej tablicy (zwykłe użycie in_array) jeśli tak - robimy ruch. Ba... Możemy na planszy umieszczać przedmioty interaktywne. Jak? Robimy tablicę $interaction (lub $objects jak kto lubi), której klucz to numer pola, a wartość to tablica przedmiotów jakie się na tym polu znajdują. Jaki plus użycia obu? Pola zabronione też mogą przechowywać przedmioty, które są... elementami otoczenia (skały, drzewa). Używając stałych i określonych identyfikatorów, można wstawić do grafiki pola grafikę owego przedmiotu. Mogą też niektóre obiekty stanowić portale między mapami. Masz więc maksymalnie uproszczone operacje do: dodawania, odejmowania, prostego wyszukiwania tablicowego po wartościach lub kluczach. Cały świat można tak "narysować". Bo jakie masz ograniczenie int? Nawet 10k na 10k nie wyczerpuje go A nie sądzę, byś tak ogromne plansze robił. Poza tym jak wyobrażasz sobie sprawdzanie pola w układzie kartezjańskim? Musiałbyś stworzyć obraz planszy i wszystkich jej pól by potem sprawdzać owe pola z możliwością ruchu. Zamiana na wektor sprawia, że przechowujesz jedynie informację o niezbędnych polach, czyli takich gdzie coś jest lub zabronionych dla ruchu. Tych będzie o niebo mniej.

EDIT: Poza tym zobacz co w bazie robisz za bałagan... Jeśli w bazie nie ma pola, to jest ono zablokowane? A co z polami pustymi, gdzie można przejść, ale nie ma nic? W bazie masz tak więc pola, które są puste i do niczego nie służą, tyko po prostu są, bo nie mogą być zablokowane. Jeśli masz na planszy duże, puste przestrzenie, masz ogrom takich pól w bazie. Jeśli byłby z kolei "zapchane" plansze, to byłoby dużo pól w bazie. I tak źle, i tak niedobrze. Ale prędzej będzie wariant z dużą ilością wolnych. No chyba, że zrobisz ścieżkę jedyną słuszną przez las czy w górach
Zauważ też, że zablokowane pola też zazwyczaj są czymś zapełnione i to też musi gdzieś być przechowane. Powstaje Ci więc tylko tak naprawdę utworzenie 3 tabel:
- Board: id, width, height
- Items: id, forbidden
- Fields_to_item: board_id, field_id, item_id
No i oczywiście reszta już zależna od tego co chcesz robić. Mogą to być tabele właściwości przedmiotów, ekwipunku, graczy itp.

@thek: ładne rozwiązanie

Jedyną zaletą rozwiązania theka jest to, że pola mają jedną współrzędną zamiast dwóch. Tworząc klucze w bazie danych, nijak odbija się to na wydajności. Tak samo tworząc tablice w samym php, klucze tablic mogą być w postaci stringów i wyglądać np. '100x92'. Natomiast ma ono dwie główne wady. Pierwsza to czytelność dla nas samych. Mając planszę szeroką na 97 pól i mając podaną liczbę 782, ciężko powiedzieć w którym miejscu znajduje się to pole. Drugą wadą jest elastyczność. Przy każdorazowej ewentualnej zmianie wielkości planszy, wszystkie pola i powiązania trzeba przenumerować. Ten problem nie obowiązuje przy numerowaniu dwoma współrzędnymi. Rozwiązanie ethanna wygląda najprościej, jest możliwa prosta rozbudowa, jest czytelne dla nas i na pewno wydajne (nie zapominając o kluczach w bazie danych).

@franki:
Problem w tym, że nie wszystko może być indeksem tablicowym w php. Poza tym jeśli już chcesz takie coś zrobić jak klucze pokroju '100x92' to masz tylko utrudnienie wykonywania operacji przemieszczania czy wyszukiwania. Czemu? Klucz obecny zrobić explode po x, zmienić jedną lub obie współrzędne odpowiednio do ruchu, skleić, sprawdzić nową pozycję. W porównaniu do operacji + lub - jakaś liczba masz naprawdę więcej roboty. A takich operacji będzie po prostu ogrom, jeśli spróbujesz to zrobić w miarę płynne.

Trudno sprawdzić pozycję pola? Numer podzielić przez szerokość planszy + 2, dd reszty odjąć 1 i mamy pozycję Poza tym jako użytkownik skryptu wcale nie musisz wiedzieć i znać reprezentacji "backendowej". Można ją prosto konwertować z jednej formy w drugą. Jest to wręcz zaleta, gdyż domorosłych "haXoruff" można prosto zmylić. Przesyłasz bowiem ruch i pola w notacji niemacierzowej, którą dopiero muszą rozkminiać. A że plansze są o różnych rozmiarach to co planszę mają zonka, bo im wyliczenia z planszy X nie będą pasowały do planszy Y.

W sytuacji gdy na planszy może być mnóstwo obiektów, pomyśl też o wielkości indeksu, który NIE jest ustawiony na unique (bo może być kilka obiektów na tym samym polu), ale jest indeksem założonym na 2 (lub 3 jeśli dodamy id planszy) kolumny by wydajność zwiększyć. W chwili gdy obiekty co chwilę są dodawane i usuwane, ostro latamy z modyfikacjami indeksu tabeli, co ma wysokie koszty po stronie silnika bazy.

Brak elastyczności przy zmianie wielkości planszy? Skądże. Przenumerowanie to będzie kwestia prostej matmy, która nam tylko dzielenie zrobi i doda odpowiednie liczby. Reindeksacja nie jest więc problemem i na dodatek skrypt sobie do tego możesz zrobić, który zrobi to za Ciebie. To prosta matma do machnięcia jako procedura składowana w bazie co będzie niezwykle szybkie. Podajesz jako parametry numer planszy, nowe wymiary i wszystko się "samo" zreindeksuje, włącznie z indeksami przedmiotów. Już nawet nie wspominam, że zawsze możesz "rozszerzenie" planszy potraktować jako osobną planszę. Argument więc nie jest więc jak dla mnie aż tak poważny jak można by myśleć.

Tak więc to co na pierwszy rzut oka wydaje się nieprzejrzyste, z biegiem czasu i wzrostem złożoności oraz ilości plansz nie staje się trudniejsze do obsługi. Jedynie gdy patrzysz na to z poziomu bazy bezpośrednio, możesz nie widzieć co jest obok czego, ale spójrzmy prawdzie w oczy... nikt nie będzie budował plansz wklepując odpowiednie rzeczy na pałę w bazę. Zrobi sobie do tego edytor graficzny i będzie wszystko wyklikane. W takiej sytuacji sposób notacji na zapleczu jest nieistotny, ale pod względem wydajności może to już być różnica. Zresztą nawet gdyby... reindeksacja jak często byłaby wykonywana? Przecież nie co 10 sekund.

Zwróć też uwagę, że czytelność to pojęcie względne. Macierz wydaje się prosta, ale obsługa kluczy w samej grze jest prostsza na intach, na których prościej operować. Idąc dalej, musisz przecież posłużyć się jakimś językiem po stronie przeglądarki. JS taki naturalny się wydawałoby, nie ma fajnej i prostej obsługi tablic asocjacyjnych, tak jak jest w php - JS trochę tu kuleje, ponieważ klucz tablicy asocjacyjnej w JS sam jest obiektem i różne operacje przeprowadzone nieumiejętnie mogą dać naprawdę nieoczekiwane rezultaty dla początkujących. Za to tablice z indeksami numerycznymi chodzą jak marzenie.

Sposób jaki podałem jest matematycznie prosty i pozwala w zasadzie do postaci wektora sprowadzić także przestrzeń o dowolnym wymiarze, między innymi 3D. Już ja widzę próbę zapisu wszystkich pól przestrzeni 3D metodą podaną przez kolegę w bazie... Zrobi się po prostu masakra z ogromem pustych punktów zajmujących i obciążających indeks.

Oczywiście nie upieram się, że moje rozwiązanie jest jedyne i słuszne, ale przedstawiam jedną z możliwych alternatyw dla podanego wyżej rozwiązania, którą można rozważyć i rozpatrzyć. Zresztą konwersja między obydwoma tu podanymi nie powinna być trudna, więc można samemu ją zrealizować i przetestować oraz ocenić co w perspektywie rozwoju da lepsze wyniki. IMHO nie warto nigdy odrzucać czegoś co na pierwszy rzut oka wydaje się dziwne,bo może się okazać, że nie jest tak głupie i nieprzemyślane na jakie z pozoru wygląda. Macierze też mają swoje zalety, ale akurat php z ich obsługą nie jest jakiś super (co innego Matlab), a przecież to język dobiera się do problemu lub tak modyfikuje problem, by pasował dobrze do języka.

Pamiętaj, że macierzy w php też można łatwo używać dopóki korzystamy z indeksów ( przykładowo $tablica[2][5] ), ale już próby operowania na nich często potrafią się skończyć tworzeniem wielu wyspecjalizowanych funkcji jedynie do tego celu. Przykład to wyszukiwanie sąsiednich pól dozwolonych. Zauważ, że niezależnie od ilości wymiarów, zawsze używam w swoim rozwiązaniu funkcji in_array i ona będzie tam niezależnie czy rozwiązanie będzie 2D czy 3D. Dla czytelnego zapisu macierzowego muszę już mieć zdefiniowaną funkcję przeszukującą 2- lub 3-wymiarową macierz po indeksach. Poza tym rozważyć trzeba jeszcze objętość mapy w pamięci przeglądarki przez każde z rozwiązań oraz potencjalne optymalizacje tego stanu. To naprawdę nie jest tak fajne i proste jak się na początku wydaje...

A czy w takich grach nie można by się oprzeć na teorii/algorytmach grafów?Wszakże na szeroką stronę są one wykorzystywane w GPS do wynajdowania najkrótszych możliwych dróg.

@Niktoś: Ja tutaj akurat skupiłem się na zapisie ruchu na sąsiednie pole. Nie wnikałem nawet w algorytmy wyszukiwania drogi z punktu A do B, bo to już byłaby zapewne dla autora tematu "matematyczna masakra całką złożoną" Tutaj już wspomniane przez Ciebie podejścia oczywiście jak najbardziej się sprawdzą w tej roli. Tylko że autor musiałby sobie matmę dyskretną nieco przyswoić. To jest właśnie problem "autorów gier przeglądarkowych". Widzą wszystko, ale gdy przychodzi do implementacji to jest wielki problem, bo zwyczajnie całego aparatu matematycznego nie potrafią ogarnąć. Właśnie dlatego o tych ciutkę bardziej złożonych nawet nie wspominałem, by nie przerazić. Oni zrobią gierkę prostą pokroju BiteFighta czy coś tego typu, gdzie matmy tyle co kot napłakał. Poważniejsze niech zostawią lepiej przygotowanym do tego celu zespołom programistów.