Имитация «прямой видимости» с препятствиями на 2-й сетке?

10

Наткнулся на интересную проблему. Мне нужно выяснить, как имитировать линию видимости - достаточно просто, только на 2-й сетке с препятствиями. Либо ячейка сетки видна, либо нет.

Я могу добиться чего-то действительно рудиментарного - например, растянуть n мест от игрока или заблокировать горизонтальное распространение при обнаружении соседнего препятствия, но я не могу позволить себе жить с этим. Множество других приложений используют более сложные методы, которые наклоняют линию обзора по углам и т. Д., И я хочу быть на высоте.

Пока DCSS был моим источником вдохновения, когда я в тупике, я надеюсь получить что-то близкое к тому, что у них есть: http://crawl.sz.org/ .

Любое понимание будет оценено - спасибо за помощь!

(Простите, если это неловко нубистски - игра началась только несколько недель назад, изо всех сил пытаясь наверстать упущенное.)

CodeMoose
источник
2
Когда вы говорите «наклоните угол обзора», что именно вы имеете в виду?
Джентльмен
Лучшее, что я могу сказать, это проверить игру на crawl.sz.org. Например, когда игрок стоит под горизонтальной стеной шириной в 5 плиток, линия обзора нарушается над горизонтальной плоскостью этой стены - но нереально за ее пределами. Лучшее, что я смог приблизить, - это держать линию обзора в горизонтальной плоскости стены.
CodeMoose

Ответы:

7

Лучевое литье - это очень быстрый и эффективный способ определения прямой видимости. Это в основном включает в себя отправку луча (думайте о нем как о бесконечном лазере, который нельзя перенаправить) из определенной позиции в определенном направлении. Используя этот луч, вы можете определить, например, какую точку (точки) он пересекает и как далеко от источника он находился, когда он пересек определенную точку.

Так, например, в сценарии игрок / враг луч может исходить от врага, причем направление является местоположением игрока. Если луч сталкивается с твердой плиткой, противник не может видеть игрока. Если это не так, враг может видеть игрока.

Вот отличный учебник, который должен помочь.

Вы также можете рассмотреть линейный алгоритм Брезенхэма (суммируя, он создает линии) для чего-то, что может быть легче масштабировано до тайлов.

Djentleman
источник
1
Похоже, путь - особенно Брезенхем. Спасибо за помощь, Джент!
CodeMoose
3

Я написал в блоге код для вычисления прямой видимости с карты высот. Простая плоская карта с препятствиями - это просто очень плоская карта высот, и эта реализация все еще полностью применима.

введите описание изображения здесь

Вот это в C ++ и его O(n); если вы знаете максимальную высоту на карте, вы можете отследить линию сканирования, в которой нет лучей, остающихся ниже этой высоты, и заблаговременно:

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);
    }
}
Будет
источник
Это хорошо, но я думаю, что гораздо больше, чем он хочет, если он хочет что-то вроде ссылки, которую он разместил.
Джентльмен
Очень глубокий и впечатляющий, но Джент прав - выход из моих возможностей. Спасибо за пост, хотя!
CodeMoose
@CodeMoose его рабочий код; просто вырезайте и переводите буквально на любой язык, на который вы ориентируетесь. Это реализация Брезенхэма, выполненная постепенно, поэтому она посещает каждый квадрат только один раз. Если вы для каждого квадрата сетки сделаете линию Брезенхема игроку, вы обнаружите, что она будет значительно медленнее.
Уилл
Хороший вопрос будет
CodeMoose