Implémentation A * multiplateforme la plus rapide?

Avec de nombreuses implémentations disponibles, ce qui est le plus rapide en cours d'exécution (moins de CPU, de la plus petite binaire), multi-plateforme (Linux, Mac, Windows, iPhone)* mise en œuvre de C++ à l'aide d'une petite grille?

Implémentations

Google retourne:

Tout les autres?

La Roue

La question, comme l'avait demandé, se rapporte à la réutilisation (prise dans un jeu), pas de réinvention (au moins pas jusqu'à ce que la performance est montré pour être un problème). Il pourrait s'avérer que un Dijkstra mise en œuvre (ou générique algorithme de pathfinding) est mieux adapté, ou que le plus rapide des implémentations ne sont pas assez rapides. J'apprécie les suggestions de la variante des algorithmes, mais la question n'est pas, "dois-je roule mes propres*?"

source d'informationauteur Dave Jarvis

  1. 6

    Regarder autre chemin pour trouver des algorithmes (comme le Souffle-tout d'Abord, la Profondeur d'Abord, Minimax, Negmax etc.) et de peser les points positifs et négatifs de votre scénario.

    Boost aussi a un Une-star de la mise en œuvre. Essayez de suivre ces instructions à construire le coup de pouce sur l'iPhone, mais il pourrait ne pas fonctionner pour vous: il n'est pas un "port" de boost et il pourrait d'erreur.

    Ce qui suit est Algorithmes en un Mot (Java, C++, mais vous aimeriez peut-port):

    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 );
}
  2. 6

    Lorsque vous avez des limites que vous pouvez travailler avec vous, vous êtes généralement mieux écrire l'algorithme de vous-même. En particulier, votre petit état de l'espace se prête à des optimisations qui font passer la mémoire afin de réduire les temps de calcul, et le fait que vous êtes à l'aide d'une grille plutôt que de l'arbitraire d'un espace d'état vous permet de faire des choses comme optimiser votre successeur du nœud de génération, ou être en mesure de traiter toutes partielle des chemins qui se terminent sur le même carré de la grille comme équivalent (une normale, une* recherche ne sera pas et ne peut pas assumer).

    (PS. OpenSteer, une collection de la direction des comportements, y a rien à faire avec Un*, qui est un algorithme de recherche, sauf que vous pouvez théoriquement utiliser l'un, l'autre ou les deux traversent un espace. On n'est pas un remplacement pour l'autre dans la plupart raisonnable circonstances.)

  3. 5

    Je vous suggère de mettre en œuvre l'algorithme par vous-même. Suivez le pseudo-code: * Algorithme De Recherche et il doit être simple. Le "openset doit être mis en œuvre comme un min-tas, qui est aussi trivial; ou vous pouvez utiliser priority_queue de STL.

  4. 5

    J'ai deux morceaux de conseils:

    • Si votre domaine est restreint à une grille, peut-être, vous trouverez de meilleurs résultats par la recherche "pathfinding" plutôt le terme plus général d'Un*.
    • Si votre domaine n'est pas strictement la recherche des chemins le long d'une surface, vous pouvez obtenir plus d'avantages de vos efforts si vous passez votre temps à améliorer votre méthode heuristique plutôt que d'essayer d'optimiser l'algorithme lui-même.
  5. 2

    Il y a un générique de C++ A* la mise en œuvre au http://www.ceng.metu.edu.tr/~cuneyt/codes.html. Il semble que c'est tous les cross-platform C++ standard.