Jednostki spawnujące w świecie wywołanym hałasem Perlina?

W mojej grze opartej na hałasie Perlin natknąłem się na pewne problemy. Spójrz na załączony zrzut ekranu poniżej.

Białe obszary, które widzisz, to ściany, a czarne obszary można chodzić pieszo. Trójkąt pośrodku to gracz.

Zaimplementowałem fizykę w tej grze, rysując ją na fakturze (białe lub czarne piksele), a następnie pobierając ją z procesora.

Jednak teraz mam inny problem. Chcę, aby jednostki (lub creepy, jakkolwiek je nazwiesz) stale pojawiały się na krawędzi ekranu. Chodzi o to, że w końcowej grze będzie „mgła wojny”, która i tak nie pozwoli graczowi zobaczyć tego tak daleko.

Uznałem, że mogę po prostu zeskanować piksele na krawędzi ekranu i sprawdzić, czy ich tekstura fizyki jest czarna, a następnie odradzać tam losowo rzeczy. Jeśli jednak spojrzysz na zrzut ekranu po raz drugi, w lewym górnym rogu znajduje się przykład, w którym nie chciałbym, aby stwory się pojawiały (ponieważ nie byłyby w stanie dotrzeć do gracza z tego miejsca) .

Czy w jakiś sposób GPU może ustalić te miejsca odrodzenia dla mnie, czy w inny sposób? Pomyślałem o stworzeniu wektorów między proponowanym punktem na brzegu ekranu a odtwarzaczem, a następnie podążaniu za nim co 10 wokseli i sprawdzeniu, czy ściana nie zderzy się, zanim pojawi się tam jednostka.

Jednak wyżej zaproponowane rozwiązanie może być zbyt obciążające procesor.

Wszelkie sugestie w tej sprawie?

Uwaga 1 W przypadku jednostek odradzających się, nie chcę używać żadnego rodzaju odnajdywania ścieżek, aby uniknąć kolizji na ścianie, gdy jednostki te biegną w kierunku gracza. Dlatego jednostki muszą się pojawiać na krawędzi ekranu, w miejscu, w którym chodzenie w linii prostej w kierunku gracza nie koliduje z żadnymi ścianami.

Istnieje bardzo przydatny algorytm do tego zadania, znacznie bardziej wydajny niż algorytm powodziowy w tej sytuacji (jego złożoność to czas działania jest proporcjonalny do wielkości granicy, a nie zalany obszar): jest to algorytm marszowych kwadratów. Pomysł jest prosty: rozpocznij lokalizację gracza (punkt środkowy ekranu), wybierz kierunek i idź, aż znajdziesz ścianę. Kiedy zderzasz się ze ścianą, uruchamiasz algorytm: wybierasz orientację (w górę lub w dół) i zaczynasz maszerować nad granicą tego obszaru, podświetlając piksele. To daje ci wewnętrzną granicę dla dozwolonego obszaru. Następnie po prostu sprawdzasz, czy punkty kandydujące do jednostek spawnujących leżą na tej granicy.

Jest to zasada, którą należy przestrzegać podczas uruchamiania granicy:

http://en.wikipedia.org/wiki/File:Marchsquares.png (meh Nie mogę jeszcze publikować zdjęć)

Opis Wikipedii (choć ma dużo większą złożoność, ponieważ jest używany z innymi aplikacjami):

http://en.wikipedia.org/wiki/Marching_squares

Zrób wypełnienie powodziowe z pozycji gracza; każdy „zalany” obszar jest wówczas ważnym obszarem zabaw, a wszystkie pozostałe są ścianami.

EDYCJA: Jeśli chodzi o dodatkowy wymóg „osiągalny w linii prostej”, należy pamiętać, że w dyskretnej przestrzeni musisz to zdefiniować nieco dalej. Na przykład wszystkie powyższe ścieżki mogą być prawidłową „linią prostą” w takim środowisku i widziałem je wszystkie w grze w pewnym momencie:

W szczególności większość z nich nie jest przemienna - co oznacza, że ​​fakt, że można dotrzeć do B z linii A w „linii prostej”, nie oznacza, że ​​można również dotrzeć do A z linii B; żadna z nich niekoniecznie musi być prawdziwa.

Ponadto pojawia się pytanie, w jaki sposób poradzisz sobie z ruchem po przekątnej, jeśli jeden lub oba punkty „boczne” blokują.

Co powiesz na pozwolenie spawnu? Nie widzę w tym żadnego konkretnego problemu.

jeśli ważne jest, aby zaznaczyć graczowi tylko punkty z prawidłową linią prostą, możesz użyć następującego algorytmu (kod c ++), zużywa on więcej niż normalne wypełnienie. mogą występować drobne błędy (będę zadowolony, jeśli ktoś je poprawi), ponieważ sam nie testowałem kodu, ale wpadniesz na pomysł.

