Jump to content
Sign in to follow this  
taviroquai

Caminho mais curto - Obstaculos são polígonos

Recommended Posts

taviroquai

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 ;)

Share this post


Link to post
Share on other sites
Warrior

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

Share this post


Link to post
Share on other sites
taviroquai

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?

Share this post


Link to post
Share on other sites
Warrior

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?

Share this post


Link to post
Share on other sites
taviroquai

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 :P porque perguntas?

Share this post


Link to post
Share on other sites
taviroquai

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...

Share this post


Link to post
Share on other sites
xtrm0

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.


<Signature goes here>

Share this post


Link to post
Share on other sites
KTachyon

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.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
taviroquai

@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 ;)

Share this post


Link to post
Share on other sites
xtrm0

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.


<Signature goes here>

Share this post


Link to post
Share on other sites
taviroquai

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.