最快的跨平台 A* 实现? [英] Fastest cross-platform A* implementation?
问题描述
有这么多可用的实现,使用小网格的 C++ 执行速度最快(CPU 占用最少、二进制最小)、跨平台(Linux、Mac、Windows、iPhone)A* 实现是什么?
With so many implementations available, what is the fastest executing (least CPU intensive, smallest binary), cross-platform (Linux, Mac, Windows, iPhone) A* implementation for C++ using a small grid?
实施
谷歌返回:
- http://www.heyes-jones.com/astar.html(该网站上的大多数链接都已失效.)
- http://www.grinninglizard.com/MicroPather(据说比 Heyes-琼斯.)
- http://www.ceng.metu.edu.tr/~cuneyt/codes.html(通用 C++ 代码.)
- http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
- http://opensteer.sourceforge.net/(对游戏很感兴趣,不是 A*.)
- Dijkstra 算法的堆栈溢出
- http://www.heyes-jones.com/astar.html (Most links on that site are dead.)
- http://www.grinninglizard.com/MicroPather (Said to be slower than Heyes-Jones'.)
- http://www.ceng.metu.edu.tr/~cuneyt/codes.html (Generic C++ code.)
- http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
- http://opensteer.sourceforge.net/ (Interesting for games, not A*.)
- Stack Overflow on Dijkstra's Algorithm
还有其他的吗?
轮子
正如所问的那样,这个问题与重用(插入游戏)有关,而不是重新发明(至少在性能被证明是一个问题之前).事实证明,Dijkstra 实现(或通用寻路算法)更适合,或者最快的实现不够快.我很欣赏替代算法的建议,但问题不是,我应该推出自己的 A* 吗?"
The question, as asked, pertains to reuse (plug into a game), not reinvention (at least not until performance is shown to be an issue). It might turn out that a Dijkstra implementation (or generic pathfinding algorithm) is better suited, or that the fastest implementations are not fast enough. I appreciate the suggestions of alternative algorithms, however the question is not, "Should I roll my own A*?"
推荐答案
查看其他寻路算法(如 Breath-First、Depth-First、Minimax、Negmax 等)并权衡您的场景的正面和负面.
Look at other path-finding algorithms (like Breath-First, Depth-First, Minimax, Negmax etc.) and weigh the positives and negatives for your scenario.
Boost 也有一个A-star实施.尝试按照这些说明在 iPhone 上构建提升,但它可能不适合您:它不是 boost 的完整端口",它可能会出错.
Boost also has an A-star implementation. Try following these instructions to build boost on iPhone, but it might not work for you: it is not a "full port" of boost and it might error out.
以下内容来自 算法简述(Java,不是 C++,但也许你喜欢移植它):
The following is from Algorithms in a Nutshell (Java, not C++ but maybe you'd like to port it):
public Solution search( INode initial, INode goal ) {
// Start from the initial state
INodeSet open = StateStorageFactory.create( StateStorageFactory.TREE );
INode copy = initial.copy();
scoringFunction.score( copy );
open.insert( copy );
// Use Hashtable to store states we have already visited.
INodeSet closed = StateStorageFactory.create( StateStorageFactory. HASH );
while( !open.isEmpty() ) {
// Remove node with smallest evaluation function and mark closed.
INode n = open.remove();
closed.insert( n );
// Return if goal state reached.
if( n.equals( goal ) ) { return new Solution( initial, n ); }
// Compute successor moves and update OPEN/CLOSED lists.
DepthTransition trans = (DepthTransition)n.storedData();
int depth = 1;
if( trans ! = null ) { depth = trans.depth + 1; }
DoubleLinkedList<IMove> moves = n.validMoves();
for( Iterator<IMove> it = moves.iterator(); it.hasNext(); ) {
IMove move = it.next();
// Make move and score the new board state.
INode successor = n.copy();
move.execute( successor );
// Record previous move for solution trace and compute
// evaluation function to see if we have improved upon
// a state already closed
successor.storedData( new DepthTransition( move, n, depth ) );
scoringFunction.score( successor );
// If already visited, see if we are revisiting with lower
// cost. If not, just continue; otherwise, pull out of closed
// and process
INode past = closed.contains( successor );
if( past ! = null ) {
if( successor.score() >= past.score() ) {
continue;
}
// we revisit with our lower cost.
closed.remove( past );
}
// place into open.
open.insert( successor );
}
}
// No solution.
return new Solution( initial, goal, false );
}
这篇关于最快的跨平台 A* 实现?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!