• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Aqua Costa

Route-finding (ajuda por favor)

15 mensagens neste tópico

Como crio um algoritmo para determinar o caminho mais rápido de um determinado ponto para outro com obstáculos pelo meio num jogo de tiles???

ajudem-me por favor

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para te tentar ajudar, é preciso explicares melhor o problema. Jogo de tiles? Explica bem isso...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tipo, o jogo é uma grelha, o teu "boneco" encontra-se num determinado quadrado da grelha e o jogador carrega com o rato noutro quadrado e o "boneco" deve dirigir-se para o quadrado em que o jogador carregou utilizando o percurso mais rápido e podendo-se mover apenas na horizontal, vertical e diagonal de quadrado em quadrado.

O meu problema está em o "boneco" ir até ao quadrado de destino desviando-se dos obstáculos que se encontram em determinados quadrados em que o "boneco" não pode passar.

Bons exemplos de jogos assim são o Dofus e o RuneScape...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

obrigado Tharis acho que é disto que andava à procura.

já agora qual é exactamente a diferença entre DFS e BFS?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

obrigado Tharis acho que é disto que andava à procura.

já agora qual é exactamente a diferença entre DFS e BFS?

Depth First Search - DFS - Pesquisa em Profundidade

Breadth First Search - BFS - Pesquisa em Largura

Tens aqui um texto MUITO BOM da USACO. :P

BTW, o mogers é que é o Senhor Grafo. ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não sabia que os textos do estágio ainda estavam disponiveis ;)  Acho que deviam estar mais "visiveis", isto é, com links a partir da página das ONI (pelo menos acho que não tem). Também acho que deves ler esse texto (também tens um texto de grafos neste link). Usa uma BFS.

BTW, o mogers é que é o Senhor Grafo. :P

"Senhor Grafo" :2funny:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

acho que o BFS funciona mais não será muito lento? por exemplo se o jogo possuir mais de 1000000 (1 milhão) de quadrados não será muito lento????

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

acho que o BFS funciona mais não será muito lento? por exemplo se o jogo possuir mais de 1000000 (1 milhão) de quadrados não será muito lento????

Não. A complexidade de tempo num DFS e BFS é igual, O( | E | + | V | ), onde E são as arestas (edges) e V os vértices (vertex).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
The A* (pronounced A-star) algorithm can be complicated for beginners.

Tu pareces que estás a iniciar-te nestas coisas, daí que seja indicado começar por uma dfs ou bfs.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

vê tb o algoritmo de Dijsktra, mto utilizado em redes de computadores para os routers traçarem as rotas de encaminhamento.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Neste caso o algoritmo de dijkstra seria mais lento porque não tens pesos nas tuas ligações (caso em que o BFS nem funciona), e o melhor que consegues fazer é um O(N log N) contra um O(N) num BFS.

Gostaria era que o senhor tharis me explicasse como calcular o shortest path em O(N) com uma pesquisa em profundidade..

(sim, sim.. renasci o tópico, mas só agora voltei de férias)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora