it-swarm-eu.dev

Jak implementuji algoritmus A * pathfinding s náklady na pohyb pro každý programovací jazyk?

Můžeme přimět lidi, aby poslali kód jednoduchých, optimalizovaných implementací algoritmu A * pathfinding do každého jazyka?

To je většinou pro zábavu a hrát s tím, co stackoverflow sám je schopen ... i když jsem vlastně zájem získat verzi ActionScript 3 tohoto.

Ale myšlenka je, že tato "otázka" bude i nadále aktualizována věčně do budoucnosti, i když jsou vytvořeny různé programovací jazyky!

Nevím o žádném jiném místě on-line, kde můžete vidět pseudocode "přeloženo" do mnoha (mnohem méně každého) jiného jazyka. Vypadá to, že je to cenný zdroj, a přestože ne nutně to, co tyto stránky byly navrženy, není žádná škoda při pokusu o to a vidět, jestli se ukáže, že je to užitečná věc, kterou by stackoverflow mohl být použit!

29
IQpierce

Zde je implementace JavaScriptu , spolu s zdrojový kód a online demo , který jsem udělal jako koníček/výzkumný projekt.

Je to velmi jednoduché, ale můžete změnit některé z parametrů (velikost mřížky, # stěn, ladění informací zapnuto/vypnuto). Zobrazí hodnoty vypočtené hodnoty f (x), g (x) a h(x) pro každý kontrolovaný uzel.

Implementace demo stránky používá jQuery.

11
Brian Grinstead

Zde je implementace C++. To je docela dobře testovaný nyní, a použitý v komerčních videohrách a různých AI projektech.

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

A je tu návod, který jsem napsal jako první:

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

9
justinhj

Zde je C # implementace provádí jeden z lidí, kteří staví jazyk.

5
Joel Coehoorn

Zdrojové kódy a ukázky v různých programovacích jazycích:

Seznam ukázek pro každý jazyk:

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

Demonstrace v různých jazycích

Užívat si :)

3
Sir

Python a C++ zdrojový kód spolu s interaktivní výukou . Kód je napsán pro práci s grafy obecně a není specifický pro mřížky (jak najdete v mnoha příkladech A * na webu). Používá binární hromady pro prioritní frontu (Python i C++ mají ve svých standardních knihovnách binární svazky). Na této stránce mám první vyhledávání, Dijkstraův algoritmus a A *. Kód je přiměřeně krátký (kratší než většina ukázkových kódů A *).

1
amitp
1
Chris

Není implementací, ale zjistil jsem, že http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html je obzvláště jasné vysvětlení algoritmu. Má pseudokód, díky kterému je velmi snadné implementovat, spolu s rozšířeným přezkoumáním různých datových struktur, které lze použít pro implementaci otevřených a uzavřených sestav, diskusí o různých heuristikách, které jsou použitelné v různých situacích, úpravách heuristiky pro získání specifického chování. (např. získání aproximace přímek v systémech, které podporují pouze omezené úhly pohybu), společná úskalí (např. použití heuristiky s odlišným měřítkem k skutečným nákladům na pohyb) a některé optimalizace (např. práce s oblastmi s jednotnými náklady spíše než mřížka).

1
Jules

A Clojure implementace, silně založená na příkladu uvedeném v PAIP .

1
Jeff Foster

Implementace VB6.

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

To je obzvláště užitečné, protože můžete postupovat procesem a získat dobré pochopení toho, jak algoritmus funguje. To může být velmi cenné při převodu algoritmu na jiný jazyk.

0
G Mastros

Implementoval jsem A * v C jako způsob, jak se naučit C, takže nemůžu slíbit, že je to krásné, ale funguje to! Použil jsem ho k řešení projektu Euler # 83 a pracoval na dvou testovacích případech.

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

0
Peter Mitrano

Optimalizovaná implementace jazyka Java je dostupná v GraphHopper.

0
Karussell