A comunidade brasileira de desenvolvimento e programação de jogos.
3D Simulador

ESTUDO DE ALGORITMOS DE BUSCA: BUSCA OTIMIZADA PELO MELHOR CAMINHO EM UMA CIDADE 

Autor: Bianca
O projeto consiste em realizar estudos comparativos entre dois algoritmos:
- A*;
- Dijkstra;

O modelo foi desenvolvido utilizando a biblioteca GLScene.
Foram construidos 2 cenários para testes onde a morfologia do terreno é diferente.
Os testes são realizados com e sem obstáculos em cada cenário.

Graças a perseverança, e a grande ajuda que obtive de alguns membros desta comunidade e a alguns códigos fontes disponíveis, consegui concretizar este projeto.

Muito Obrigada.
  Cadastro: 25/07/2007
Atualização: 22/03/2009
Status: 000% concluído
Views: 871

Arquivos 

Estudo de Algoritmos de Busca: Busca otimizada pelo melhor caminho em uma cidade. (25/07/2007 14:33)

Imagens 

Projeto PreciosoAlgoritmo Dijkstra sem obstáculoTeste realizado com o algoritmo A* no cenário 1 com obstáculo

Discussão 

 

Entrar no Tópico

Bianca Jalegria Legal teu trabalho. Só agora fui olhar, pois nunca mais postei aqui... Como mencionei anteriormente, fiquei muito chateada com minha avaliação, então larguei tudo... Mas agora estou regressando...
jalegria Parabéns Bianca!!! Pelas telas que vi parece muito legal, por coincidencia tive que fazer um trabalho semelhante, depois se quiser dá uma olhadinha, . Eu vou me formar só agora (31 anos, to ficando véio), to fazendo design de jogos. Sempre programei com OpenGL puro e C++ e sempre gostei. Agora to aprendendo XNA com C# e to achando legal, e olha que sou fanático pelo OpenGL e sempre detestei o DirectX, mas agora acho que a M$ caprichou.
igtukra Me permitem ressucitar o tópico???? ) - Um algoritimo que ele criou-modificou, sei lá, conseguia simular a absorção interna dos meshes (assim como um corpo humano). O outro, tinha um idéa vaga de fazer algo sobre AI e elementos de jogos.... No fim das contas, o primeiro, que tinha uma idéa bacana e com elementos muito interessantes, desistiu da idéia, pois segundo ele, o professor, não iria entender do que se tratava, e decidiu fazer um compactador de voz, que usou em um sistema de trasmissão de dados pela net - um skype tosco. Projeto esse 1000 vezes mais simples que o anterior. Meu outro colega etão, decidiu usar a ideia dele, e fez o bendito simulador. E como estava previsto, o projeto foi mal analisado, e recebeu uma nota buracrática..... Já o Skype tosco, foi febre entre os professores. Então é o seguinte: Continua com o teu bom trabalho. Eu dei uma olhada rápida naquilo que tu publicou e achei muito interessante. Na real duvido alguem aqui da comunidade que...
Bianca Entendo.,. eu tb vou ter que ficar um período pagando o financiamento... O dinheiro que juntei só deu pro começo. Depois consegui um financiamento de 70%
Bianca , mas..., percebi que me desgastei muito mais que o necessário ao longo da graduação. Percebi tb que os professores exigem coisas que só agradam a eles próprios. Ou seja, se tu queres ficar bem colocado na graduação ou pós, tu tens que puxar o saco deles. Em outras palavras, para iniciar um projeto de pesquisa, tu tens que escolher o mesmo assunto de algum professor, só assim que se ganha prestígio no fim de uma graduação. E eu não gosto disso. Como assunto para um projeto, procuro escolher aquilo que gosto, para que assim, as coisas sejam feitas com prazer, e ao mesmo tempo, possamos aprender cada vez mais. Melhor do que escolher o mesmo assunto do professor que da o peixe, é aprender a pescar, e conseguir se virar sozinho. Acho mais divertido assim. Ao constatar que alguém que ganha o peixe, recebe uma melhor colocação do que aquele que se esforça, fiquei com trauma de formatura. A minha formatura é no dia 10 e vai ser em gabinete. Não convidei ninguém,...
Aziz Cursos superiores na area de informática não valem nada na minha opinião, as tecnologias evoluem e mudam tão rápido que só estudando por si só vc consegue acompanhar , não liga pra opinião da banca pq a opinião deles não vale nada aproveite os conhecimentos que vc adquiriu nesse projeto pra fazer alguma coisa legal e que va te trazer experiência e dinheiro!.rs
Luiz Pestana eu me formei cedo, porém 2 anos depois ainda estava pagando a faculdade...
Bianca Te formaste novo.., eu me formei véia... Eu não tinha dinheiro pra pagar, esperei um bom tempo até que finalmente consegui um emprego, só assim pude juntar dinheiro. A partir daí foi possível pagar a graduação. Vida de pobre é difícil.
Luiz Pestana
Bianca Só uma observação.., eles não deram a mínima para o software que desenvolvi..., e ainda, acharam que modelagem em si é superfulo. Quando escolhi o tema para o TC, resolvi associar computação gráfica com inteligência artificial. O que deu a entender, é que eles (a banca) não acham importante a computação gráfica. O que posso adiantar aqui é que o meu projeto propõe um estudo comparativo de dois algoritmos de busca otimizada: Dijkstra e A* O objetivo é saber se a heurística utilizada em A* é admissível, e se ela influencia na eficiência do desempenho do algoritmo. Pois, Dijkstra e A* são semelhantes, diferenciando-se apenas que A* utiliza heurística e Dijkstra não. A implementação no início foi difícil, mas foi tão prazeirosa, vcs devem saber a sensação...
Luiz Pestana Estou muito curioso para ver seu trabalho.
Bianca Pelo menos fico feliz de não ter gastado 690 reais nessa imundície de formatura! É horrível gastar uma nota preta em uma comemoração sem sentido, onde estamos insatisfeitos com os resultados. Comemora-se algo quando se está satisfeito e imensamente feliz com o desfecho.
Bianca
Bianca
JD557 Ora aí está uma grande verdade... para se arranjar um emprego no ramo do gamedev é mais importante um portefólio com bons trabalhos do que um bom curso.
c-low Concordo com você e com o Luiz. O que deve ser julgado não são as ferramentas e sim as técnicas e o conhecimento empregado. De qualquer forma quando qualquer um daqueles seus amigos "pouco estudiosos" terminarem a facu, vão ser desempregados, ou no máximo programadores meia boca. Quando estiveres trabalhando, o que vai contar é teu conhecimento e experiência, e isso com certeza você vai ter mais do que "os colegas de classe que procuraram o caminho mais fácil". Com bastante conhecimento você sobe mais rápido de cargo que os outros, ou ainda pode criar algo inovador, enquanto que os outros estão presos às mesmas idéias acadêmicas. Suas dores de coluna não foram uma perda total, afinal você tirou muito conhecimento daí. Este conhecimento, no futuro, pode e será útil para algum propósito. Tudo vem ao seu tempo e provavelmente alguma coisa vai ser aproveitada. Gostaria de dar o mais sincero "parabéns" pela perseverança e coragem. "Uma grande realiza...
Luiz Pestana Bom, acho que se é emergente ou não, não deveria ter sido considerado um ponto falho no seu trabalho, dou um exemplo: eu não considero o C++ uma linguagem emergente mas tenho certeza que até hj é a mais aplicada em desenvolvimento de jogos. Oq deveria ser analisado em seu trabalho é a técnica que você utilizou para desenvolve-lo, e não se a ferramenta X ou Y não está mais em desenvolvimento. Até pq no contexto qual você necessita dela, ela atende perfeitamente sem necessidade de evolução. Também tive o mesmo problema que você ao fazer meu trabalho de conclusão, fiz um tema muito dificil, pouco trivial e que tive que pesquisar muito para desenvolver, porém não compliquei minha saude por causa disso. Acho que devemos priorizar nossa saude. Parabens pela conclusão do seu trabalho, e se puder, disponibilize seu trabalho para que possamos examina-lo também! =)
Bianca Primeiro vou finalizar o processo do trabalho, e assim publicarei o mais breve possível. Mas uma coisa eu digo..., para quem está em uma faculdade, não vale à pena se esforçar não. Pois tu constatas que muitos dos teus colegas nunca se esforçaram tanto para estudar ou fazer trabalhos, eles se escoram nos outros colegas mais esforçados, e conseguem as melhores notas. Enquanto que tu, durante todos os anos acadêmicos, fica ali ralando estudando e sacrificando 90% dos teus finais de semana. Enquanto isso, tu ve os teus colegas sairem com os amigos, se divertirem. Colegas esses que no final, tu verás ganhando nota boa e menção honrosa.
JD557 Bianca, pode mostrar aí o seu trabalho? Talvés com tecnologias emergentes eles se estivessem a referir a shaders/efeitos especiais. GLScene suporta GLSL?
c-low Bom, isso é uma questão delicada, eu também tive a infelicidade de conhecer professores que só julgam como bom o que conhecem a fundo. Também conheci outros que eram mais justos em suas decisões. De qualquer forma justiça não é algo que podemos esperar da maioria. Eu acredito que GLScene é uma tecnologia que pode ser considerada emergente sim. Bem como o Delphi que está em constante desenvolvimento. Se for comparar em termos de ser novo ou velho, uma tecnologia considerada por quase todos como nova, o Java, foi oficialmente lançado em 1995, enquanto o GLScene começou a ser desenvolvido em 1999. Referências: Se ainda houver algo que possa ser feito, não desista. Boa sorte!
Bianca É o seguinte amigo, fiz meu trabalho de conclusão utilizando o GLScene. Fiquei super decepcionada com a avaliação da banca. Ainda tiveram a petulância de dizer que não utilizei nenhuma ferramenta emergente. ¬¬ É duro tu te dedicares de corpo e alma a um projeto, te matar programando, escrever 125 páginas, e ninguém ver valor nisso. Tenho colegas que bancam os espertos, escolhem professores que estejam pesquisando um assunto, de preferência tecnologia de ponta. Escolhem estes professores como orientadores, e escolhem o mesmo assunto de pesquisa dos orientadores, pois vão receber toda a barbada, tudo praticamente pronto, informação direto da fonte. O pior disso é que eles recebem menção honrosa e bolsa de estudos. Enquanto que pessoas como eu que escolhem um assunto completamente desconhecido pelos professores e orientadores, e correm atrás do desconhecido, não recebem mérito algum por isso. O fim da picada foi dizer que GLScene não é uma ferramenta ...
c-low Primeiro, desculpa se minha resposta não tiver nada haver. Espero ter colaborado.
Bianca Boa noite pessoal. Sei que existe muita gente experiente aqui que está habituada a utilizar esta ferramenta. Quero saber de vcs, GLScene, é uma ferramenta emergente? Ou seja, é uma ferramenta nova ou uma ferramenta não emergente? A opinião de vcs programadores experientes no uso desta ferramenta, é muito importante. Conto com vcs.

Desenvolvido e administrado por: Luiz Pestana (2004 - 2011)