26-03-2014, 03:38 PM
Avec exactement le même principe que plus haut ou que thetaTauTau l'a suggéré:
au lieu de dire "A* est en M[x,y] et il teste M[x±1, y±1]", tu changes pour
"A* est en M[x,y] et il teste M[(x±1)%X, (y±1)%Y]"
avec X, Y la taille de la carte, et % l'opération modulo positif (aka -5%3 = 1 et pas -2).
Utiliser une matrice, même avec des booléens, me semble assez lourd, surtout si tu utilises PHP, qui est un vrai boulet pour ce qui est de l'optimisation mémoire (à part les chaînes de caractères, tout prend une place de dingue en mémoire je crois).
De mon coté, j'ai stocké les liens entre les cases ("on peut aller de la case ... à la case ..."). Partant de là, si je veux implémenter A*, à chaque étape de calcul je peux interroger la BDD pour récupérer les cases voisines de la case en cours de test. L'intérêt est qu'A* utilise bien un graphe, quelconque, et que l'algorithme implémenté n'est alors plus dépendant de la forme de la carte: je peux changer de forme de carte sans difficulté
Une petite variante pour éviter de faire une requête SQL à chaque case à récupérer peut consister à extraire seulement les cases qui se trouvent dans la bouding box et de ne récupérer une "couche" supplémentaire de cases (aka, élargir la bounding box et récupérer les cases qui se trouvent dans l'intervalle) que si le besoin s'en fait sentir.
Je me demande si certains SGDB n'auraient pas A* directement implémenté...
au lieu de dire "A* est en M[x,y] et il teste M[x±1, y±1]", tu changes pour
"A* est en M[x,y] et il teste M[(x±1)%X, (y±1)%Y]"
avec X, Y la taille de la carte, et % l'opération modulo positif (aka -5%3 = 1 et pas -2).
Utiliser une matrice, même avec des booléens, me semble assez lourd, surtout si tu utilises PHP, qui est un vrai boulet pour ce qui est de l'optimisation mémoire (à part les chaînes de caractères, tout prend une place de dingue en mémoire je crois).
De mon coté, j'ai stocké les liens entre les cases ("on peut aller de la case ... à la case ..."). Partant de là, si je veux implémenter A*, à chaque étape de calcul je peux interroger la BDD pour récupérer les cases voisines de la case en cours de test. L'intérêt est qu'A* utilise bien un graphe, quelconque, et que l'algorithme implémenté n'est alors plus dépendant de la forme de la carte: je peux changer de forme de carte sans difficulté
Une petite variante pour éviter de faire une requête SQL à chaque case à récupérer peut consister à extraire seulement les cases qui se trouvent dans la bouding box et de ne récupérer une "couche" supplémentaire de cases (aka, élargir la bounding box et récupérer les cases qui se trouvent dans l'intervalle) que si le besoin s'en fait sentir.
Je me demande si certains SGDB n'auraient pas A* directement implémenté...