Lokalizacja 2d z ograniczoną precyzją

0

Nie wiem czy wątek powinien być tutaj, czy w algorytmach i strukturach danych, czy w gamedev, jak coś to proszę przenieść.

Mam mapę, na której w dowolnym miejscu (tj. nie ma żadnej siatki) może znajdować się dowolna jednostka. Pozycje wszystkich jednostek mają być globalne znane i widoczne z pewną dokładnością. Chcę stworzyć coś na wzór minimapy (patrz obrazek, lewy dolny róg)

screenshot-20211115120827.png

Z tym, że położenie ma być znane "mniej-więcej", inaczej mówiąc: gracz ma znać tylko ogólny obszar, w którym może się spodziewać napotkania na jakaś jednostkę.

Na początku pomyślałem, żeby nałożyć na mapę siatkę i w ten sposób podzielić ją na obszary w kształcie kwadratu, wtedy podświetlałbym obszar, w obrębie którego jednostka może się znajdować. Problem jest taki, że jednostki mogą się poruszać, więc jeśli jednostka będzie na krawędzi dwóch obszarów i będzie poruszała się między jednym a drugim, obszar poszukiwań można będzie zawęzić do tej krawędzi. Jeśli jednostka poruszałaby się w okolicach styku czterech obszarów, wchodząc co jakiś czas na inny obszar, można wydedukować jej pozycję dość dokładnie.

Myślałem też o dodawaniu losowego przesunięcia, ale to też nie jest idealne, bo 1. jeśli przesunięcie wylosuję raz, w momencie tworzenia jednostki i będzie ono stałe, gracz będzie mógł się go nauczyć, a 2. jeśli przesunięcie będę losował z każdym ruchem, to jednostki będą skakać na mapie, do tego niektóre jednostki mają stały schemat ruchu, więc po zebraniu X punktów z ich "przesuniętym" położeniem będzie można dość precyzyjnie wyznaczyć dokładne położenie, albo przynajmniej znacznie zawęzić obszar poszukiwań.

Macie jakiś pomysł jak się za to zabrać?

2
iksde napisał(a):

Problem jest taki, że jednostki mogą się poruszać, więc jeśli jednostka będzie na krawędzi dwóch obszarów i będzie poruszała się między jednym a drugim, obszar poszukiwań można będzie zawęzić do tej krawędzi. Jeśli jednostka poruszałaby się w okolicach styku czterech obszarów, wchodząc co jakiś czas na inny obszar, można wydedukować jej pozycję dość dokładnie.

To zrób tak, żeby jednostka nie była nigdy na krawędzi, tylko albo w jednym albo drugim kwadracie. Krawędź to tylko granica między 2ma obszarami, nie ma grubości, więc nic nie powinno się do niej zawęzić.

0
GutekSan napisał(a):
iksde napisał(a):

Problem jest taki, że jednostki mogą się poruszać, więc jeśli jednostka będzie na krawędzi dwóch obszarów i będzie poruszała się między jednym a drugim, obszar poszukiwań można będzie zawęzić do tej krawędzi. Jeśli jednostka poruszałaby się w okolicach styku czterech obszarów, wchodząc co jakiś czas na inny obszar, można wydedukować jej pozycję dość dokładnie.

To zrób tak, żeby jednostka nie była nigdy na krawędzi, tylko albo w jednym albo drugim kwadracie. Krawędź to tylko granica między 2ma obszarami, nie ma grubości, więc nic nie powinno się do niej zawęzić.

Jednostki mogą się poruszać w sposób losowy albo być kontrolowane przez innych graczy, więc nie mam takiej możliwości.

Nie chodzi mi o to, że jeśli jednostka będzie na krawędzi, to będę podświetlał krawędź. Podświetlałbym cały kwadrat, w którym jednostka się znajduje, ale jeśli będzie ona skakać między jednym a drugim kwadratem, to będzie to widać i drogą dedukcji dojdzie się do tego, że jednostka musi być blisko krawędzi.

1

[...] więc [...] będzie można dość precyzyjnie wyznaczyć dokładne położenie, albo przynajmniej znacznie zawęzić obszar poszukiwań

Skoro wyznaczanie pozycji / zawężanie obszaru poszukiwań jest niepożądane, to tak w zasadzie w jakim celu chcesz wyświetlacz ikony graczy na minimapie? 😅

3
iksde napisał(a):

Nie chodzi mi o to, że jeśli jednostka będzie na krawędzi, to będę podświetlał krawędź. Podświetlałbym cały kwadrat, w którym jednostka się znajduje, ale jeśli będzie ona skakać między jednym a drugim kwadratem, to będzie to widać i drogą dedukcji dojdzie się do tego, że jednostka musi być blisko krawędzi.

No to dojdzie :)
Trochę nie rozumiem celu, który sobie postawiłeś. Tzn. rozumiem, że chcesz ograniczyć dokładność pozycji, ale nie chcesz aby ktoś oszacował pozycję z lepszą dokładnością na podstawie wielu odczytów. To trochę kłoci się ze statystyką :).
Nawiązując do Twojego poprzedniego pomysłu z losowaniem błędu przy każdym ruchu - możesz uzależnić promień błędu od prędkości przesuwania się jednostki.

3

Zaimplementuj "próg" przejścia do nowej klatki.

Czyli zapisujesz w jakiej klatce jest jednostka (x,y) (trzeba to zapamiętać).
Co jakiś czas porównujesz z aktualną klatką (x1, y1)
którą ustalasz (zapisujesz i wyświetlasz) dopiero kiedy jednostka oddali się od klatki (x,y) o zadany próg (np. bedzie już prawie na środku sąsiedniej klatki).

