Unidades desova em um mundo feito pelo ruído Perlin?

16

Há alguns problemas que encontrei no meu jogo baseado em ruído Perlin. Dê uma olhada na captura de tela em anexo abaixo.

insira a descrição da imagem aqui

As áreas brancas que você vê são paredes e as áreas pretas são passáveis. O triângulo no meio é o jogador.

Eu implementei a física neste jogo, desenhando-a em uma textura (pixels brancos ou pretos) e depois obtendo isso da CPU.

No entanto, agora estou com um problema diferente em mãos. Quero que as unidades (ou creeps, como você as chama) sejam geradas constantemente, na borda da tela. O ponto aqui é que, no jogo final, haverá um "nevoeiro de guerra" que não permite que o jogador veja tão longe assim.

Imaginei que poderia apenas digitalizar os pixels na borda da tela e ver se a textura física deles era preta, e então gerar coisas aleatoriamente lá. No entanto, se você der uma segunda olhada na captura de tela, existe (no canto superior esquerdo) um exemplo de onde eu não gostaria que os creeps aparecessem (já que eles não seriam capazes de alcançar o jogador de lá) .

É possível que, de alguma forma, a GPU determine esses pontos de reprodução para mim, ou de alguma maneira diferente? Pensei em criar vetores entre o ponto proposto na borda da tela e o player e segui-lo a cada 10 voxels, e ver se uma parede colide antes de gerar uma unidade lá.

No entanto, a solução proposta acima pode exigir muita CPU.

Alguma sugestão sobre este assunto?

Nota 1 Para as unidades geradas, não quero usar nenhuma forma de busca de caminhos para evitar colisões na parede, pois essas unidades correm em direção ao jogador. Portanto, as unidades devem aparecer na borda da tela, em um local em que caminhar em linha reta em direção ao jogador não colidir com nenhuma parede.

Mathias Lykkegaard Lorenzen
fonte
1
O mapa se move com o jogador ou o jogador se move no mapa? Ou seja, o mapa estará mudando? Caso contrário, sugiro preencher todos os pontos inacessíveis na geração, para que você não precise se preocupar com eles.
dlras2
Se o jogador estiver em movimento, as unidades precisarão de um método de localização de caminho. Se você deseja áreas côncavas, terá esse problema e precisará fornecer uma solução para a unidade móvel que tenta alcançar um jogador em movimento ...
Blau
1
Ou, para colocar o comentário de Blau de outra maneira: sua pergunta provavelmente não tem uma resposta válida (além do caso trivial de um mapa sem azulejos / pixels) se o jogador puder se mover. Ainda requer que você defina o que você quer dizer com "linha reta" para ter uma resposta se o jogador estiver parado.
Martin Sojka

Respostas:

3

Existe um algoritmo bastante útil para este trabalho, muito mais eficiente do que o algoritmo de inundação nesta situação (sua complexidade é o tempo de execução é proporcional ao tamanho do limite, em vez da área inundada): é o algoritmo de quadrados de marcha. O conceito é simples: comece a localização dos jogadores (ponto médio da tela), escolha uma direção e caminhe até encontrar uma parede. Ao colidir com a parede, você inicia o algoritmo: escolhe uma orientação (para cima ou para baixo) e começa a marchar sobre o limite dessa área, destacando os pixels. Isso fornece o limite interno para a área permitida. Depois, você simplesmente verifica se os pontos candidatos às unidades de reprodução estão nesse limite.

Este é o princípio que você deve seguir para executar o limite:

http://en.wikipedia.org/wiki/File:Marchsquares.png (meh ainda não posso postar fotos)

Descrição da Wikipedia (embora tenha muito mais complexidade porque é usada com outros aplicativos em mente):

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

almightyon
fonte
10

Faça uma inundação a partir da posição do jogador; toda área "inundada" é então uma área de recreação válida, e todas as outras são paredes.

EDIT: Quanto ao requisito adicional "alcançável em linha reta", lembre-se de que em um espaço discreto , é necessário definir um pouco mais. Por exemplo, todos os caminhos acima podem ser uma "linha reta" válida em um ambiente assim, e eu já vi todos eles usados ​​em um jogo em algum momento ou outro:

variantes "linha reta"

Em particular, a maioria deles não é comutativa - o que significa que apenas porque você pode alcançar B de A em uma "linha reta" não significa que você também pode alcançar A de B; nem o oposto é necessariamente verdadeiro.

Além disso, há a questão de como você lida com o movimento diagonal se um ou ambos os pontos "laterais" estão bloqueando.

