IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Intelligence artificielle Discussion :

help IA, Astar


Sujet :

Intelligence artificielle

  1. #1
    Membre à l'essai
    Inscrit en
    Avril 2006
    Messages
    21
    Détails du profil
    Informations forums :
    Inscription : Avril 2006
    Messages : 21
    Points : 13
    Points
    13
    Par défaut 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

  2. #2
    Membre habitué Avatar de archer
    Ingénieur développement logiciels
    Inscrit en
    Mai 2007
    Messages
    338
    Détails du profil
    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : Mai 2007
    Messages : 338
    Points : 180
    Points
    180
    Par défaut
    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)
    rien pour l'instant

  3. #3
    Membre éprouvé
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    865
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 865
    Points : 1 069
    Points
    1 069
    Par défaut
    Si tu trouves que ta matrice prend trop de place pour le peu d'informations qu'elle contient, oriente-toi vers une matrice creuse.

  4. #4
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    Pour A* :

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

    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.

  5. #5
    Membre actif
    Inscrit en
    Mars 2008
    Messages
    209
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 209
    Points : 227
    Points
    227
    Par défaut
    Citation Envoyé par aoyou Voir le message
    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 mais c'est une matrice creuse
    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

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    38
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 38
    Points : 46
    Points
    46
    Par défaut
    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

  7. #7
    Membre éprouvé
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    865
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 865
    Points : 1 069
    Points
    1 069
    Par défaut
    Citation Envoyé par benDelphic Voir le message
    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

  8. #8
    Membre confirmé

    Inscrit en
    Février 2007
    Messages
    202
    Détails du profil
    Informations forums :
    Inscription : Février 2007
    Messages : 202
    Points : 450
    Points
    450
    Billets dans le blog
    1
    Par défaut en vrac
    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.

Discussions similaires

  1. Réponses: 2
    Dernier message: 10/03/2003, 17h20
  2. help please
    Par atom267 dans le forum CORBA
    Réponses: 2
    Dernier message: 24/01/2003, 11h41
  3. [Kylix] fichiers help kylix2 oe ??
    Par sdoura2 dans le forum EDI
    Réponses: 2
    Dernier message: 29/11/2002, 15h32
  4. Help :Problème de clignotement
    Par LE CHAKAL dans le forum Composants VCL
    Réponses: 6
    Dernier message: 14/08/2002, 11h53
  5. Help InnoSetup ou Installshield
    Par buzz dans le forum Outils
    Réponses: 4
    Dernier message: 30/07/2002, 16h26

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo