Mensimulasikan "garis pandang" dengan rintangan di grid 2d?

10

Terjadi masalah yang menarik. Saya perlu mencari cara untuk mensimulasikan garis pandang - cukup sederhana, hanya pada grid 2d dengan hambatan. Entah sel kisi terlihat, atau tidak.

Saya bisa mendapatkan sesuatu yang benar-benar belum sempurna - seperti menyebarkan n spasi dari pemain, atau memblokir perambatan horizontal ketika ada kendala yang berdekatan terdeteksi, tetapi saya tidak bisa membiarkan diri saya hidup dengannya. Banyak aplikasi lain menggunakan metode yang lebih canggih yang memiringkan garis pandang di sudut-sudut dll, dan saya ingin secara normal.

Sejauh ini DCSS telah menjadi sumber inspirasi saya ketika saya bingung, saya berharap untuk mendapatkan sesuatu yang dekat dengan apa yang mereka miliki: http://crawl.sz.org/ .

Wawasan apa pun akan dihargai - terima kasih atas bantuannya!

(Maafkan jika ini memalukan - hanya memulai permainan dev beberapa minggu lalu, berusaha keras untuk mengejar ketinggalan.)

CodeMoose
sumber
2
Ketika Anda mengatakan "kemiringan garis pandang di sudut-sudut", apa sebenarnya yang Anda maksud?
Djentleman
Yang terbaik yang bisa saya katakan adalah memeriksa game di crawl.sz.org. Sebagai contoh, ketika pemain berdiri di bawah dinding horizontal selebar 5 ubin, garis pandang pecah di atas bidang horizontal dinding itu - tetapi tidak secara realistis di luarnya. Perkiraan terbaik yang bisa saya dapatkan adalah menjaga garis pandang di bidang horizontal dinding.
CodeMoose

Jawaban:

7

Pengecoran sinar adalah cara yang sangat cepat dan efisien untuk menentukan garis pandang. Ini pada dasarnya melibatkan pengiriman sinar (anggap saja seperti laser tak terbatas yang tidak dapat diarahkan) dari posisi tertentu ke arah tertentu. Dengan menggunakan sinar ini, Anda dapat menentukan hal-hal seperti titik mana yang bersilangan dan seberapa jauh dari titik asal ketika melintasi titik tertentu.

Jadi misalnya, dalam skenario pemain / musuh, sinar bisa berasal dari musuh dengan arah menjadi lokasi pemain. Jika sinar bertabrakan dengan ubin padat, musuh tidak dapat melihat pemain. Jika tidak, musuh dapat melihat pemain.

Berikut ini adalah tutorial yang luar biasa yang akan membantu.

Anda juga dapat mempertimbangkan algoritma garis Bresenham (disimpulkan, itu menciptakan garis) untuk sesuatu yang mungkin lebih mudah diskalakan ke ubin.

Djentleman
sumber
1
Sepertinya cara untuk pergi - terutama bresenham. Terima kasih atas bantuannya!
CodeMoose
3

Saya memiliki kode blog untuk menghitung garis pandang dari peta ketinggian. Sebuah peta datar sederhana dengan rintangan hanyalah peta ketinggian yang sangat datar, dan implementasi ini masih sepenuhnya dapat diterapkan.

masukkan deskripsi gambar di sini

Ini dia dalam C ++ dan itu O(n); jika Anda tahu ketinggian maksimum di peta, Anda dapat melacak garis pindaian yang tidak memiliki sinar tersisa di bawah ketinggian itu, dan lebih awal:

typedef std::vector<float> visbuf_t;

inline void map::_visibility_scan(const visbuf_t& in,visbuf_t& out,const vec_t& eye,int start_x,int stop_x,int y,int prev_y) {
    const int xdir = (start_x < stop_x)? 1: -1;
    for(int x=start_x; x!=stop_x; x+=xdir) {
        const int x_diff = abs(eye.x-x), y_diff = abs(eye.z-y);
        const bool horiz = (x_diff >= y_diff);
        const int x_step = horiz? 1: x_diff/y_diff;
        const int in_x = x-x_step*xdir; // where in the in buffer would we get the inner value?
        const float outer_d = vec2_t(x,y).distance(vec2_t(eye.x,eye.z));
        const float inner_d = vec2_t(in_x,horiz? y: prev_y).distance(vec2_t(eye.x,eye.z));
        const float inner = (horiz? out: in).at(in_x)*(outer_d/inner_d); // get the inner value, scaling by distance
        const float outer = height_at(x,y)-eye.y; // height we are at right now in the map, eye-relative
        if(inner <= outer) {
            out.at(x) = outer;
            vis.at(y*width+x) = VISIBLE;
        } else {
            out.at(x) = inner;
            vis.at(y*width+x) = NOT_VISIBLE;
        }
    }
}

void map::visibility_add(const vec_t& eye) {
    const float BASE = -10000; // represents a downward vector that would always be visible
    visbuf_t scan_0, scan_out, scan_in;
    scan_0.resize(width);
    vis[eye.z*width+eye.x-1] = vis[eye.z*width+eye.x] = vis[eye.z*width+eye.x+1] = VISIBLE;
    scan_0.at(eye.x) = BASE;
    scan_0.at(eye.x-1) = BASE;
    scan_0.at(eye.x+1) = BASE;
    _visibility_scan(scan_0,scan_0,eye,eye.x+2,width,eye.z,eye.z);
    _visibility_scan(scan_0,scan_0,eye,eye.x-2,-1,eye.z,eye.z);
    scan_out = scan_0;
    for(int y=eye.z+1; y<height; y++) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y-1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y-1);
    }
    scan_out = scan_0;
    for(int y=eye.z-1; y>=0; y--) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y+1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y+1);
    }
}
Akan
sumber
Ini bagus, tapi saya pikir jauh lebih daripada yang dia kejar jika yang dia inginkan adalah sesuatu seperti tautan yang dia posting.
Djentleman
Sangat mendalam dan mengesankan, tetapi DJ benar - jalan keluar dari ruang lingkup saya. Terima kasih untuk posnya!
CodeMoose
@CodeMoose eh kode kerjanya; cukup potong-tempel, terjemahkan secara harfiah ke bahasa apa pun yang Anda targetkan. Ini adalah implementasi dari Bresenham, dilakukan secara bertahap sehingga hanya mengunjungi setiap kotak sekali saja. Jika Anda, untuk setiap kotak, lakukan garis Bresenham kepada pemain, Anda akan menemukannya lebih lambat.
Will
Poin
baiknya adalah