void straightlineFill(Point startPoint, Texture target)
{
    queue<Point> pointQueue;
    for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(startPoint.x + dx, startPoint.y + dy));
    while (!pointQueue.empty())
    {
        point front = pointQueue.front();
        pointQueue.pop();
        if (target.pixelAt(front) == COLOR_SPAWNABLE||
            target.pixelAt(front) == COLOR_WALL||
            target.pixelAt(front) == COLOR_NOT_SPAWNABLE)
                continue;
        taraget.setPixelAt(front, colorFilled); 
        for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(front.x + dx, front.y + dy));
        // up until now was the normal floodfill code
        // and here is the part that will do the real straight line checking

        // lineDX & lineDY will keep how much the line we are checking is skewed
        int lineDX = front.x - startPoint.x;
        int lineDY = front.y - startPoint.y;

        // step will show us how much we have to travel to reach each point of line
        point step;
        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDX < 0)
                step = point(-1,0);
            if (lineDX == 0)
                if (lineDY < 0)
                    step = point(0,-1);
                else
                    step = point(0,1);
            if (lineDX > 0)
                step = point(1,0);
        }

        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDY < 0)
                step = point(0,-1);
            if (lineDY == 0)
                if (lineDX < 0)
                    step = point(-1,0);
                else
                    step = point(1,0);
            if (lineDY > 0)
                step = point(0,1);
        }

        // moved will keep how much we have traveled so far, it's just some value that will speed up calculations and doesn't have any mathematical value
        point moved = 0;

        // spawnable will keep if the current pixel is a valid spawnpaint

        bool spawnable = true;

        // now we will travel on the straight line from player position to the edges of the map and check if whole line is valid spawn points or not.

        while (target.isInside(front))
        {
            front = front + step;
            moved = moved + point(step.x * lineDX, step.y * lineDY);
            if (step.x != 0 && moved.x < moved.y)
            {
                moved.x = moved.x - lineDY * sign(lineDY);
                front.y = front.y + sign(lineDY);
            }
            if (step.y != 0 && moved.y < moved.x)
            {
                moved.y = moved.y - lineDX * sign(lineDX);
                front.x = front.x + sign(lineDX);
            }

            if (target.getPixelAt(front) == COLOR_WALL)
                spawnable = false;

            if (spawnable)
            {
                target.setPixelAt(front,COLOR_SPAWNABLE);
                for (int dx = -1;dx <=1;dx ++)
                    for(int dy = -1;dy <=1;dy++)
                        if(dx != 0 && dy != 0)
                            pointQueue.push(point(front.x + dx, front.y + dy));             
            }
            else
            {
                target.setPixelAt(front,COLOR_NOT_SPAWNABLE);
            }
        }
    }
}

Możesz wypełnić mapę kolorami reprezentującymi obszary wypukłe ... w ten sposób możesz spawnować swoją jednostkę, jeśli leży w tym samym obszarze. Lub możesz łatwiej wyszukiwać dostępne obszary.

To są dane statyczne, więc możesz je wstępnie skalibrować.

musiałeś wypełnić punkt znajdujący obraz, w którym następuje zmiana z konwekcyjnego na wypukły, wizualnie wydaje się łatwy do znalezienia, masz dwie sytuacje:

1. Poziomo: tam, gdzie zmienia się kolor pomarańczowy z niebieskim.
2. Pionowo: gdzie czerwony zmienia się na zielony i pomarańczowy.

Oto coś, czego faktycznie użyłem w mojej własnej grze (świat generowany przez hałas 2D, prawie dokładnie tak jak twój) - Promienie. Zacznij od gracza, określ orientację (losowo, jeśli chcesz) i idź wzdłuż tej linii, aż coś trafisz (krawędź ekranu LUB asteroida). Jeśli uderzysz w krawędź ekranu (a nie asteroidę / białą kroplę), to wiesz, że od krawędzi ekranu do gracza jest prosta, otwarta linia. Następnie spawnuj potwora w miejscu, w którym trafiłeś. Jeśli trafisz asteroidę, ponownie wykonaj test.

Innym rozwiązaniem (bez GPU), którego można użyć, jest wyszukiwanie ścieżek. Przed narysowaniem mapy znajdź ścieżkę z każdego potencjalnego punktu odradzania na każdej krawędzi mapy i sprawdź, czy jest ścieżka do centrum. * Wyszukiwanie ścieżek jest całkiem OK pod względem kosztów / wydajności, ale możesz to zrobić przed rozpoczęciem gry, jeśli to problem.

Każdy punkt odradzania, który nie ma ścieżki, może zostać umieszczony na liście wykluczeń; lub odwrotnie (dowolny punkt ze ścieżką można umieścić na liście włączającej).