help IA, Astar

Bonjour,

Voici mon souci , j'aurai besoin de conseil.
Je developpe une application tierce qui commande des bots a travers une map. Je veux donc utiliser l'algorithme A* (astar) pour optimiser le deplacement de mes bots (pas le droit aux waypoints).

La map etant au format 65536 coordonnées (x) par 65536 coordonnées (y) je voulais donc creer une matrice 65k * 65k et entrer les donnees des batiments sur cette matrice.
(ex : 000000
011000
000000
000000)

L'algorithme A* me permettant ainsi de ne pas entrer en colision avec les objets du decor lors de mon deplacement.

Le probleme etant que
1) je trouve cette matrice un peu encombrante pour le peu de données utile qu'elle contient.
2) j'ai les coordonnées des extremités des batiments mais je me suis pas amusé a prendre chaque batiment point par point. Existe il une fonction permettant de trouver la diagonale entre un point a(3, 2) et un point e(54,12) par exemple ?

J'avoue avoir besoin de vos conseils. :)
Merci d'avance pour votre aide.
Feez

Salut
Je crois qu’il faut calculer l’équation de la droite qui relie ces deux points a(ax,ay) et e(ex,ey) : tout calcul fait on trouve
Y= (ay-ey)/(ax-ex)*X+ (ay-ax*(ay-ey)/(ax-ex)) avec min(ax,ex)<=X<=max(ax,ex) et min(ay,ey)<=Y<=max(ay,ey)

Si tu trouves que ta matrice prend trop de place pour le peu d'informations qu'elle contient, oriente-toi vers une matrice creuse.

Pour A* :

http://khayyam.developpez.com/articles/algo/astar/

Citation:

---

1) je trouve cette matrice un peu encombrante pour le peu de données utile qu'elle contient.

---

Comme l'a dit aoyou, utilise une matrice creuse.

Citation:

---

Envoyé par aoyou

Si tu trouves que ta matrice prend trop de place pour le peu d'informations qu'elle contient, oriente-toi vers une matrice creuse.

---

euh :roll: mais c'est une matrice creuse:lol:
au lieu de coder tes bâtiments ainsi (les zéros sont inutiles) sauvegarde juste des points repères . vu que tu cherche comment calculer la diagonale non

Si tu trouves que ta matrice est trop grande regarde les changements de base et matrice de passage :

http://serge.mehl.free.fr/anx/ChgtBTri.html
http://www.meca.unicaen.fr/Enseignem...rs/node18.html

Citation:

---

Envoyé par benDelphic

au lieu de coder tes bâtiments ainsi (les zéros sont inutiles) sauvegarde juste des points repères . vu que tu cherche comment calculer la diagonale non

---

C'est justement ce qu'on cherche à faire avec une matrice creuse...
http://fr.wikipedia.org/wiki/Matrice_creuse

salut,

comme ça je dirait que l'algorithme de Bresenham est en mesure de répondre à ton besoin.

Surtout je te renvoie aux articles de la série "AI wisdom" dont un qui correspond particulierement : précalculated pathfinding, où l'on explique
comment avoir des chemins dans un tableau

et 2 articles du meme nom sur Gamedev:
http://www.gamedev.net/reference/art...rticle1939.asp

qui est une version remaniée d'un précèdent qui n'était pas tout à fait fonctionnel.