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
Tableau muti-dimonsion?
Bonjour g'ai un probleme avec mon programme (exercice) qui consiste a faire un espace contenant des obstacles .
voici mes question presises:
1-dois-je utiliser une matrice(tableau)ou une liste chainée pour representé cette espace caré . S.V.P donner moi des argument
merci d'avance
quelques petites questions: quel type d'obstacle envisage-tu ?
et quelle est la taille de ton parcours/map ?
n'y as t'il que des obstacle à représenter ?
en effet, si ta map est grande et ton pas petit, il parais logique d'utiliser plutot une liste, mais si il y as des éléments définis en chaques points de ta map, un tableau serait plus performant...
salut
Donc ton niveau est de taille très raisonnable.
Donc j'aurais une question, pourquoi souhaiterais-tu utiliser une liste chainée ? (sachant en plus que chaque case est susceptible d'avoir des informations importantes tel la présence d'un mur ou non)
Sachant aussi qu'une telle liste est utile dans le cas ou des choses peuvent disparaitre totalement (au sens ou ton niveau va réduire ou augmenter de taille un peu n'importe comment ou que des informations sont susceptibles de disparaitre ou d'arriver).
Il peut être utile d'utiliser des listes chainées couplées à une matrice dans le cas ou il faut stocker dans informations sur d'autres choses (par exemple des ennemis, des joueurs), mais a priori, tu n'as pas besoin de ça.
EDIT : Un autre avantage à utiliser un tableau est que la création du graphe pour lancer le parcours se déduit assez facilement de celui-ci. Alors qu'avec une liste d'obstacle, ce n'est pas évident du toutA moins que tu regroupes les couloirs de ton labyrinthe dans des sommets et que tu construises directement le graphe qui sera de taille optimal, et donc dans ce cas, il ne faut ni un tableau, ni liste chainée, mais un graphe (qui pourra être implementé par une liste cela dit). Mais ça sera moins pratique à visualiser et à créer.
Oui, ca sera plus simple qu'une liste.Envoyé par Super Byte
Mais il faut voir si tu prends en considération que les cases (dans ce cas, matrice pas de problème) ou si tu cherches un type abstrait qui te permet de manipuler également les couloirs (+ efficace pour le parcours) mais différent d'une matrice.
Mais la partie délicate sera toujours l'adaptation de l'algorithme de parcours sur une matrice (enfin, ça sera au moins autant difficile que dans une liste).
Bonjour,
Pour résoudre le problème on pourra utiliser :
- une matrice O permettant d'identifier les obstacles,
- une matrice C indiquant si la cellule a été déjà traitée,
- une matrice P (prédecesseur) indiquant les coordonées en X et Y de la case précédente,
- une file d'attente avec les coordonnées X et Y des cellules à traiter (les cellules non traitées au voisinage de la cellule en cours s'empilent).
Le traitement commence avec dans la file d'attente la cellule de départ et se termine lorsqu'on tombe, parmi les voisins de la cellule à traiter, sur la cellule de fin (ou lorsque la file d'attente est vide ==> pas de solution).
A la fin, on obtiendra le meilleur chemin et sa longueur en faisant le parcours en partant de l'arrivée via la matrice P des prédecesseurs.
Merci pour ta reponse je pense que c'est la meilleure solution (trés optimale :p ) je vais commencer mon algorithme en pascal et je te poserais des questions si je serai coinsé car je ne suis pas trés experimenté en programmation!
merci encore!
Une liste c'est pour gérer de manière dynamique des entités par exemple des personnages d'un jeu: ajouter ou retirer une collection d'entités à la demande.
Un tableau c'est pour une gestion statique,la taille du tableau étant fixe..
donc un tableau sera plus simple
oui je vais tout droit a une representation statique (tableau)
merci pour ta reponse
ce programme sera il plain de sous programme ?
je pense qu'il est purement recursif ? oui ou non
Bonjour,
La recursivité n'est pas indispensable si on gére la file d'attente, on prend en début de file les cellules dèjà atteintes dont on veut traiter les voisins. lors de cetraitement, on rajoutera en fin de file les voisins qui n'ont pas dèjà été traités.
L'avantage d'une telle file d'attente est que les cellules de la file sont directement triées en fonction de la distance au départ.
Pour les sous programmes, ca pourrait être qqchose du genre :
- init des matrices,
- gestion de la file d'attente (init, ajout d'élément en fin de file)
- traitement de l'élément courrant de la file d'attente,
- récupération du chemin et de sa longueur
une matrice O permettant d'identifier les obstacles,
une matrice C indiquant si la cellule a été déjà traitée,
une matrice P (prédecesseur) indiquant les coordonées en X et Y de la case précédente,
une file d'attente F avec les coordonnées X et Y des cellules à traiter (les cellules non traitées au voisinage de la cellule en cours s'empilent).
init des matrices,
O[x,y] : donnée d'entrée (tout à zéro, sauf obstacles à 1)
C[x,y] : tous non traités (à 0) , sauf case départ (à 1)
PX[x,y],PY[x,Y] : tous vide (PX/PY = coord en X/Y du prédecesseur)
gestion de la file d'attente (init, ajout d'élément en fin de file)
Init : TailleF=0
Ajout(x,y) : inc(tailleF) ; FX[taillef]=X ; FY[taillef]=Y ;
traitement de l'élément courrant de la file d'attente,
Pour tous les voisins de {FX[curF],FY[curf]}
non traités ( soit si C[X[curF],FY[curf]] ) ET
non obstacles ( soit si O[X[curF],FY[curf]]=0 )
on ajoute le voisin, on le marque comme traité et on assigne au prédecesseur de ce voisin les coordonnées de l'élément courant (soit FX[curF],FY[curf]}
(si ce voisin est le dernier élement : on aura trouvé)
récupération du chemin et de sa longueur
on part de la case Finale et on parcourt les prédecesseurs jusqu'à ce qu'on tombe sur la case départ.
Merci tres bien
je pense qu'avec tes superbe explications je peut avancé dans mon programme
merci encore
resolu
Répondre avec citation
Partager