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

Sign in to follow this  
Aqua Costa

Route-finding (ajuda por favor)

Recommended Posts

Aqua Costa

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

Share this post


Link to post
Share on other sites
mogers

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


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Aqua Costa

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

Share this post


Link to post
Share on other sites
Aqua Costa

obrigado Tharis acho que é disto que andava à procura.

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

Share this post


Link to post
Share on other sites
Tharis

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

Share this post


Link to post
Share on other sites
mogers

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" 😆


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Aqua Costa

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

Share this post


Link to post
Share on other sites
Tharis

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

Share this post


Link to post
Share on other sites
djthyrax

O A* é basicamente um BFS com heurística.


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
mogers
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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

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)

Share this post


Link to post
Share on other sites
mogers

Hint: Tharis, é possível, mas não sempre...


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

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  

×

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.