Czy sprawiedliwe są losowe punkty odradzania?

Jeśli wszyscy gracze pojawią się na losowych pozycjach w tej samej odległości od sąsiednich graczy, liczba graczy będzie proporcjonalna do prawdopodobieństwa, że ​​ich pozycje odradzania będą niesprawiedliwe. Im bardziej gracze odradzają się na środku mapy, tym bardziej prawdopodobne jest, że spotkają innych graczy i tym mniejsze prawdopodobieństwo, że przeżyją, w porównaniu z graczami na krawędzi mapy. Załóż, że wszyscy gracze są spawnowani jednocześnie.

Czy istnieje sposób na ukształtowanie punktów odradzania lub zmianę mapy, aby:

1. Wszyscy gracze mają ograniczoną liczbę sąsiadujących wrogów.
2. Wszyscy gracze mają równe szanse na spotkanie z sąsiadującymi wrogami.
3. Rozmiar mapy nie musi zwiększać się proporcjonalnie do liczby graczy.
4. Ograniczenia te nie są egzekwowane w przypadku dowolnych nieprzekraczalnych przestrzeni.

Odpowiedź nie musi być idealna, ale oczywiście lepsza niż alternatywa. Po wyjęciu z pudełka mile widziane.

Niech gracze sami wybiorą swoje początkowe lokalizacje.

Na początku gry odradzaj wszystkich graczy na środku mapy, ale bez żadnych obrażeń dla innych graczy. Będą wtedy musieli wylać się i zdobyć środki do wzajemnej walki (zbuduj bazę, podnieś broń, zbierz zasoby itp.)

Do wczesnego znalezienia dobrej lokalizacji początkowej wymagana jest odrobina szczęścia lub znajomość map (w zależności od tego, czy korzystasz z map proceduralnych, czy ręcznie). Ale kiedy i gdzie osiedlić się, jest to głównie decyzja strategiczna. Wcześniejsze wdrożenie daje przewagę czasową, ale stawia Cię w niebezpiecznej pozycji. Staranne wybranie bazy pozostawia cię w tyle we wczesnej fazie gry, ale może być decydującą przewagą w środkowej i późnej fazie gry.

Zrozumienie wymagań

1. Wszyscy gracze mają ograniczoną liczbę sąsiadujących wrogów.

Po pierwsze, mówimy o punktach odradzania się graczy, a nie o bieżącej pozycji graczy w danym punkcie gry. Po prostu usuwam to z drogi.

Przylegający jest dobrze zdefiniowany, gdy mówimy o wykresie. Możemy wymyślić mapę, która reprezentuje nawigację na mapie - odtąd „wykres”.

Jeśli węzeł może mieć co najwyżej jeden punkt odradzania, wówczas mówienie o tym, że są „sąsiadujące” ma sens. Uwaga: nie będę ograniczać węzłów do posiadania jednego pojedynczego punktu odradzania, z powodów, które pojawią się później.

Aby zbudować wykres, musimy wziąć pod uwagę takie rzeczy, jak ściany, mosty, drabiny, punkty teleportacji, a nawet wziąć pod uwagę przestrzeń lotu, jeśli może istnieć gracz, który potrafi latać. Każdy węzeł reprezentuje ruchome położenie; każde połączenie reprezentuje możliwy ruch.

Uwaga: poznaj rozmiar i kształt węzłów i pracuj z faktycznie sąsiadującymi węzłami. Nie uważaj węzłów za punkt. Nie traktuj połączeń jako posiadających długość. Użyj również wypukłych węzłów.

Wykres mógł zostać wstępnie skompilowany (mapa została stworzona przez projektanta); w przeciwnym razie można go utworzyć w locie, jeśli mapa jest generowana losowo.

2. Wszyscy gracze mają równe szanse na spotkanie z sąsiadującymi wrogami.

Zakładam, że wrogami są inni gracze. Ponownie, po prostu usuwam to z drogi.

