it-swarm-pt.tech

Como faço para implementar um algoritmo de pathfinding A *, com custos de movimentação para cada linguagem de programação?

Podemos levar as pessoas a postar código de implementações simples e otimizadas do algoritmo de pathfinding A *, em cada idioma?

Isso é principalmente por diversão e para brincar com o que o stackoverflow é capaz de fazer ... embora eu realmente esteja interessado em obter uma versão do ActionScript 3 disso.

Mas a ideia é que essa "Questão" continuará a ser atualizada eternamente no futuro, mesmo que diferentes linguagens de programação sejam criadas!

Eu não sei de nenhum outro lugar on-line onde você pode ver o pseudocódigo "traduzido" em muitos (muito menos em cada) idioma diferente. Parece que é um recurso que vale a pena, e embora não seja necessariamente para o que este site foi projetado, não há nenhum mal em experimentá-lo e ver se é uma coisa que vale a pena que o stackoverflow possa ser usado!

29
IQpierce

Aqui está uma implementação JavaScript , juntamente com código-fonte e uma demonstração online Eu fiz como um hobby/projeto de pesquisa.

É muito simples, mas você pode alterar alguns dos parâmetros (tamanho da grade, número de paredes, informações de depuração ativadas/desativadas). Ele mostrará os valores calculados de f (x), g (x) e h(x) para cada nó que é inspecionado.

A implementação da página de demonstração usa o jQuery.

11
Brian Grinstead

Aqui está uma implementação do C++. É bastante bem testado até agora e usado em videogames comerciais e vários projetos de inteligência artificial.

http://code.google.com/p/a-star-algorithm-implementation/

E tem um tutorial, que eu escrevi primeiro:

http://www.heyes-jones.com/astar.html

9
justinhj

Aqui está uma implementação de C # feita por uma das pessoas que criam o idioma.

5
Joel Coehoorn

Códigos-fonte e demonstrações em diferentes linguagens de programação:

Lista de demos para cada idioma:

C++: 1
Java: 3
Processing: 1
Actionscript 3 (Flash): 4
Flex (Flash): 1
Javascript: 6
C#: 1
Ruby: 1
Prolog: 1
Unity: 1
Lua: 1

Pathfinding Demo em diferentes idiomas

Apreciar :)

3
Sir

código-fonte Python e C++ juntamente com tutorial interativo . O código é escrito para trabalhar em gráficos em geral e não é específico para grades (como você encontrará em muitos exemplos de A * na Web). Ele usa heaps binários para a fila de prioridades (tanto Python quanto C++ possuem heaps binários em suas bibliotecas padrão). Eu tenho a Primeira Pesquisa em Largura, o Algoritmo de Dijkstra e A * nessa página. O código é razoavelmente curto (menor que a maioria dos códigos de amostra A * encontrados).

1
amitp

Um exemplo AS 3 ... http://www.dauntless.be/astar/

1
Chris

Não é uma implementação, mas eu achei http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html para ser uma explicação particularmente clara do algoritmo. Possui um pseudocódigo que facilita a implementação, juntamente com uma revisão extensiva de várias estruturas de dados que podem ser usadas para implementar os conjuntos abertos e fechados, uma discussão de diferentes heurísticas que são aplicáveis ​​em diferentes situações, modificações na heurística para obter comportamentos específicos (por exemplo, obter aproximações de retas em sistemas que suportam apenas ângulos limitados de movimento), armadilhas comuns (por exemplo, usando uma heurística com uma escala diferente dos custos reais de movimento) e algumas otimizações (por exemplo, trabalhando com regiões de custo uniforme em vez de grade).

1
Jules

A Clojure implementation, fortemente baseado em um exemplo dado em PAIP .

1
Jeff Foster

Uma implementação do VB6.

http://www.gandraxa.com/pathfinding_with_a_star.xml

Isso é particularmente útil porque você pode percorrer o processo e entender bem como o algoritmo funciona. Isso pode ser muito valioso ao converter o algoritmo para outro idioma.

0
G Mastros

Eu implementei A * em C como uma maneira de aprender C, então não posso prometer que é lindo, mas funciona! Eu usei para resolver o Projeto Euler # 83 e ele funcionou em dois casos de teste.

https://github.com/PeterMitrano/A-star-Pathfinding/blob/master/problem_83.c

0
Peter Mitrano

Uma implementação otimizada Java está disponível no GraphHopper.

0
Karussell