PathFinding en ligne droite ( Java )

Salut !
Alors voila, en faite je cherche à développer un système de création aléatoire de niveau.
J'ai réussis à faire à créer les salles en nombres et tailles aléatoires, les placer, mais je n'arrive pas à les relier.
Donc mon problème est "simplement" de relier deux points A et B, sans passer à l'intérieur des salles ( Mais les couloirs peuvent se croiser eux. ), et en étant le plus possible "droits".
Pour faire simple :
http://img13.imageshack.us/img13/8625/6wc3.png
Le point Vert est le point de départ, et le Rouge l'arrivé.
Moi je voudrais avoir le chemin Noir, et pas le chemin Bleu.

Voila un autre petit dessin :
http://img824.imageshack.us/img824/1591/uhjh.png
Les deux chemins Verts peuvent donc se croiser, mais ils ne peuvent pas rentrer dans les carrés Noirs.

Je pense que le mieux serait d'utiliser l'Algorithme AStar, mais impossible de trouver une explication "correcte" en français.

Si possible, je cherche des explications qui prennent le Java pour base, ça me sera moins compliquer que si c'est expliquer pour un langage.

Merci d'avance !

( Désoler si c'est le mauvais endroit, je savais pas trop où poster ^^" )

Bonjour,

Je pense que le A* n'est pas vraiment une bonne idée, car vous souhaitez le limiter (pas de possibilité de faire des escaliers et pas de possibilités de coller les murs de la salle).
L'idée, c'est de partir sur une idée simple.
À la première case d'entrée et de sortie, vous devez d'abord vous décaler de un, pour ne pas longer les murs, après, vous devez vous déplacer que sur une seule direction à la fois et autant que possible (tant que cela vous rapproche de la case destination) continuer sur cette direction.

Enfin, votre algorithme ne doit pas traverser de salle, tout en vous déplaçant avec les contrainte précédentes. Le fait de coder ces trois règles, je pense, donneront déjà un résultat prometteur.

Une simple carte de distance peut aussi faire l'affaire :
- carte de distance depuis l'origine.
- parcours inverse à partir de l'arrivée.

Citation:

---

Envoyé par LittleWhite

Je pense que le A* n'est pas vraiment une bonne idée, car vous souhaitez le limiter (pas de possibilité de faire des escaliers et pas de possibilités de coller les murs de la salle).

---

Il est assez simple d'obtenir des chemins "orthogonaux" avec A* si on utilise une distance de Manhattan.

Finalement, j'ai très légérement modifier le code de la génération des salles, en rajoutant un mur "fictif" autour de mes salles.
( J'entends par cela que ce murs ne peut pas être traverser par le chemin comme un mur normal. )
Par contre, j'aimerais ( Si possible ) éviter que deux chemins ne se longent, je prefèrerais qu'ils se superpose.

Ça donnerais ça :
http://img689.imageshack.us/img689/5576/3zg4.png


Avec en noir les murs "traversable" par le chemin, en rouge les murs non traversables, en vert le chemin que je souhaiterais avoir, et en bleu celui que j'aimerais éviter.

Donc j'avais effectivement vu qu'avec un AStar et une distance de Manathan c'était possible, il faut que je regarde dans cette direction.

Par contre, c'est quoi une carte de distance ?