Zakładając, że każdy gracz wykona losowy spacer, prawdopodobieństwo znalezienia gracza w danym punkcie - na płaskiej przestrzeni, wolnej od przeszkód - zostanie określone przez (Gaussowską) funkcję odległości do punktu odrodzenia - od teraz „ funkcjonować".

Ponieważ pracujemy na wykresie, zamiast tego adnotujemy wartości na wykresie.

3. Rozmiar mapy nie musi zwiększać się proporcjonalnie do liczby graczy.

Gdybyśmy mieli ograniczenie posiadania jednego punktu odradzania na węzeł, to aby dodać więcej graczy, potrzebowalibyśmy mniejszych węzłów. Jeśli zdecydujemy się na wykresie, zanim będziemy wiedzieć, ilu graczy będziemy mieli, być może będziemy musieli podzielić węzły dla konkretnej gry.

4. Ograniczenia te nie są egzekwowane w przypadku dowolnych nieprzekraczalnych przestrzeni.

Nie zamierzam dodawać przeszkód, aby rozwiązać problem. Au contraire , muszę pracować wokół przeszkód. Gdyby ich nie było, wdrożenie byłoby prostsze.

Rozwiązanie

Próbujemy umieścić N punktów odradzania w taki sposób, aby szanse na spotkanie z innym graczem we wszystkich punktach odradzania były równe.

Możemy otrzymać miarę błędu jako sumę różnic szans do średniej szans. Staramy się to zminimalizować (w rzeczywistości chcemy, aby było to 0).

Aby to zrobić, musimy znać szansę napotkania gracza na każdym węźle wykresu.

Aby obliczyć tę szansę, zacznij od zera. Ponieważ szansa na znalezienie gracza w dowolnym węźle, gdy nie ma graczy, wynosi zero. Następnie dla każdego punktu odradzania przejdź wykres, dodając do opisanej szansy wartość funkcji dla bieżącego punktu odradzania.

Uwaga 1: Dodanie lub przesunięcie punktu odradzania wpłynie na szansę spotkania gracza na całej mapie.

Uwaga 2: Śledzenie, jak bardzo każdy punkt odradzania wpływa na szansę, ułatwi sprawy.

Uwaga 3: Ponieważ węzły mają rozmiar, to, jak blisko można dostać się do błędu = zero, zależy od wielkości węzłów. Możesz być bardziej precyzyjny, pracując z zakresami wartości (szansa minimalna i maksymalna, zależnie od konkretnej pozycji punktów odradzania w węźle).

Umieść losowo punkty odradzania, a następnie zacznij je przesuwać w taki sposób, aby błąd się zmniejszył (rozważ możliwy ruch, a jeśli spowoduje zmniejszenie błędu, zatrzymaj go, w przeciwnym razie cofnij). I rób to dalej, dopóki nie będziemy mogli dalej poprawiać (zbyt wiele iteracji bez poprawy lub błąd wynosi zero).

Uwaga 4: Podczas przenoszenia punktu odrodzenia możesz wykorzystać szansę na spotkanie z graczem (z wyłączeniem punktu odrodzenia, który przeniesiesz), aby losowo wybrać nową pozycję dla punktu odrodzenia, taką pozycję, która ma szansę spotkać gracza bliżej średnie są bardziej prawdopodobne. Przypominam, że przesunięcie punktu odradzania wpłynie na średnią.

Oczekiwanym zachowaniem jest to, że punkty odradzania, które są zbyt blisko siebie, oddalają się od siebie, a punkty odradzania, które są zbyt daleko od siebie, zbliżają się. Dopóki nie osiągną równowagi.

Jeśli w dowolnej iteracji masz wiele punktów odradzania w węźle (co jest mało prawdopodobne, ponieważ powinny mieć tendencję do rozsuwania się, ale możliwe, jeśli masz wystarczająco duże węzły), podziel węzeł i kontynuuj rozwiązywanie. Każdy podział węzła jest poprawny.

