Unit pemijahan di dunia yang dibuat oleh Perlin noise?

16

Ada beberapa masalah yang saya temui dalam game berbasis kebisingan Perlin saya. Lihatlah screenshot terlampir di bawah ini.

masukkan deskripsi gambar di sini

Area putih yang Anda lihat adalah dinding, dan area hitam bisa dilalui dengan berjalan kaki. Segitiga di tengah adalah pemain.

Saya telah mengimplementasikan fisika dalam game ini dengan menggambarnya menjadi tekstur (piksel putih atau hitam), dan kemudian mendapatkannya dari CPU.

Namun, sekarang saya berdiri dengan masalah yang berbeda. Saya ingin unit (atau merayap, apa pun sebutan Anda) untuk terus-menerus muncul, di tepi layar. Intinya di sini adalah bahwa dalam pertandingan terakhir, akan ada "kabut perang" yang tidak memungkinkan pemain untuk melihat sejauh itu.

Saya pikir saya hanya bisa memindai piksel di tepi layar dan melihat apakah tekstur fisiknya hitam, lalu menelurkan barang secara acak di sana. Namun, jika Anda melihat screenshot kedua, ada (di sudut kiri atas) contoh di mana saya tidak ingin creep muncul (karena mereka tidak akan dapat menjangkau pemain dari sana) .

Apakah mungkin untuk memiliki GPU menentukan spawn-spot ini untuk saya, atau cara lain? Saya berpikir untuk membuat vektor antara titik yang diusulkan di tepi layar dan pemain, dan kemudian mengikutinya setiap 10 voxel, dan melihat apakah dinding bertabrakan, sebelum menelurkan unit di sana.

Namun, solusi yang diusulkan di atas mungkin terlalu intensif CPU.

Ada saran tentang masalah ini?

Catatan 1 Untuk unit yang muncul, saya tidak ingin menggunakan bentuk pathfinding apa pun untuk menghindari tabrakan di dinding saat unit ini berjalan ke arah pemain. Oleh karena itu, unit harus menelurkan di tepi layar, di lokasi di mana berjalan dalam garis lurus ke arah pemain tidak akan bertabrakan dengan dinding apa pun.

Mathias Lykkegaard Lorenzen
sumber
1
Apakah peta bergerak dengan pemain, atau apakah pemain bergerak di peta? Yaitu, apakah peta akan berubah? Jika tidak, saya sarankan mengisi semua poin yang tidak dapat dijangkau pada generasi, sehingga Anda tidak perlu khawatir tentang mereka.
dlras2
Jika pemain bergerak, unit akan membutuhkan metode pencarian jalur. Jika Anda ingin area cekung, Anda akan mengalami masalah ini dan Anda harus memberikan solusi untuk unit bergerak yang mencoba menjangkau pemain yang bergerak ... alias pencarian jalur.
Blau
1
Atau, untuk memberikan komentar Blau dengan cara lain: Pertanyaan Anda terbukti tidak memiliki jawaban yang valid (selain dari kasus sepele peta tanpa ubin dinding / piksel sama sekali) jika pemain dapat bergerak. Masih mengharuskan Anda menentukan apa yang Anda maksud dengan "garis lurus" untuk memiliki jawaban jika pemain stasioner.
Martin Sojka

Jawaban:

3

Ada algoritma yang cukup berguna untuk pekerjaan ini, jauh lebih efisien daripada algoritma banjir dalam situasi ini (kerumitannya adalah runtime sebanding dengan ukuran batas daripada area yang dibanjiri): ini adalah algoritma kotak marching. Konsepnya sederhana: mulai dari lokasi pemain (titik tengah layar), pilih arah dan berjalan sampai Anda menemukan dinding. Ketika Anda bertabrakan dengan dinding, Anda memulai algoritme: Anda memilih orientasi (atas atau bawah) dan mulai berbaris di atas batas area ini, menyoroti piksel. Ini memberi Anda batas dalam untuk area yang diizinkan. Setelah itu, Anda cukup memeriksa apakah kandidat poin untuk unit pemijahan terletak pada batas ini.