Martin Sojka
fonte
Isso pode ser implementado inteiramente no HLSL?
Mathias Lykkegaard Lorenzen
@Mathias Lykkegaard Lorenzen: Sim, na dúvida, executando cada etapa do algoritmo como um shader de pixel e renderização entre dois alvos de textura, por exemplo, mas ... por quê ? Você provavelmente precisará das informações do algoritmo na CPU de qualquer maneira, para encontrar o caminho, no mínimo.
Martin Sojka 10/09
1
@Mathias Lykkegaard Lorenzen: Isso é um pouco diferente do que você pediu. Nesse caso: como você define uma "linha reta", considerando seu esquema de particionamento de espaço discreto?
Martin Sojka 10/09
2
mesmo que você não queira usar o pathfinding, é possível solicitar à cpu que faça o trabalho de floodfill, lembre-se de que você só precisa chamar o floodfill uma vez e terá uma textura de três cores definindo parede, espaços livres e espaços desováveis. para a textura de 4096 x 4096, levaria menos de um segundo para a CPU concluir o trabalho de preenchimento.
Ali1S232 10/10
1
O ponto é que você só precisa executar esse preenchimento de inundação uma vez, e mesmo que seu terreno mude durante o jogo, você só precisa atualizar as seções afetadas e executar o preenchimento de inundação, o que é terrivelmente rápido.
TravisG 11/11/11
1

Que tal apenas deixar os filhotes acontecerem? Não vejo nenhum problema em particular nisso.

aaaaaaaaaaaa
fonte
E se eles aparecerem atrás de um muro? Como você os faria alcançar o jogador?
Mathias Lykkegaard Lorenzen
1
pode ser um problema se o jogo tiver um cenário para matar todos os inimigos e gerar 50 inimigos, mas alguns foram criados atrás do muro. O jogador não seria capaz de matar os inimigos e o cenário não terminaria.
Lie Ryan
1
Outras unidades ainda podem não ser capazes de alcançar o jogador, dependendo de como o jogador se move depois de ter sido gerado, você terá que desparecer algumas unidades em ambos os casos.
Aaaaaaaaaaaa
a névoa da guerra cobrirá as desovas de baixa qualidade
KRB
1
Isso não funcionará de qualquer maneira quando o jogador se mover.
Aaaaaaaaaaaa
1

se for importante marcar apenas pontos com uma linha reta válida para o player, você pode usar um algoritmo como o seguinte (é um código c ++), ele consome mais do que o preenchimento normal. pode haver alguns bugs menores (ficarei feliz se alguém os corrigir), já que eu não testei o código sozinho, mas você entenderá.

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
fonte
1

Você pode preencher o mapa com cores que representam áreas convexas ..., dessa maneira você pode gerar sua unidade se estiver na mesma área. Ou você pode procurar mais facilmente áreas acessíveis.

Esses são dados estáticos, para que você possa pré-calcular.

você tinha que preencher os pontos de localização da imagem onde há uma mudança de convave para convexa, visualmente parece fácil de encontrar, você tem duas situações:

  1. Horizontal: onde o laranja muda para o azul.
  2. Vertical: Onde o vermelho muda de verde e laranja.

insira a descrição da imagem aqui

Blau
fonte
Isso não funciona. Olhe no canto inferior direito, especificamente o blob na área vermelha. É totalmente convexa, portanto não há alteração para fazer com que outra cor seja usada, mas claramente não existe linha reta desde o fundo do vermelho na borda direita até a parte mais à direita do vermelho na borda inferior.
Loren Pechtel
@ Loren Pechtel, isso é feito à mão, você está certo, há um erro, a culpa é minha, mas você pode perceber que é a mesma situação que a transição de laranja para azul.
Blau
@ Loren Pechtel, lembre-se de que o objetivo é evitar gerar em áreas como o amarelo. Este método garante que, se você liberar um inimigo na mesma área que contém o jogador, isso é alcançável. Obviamente, pode ser difícil de implementar, mas a ideia é válida.
Blau
Sua revisão não ajuda. Dois pontos em uma curva convexa nunca terão uma linha reta legal entre eles, ponto final. Mais divisões não ajudarão.
Loren Pechtel 12/09
verifique a definição de convexo referente a áreas ou conjunto de pontos ... en.wikipedia.org/wiki/Convex
Blau
1

Aqui está algo que eu realmente usei no meu próprio jogo (mundo simplificado gerado por ruído em 2D, quase exatamente como o seu) - Raios. Comece no jogador, determine uma orientação (aleatória, se quiser) e siga essa linha até atingir algo (borda da tela OU asteróide). Se você atingir a borda da tela (e não um asteróide / blob branco), saberá que há uma linha reta e aberta da borda da tela até o player. Então crie um monstro no ponto em que você acertar. Se você acertar um asteróide, refaça o teste.

khyperia
fonte
0

Outra solução (sem GPU) que você pode usar é a localização de caminhos. Antes de desenhar o mapa, localize o caminho a partir de cada ponto de desova em potencial em cada extremidade do mapa e veja se existe um caminho para o centro. Uma descoberta de caminho * é bastante boa em custo / desempenho, mas você pode fazer isso antes do jogo começar, se isso for um problema.

Qualquer ponto de desova que não possua um caminho pode ser colocado em uma lista de exclusão; ou vice-versa (qualquer ponto com um caminho pode ser colocado em uma lista de inclusão).

ashes999
fonte