Simuler une «ligne de vue» avec des obstacles sur une grille 2D?

10

Ran dans un problème intéressant. J'ai besoin de comprendre comment simuler la ligne de vue - assez simple, juste sur une grille 2D avec des obstacles. Soit une cellule de la grille est visible, soit elle ne l'est pas.

Je peux obtenir quelque chose de vraiment rudimentaire - comme écarter n espaces du joueur, ou bloquer la propagation horizontale lorsqu'un obstacle adjacent est détecté, mais je ne peux pas me permettre de vivre avec. De nombreuses autres applications utilisent des méthodes plus sophistiquées qui inclinent la ligne de vue dans les coins, etc., et je veux être à la hauteur.

Jusqu'à présent, DCSS a été ma source d'inspiration lorsque je suis perplexe, j'espère obtenir quelque chose de proche de ce qu'ils ont: http://crawl.sz.org/ .

Toute information serait appréciée - merci pour l'aide!

(Pardonnez si c'est un noobish gênant - vous n'avez commencé le développement du jeu qu'il y a quelques semaines, en essayant de rattraper votre retard.)

CodeMoose
la source
2
Quand vous dites "inclinez la ligne de vue autour des coins", que voulez-vous dire exactement?
Djentleman
Le mieux que je puisse dire est de découvrir un jeu sur crawl.sz.org. Par exemple, lorsque le joueur se tient sous un mur horizontal de 5 carreaux de large, la ligne de vue se rompt au-dessus du plan horizontal de ce mur - mais pas irréaliste au-delà. Le mieux que j'ai pu approximer est de garder la ligne de vue sur le plan horizontal du mur.
CodeMoose

Réponses:

7

Le lancer de rayons est un moyen très rapide et efficace de déterminer la ligne de visée. Cela implique essentiellement d'envoyer un rayon (pensez-y comme un laser infini qui ne peut pas être redirigé) à partir d'une certaine position dans une certaine direction. En utilisant ce rayon, vous pouvez déterminer des choses comme le (s) point (s) qu'il intersecte et la distance à laquelle il se trouvait lorsqu'il a traversé un certain point.

Ainsi, par exemple, dans un scénario joueur / ennemi, le rayon pourrait provenir de l'ennemi avec la direction étant l'emplacement du joueur. Si le rayon entre en collision avec une tuile solide, l'ennemi ne peut pas voir le joueur. Si ce n'est pas le cas, l'ennemi peut voir le joueur.

Voici un excellent tutoriel qui devrait vous aider.

Vous pouvez également envisager algorithme de ligne de Bresenham (résumé, il crée des lignes) pour quelque chose qui pourrait être plus facilement mis à l'échelle en tuiles.

Djentleman
la source
1
On dirait la voie à suivre - en particulier celle de Bresenham. Merci pour l'aide djent!
CodeMoose
3

J'ai blogué du code pour calculer la ligne de vue à partir d'une carte de hauteur. Une simple carte plate avec des obstacles n'est qu'une carte très plate en hauteur, et cette implémentation est toujours complètement applicable.

entrez la description de l'image ici

Le voici en C ++ et son O(n); si vous connaissez la hauteur maximale sur la carte, vous pouvez suivre une ligne de balayage qui n'a aucun rayon restant sous cette hauteur, et au début:

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);
    }
}
Volonté
la source
C'est bien, mais je pense bien plus qu'il ne le veut si ce qu'il veut est quelque chose comme le lien qu'il a posté.
Djentleman
Très en profondeur et impressionnant, mais djent a raison - bien en dehors de mon domaine. Merci pour le message!
CodeMoose
@CodeMoose eh son code de travail; il suffit de couper-coller, de traduire littéralement dans la langue que vous ciblez. Il s'agit d'une implémentation de Bresenham, effectuée de manière incrémentielle, de sorte qu'elle ne visite chaque place qu'une seule fois. Si vous, pour chaque carré de la grille, faites une ligne de Bresenham au joueur, vous la trouverez massivement plus lente.
Will
Bonne volonté
CodeMoose