Ini adalah prinsip yang harus Anda ikuti untuk menjalankan batas:

http://en.wikipedia.org/wiki/File:Marchsquares.png (meh saya belum bisa memposting foto)

Deskripsi Wikipedia (walaupun memiliki banyak kompleksitas karena digunakan dengan aplikasi lain dalam pikiran):

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

almightyon
sumber
10

Membuat banjir mengisi dari posisi pemain; setiap area "banjir" kemudian merupakan area bermain yang valid, dan yang lainnya adalah tembok.

EDIT: Mengenai persyaratan tambahan "yang dapat dijangkau dalam garis lurus", ingatlah bahwa dalam ruang diskrit , Anda harus mendefinisikannya sedikit lebih jauh. Misalnya, semua jalur di atas bisa menjadi "garis lurus" yang valid di lingkungan seperti itu, dan saya telah melihat semuanya digunakan dalam permainan di beberapa titik:

varian "garis lurus"

Secara khusus, sebagian besar dari itu tidak komutatif - yang berarti hanya karena Anda dapat mencapai B dari A dalam "garis lurus" tidak berarti Anda juga dapat mencapai A dari B; tidak sebaliknya yang benar.

Selain itu, ada pertanyaan tentang bagaimana Anda menangani gerakan diagonal jika salah satu atau kedua titik "samping" menghalangi.

Martin Sojka
sumber
Bisakah ini diimplementasikan seluruhnya dalam HLSL?
Mathias Lykkegaard Lorenzen
@Mathias Lykkegaard Lorenzen: Ya, ragu dengan melakukan setiap langkah algoritma sebagai pixel shader dan merender antara dua target tekstur misalnya, tapi ... mengapa ? Anda mungkin akan memerlukan informasi dari algoritma pada CPU, untuk mencari jalur paling tidak.
Martin Sojka
1
@Mathias Lykkegaard Lorenzen: Tapi itu sedikit berbeda dari yang Anda minta. Dalam hal ini: Bagaimana Anda mendefinisikan "garis lurus", mengingat skema partisi ruang diskrit Anda?
Martin Sojka
2
bahkan jika Anda tidak ingin menggunakan pathfinding, meminta cpu untuk melakukan pekerjaan penimbunan adalah mungkin, ingat Anda hanya perlu memanggil penampung banjir sekali dan kemudian Anda akan memiliki tekstur 3 warna yang mendefinisikan dinding, ruang bebas, dan ruang spawnable. untuk tekstur 4096x4096 akan membutuhkan waktu kurang dari satu detik untuk cpu menyelesaikan pekerjaan penimbunan banjir.
Ali1S232
1
Intinya adalah bahwa Anda hanya perlu menjalankan pengisian banjir ini sekali saja, dan bahkan jika medan Anda berubah saat bermain game, Anda hanya perlu memperbarui bagian yang terpengaruh dan menjalankan banjir melalui mereka yang sangat cepat.
TravisG
1

Bagaimana kalau membiarkan saja terjadi? Saya tidak melihat ada masalah khusus dalam hal itu.

aaaaaaaaaaaa
sumber
Dan bagaimana jika mereka muncul di balik dinding? Bagaimana Anda membuat mereka mencapai pemain?
Mathias Lykkegaard Lorenzen
1
itu bisa menjadi masalah jika permainan memiliki skenario untuk membunuh semua musuh, dan itu menumbuhkan 50 musuh, tetapi beberapa muncul di belakang tembok. Pemain tidak akan bisa membunuh musuh dan skenario tidak akan selesai.
Lie Ryan
1
Unit lain mungkin masih tidak dapat mencapai pemain tergantung pada bagaimana pemain bergerak setelah mereka lahir, Anda harus membatalkan beberapa unit dalam kedua kasus.
aaaaaaaaaaaa
kabut perang akan menutupi tumbuhnya jelek
KRB
1
Lagipula itu tidak akan berhasil ketika pemain bergerak.
aaaaaaaaaaaa
1

