Gerar aleatoriamente gráfico direcionado em uma grade

Eu estou tentando gerar aleatoriamente um gráfico direcionado com o objetivo de criar um jogo de quebra-cabeça semelhante aos quebra-cabeças deslizantes de gelo de Pokemon.
Isto é essencialmente o que eu quero ser capaz de gerar aleatoriamente: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory .

Preciso limitar o tamanho do gráfico nas dimensões x e y. No exemplo dado no link, ele seria restrito a uma grade 8x4.
O problema que eu estou enfrentando não é gerar o gráfico aleatoriamente, mas gerar um gráfico aleatoriamente, que eu possa mapear corretamente em um espaço 2D, pois preciso de algo (como uma rocha) no lado oposto de um nó, para torná-lo visualmente faz sentido quando você para de deslizar. O problema disso é que, às vezes, a rocha acaba no caminho entre dois outros nós ou possivelmente em outro nó, o que faz com que todo o gráfico seja quebrado.

Depois de discutir o problema com algumas pessoas que conheço, chegamos a algumas conclusões que podem levar a uma solução.

• Incluindo os obstáculos na grade como parte do gráfico ao construí-lo.
• Comece com uma grade totalmente preenchida e apenas desenhe um caminho aleatório e exclua os blocos que farão esse caminho funcionar.

O problema então é descobrir quais excluir, para evitar a introdução de um caminho adicional mais curto. Também estávamos pensando que um algoritmo de programação dinâmica pode ser benéfico, embora nenhum de nós tenha muita habilidade em criar algoritmos de programação dinâmica do nada. Qualquer idéia ou referência sobre como esse problema é chamado oficialmente (se for um problema gráfico oficial) seria muito útil.

Aqui estão alguns exemplos do que consegui até agora, colocando blocos aleatoriamente e gerando o gráfico de navegação a partir do início / término escolhido. A idéia (conforme descrito no link anterior) é começar no verde S e desejar chegar ao verde F. Você faz isso movendo-se para cima / baixo / esquerda / direita e continua na direção escolhida até atingir um parede. Nestas fotos, cinza é uma parede, branco é o chão e a linha roxa é o comprimento mínimo do início ao fim, e as linhas pretas e os pontos cinza representam possíveis caminhos.

Aqui estão alguns exemplos ruins de gráficos gerados aleatoriamente:

Aqui estão alguns bons exemplos de gráficos gerados aleatoriamente (ou ajustados manualmente):

Também pareci notar os mais desafiadores quando, na verdade, jogar isso como um quebra-cabeça são aqueles que possuem muitos nós de alto grau no caminho mínimo.

• é gelo, você se moverá a menos que bata em uma pedra.
• a única maneira de mudar de direção é bater em uma pedra.
• se você bater em uma pedra, terá que mudar de direção.
• os ciclos são bons, por razões óbvias.
• pode haver várias partidas e várias finalizações.

propriedades mais avançadas:

• as células sem rochas adjacentes não são alcançáveis ​​(algumas podem ser atravessadas)
• as paredes também são pedras; se você removê-las, pode decidir enrolar.
• você pode usar sub-grades como padrões ("lado a lado" 3x3, 3x4, 5x5, ... etc)
• você pode sobrepor um bloco MxN do quebra-cabeça em cima da área MxN não atravessável e adicionar uma pedra para redirecionar para dentro / fora dela.
• rotação ou simetria de uma peça pode ser interessante
• você pode expandir um bloco inserindo linhas / colunas geladas

exemplo:

S=start, E=end, o=rock, .=ice

3 . 2 o        3 . . 2 o         . . . . . o o
4 . . E   ~=   4 . . . E   ~=    . . . . . 2 E
o . . .        o . . . .         . . . . . . .
S . 1 o        S . . 1 o         S . . . . 1 o

exemplo de combinação de ladrilhos:

3 . . 2 o       o 2 . . 3      3 . . 2 o 7 . . 6
4 . . . E   +   E . . . 4  =   4 . . . . . . . 5
o . . . .       . . . . o      o . . . . . . . o
S . . 1 o       o 1 . . S      S . . 1 o 8 . . E

você pode gostar do jogo Tsuro , ele usa peças para gerar um tabuleiro aleatório.

Talvez a engenharia reversa possa ajudá-lo se você estiver disposto a isso.

Se houver uma e apenas uma solução para cada problema, provavelmente você poderá gerar um gráfico com base na resposta exclusiva. Isso não exigirá que você faça programação dinâmica ou pule a força bruta e opte por uma geração metódica.

Você pode fazer isso:

1. Mantendo um gráfico MxN pronto
2. criando uma / várias soluções
3. fazendo uma pergunta em torno dele, se é um problema de solução singular
4. se houver várias soluções para o problema, você poderá repetir o procedimento acima de forma que a iteração atual não iniba outra solução.

Embora você precise criar um dispositivo de acordo com a complexidade e o tamanho do problema que irá gerar essa pergunta para você. Não use apenas força bruta. Tente algum algoritmo aleatório. Isso pode ajudá-lo.

Que tal outra abordagem? Comece com um labirinto vazio e adicione blocos como este:

1. Bloco inicial e final aleatoriamente.
2. Faça 1-3 etapas "deslizantes" na direção aleatória (mas não retornando) e com comprimento aleatório (*). Coloque um bloco após cada etapa (para parar o slide).
3. Encontre o caminho mais curto para a saída. Se houver muito poucos segmentos (dificuldade de nível baixo), pegue um segmento aleatório do caminho e divida-o com um bloco. Caso contrário, coloque um bloco como na etapa 1 e saia.
4. Repita 1 com cuidado (*): ao escolher o comprimento de uma etapa deslizante, faça com que o bloco inserido não feche o caminho anterior.

Toque final: encontre a rota mais curta com o algoritmo que você forneceu. Anote todas as células usadas e comece a preencher o restante aleatoriamente, sempre garantindo que o caminho mais curto não fique mais curto.

Há uma advertência na etapa dois, quando você não pode colocar o último bloco para que ele não cruze os caminhos usados, mas vejo duas soluções para isso: mova o bloco final mais cedo ou desfaça algumas etapas e tente novamente.

E outro pensamento para o comprimento aleatório das etapas deslizantes - você pode escolher para que um bloco colocado anteriormente seja reutilizado, desde que os caminhos não se sobreponham.