Como posso gerar um caminho de calabouço (relativamente) linear?

Estamos desenvolvendo um conceito para um side-scroller de ação. O que precisamos é de uma maneira de gerar um mapa (relativamente) direto. Com isso, quero dizer algo como ...

É claro que este mapa segue uma rota simples, mesmo que se desvie um pouco. Com isso, também vamos implementar caminhos dispersos - atalhos ou passagens secretas. Para que, talvez, para ir da terceira área circundada para a quarta, você tenha o caminho principal e uma passagem secreta cheia de inimigos mais fortes, mas que seja mais rápida e tenha recompensas mais altas.

Aqui chegamos a um impasse. Estamos explorando algumas opções, mas realmente não fizemos nenhum progresso. Que abordagem poderíamos usar para gerar esse tipo de caminho? Não estamos limitados a linguagens de programação, já que até agora experimentamos Java, C # e C ++. Da mesma forma, não temos dependências atuais em mecanismos de jogos específicos.

Exigências

1. Você deseja vários caminhos de A a B.
2. Você deseja trabalhar no espaço da grade, presumivelmente, esse é o espaço do bloco para o seu side-scroller.
3. Você não quer que os caminhos se cruzem, ou isso estragará a progressão do jogo.
4. Você deseja que os caminhos pareçam razoavelmente orgânicos.

Diagramas de Voronoi

Os diagramas de Voronoi são gráficos planares de preenchimento de espaço:

Uma coisa boa sobre eles é como você pode usá-los para criar caminhos orgânicos. Se você desenhar uma linha reta de um centro para o outro, obterá um caminho bastante imprevisível (leia-se: não ortolinear).

Como criar um diagrama de Voronoi para uso com um sistema baseado em bloco

Crie um mapa de tamanho razoável, por exemplo, 128x128. Gerarn coordenadas aleatórias da grade (x, y) no mapa e preencha cada uma com uma ID / cor exclusiva. Crie uma lista para essa cor e adicione a célula inicial a ela; faça isso para cada cor.

Agora você tem esses pontos de cores exclusivos flutuando no vazio, mas precisa criar ilhas inteiras de cores ao seu redor, com o resultado final parecendo o seguinte:

Para fazer isso, precisamos ver qual cor possui cada célula no mapa (célula = pixel na imagem acima). Percorremos todas as células do mapa, verificando qual dos nossos npontos de cores iniciais é o mais próximo (via pitágoras). Essa célula entra na lista associada àquela identificação / cor exclusiva ... daqui em diante denominadas células ilhas AKA Voronoi (no diagrama acima, grupos de pixels da mesma cor).

Agora você deve ter um diagrama de Voronoi quantizado. O próximo passo é analisar a adjacência de cada ilha a outras ilhas. Configure um nó simples e uma estrutura de aresta para poder armazenar um gráfico (o nó é apenas o ID, a lista para esse ID e uma lista vazia de arestas; a borda é apenas o nó inicial e final). Para cada ilha com identificação exclusiva, crie um nó e adicione arestas para vinculá-lo a cada ilha à qual está adjacente.

Depois de ter o diagrama completo (gráfico), você começa a parte divertida - use o gráfico para encontrar cadeias de ilhas e, fazendo com que todas as células de cada ilha da cadeia tenham o mesmo ID, você estará criando uma das seus caminhos. Digamos que uma ilha com todas as células com ID 503 esteja próxima a uma ilha com o ID 657. Você pode substituir todas as 503 células por um ID 657, criando assim uma ilha maior de 657s adjacentes.

Por exemplo - vermelho é o caminho 1, azul é o caminho 2, magenta é ambos:

Você pode usar qualquer algoritmo de gráfico existente (incluído A *) para gerar os caminhos do início ao fim. Obter um caminho sinuoso é um caso de nem sempre usar o passo ideal em direção à ilha de meta.

Por fim, é trivial encolher as ilhas se você quiser caminhos mais estreitos ou usar um mapa maior com muito mais ilhas para obter uma resolução mais precisa.

Uma etapa final opcional para a busca de caminhos

Você pode usar o gráfico de alto nível que você criou em conjunto com as células / blocos subjacentes para executar o tempo de execução A *, OU você pode fazer uma escalada nas células / blocos subjacentes para obter melhor movimento:

No centro (ou em qualquer coordenada) da sua ilha de objetivo, você pode colocar uma célula de influência. Essa influência pode bombear "perfume", como na Difusão Colaborativa . Esse perfume se espalhará por todo o caminho de volta para o que era a ilha inicial, ficando cada vez mais fraca. Agora, para uma entidade no início, simplesmente subimos de uma célula com odor mais baixo para uma mais perfumada, cada vez mais aproximando você do objetivo - da mesma forma que um cachorro opera. Cada caminho sendo aproximadamente linear, isso evita o uso de A * em tempo de execução. Ou você pode fazer o mesmo com o gráfico de ilhas, mas esse caminho é um pouco mais complexo, porque você provavelmente desejará navegar pelas suas entidades no nível do bloco. Então a primeira maneira é talvez melhor. De qualquer maneira, você poderá navegar até a meta com baixo custo de processamento.