PATHFINDING - Page 1

je voudrais faire une routine de path finding (si vous connaissez heroes ou civilization c pour tracer le chemin le + rapide d'un pt a un autre) sachant qu'il faut detecter les murs ou mers et que tous les sols n'ont pas la meme penalité de deplacement............
le chemin est faisable mais avec moi c jamais le plus court.....;

Là on est dans une phase ou il faut utiliser les graphs...
En gros t'as un tableau n,p replie de true (la case est accéssible) et de false.
Après c'est un algo récursif (sujet des mines de cette année, ou des ensi). Si je retrouve mon TD j'en parlerais plus longuement.

J'ai fait un path-fiding pour total, je peut essayer de t'expliquer :

Tu fais une routine path_lenght (A, B) qui te trouve la distance du meilleur chemin entre A et B. Voila comment elle marche:

| Pour commencer, tu va en ligne droite du point A au point B.
| Si tu rencontre un obstacle (un case a penalité pour toi), tu prend la direction perpendiculaire au deplacemnt, et du trouve les deux case a droite et a gauche de l'abstacle (C et D).
 | Et tu renvoie [b]MIN ( path_lenght(A,C)+path_lenght(C,B), path_lenght(A,D)+path_lenght(d,B) )[b] (appel recurcif)
| Sinon, tu renoie la distance en ligne droite
| Et s'il y a un ostacle incontournable (la mer qui va j'usqu'au bout de la map), tu renvoie 0xffff.

Il va falloir qui tu limite le nombre de recursivitées, sinon, le calcul ne finira jamais !

Et tu rajouter quelques subtilitées pour eviter de recalculer plusieurs foi la meme chose, mais c'est pas facile ...

Dark Angel, c'est du bidouillage

Comme Paxal l'a dit, faut faire appel à la théorie des graphes.
M'enfin, la solution idéal n'est franchement pas économique en temps et en place.
Faudrait aussi que je rouvre mes TD

JM> Je n'ai aucunes connaissances sur la theorie des graphs, ou quoique ce soit qui y ressemble, et cette methode est celle que j'ai inventée pour Total (apres une autre beaucoup plus bricolage).

Je trouve qu'elle marche pas mal pour une consommation CPU raisonnable (en fait, ca depend du nombre maximum de recurence qu'on autorise) ...

Par contre, si vous voulez bien expliquer la theorie des graphs, ca peut etre interressant

Bah ! La théorie des graphes c'est pour faire joli

Si ça prend trop de ressources, on préféra se tourner vers des bidouilles : il n'y a qu'à regarder la commande 'go to' dans Civ II.

dark angel>pas mal comme bidouillage je crois que je vais essayer ça...

sinon ça me derange pas que vous rouvriez vos TD !!!ça peut etre instructif

moi je vois que le récursif au pb, je peux parler du sujet car j'ai fait un programme qui passe les 4500 sous-niveaux, donc question de ça c'est bon !
il faut monoploliser un petit coup la calc pour calculer le chemin, et en très peu de temps, je pense que le truc est faisable !
Si tu vois mal comment on peux faire, je te filerai un coup de main

Pour la recherche des chemins possibles, et particulierement le plus court, il existe l'algo "Graphsearch" (utilisé dans le jeux Sim's)

Voila l'algo écrit par un de mes profs :
[url]http://www-prima.imag.fr/Prima/jlc/Courses/1999/ENSI3.SE/graphsearch.pdf [/url]
Il est anglais, donc si tu captes pas ce qui raconte, c normal

Cet algo peut etre amélioré (version A*)

Si tu connais déjà tes chemins, l'algo Dijkstra te permettra de trouver le plus court (algo ss doute trouvable sur le Net).
Mais je pense qu'il est preferable d'utiliser Graphsearch.

Si tu captes pas le Clips, il existe une version d'explication de l'algo en francais :

http://www-prima.imag.fr/Prima/jlc/Courses/1998/ENSI3.SE/ENSI3.SE.S3.pdf

mais on n'a pas les droits en dehors du domaine imag. Des que j'y ai a nouveau acces, je te l'envoie.

Tu expliques un truc ? :0
Whoua

kes tu fous la ?
pis j'explique qd je sais.
bon d'accord j'y connais rien en assembleur ==> j'explique rien

le jour ou je saurais, peut etre...

PpHd-> et la cour martiale tu y a pensé ?

merci

Bah, j'ai finis mon stage deja
Il me reset 8 semaines a glander.

Nan nan

Hum !

c nikel l'algo!!!
ça peut etre prndre de le mem par contre

Je pense que t'as pu le trouver, mais qd meme :
http://www-prima.imag.fr/Prima/jlc/Courses/1998/ENSI2.SE/

pis tu recuperes le ENSI2.SE.S3.*
par exemple le .word (ouais, c du .doc quoi)
y a meme un .ps

liquid --> tu parles de Graphsearch ?
Si c le cas je vois pas ce qui prendrait trop de memeoire ??
en ASM je sais pas, je suis pire qu'un Newbie...

sur qu'un algo avec un tableau de bits, question memoire ...

JM: Oui. Mais c'est aussi pour ca que je me suis grouiller

tu poste pas tres vite en ce moment.
tu bosses en parallelle ?

Non. C'est un ordi a part, l'ordi internet. Max securisise.

il tourne avec Genlib ou pas ?

Surement pas. Genlib pour les systémes Unix n'est qu'en version bêta 0.8. Je pense qu'il a du l'installer discretos sur sa SGI, et il fait les betas tests dessus.

Alalala

non tu as p e raison ça doit pas prendre trop de mem (en C)
mais c koi les != entre les deux liens?

en fait c pas des pb de droits d'acces, mais la version .pdf n'existe plus.

Comme c les vacances, Crowley a fait le menage dans ses repertoires...

bref g imprimé le 1er lien en fr et il me convient parfaitement

Je sais pas si ça peut t'aider mais il y a quelques années (et je crois que c'est le premier algo que j'ai jamais "inventé". J'avait donc eu l'idée de trouver le chemin a partir du contour des cases ou groupes de cases non franchissables.

Description rapide de l'algo qui trouve le trajet :
On va en direction du point de destination. Si on rencontre un obstacle, on suit son contour un fois par la gauche, une fois par la droite puis on repere si entre un des point du contour et le point de destination il y a un chemin sans obstacle. Si oui voila un chemin non réduit trouvé, sinon prendre le point du contour le plus proche du point de destination et recommencer.
Ensuite opérer à une réduction du chemin complet avec un petit algo récursif.

Je n'ai pas trop envie de réfléchir la dessus mais je peux te dire qu'il y a plein de bidouillages a découvrir pour améliorer l'efficacité (le plus simple c'est d'avoir les contours des objets déja calculés au lieu de les retrouver a chaque fois).
Sinon je peux t'assurer que meme avec des labyrinthes le chemin est toujours trouvé (a part certains cas, ça dépent de l'algo) et si il est réduit correctement il peut etre le quasi plus court. Mais bon cet algo est bien car il reproduit une marche intelligente si tu veux l'implémenter dans un jeu ou tu peux guider un perso. J'entend ici par intelligente car elle ressemble au trajet qu'aurait eu un humain et non pas a un sujet omniscient qui voit tout et aurait tracé un trajet en conséquent.