Caminho mais curto - Obstaculos são polígonos

[taviroquai 55]

Viva pessoal!

Qual será a melhor forma de resolver o caminho mais curto sendo os "obstaculos", entre o ponto A e o ponto B, polígonos... é o que se verifica nos jogos...

O dijsktra eu conheço e usa os grafos, mas neste caso, há hipotese de transformar os poligonos em grafos (ou pontos dos polígonos)?

Obrigado

[Warrior 68]

Sim, pensa que pontos do espaço necessitam de ser considerados como possíveis pontos de passagem e quais os edges.

[taviroquai 55]

Hmm... vejam se este raciocinio está correcto:

1 - traço uma recta do ponto A ao ponto B

2 - obtenho o conjunto de poligonos [pol1, pol2, ... , polN] intersectados pela recta

3 - se o conjunto estiver vazio então o grafo são só os dois pontos A e B e o edge é a distancia entre eles

4 - se o conjunto não estiver vazio, o grafo será constituido pelos vertices dos poligonos intersectados + os pontos A e B

5 - definino no grafo, edges de custo altíssimo para os edges que intersectam o interior dos polígonos (ainda nao sei como vou fazer isto...)

6 - corro um algoritmo shorttest-path

Será que isto funciona?

[Warrior 68]

Edges de custo altíssimo são edges que não existem.

Basicamente para todos os pares p1 e p2 de vértices dos polígonos intersectados + os pontos A e B, crias edge p1-p2 se p1-p2 não intersectar nenhum polígono.

O único problema é o passo 2. Não o podes aplicar, tens que considerar todos os vértices dos polígonos. Pensa num caso em que o algoritmo com o ponto 2 falha mas sem ele funciona.

Edit: isto é para algum trabalho universitário?

[taviroquai 55]

Edges de custo altíssimo são edges que não existem.

Basicamente para todos os pares p1 e p2 de vértices dos polígonos intersectados + os pontos A e B, crias edge p1-p2 se p1-p2 não intersectar nenhum polígono.

Ok

Edit: isto é para algum trabalho universitário?

Não... mas podia ser porque perguntas?

[Warrior 68]

Acho que existia um enunciado semelhante numa cadeira na feup.

[taviroquai 55]

Isto é para implementar no Diplomatic Wars

O objectivo é mandar as unidades (terrestres ou marítimas) de um ponto para o outro... os polígonos serão as costas dos continentes e ilhas. Só temo que exija bastante de processamento pois os polígonos terão centenas de pontos...

[xtrm0 1]

Não sei como é que funciona o jogo (porque não me consegui increver).

Mas se as rotas forem sempre a partir e para pontos fixos, mais vale préprocessar-los a todos e guardar para cada um uma variavel do estilo:

caminho distancia [ x ][y][j];

sendo x, e y as coordenadas de um ponto e j o passo actual que o tanque está a executar. Por exemplo passo 1=andar 100 metros para a frente. Passo 2 = virar para a direita. Etc.

[KTachyon 276]

Ou, pelo menos utiliza uma heurística para acelerares o processo. Em vez de calculares as rotas mais pequenas, calcula, por exemplo, aquelas que se encontram "mais próximas" do destino. Só tens que arranjar uma heurística que represente o melhor possível a distância ao destino.

[Warrior 68]

Mas o jogo envolve programação ou tu é que o estás a programar?

[taviroquai 55]

@xtrm0

Actualmente, temos duas soluções a funcionar.

1. Movimento simples: movimentos em linha recta que não intersectem obstáculos.

2. Rota personalizada: o jogador pode desenhar as próprias rotas; as que intersectam obstáculos são sempre rotas aéreas.

@KTachyon

Por acaso isso já fiz... as bases dos países sao nós, temos um grafo da rede terrestre e um grafo da rede marítima e com dijsktra já se pode calcular rotas de um pais para o outro...

@Warrior

Sou e mais dois colaboradores que estamos a programar.

Mas gostávamos mesmo de ter um algoritmo para "contornar" os obstáculos como acontece em outros jogos RTS e criar as rotas on-the-fly... daí este tópico

[xtrm0 1]

Não estou a perceber, queres que o utilizador possa desenhar rotas, tipo como se agarra-se numa caneta e desenha-se livremente?

Os calculos seriam feitos em duas ou em três dimensões? Não estou a perceber porque é que queres utilizar poligonos em rotas aéreas.

[taviroquai 55]

Para as rotas aéreas, não há problema nenhum: são rectas, sem obstáculos.

Já é possível o jogador desenhar rotas. Entenda-se por desenhar, marcar os vários waypoints que compõem a rota final... para além desta solução... queremos um processo automático, ou seja, o computador, com base num ponto inicial e final, resolver os waypoints intermédios

A solução o Warrior já disse... converter os vertices dos polígonos em nós do grafo e remover os edges que intersectam os polígonos.

[xtrm0 1]

Há ok. Vou tentar inscrever-me a usar outro browser.