Powyższe rozwiązanie zbliży się do błędu = zero, ale nie ma gwarancji, że osiągnie zero. Możesz go uruchomić, dopóki nie osiągnie lokalnego minimum ... Teoretycznie możesz następnie podzielić węzły, aby było dokładnie zero ... To jednak jest równoważne z poprawieniem współrzędnych punktu odradzania!

Spróbuj symulować wyżarzanie, aby przenieść punkt odradzania w węźle. Chociaż, szczerze mówiąc, prawdopodobnie nie warto zawracać sobie głowy takim poziomem szczegółowości.

Chcę wyjaśnić, że wynikiem płaskiej mapy wolnej od przeszkód nie będą równomiernie rozmieszczone punkty. Zamiast tego, jeśli mapa ma krawędzie (to znaczy, jeśli się nie zawija), wówczas więcej punktów odradzania będzie bliżej krawędzi, ponieważ punkty w centrum można dotrzeć z większej liczby kierunków, co zwiększa szansę na spotkanie inni gracze tam. W ten sposób punkty są dalej od siebie w pobliżu środka, aby to zrekompensować.

To zależy od rodzaju gry, którą chcesz stworzyć i od tego, jak szybka jest. Idealnie równomiernie rozmieszczone rozmieszczenie jest możliwe na kuli podobnej do świata (na przykład Anihilacja Planetarna). Ale czy to uczciwa opcja w twojej grze? Nawet jeśli wszyscy ludzie spawnują się w równej odległości, niektóre spawn mogą mieć większą przewagę.

• Bliższa / lepsza broń w zasięgu / więcej zasobów
• Lepsza ochrona / więcej ukrytych / przegląd
• „przepływ” graczy, niektóre miejsca są bardziej atrakcyjne niż inne (pomyśl o pełnej mapie lasu z jednym domem w jednym miejscu, niezależnie od tego, gdzie jest ten dom, duża szansa, że ​​ludzie to sprawdzają)

Czy twoja mapa jest stała, czy generowana proceduralnie? Czy kiedykolwiek próbowałeś grać w Age of Empires z 8 osobami na mapie 2-osobowej? Nie można skalować graczy w nieskończoność bez dostosowania rozmiaru mapy. Nawet niesprawiedliwe miejsce początkowe może przynieść dużo dynamiki w grze (patrz seria Worms). Nikt nie narzekał, jeśli odrodziłeś się w dużej grupie, tak długo, jak trwał twój sojusz z jedną rundą z innym graczem lub po pierwszej rundzie nie miałeś najlepiej żyjących robaków.

(Dodam jeszcze kilka przykładów, jeśli wiem więcej o twoim typie gry)

W poszukiwaniu czegoś, co do tej pory nie było sugerowane: spraw, aby nie było centrum mapy. Rozumiem przez to, że krawędzie mapy łączą się po przeciwnych stronach. Zajmie to dużo pracy programistycznej, ale w praktyce może sprawić, że poziom będzie się powtarzał nieskończenie, jeśli pójdziesz w jednym kierunku. Oznacza to, że nie ma centrum, a losowa pozycja odradzania nie będzie miała żadnych zalet ani wad.

Możesz to zrobić, tworząc płaską mapę, która jest kwadratowa, i łącząc każdą krawędź z kopią przeciwnej krawędzi. Kiedy gracz schodzi z boku, zostaje teleportowany bez wiedzy gracza do przeciwnej krawędzi. Oczywiście teoretycznie nie byłoby widać graczy po drugiej stronie granicy. Aby to naprawić, utwórz klony tego gracza, które wydają się krążyć po drugiej stronie granicy, abyś mógł je zobaczyć, a gdy podbiegniesz do nich, teleportujesz się, a rzeczywisty gracz będzie stał tam, gdzie był manekin.

Alternatywnie cała mapa mogłaby istnieć na zewnątrz kuli, jednak utrudnia to współrzędne odradzania.

Oto kilka możliwych rozwiązań:

• Odradza się losowo na obwodzie koła
• Odradza się losowo na promieniach (nie spawnuje się, aby zamknąć środek)
• Dodaj losowy składnik czasu odrodzenia

Zasadniczo uważam, że jest to problem z rozkładem grafów. Zakładając sytuację deathmatch (każdy inny gracz jest wrogiem), musisz modelować swoje mapy jako wykres połączony i śledzić, który węzeł na wykresie jest najbliższy każdemu graczowi. Nie każdy węzeł musi być punktem odradzania, ale potrzebny jest złożony wykres do modelowania odległości między punktami odradzania. W czasie odrodzenia następnie iterujesz wykres i oceniasz każdy węzeł do odrodzenia na podstawie tego, czy w pobliskich węzłach znajdują się gracze.

Idealny węzeł ma wtedy:

• Brak graczy w tej chwili
• Ponad zero graczy w pobliskich węzłach (niewielka liczba linków dalej)

Wyobraź sobie, że twój wykres został uregulowany i rysujesz koncentryczne strefy wokół każdego węzła. Karzesz węzeł, jeśli w wewnętrznych strefach są już gracze, i nagradzasz węzły, które mają graczy w odpowiedniej odległości. Chcesz zachęcić graczy do odrodzenia się wystarczająco blisko innych graczy, aby mogli szybko znaleźć zainteresowanie, ale nie tak blisko, aby wskoczyli na nie, zanim mieli szansę na uzyskanie orientacji.

Państwo będzie trzeba zwiększyć rozmiar mapy jak liczba graczy rośnie, ale knie musi być 1 lub więcej. Najgorszym przypadkiem będzie nadal to, że każdy węzeł na wykresie ma co najmniej jednego gracza - w takim przypadku nie ma dobrych węzłów do użycia, a ty będziesz musiał cierpieć z tego powodu i spawnować gracza, wiedząc, że będzie wylądować na innym. Algorytm oceniania powinien nadal ważyć węzły, abyś odrodził się w węźle z najmniejszą liczbą innych graczy.

Pamiętaj, że wykres mapy trzeba będzie starannie zbudować, ze znajomością mapy, jej tras, punktów pośrednich i skutecznej odległości między punktami węzłowymi, a nie rzeczywistej odległości. W miarę upływu czasu używaj czegoś w rodzaju zmierzonego czasu do przechodzenia między węzłami niż odległości, aby uwzględnić trudniejszy teren. Musisz także wziąć pod uwagę otwartość kontra ochrona; dwa węzły mogą być fizycznie daleko od siebie, ale ponieważ są bardzo otwarte, odradzanie się gracza w każdym węźle może oznaczać, że są one równie wrażliwe, jakbyś odrodził je obok siebie.

Udoskonalenia:

• Dodaj tymczasową karę, aby zdobyć, jeśli gracz niedawno pojawił się w tym węźle, aby powstrzymać powstawanie punktów chokepunktów (niekończący się strumień graczy nadchodzących z tego samego kierunku i odbieranych)
• Dodaj losowość w zakresie (np. Wybierz najlepsze 3 węzły, a następnie losowo wybierz między nimi z jednakowym prawdopodobieństwem), aby uzyskać większą zmienność.
• Dodaj początkową wagę do środka mapy (lub najciekawszych punktów), gdy nikt jeszcze się nie pojawił, aby spawnować się w znanych miejscach, nawet gdy każdy węzeł ma wynik zero, ponieważ nie ma innych graczy.

Kilka innych już omawiało ograniczenia twoich wymagań (mapa będzie musiała w pewnym momencie skalować się, aby zapobiec przeludnieniu itp.), I ostatecznie uniknęły faktu, że prawdopodobnie nie ma „idealnego” algorytmu rozmieszczania. Kiedy prawdopodobnie nie ma „idealnego” algorytmu, zawsze patrzę na heurystykę. Masz kilka kryteriów, które są ze sobą bezpośrednio lub pośrednio sprzeczne, wraz z bardzo skomplikowaną przestrzenią wyszukiwania. Znalezienie optymalnego rozwiązania może nie być wykonalne lub praktyczne, ale przy niewielkim dostosowaniu podejście statystyczne może być bardzo skuteczne przez większość czasu.

