Dav*_*vis 14 c++ iphone algorithm a-star
有这么多可用的实现,使用小网格的C++最快执行(最少CPU密集,最小二进制),跨平台(Linux,Mac,Windows,iPhone)A*实现是什么？
实现
谷歌回归:
还有其他人？
轮
正如所提出的,问题涉及重用(插入游戏),而不是重新发明(至少在性能显示为问题之前).可能会发现Dijkstra实现(或通用寻路算法)更适合,或者最快的实现速度不够快.我很欣赏替代算法的建议,但问题不是,"我应该自己推出A*吗？"
当你有可以使用的特定边界时,你通常最好自己编写算法.特别是您的小状态空间有助于优化前置内存以减少CPU时间,并且您使用网格而不是任意状态空间这一事实允许您执行诸如优化后继节点生成之类的事情,或者能够将所有在同一网格平方上结束的部分路径视为等效(正常A*搜索不会也不能假设).
(PS.OpenSteer,转向行为的集合,与A*无关,这是一种搜索算法,除了你可以理论上使用一个,另一个或两者来遍历一个空间.一个不是替代在最合理的情况下另一个.)
我有两条一般建议:
查看其他路径寻找算法(如Breath-First,Depth-First,Minimax,Negmax等)并权衡您的场景的正面和负面.
Boost还有一个A-star实现.尝试按照这些说明在iPhone上构建boost,但它可能对你不起作用:它不是boost的"完整端口",它可能会出错.
以下是来自Nutshell中的算法(Java,而不是C++,但也许你想要移植它):
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 );
}