jika penting bagi Anda untuk hanya menandai poin dengan garis lurus yang valid ke pemain, Anda dapat menggunakan algoritme seperti berikut (ini adalah kode c ++), ia menghabiskan lebih dari sekadar penimbunan banjir. mungkin ada beberapa bug kecil (saya akan senang jika ada yang memperbaiki mereka) karena saya tidak menguji kode sendiri tetapi Anda akan mendapatkan ide.

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);
            }
        }
    }
}
Ali1S232
sumber
1

Anda dapat mengisi peta dengan warna-warna yang mewakili area cembung ..., dengan cara ini Anda dapat menelurkan unit Anda jika terletak di area yang sama. Atau Anda dapat mencari area yang mudah dijangkau dengan lebih mudah.

Ini adalah data statis sehingga Anda dapat melakukan precalc.

Anda harus mengisi titik-titik penemuan gambar di mana ada perubahan dari konvave ke cembung, secara visual sepertinya mudah ditemukan, Anda memiliki dua situasi:

  1. Horizontal: Perubahan warna oranye ke biru.
  2. Vertikal: Di mana merah berubah hijau dan oranye.

masukkan deskripsi gambar di sini

Blau
sumber
Ini tidak berfungsi. Lihat di kanan bawah, khususnya gumpalan di area merah. Ini sepenuhnya cembung sehingga tidak ada perubahan yang menyebabkan warna lain digunakan, tetapi jelas tidak ada garis lurus dari bagian bawah merah di tepi kanan ke bagian paling kanan dari merah di tepi bawah.
Loren Pechtel
@ Loren Pechtel ini buatan tangan, Anda benar, ada kesalahan di sana, ini salah saya, tetapi Anda dapat menyadari bahwa ini adalah situasi yang sama dengan transisi oranye ke biru.
Blau
@ Loren Pechtel, ingatkan bahwa objektifnya adalah untuk tidak menelurkan di area seperti kuning. Metode ini memastikan bahwa jika Anda melepaskan musuh di area yang sama yang berisi pemain, ini dapat dijangkau. Tentu saja, mungkin sulit untuk diterapkan, tetapi idenya valid.
Blau
Revisi Anda tidak membantu. Dua titik pada kurva cembung tidak akan pernah memiliki garis lurus hukum di antara mereka, titik. Lebih banyak divisi tidak akan membantu.
Loren Pechtel
silakan periksa definisi cembung yang merujuk pada area atau sekumpulan poin ... en.wikipedia.org/wiki/Convex
Blau
1

Berikut adalah sesuatu yang saya benar-benar digunakan dalam permainan saya sendiri (dunia 2d dihasilkan suara simpleks, hampir persis seperti milik Anda) - Sinar. Mulai dari pemain, tentukan orientasi (acak jika Anda mau), dan ikuti garis itu sampai Anda menekan sesuatu (tepi layar ATAU asteroid). Jika Anda menekan tepi layar (dan bukan asteroid / gumpalan putih), maka Anda tahu ada garis lurus dan terbuka dari tepi layar ke pemain. Kemudian muncul monster pada titik yang Anda tekan. Jika Anda menabrak asteroid, lakukan tes ulang.

khyperia
sumber
0

Solusi (non-GPU) lain yang dapat Anda gunakan adalah pencarian jalur. Sebelum menggambar peta, cari jalan dari setiap titik potensial di setiap tepi peta dan lihat apakah ada jalur ke tengah. Pencarian jalur * cukup baik untuk biaya / kinerja, tetapi Anda dapat melakukan ini sebelum permainan dimulai jika itu masalah.

Titik bertelur yang tidak memiliki jalur dapat diletakkan pada daftar pengecualian; atau sebaliknya (titik mana pun dengan jalur dapat diletakkan pada daftar penyertaan).

ashes999
sumber