Des unités de frai dans un monde fait de bruit Perlin?

16

Il y a quelques problèmes que j'ai rencontrés dans mon jeu basé sur le bruit Perlin. Jetez un œil à la capture d'écran ci-dessous.

entrez la description de l'image ici

Les zones blanches que vous voyez sont des murs et les zones noires sont accessibles à pied. Le triangle au milieu est le joueur.

J'ai implémenté la physique dans ce jeu en la dessinant sur une texture (pixels blancs ou noirs), puis en obtenant cela du CPU.

Cependant, je suis maintenant face à un problème différent. Je veux que des unités (ou rampantes, peu importe comment vous les appelez) apparaissent constamment, au bord de l'écran. Le point ici est que dans le jeu final, il y aura un "brouillard de guerre" qui ne permettra pas au joueur de voir aussi loin de toute façon.

J'ai pensé que je pouvais simplement scanner les pixels au bord de l'écran et voir si leur texture physique est noire, puis faire apparaître des trucs au hasard là-bas. Cependant, si vous jetez un deuxième coup d'œil à la capture d'écran, il y a (dans le coin supérieur gauche) un exemple où je ne voudrais pas que les creeps apparaissent (car ils ne pourraient pas atteindre le joueur à partir de là) .

Est-il possible que le GPU détermine ces points d'apparition pour moi, ou d'une manière différente? J'ai pensé à faire des vecteurs entre le point proposé au bord de l'écran et le lecteur, puis à le suivre tous les 10 voxels, et à voir si un mur entre en collision, avant de faire naître une unité là-bas.

Cependant, la solution proposée ci-dessus peut être trop gourmande en ressources processeur.

Des suggestions à ce sujet?

Remarque 1 Pour les unités générées, je ne veux utiliser aucune forme de recherche de chemin pour éviter les collisions avec les murs lorsque ces unités se dirigent vers le joueur. Par conséquent, les unités doivent apparaître au bord de l'écran, à un endroit où marcher en ligne droite vers le joueur ne heurterait aucun mur.

Mathias Lykkegaard Lorenzen
la source
1
La carte se déplace-t-elle avec le joueur ou le joueur se déplace-t-il sur la carte? Autrement dit, la carte va-t-elle changer? Sinon, je suggère de remplir tous les points non joignables à la génération, afin que vous n'ayez pas à vous en préoccuper.
dlras2
Si le joueur bouge, les unités auront besoin d'une méthode de recherche de chemin. Si vous voulez des zones concaves, vous aurez ce problème et vous devrez fournir une solution à l'unité en mouvement essayant d'atteindre un joueur en mouvement ... alias trouver un chemin.
Blau
1
Ou, pour mettre le commentaire de Blau d'une autre manière: Votre question n'a sans doute aucune réponse valide (à part le cas trivial d'une carte sans carreaux / pixels du tout) si le joueur peut se déplacer. Il faut toujours que vous définissiez ce que vous voulez dire par "ligne droite" pour avoir une réponse si le joueur est immobile.
Martin Sojka

Réponses:

3

Il existe un algorithme assez utile pour ce travail, beaucoup plus efficace que l'algorithme d'inondation dans cette situation (sa complexité est que l'exécution est proportionnelle à la taille de la frontière plutôt qu'à la zone inondée): c'est l'algorithme des carrés de marche. Le concept est simple: démarrez l'emplacement des joueurs (écran au milieu), choisissez une direction et marchez jusqu'à trouver un mur. Lorsque vous entrez en collision avec le mur, vous démarrez l'algorithme: vous choisissez une orientation (vers le haut ou vers le bas) et commencez à marcher sur la limite de cette zone, en mettant en évidence les pixels. Cela vous donne la limite intérieure de la zone autorisée. Ensuite, vous vérifiez simplement si les points candidats pour les unités de frai se trouvent sur cette frontière.

Voici le principe que vous devez suivre pour exécuter la frontière:

http://en.wikipedia.org/wiki/File:Marchsquares.png (meh je ne peux pas encore poster de photos)

Description de Wikipédia (bien qu'elle ait beaucoup plus de complexité car elle est utilisée avec d'autres applications à l'esprit):

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

tout-puissant
la source
10

Faites un remplissage à partir de la position du joueur; chaque zone «inondée» est alors une aire de jeu valide, et toutes les autres sont des murs.

EDIT: En ce qui concerne l'exigence supplémentaire «accessible en ligne droite», gardez à l'esprit que dans un espace discret , vous devez définir cela un peu plus loin. Par exemple, tous les chemins ci-dessus pourraient être une "ligne droite" valide dans un tel environnement, et je les ai tous vus utilisés dans un jeu à un moment ou à un autre:

variantes "en ligne droite"

En particulier, la plupart de ceux -ci ne sont pas commutatifs - ce qui signifie simplement que vous pouvez atteindre B depuis A en "ligne droite" ne signifie pas que vous pouvez également atteindre A depuis B; le contraire n'est pas nécessairement vrai non plus.

De plus, il y a la question de savoir comment gérer le mouvement diagonal si l'un ou les deux points "latéraux" se bloquent.

Martin Sojka
la source
Cela peut-il être implémenté entièrement dans HLSL?
Mathias Lykkegaard Lorenzen du
@Mathias Lykkegaard Lorenzen: Oui, dans le doute en faisant chaque étape de l'algorithme comme pixel shader et rendu entre deux cibles de texture par exemple, mais ... pourquoi ? Vous aurez probablement besoin des informations de l'algorithme sur le CPU de toute façon, pour au moins trouver un chemin.
Martin Sojka
1
@Mathias Lykkegaard Lorenzen: C'est légèrement différent de ce que vous avez demandé. Dans ce cas: Comment définissez-vous une "ligne droite", compte tenu de votre schéma de partitionnement d'espace discret?
Martin Sojka
2
même si vous ne voulez pas utiliser le pathfinding, demander à cpu de faire le travail d'inondation est possible, rappelez-vous que vous n'avez besoin d'appeler l'inondation qu'une seule fois et vous aurez alors une texture de 3 couleurs définissant le mur, les espaces libres et les espaces pouvant apparaître. pour la texture 4096x4096, il faudrait moins d'une seconde au processeur pour terminer le travail de remplissage.
Ali1S232
1
Le fait est que vous ne devez exécuter ce remplissage d'inondation qu'une seule fois, et même si votre terrain change pendant le jeu, il vous suffit de mettre à jour les sections qui sont affectées et de faire en sorte que le remplissage d'inondation les traverse, ce qui est incroyablement rapide.
TravisG
1

Que diriez-vous simplement de laisser les apparitions se produire? Je ne vois aucun problème particulier à cela.

aaaaaaaaaaaa
la source
Et s'ils frayaient derrière un mur? Comment les feriez-vous parvenir au joueur?
Mathias Lykkegaard Lorenzen du
1
cela pourrait être un problème si le jeu a un scénario pour tuer tous les ennemis, et il engendre 50 ennemis, mais quelques-uns ont été engendrés derrière le mur. Le joueur ne pourrait pas tuer les ennemis et le scénario ne se terminerait pas.
Lie Ryan
1
D'autres unités peuvent toujours ne pas être en mesure d'atteindre le joueur en fonction de la façon dont le joueur se déplace après leur apparition, vous devrez réapparaître certaines unités dans les deux cas.
aaaaaaaaaaaa
le brouillard de la guerre couvrira les
fous de
1
Cela ne fonctionnera pas de toute façon lorsque le joueur bouge.
aaaaaaaaaaaa
1

s'il est important pour vous de marquer uniquement des points avec une ligne droite valide pour le joueur, vous pouvez utiliser un algorithme comme le suivant (c'est un code c ++), il consomme plus que l'inondation normale. il peut y avoir quelques bugs mineurs (je serai content si quelqu'un les corrige) car je n'ai pas testé le code moi-même mais vous aurez l'idée.

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
la source
1

