С таким количеством доступных реализаций, что самое быстрое выполняет (наименьшее количество ЦП интенсивный, самый маленький двоичный файл), межплатформенный (Linux, Mac, Windows, iPhone)* реализация для C++ с помощью маленькой сетки?
Реализации
Возвраты Google:
Какие-либо другие?
Колесо
Вопрос, как спросили, принадлежит повторному использованию (включите игру), не переизобретение (по крайней мере, только когда производительность, как показывают, является проблемой). Могло бы оказаться, что реализация Dijkstra (или универсальный новаторский алгоритм) лучше подходит, или что самые быстрые реализации не достаточно быстры. Я ценю предложения альтернативных алгоритмов, однако вопрос не, "Я должен прокрутить свое собственное*?"
посмотрите на другие алгоритмы нахождения пути (например, дыхание - сначала глубину, MiniMax, Negmax и т. Д.) Положительные и негативы для вашего сценария.
Усилие также имеет реализацию A-Star . Попробуйте использовать Эти инструкции для создания повышения на iPhone, но это может не работать для вас: это не «полный порт» повышения, и это может быть ошибка.
Ниже приведен из алгоритмов в двух словах (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 );
}
Когда у вас есть определенные границы, с которыми вы можете работать, вам обычно лучше писать алгоритм самостоятельно. В частности, ваше небольшое пространство государства поддается оптимациям, которые проводят память UP-Front, чтобы уменьшить время процессора, и тот факт, что вы используете сетку, а не произвольное пространство государства, позволяет вам делать такие вещи, как оптимизировать генерацию узла преемника или Сможете лечить все частичные пути, которые заканчиваются на одной и той же сетке, что и эквивалентны (что нормальный поиск * не будет и не может предположить).
(PS. OpenSteer, коллекция поведения рулевого управления, не имеет ничего общего с помощью A *, что является алгоритмом поиска, за исключением того, что вы можете использовать один, другой или оба для прохождения пространства. Обык замена для другой в самых разумных обстоятельствах.)
У меня есть два общих совета:
Я предлагаю вам реализовать алгоритм самостоятельно. Следуйте псевдокоду: A* Поисковый алгоритм и он должен быть прямым. Openet" должен быть реализован как min-heap, что также тривиально; или вы можете использовать priority_queue из STL.
Там в есть универсальная реализация C ++ A * http://www.ceng.metu.eedu.tr/~cune/codes.html . Похоже, это все кроссплатформенные стандартные C ++.