Spełniając twoje trzecie i czwarte kryterium: „Mapa nie powinna się rozwijać.”

Chciałbym upewnić się na początku, że masz nadmiar węzłów (tj. Tak gęsty jak siatka nawigacyjna do wyszukiwania ścieżek). To sprawia, że ​​obliczanie odległości od innych graczy jest droższe (nie bezpośrednio sąsiadujące węzły), ale nie jest to proces, który będzie się powtarzał więcej niż raz na rundę (zakładam). Dodatkową korzyścią jest to, że do większości operacji możesz korzystać z gotowej biblioteki nawigacji. Dodatkowo przestrzega to pokonywania przeszkód w uczciwy sposób, gdzie odległość euklidesowa może nie być (gracze w labiryncie mogą być umieszczeni bliżej siebie niż na otwartym polu)

Oblicz heurystykę dla pożądanych cech odradzania:

Po losowym umieszczeniu wszystkich graczy, oblicz wydajność otaczających węzłów w oparciu o twoje kryteria (odległość od innych graczy, odległość do spawnowania itp.) Wagi twoich wartości można modyfikować i manipulować, aby były nieliniowe, aby dostroić dokładnie wydajność chcesz w odkażonej idealnej obudowie (płaska prostokątna siatka bez przeszkód), a wydajność powinna być podobna, gdy dodasz świat z powrotem. Stamtąd możesz zdecydować, ile węzłów przeszukać, jaki jest próg przesunięcia punktu początkowego oraz ile iteracji chcesz wykonać przed zakończeniem odrodzenia i rozpoczęciem gry.

Jeśli pole gry to torus topologiczny (tj. Prostokąt, w którym „wyjście poza granice” oznacza wejście po przeciwnej stronie), prawdopodobnie jest to dobra odpowiedź: gracz jspawnuje się przy x = (pjW/N) mod W, y = (qjH/N) mod H, gdzie W,Hsą wymiary prostokąta, Njest liczba graczy i p,qsą liczbami całkowitymi do ustalenia; są odrębne (prawdopodobnie) względnie pierwsze i nie za daleko sqrt(N). Punkty odradzania tworzą ukośny wzór „tapety”.

Zakłada się, że gracze spawnują się tylko na początku gry. Jeśli pojawią się później, myślę, że chcesz umieścić je jak najdalej od aktualnej pozycji dowolnego gracza - na wierzchołku diagramu Voronoi określonego przez innych graczy.

Co powiesz na:

Każdy gracz otoczony jest nie spawnującym się polem (lub kółkiem).

Wewnątrz znajduje się kwadrat o określonym rozmiarze, który pojawia się wokół każdego gracza i podąża za nim - żaden inny gracz nie może się odrodzić w obrębie tego pola.

Te kwadraty wpływają tylko na spawnowanie, a nie na żaden inny ruch podczas gry.

Działa to zarówno z początkowym jak i ciągłym spawaniem.

(Kropki wskazują graczy, a kolor zielony wskazuje możliwy obszar odradzania dla nowych graczy)

Rozmiar mapy nie musi zwiększać się proporcjonalnie do liczby graczy

Aby sobie z tym poradzić, możesz zrobić jedną z dwóch rzeczy: (lub obie)

• Zmniejsz rozmiar nieodradzających się skrzynek na podstawie liczby graczy.
• Pozwól odrodzić się X wrogom w każdym polu.
  • Liczba ta może wzrastać w miarę upływu czasu (od 0).
  • Wariant 1: ma mniejsze pudełko bez spawnu i większe pudełko z ograniczonym spawnem.
  • Wariant 2: prawdopodobieństwo wagi w zależności od odległości nowego spawnu od tego gracza (jeśli jest w pudełku) - może być trudne do wydajnego wdrożenia.