0
Patryk27 napisał(a):

[...] więc [...] będzie można dość precyzyjnie wyznaczyć dokładne położenie, albo przynajmniej znacznie zawęzić obszar poszukiwań

Skoro wyznaczanie pozycji / zawężanie obszaru poszukiwań jest niepożądane, to tak w zasadzie w jakim celu chcesz wyświetlacz ikony graczy na minimapie? 😅

Chcę pokazywać ogólny obszar, w którym można coś znaleźć. Np masz zadanie "zabij 10 potworów X", ale cała mapa jest za duża, żeby za nimi latać, więc chcę gracza jakoś na to naprowadzić, ale chcę, żeby jednak trochę się pomęczył a nie miał wszystko podane na tacy. Podobnie z graczami, ma być możliwość atakowania konkretnego gracza, ale nie może być zbyt łatwo, ma to wymagać poświęcenia się sprawie :)

GutekSan napisał(a):

Nawiązując do Twojego poprzedniego pomysłu z losowaniem błędu przy każdym ruchu - możesz uzależnić promień błędu od prędkości przesuwania się jednostki.

Nie zda to egzaminu, bo ktoś może się nie poruszać/nieznacznie się poruszać przez długi okres.

jarekr000000 napisał(a):

Zaimplementuj "próg" przejścia do nowej klatki.

Czyli zapisujesz w jakiej klatce jest jednostka (x,y) (trzeba to zapamiętać).
Co jakiś czas porównujesz z aktualną klatką (x1, y1)
którą ustalasz (zapisujesz i wyświetlasz) dopiero kiedy jednostka oddali się od klatki (x,y) o zadany próg (np. bedzie już prawie na środku sąsiedniej klatki).

O, to może być to. Pokombinuję w tę stronę.

0
iksde napisał(a):

Nie zda to egzaminu, bo ktoś może się nie poruszać/nieznacznie się poruszać przez długi okres.

Ale co z tego? Jeśli się nie rusza, to nadal jest jakiś niezerowy promień błędu. W raz ze wzrostem prędkości ten błąd na pozycji wzrasta.

2

Jeszcze usprawnienie - zamiast uaktualniać klatkę po przekroczeniu pewnej odległości od poprzedniej klatki (próg) - możesz też ustawić próg na kumulowanym błedzie:
w każdym przebiegu pętli obliczasz odległość od bieżącej klatki (0 jeśli w klatce, dodatnia jeśli obiekt wyszedł poza klatkę (odległość od krawędzi) i dodajesz to do jakiejś zmiennej w obiekcie ("acumulated_position_error"). Jak ten błąd przekroczy zadany próg to uaktualniasz klatkę.
Ma to zaletę, że obiekt w końcu zmieni położenie jeśli się długo będzie kręcił przy krawędzi. Trudniej też będzie wydedukować dokładną pozycję.

0
iksde napisał(a):
Patryk27 napisał(a):

[...] więc [...] będzie można dość precyzyjnie wyznaczyć dokładne położenie, albo przynajmniej znacznie zawęzić obszar poszukiwań

Skoro wyznaczanie pozycji / zawężanie obszaru poszukiwań jest niepożądane, to tak w zasadzie w jakim celu chcesz wyświetlacz ikony graczy na minimapie? 😅

Chcę pokazywać ogólny obszar, w którym można coś znaleźć. Np masz zadanie "zabij 10 potworów X", ale cała mapa jest za duża, żeby za nimi latać, więc chcę gracza jakoś na to naprowadzić, ale chcę, żeby jednak trochę się pomęczył a nie miał wszystko podane na tacy. Podobnie z graczami, ma być możliwość atakowania konkretnego gracza, ale nie może być zbyt łatwo, ma to wymagać poświęcenia się sprawie :)

czyli zależy ci na ogólnym kierunku, jak strzałeczki w GTA? Ale jednocześnie chcesz, żeby ten kierunek nie był zbyt dokładny?

No to może w tę stronę pójść? Tzn. nie kombinować z kratkami, tylko pomyśleć o kierunku i odległości obiektu A od obiektu B?

Tzn. obliczyć odległość (prawo pitagorasa) i sprawdzić jaki jest kierunek (kąt) od gracza do danej jednostki (atan2, uważaj na kolejność parametrów, bo jest zwykle zamieniona), a później jakoś zaokrąglić ten kąt i odległość i skonwertować na współrzędne x, y:

x = cos(approximateAngle) * approximateDistance
y = sin(approximateAngle) * approximateDistance

ja bym tak spróbował to zrobić, jeśli nie za pomocą kratek, których nie chcesz używać. Innymi słowy skonwertować na współrzędne biegunowe, pozaokrąglać, a potem znowu obliczyć x, y.

No i to podejście miałoby taką cechę, że im ktoś jest dalej, tym mógłby mniej dokładnie widzieć (jeśli zaokrąglisz kąt np. do 0.1 radiana, to przy bliskiej odległości niewielka będzie różnica, ale przy większych odległościach rozrzut będzie większy, co byłoby realistyczne, że na większe odległości ktoś gorzej by ocenił miejsce, gdzie jest dokładnie potwór.

1

Takie coś jest w trybie battle royale w cs:go - tam jeśli przeciwnik znajduje się blisko krawędzi to podświetlone są dwa lub więcej sektorów. Śledząc mapę można zobaczyć kierunek ruchu ale nie da się konkretnie ustalić pozycji

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