Vous pouvez remplir la carte avec des couleurs qui représentent des zones convexes ..., de cette façon, vous pouvez faire apparaître votre unité si elle se trouve dans la même zone. Ou vous pouvez rechercher plus facilement les zones accessibles.

Il s'agit de données statiques afin que vous puissiez les précalculer.

vous avez dû remplir les points de recherche d'image où il y a un changement de convave à convexe, visuellement, cela semble facile à trouver, vous avez deux situations:

  1. Horizontal: où l'orange au bleu change.
  2. Vertical: où le rouge change de vert et d'orange.

entrez la description de l'image ici

Blau
la source
Ça ne marche pas. Regardez en bas à droite, en particulier la goutte dans la zone rouge. Il est entièrement convexe, il n'y a donc aucun changement pour provoquer l'utilisation d'une autre couleur, mais clairement aucune ligne droite n'existe du bas du rouge sur le bord droit à la partie la plus à droite du rouge sur le bord inférieur.
Loren Pechtel
@ Loren Pechtel c'est fait à la main, vous avez raison, il y a une erreur là, c'est ma faute, mais vous pouvez vous rendre compte que c'est la même situation que la transition orange vers bleu.
Blau
@ Loren Pechtel, rappelez-vous que l'objectif est d'éviter de frayer dans des zones comme le jaune. Cette méthode garantit que si vous lâchez un ennemi dans la même zone qui contient le joueur, cela est accessible. Bien sûr, il peut être difficile à mettre en œuvre, mais l'idée est valide.
Blau
Votre révision n'aide pas. Deux points sur une courbe convexe n'auront jamais de ligne droite légale entre eux, point. Plus de divisions n'aideront pas.
Loren Pechtel,
veuillez vérifier la définition de convexe se référant à des zones ou à un ensemble de points ... en.wikipedia.org/wiki/Convex
Blau
1

Voici quelque chose que j'ai réellement utilisé dans mon propre jeu (monde généré par le bruit simplex 2D, presque exactement comme le vôtre) - Rayons. Commencez par le joueur, déterminez une orientation (aléatoire si vous voulez) et continuez le long de cette ligne jusqu'à ce que vous frappiez quelque chose (bord de l'écran OU astéroïde). Si vous touchez le bord de l'écran (et non un astéroïde / une goutte blanche), alors vous savez qu'il y a une ligne droite ouverte entre le bord de l'écran et le lecteur. Faites ensuite apparaître un monstre au point que vous avez touché. Si vous touchez un astéroïde, refaites le test.

khyperia
la source
0

Une autre solution (non GPU) que vous pouvez utiliser est la recherche de chemin. Avant de dessiner la carte, recherchez un chemin à partir de chaque point d'apparition potentiel à chaque bord de la carte et voyez s'il y a un chemin vers le centre. Un * chemin de recherche est assez correct sur le coût / performance, mais vous pouvez le faire avant le début du jeu si c'est un problème.

Tout point d'apparition qui n'a pas de chemin peut être placé sur une liste d'exclusion; ou vice-versa (tout point avec un chemin peut être placé sur une liste d'inclusion).

cendres999
la source