taviroquai 55 Posted March 25, 2011 Report Share Posted March 25, 2011 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 Link to post Share on other sites
Warrior 68 Posted March 25, 2011 Report Share Posted March 25, 2011 Sim, pensa que pontos do espaço necessitam de ser considerados como possíveis pontos de passagem e quais os edges. Link to post Share on other sites
taviroquai 55 Posted March 25, 2011 Author Report Share Posted March 25, 2011 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? Link to post Share on other sites
Warrior 68 Posted March 25, 2011 Report Share Posted March 25, 2011 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? Link to post Share on other sites
taviroquai 55 Posted March 25, 2011 Author Report Share Posted March 25, 2011 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? Link to post Share on other sites
Warrior 68 Posted March 25, 2011 Report Share Posted March 25, 2011 Acho que existia um enunciado semelhante numa cadeira na feup. Link to post Share on other sites
taviroquai 55 Posted March 25, 2011 Author Report Share Posted March 25, 2011 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... Link to post Share on other sites
xtrm0 1 Posted March 25, 2011 Report Share Posted March 25, 2011 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> Link to post Share on other sites
KTachyon 276 Posted March 25, 2011 Report Share Posted March 25, 2011 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 Link to post Share on other sites
Warrior 68 Posted March 25, 2011 Report Share Posted March 25, 2011 Mas o jogo envolve programação ou tu é que o estás a programar? Link to post Share on other sites
taviroquai 55 Posted March 25, 2011 Author Report Share Posted March 25, 2011 @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 Link to post Share on other sites
xtrm0 1 Posted March 25, 2011 Report Share Posted March 25, 2011 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> Link to post Share on other sites
taviroquai 55 Posted March 25, 2011 Author Report Share Posted March 25, 2011 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. Link to post Share on other sites
xtrm0 1 Posted March 26, 2011 Report Share Posted March 26, 2011 Há ok. Vou tentar inscrever-me a usar outro browser. <Signature goes here> Link to post Share on other sites
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now