Can we get people to post code of simple, optimized implementations of the A* pathfinding algorithm, in every single language?
我们是否可以让人们在每种语言中发布A *寻路算法的简单优化实现代码?
This is mostly for fun and to play with what * itself is capable of... although I actually am interested in getting an ActionScript 3 version of this.
这主要是为了获得乐趣,并且可以使用*本身的功能......虽然我实际上对获取ActionScript 3版本感兴趣。
But the idea is that this "Question" will continue to be updated eternally into the future, even as different programming languages are created!
但是这个想法是,即使创建了不同的编程语言,这个“问题”将继续在未来永久更新!
I don't know of any other place online where you can see pseudocode "translated" into many (much less every) different language. Seems like it's a worthwhile resource, and while not necessarily what this site was designed for, there's no harm in trying it out and seeing if it turns out to be a worthwhile thing that * could be used for!
我不知道在线的任何其他地方你可以看到伪代码“翻译”成许多(少得多)的不同语言。看起来它是一个有价值的资源,虽然不一定是这个网站的设计目的,但尝试它并看看是否有可能用于堆栈溢出的有价值的东西是没有害处的!
11 个解决方案
#1
11
Here is a JavaScript implementation, along with source code and an online demo I did as a hobby/research project.
这是一个JavaScript实现,以及作为业余爱好/研究项目的源代码和在线演示。
It is very simple, but you can change some of the params (grid size, # of walls, debugging info on/off). It will show you the calculated f(x), g(x), and h(x) values for each node that is inspected.
它非常简单,但您可以更改一些参数(网格大小,墙壁数量,打开/关闭调试信息)。它将显示检查的每个节点的计算f(x),g(x)和h(x)值。
The demo page implementation uses jQuery.
演示页面实现使用jQuery。
#2
9
Here's a C++ implementation. It's fairly well tested by now, and used in commercial video games and various AI projects.
这是一个C ++实现。它现在已经过相当好的测试,并用于商业视频游戏和各种AI项目。
http://code.google.com/p/a-star-algorithm-implementation/
And there's a tutorial, which I actually wrote first:
还有一个教程,我实际上是先编写的:
#3
#4
3
Source codes and demos in different programming languages:
不同编程语言的源代码和演示:
List of demo's for each language:
每种语言的演示列表:
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 in different languages
寻路演示用不同的语言
Enjoy :)
#5
#7
1
Not an implementation, but I found http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html to be a particularly clear explanation of the algorithm. Has pseudocode that makes it very easy to implement, along with an extended review of various data structures that can be used for implementing the open & closed sets, a discussion of different heuristics that are applicable in different situations, modifications to heuristics to get specific behaviours (e.g. getting approximations of straight lines in systems that only support limited angles of movement), common pitfalls (e.g. using a heuristic with a different scale to the actual movement costs), and some optimizations (e.g. working with regions of uniform cost rather than a grid).
不是实现,但我发现http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html是对算法的特别清楚的解释。具有伪代码,使其易于实现,以及可用于实现开放和封闭集的各种数据结构的扩展审查,讨论适用于不同情况的不同启发式,修改启发式以获得特定行为(例如,在仅支持有限运动角度的系统中得到直线的近似值),常见的陷阱(例如,使用与实际运动成本不同的规模的启发式算法),以及一些优化(例如,使用统一成本的区域而不是格)。
#8
1
Python and C++ source code along with interactive tutorial. The code is written to work on graphs in general, and is not specific to grids (as you will find in many examples of A* on the web). It uses binary heaps for the priority queue (both Python and C++ have binary heaps in their standard libraries). I have Breadth First Search, Dijkstra's Algorithm, and A* on that page. The code is reasonably short (shorter than most A* sample code I find).
Python和C ++源代码以及交互式教程。编写的代码通常用于图形,而不是特定于网格(正如您在Web上的许多A *示例中所见)。它使用二进制堆作为优先级队列(Python和C ++在其标准库中都有二进制堆)。我在该页面上有广度优先搜索,Dijkstra算法和A *。代码相当短(比我找到的大多数A *示例代码短)。
#10
0
I implemented A* in C as a way to learn C, so I can't promise it's beautiful, but it works! I used it to solve Project Euler #83 and it worked on two test cases.
我在C中实现了A *作为学习C的一种方式,所以我不能保证它很漂亮,但它有效!我用它来解决Project Euler#83并且它处理了两个测试用例。
https://github.com/PeterMitrano/A-star-Pathfinding/blob/master/problem_83.c
#11
0
A VB6 implementation.
一个VB6实现。
http://www.gandraxa.com/pathfinding_with_a_star.xml
This is particularly useful because you can step through the process and get a good understanding of how the algorithm works. This can be quite valuable when converting the algorithm to another language.
这特别有用,因为您可以逐步完成整个过程并充分了解算法的工作原理。将算法转换为另一种语言时,这非常有用。
#1
11
Here is a JavaScript implementation, along with source code and an online demo I did as a hobby/research project.
这是一个JavaScript实现,以及作为业余爱好/研究项目的源代码和在线演示。
It is very simple, but you can change some of the params (grid size, # of walls, debugging info on/off). It will show you the calculated f(x), g(x), and h(x) values for each node that is inspected.
它非常简单,但您可以更改一些参数(网格大小,墙壁数量,打开/关闭调试信息)。它将显示检查的每个节点的计算f(x),g(x)和h(x)值。
The demo page implementation uses jQuery.
演示页面实现使用jQuery。
#2
9
Here's a C++ implementation. It's fairly well tested by now, and used in commercial video games and various AI projects.
这是一个C ++实现。它现在已经过相当好的测试,并用于商业视频游戏和各种AI项目。
http://code.google.com/p/a-star-algorithm-implementation/
And there's a tutorial, which I actually wrote first:
还有一个教程,我实际上是先编写的:
#3
#4
3
Source codes and demos in different programming languages:
不同编程语言的源代码和演示:
List of demo's for each language:
每种语言的演示列表:
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 in different languages
寻路演示用不同的语言
Enjoy :)
#5
#6
#7
1
Not an implementation, but I found http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html to be a particularly clear explanation of the algorithm. Has pseudocode that makes it very easy to implement, along with an extended review of various data structures that can be used for implementing the open & closed sets, a discussion of different heuristics that are applicable in different situations, modifications to heuristics to get specific behaviours (e.g. getting approximations of straight lines in systems that only support limited angles of movement), common pitfalls (e.g. using a heuristic with a different scale to the actual movement costs), and some optimizations (e.g. working with regions of uniform cost rather than a grid).
不是实现,但我发现http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html是对算法的特别清楚的解释。具有伪代码,使其易于实现,以及可用于实现开放和封闭集的各种数据结构的扩展审查,讨论适用于不同情况的不同启发式,修改启发式以获得特定行为(例如,在仅支持有限运动角度的系统中得到直线的近似值),常见的陷阱(例如,使用与实际运动成本不同的规模的启发式算法),以及一些优化(例如,使用统一成本的区域而不是格)。
#8
1
Python and C++ source code along with interactive tutorial. The code is written to work on graphs in general, and is not specific to grids (as you will find in many examples of A* on the web). It uses binary heaps for the priority queue (both Python and C++ have binary heaps in their standard libraries). I have Breadth First Search, Dijkstra's Algorithm, and A* on that page. The code is reasonably short (shorter than most A* sample code I find).
Python和C ++源代码以及交互式教程。编写的代码通常用于图形,而不是特定于网格(正如您在Web上的许多A *示例中所见)。它使用二进制堆作为优先级队列(Python和C ++在其标准库中都有二进制堆)。我在该页面上有广度优先搜索,Dijkstra算法和A *。代码相当短(比我找到的大多数A *示例代码短)。
#9
#10
0
I implemented A* in C as a way to learn C, so I can't promise it's beautiful, but it works! I used it to solve Project Euler #83 and it worked on two test cases.
我在C中实现了A *作为学习C的一种方式,所以我不能保证它很漂亮,但它有效!我用它来解决Project Euler#83并且它处理了两个测试用例。
https://github.com/PeterMitrano/A-star-Pathfinding/blob/master/problem_83.c
#11
0
A VB6 implementation.
一个VB6实现。
http://www.gandraxa.com/pathfinding_with_a_star.xml
This is particularly useful because you can step through the process and get a good understanding of how the algorithm works. This can be quite valuable when converting the algorithm to another language.
这特别有用,因为您可以逐步完成整个过程并充分了解算法的工作原理。将算法转换为另一种语言时,这非常有用。