[RPG-MAKER.FR] Oniromancie: tout l'univers de RPG Maker en français - Les forums

Surement que AStar cherche pas le plus court, mais le chemin le moins coûteux ( Et c'est pas la même chose apparemment )

Je n'y ai réfléchit que très sommairement mais peut-être un truc dans ce genre ferait l'affaire:

-De base, tu traces depuis la porte un chemin de deux cases qui s'éloigne de la salle, et tu appliques l'algorithme sur l'extrémité de ces chemins plutôt que sur les portes.
-L'algo suit l'un des parcours en L d'un point à l'autre (tout horizontal puis tout vertical, ou l'inverse).
-S'il s'approche d'une salle, il la contourne jusqu'à retombe sur un de point d'un des L.

Par contre si on applique ça sur ton deuxième dessins le couloir vert clair va se superposer au vert foncé sur 5 case, je sais pas si ça pose problème?

-Si c'est pour éviter de coller les chemins aux salles, c'est pas graves, j'ai légèrement modifier le truc depuis ( CF plus bas )
-Pour les portes, je pensais plutôt qu'il choisirais le point le plus proche.
( En gros, je prend un mur de ma salle principale, et je trace un cercle autour avec un rayon qui augmente jusqu'à ce qu'il tombe sur une salle "libre". )
Après, oui faire que des chemins en L sera une bonne idée, mais aucune idée de comment le faire xD.

Pour la dernière question, non c'est pas grave, c'est même presque mieux, si possible j'aimerais justement que lorsque deux chemins sont côte à côte, ils se superpose ( Eviter d'avoir des couloirs de deux cases de largeurs donc ).

Zou :

Pour le chemin vert, y a pas de soucis, j'ai modifier légèrement le code, ce qui fait que autour de la salle y a un mur en plus dans lequel les couloirs ne peuvent pas être créé.

Je me doute que ça sera pas possible d'obtenir exactement ça, je voudrais juste avoir quelques choses le plus près de ça possible ^^.

Tassle : C'est ce que me propose Zou ^^.
J'y avais pas pensé, mais c'est une bonne idée, même si j'en suis pas encore là xD.

J'ai trouvé ce tutoriel :
http://www.game-corp.net/article-12-les-algorithmes-de-pathfinding.html

J'ai essayer de le suivre, mais j'arrive à rien :

package mack.pathfinding;
 
import java.util.ArrayList;
 
public class Path {
 
        
        //Mes deux listes
        public ArrayList<Node> open;
        public ArrayList<Node> close;
 
        
        //Mes Nodes de départ et d'arrivé.
        public Node start;
        public Node end;
 
        
        //Ma carte
        public int[][] map;
 
        //Quand je demande de créer un chemin, j'initialise mes variables.
        public Path(Node s, Node e, int[][] m) {
                start = s;
                end = e;
 
                map = m;
 
                close = new ArrayList<Node>();
                open = new ArrayList<Node>();
        }
 
        //Je lance la création en essayant la première case.
        public void calc() {
                try_node(start);
        }
 
        public void try_node(Node n) {
                close.add(n);
                Node n2 = null;
 
                //J'essai sur la case de Droite
                //Si c'est passable
                if (passable(n.x + 1, n.y)) {
                        //Je créer une node, avec les coordonnées testées, et le parent.
                        Node n3 = new Node(n.x + 1, n.y);
                        n3.parent = n;
                        n3.F = calc_F(n3);
                        //Si elle est pas fermé, je l'ajoute dans la liste fermé, et si son F est plus petit que l'ancien
                        //F je remplace n2 par la nouvelle node.
                        //( Ca se voit pas ici puisque de toute façon c'est la première node )
                        if (!contains(n3)) {
                                n2 = n3;
                                close.add(n2);
                        }
                }
 
                //Et je teste comme ça les 4 cases autours.
                if (passable(n.x - 1, n.y)) {
                        Node n3 = new Node(n.x - 1, n.y);
                        n3.parent = n;
                        n3.F = calc_F(n3);
                        if (!contains(n3))
                                if (n2 != null) {
                                        if (n3.F > n2.F) {
                                                n2 = n3;
                                                close.add(n2);
                                        }
                                } else {
                                        n2 = n3;
                                        close.add(n2);
                                }
 
                }
 
                if (passable(n.x, n.y - 1)) {
                        Node n3 = new Node(n.x, n.y - 1);
                        n3.parent = n;
                        n3.F = calc_F(n3);
                        if (!contains(n3))
                                if (n2 != null) {
                                        if (n3.F > n2.F) {
                                                n2 = n3;
                                                close.add(n2);
                                        }
                                } else {
                                        n2 = n3;
                                        close.add(n2);
                                }
                }
 
                if (passable(n.x, n.y + 1)) {
                        Node n3 = new Node(n.x, n.y + 1);
                        n3.parent = n;
                        n3.F = calc_F(n3);
                        if (!contains(n3))
                                if (n2 != null) {
                                        if (n3.F > n2.F) {
                                                n2 = n3;
                                                close.add(n2);
                                        }
                                } else {
                                        n2 = n3;
                                        close.add(n2);
                                }
                }
                if (n2 != null) {
                        if (n2 != end) {
                                map[n2.x][n2.y] = 5;
                                open.add(n2);
                                try_node(n2);
                        } else {
                                System.out.println("QSD");
                        }
                }
 
        }
 
        //Vérifie si une node avec ces coordonnées existe déjà.
        private boolean contains(Node n3) {
                for (int i=0;i<close.size();++i)
                {
                        if (n3.x==close.get(i).x && n3.y==close.get(i).y)
                                return true;
                }
                return false;
        }
 
        //Je calcul le F  de la node
        public int calc_F(Node n) {
                int i = calc_manhatan(n);
                int j = calc_AN(n);
 
                return i + j;
 
        }
 
        //Je calcul la distance de Manhatan
        public int calc_manhatan(Node n) {
                int i = Math.abs(end.x - n.x) + Math.abs(end.y - n.y);
 
                return i;
        }
 
        //Et je calcul la distance AN ( Pas sur de celle là )
        public int calc_AN(Node n) {
                double i = Math.sqrt(Math.pow(start.x - n.x, 2)
                                - Math.pow(start.y - n.y, 2));
 
                return (int) i;
        }
 
        //Permet de savoir si je peux créer un chemin.
        public boolean passable(int i, int j) {
                if (i >= 0 && j >= 0 && i < map.length && j < map[0].length)
                        return map[i][j] == 0 || map[i][j] == 1; 
                return false;
        }
 
        
        //Permet de lancer le programme directement sans passer par le jeu en lui même.
        //Je m'en sert pour faire mes tests avec une map prè-créer.
        public static void main(String[] args) {
                System.out.println("START");
                
                //Ma map test.
                int[][] m = new int[][] { new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 1, 2, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 2, 2, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 2, 2, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 2, 1, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                                new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
 
                //J'initialise mes Nodes de départ et d'arrivé.
                Node s = new Node(1, 1);
                Node e = new Node(6, 4);
 
                //J'essaie de créer un chemin.
                Path p = new Path(s, e, m);
 
                p.calc();
 
                //Me permet d'afficher dans la console le résultat.
                show_build(m, m.length, m[0].length);
        }
 
        public static void show_build(int[][] room, int x, int y) {
                for (int i = 0; i < x; ++i) {
                        System.out.println();
                        for (int j = 0; j < y; ++j) {
                                switch (room[i][j]) {
                                case 0:
                                        System.out.print(".");
                                        break;
                                case 1:
                                        System.out.print("O");
                                        break;
                                case 2:
                                        System.out.print("#");
                                        break;
                                case 5:
                                        System.out.print("H");
                                        break;
                                }
                        }
                }
        }
 
}

HHHH....HH
H.HH....HH
HO#H....HH
H##H....HH
HHHH.##.HH
HHHH.#O.HH
HHHH....HH
HHHH....HH
HHHHHHHHHH
HHH......H
HHHHHHHHHH

H c'est mon chemin, O c'est le point de départ et d'arrivé et les # sont les chemins pas traversables.

Et voila la Maj du schéma :

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

import java.io.*; import java.util.Vector; public class Path { public Node[] startEnd; public char[][] map; //J'ai viré les deux ArrayList parce que j'ai pas trop compris à quoi elles servaient en fait. //lecture de la carte et des coordonnées de départ arrivé à partir d'un txt parce que c'est plus pratique, quand même :p public Vector<String> lectureMap(String file){ FileReader fread=null; Vector<String> vec=new Vector<String>(); int c=0; int cnt=0; String strtmp=new String(); startEnd=new Node[2]; try { fread =new FileReader(file); } catch (FileNotFoundException e) { System.out.println("Nom de fichier invalide"); } do{ try { c= fread.read(); } catch (IOException e) { System.out.println("Erreur lors de la lecture"); } if((char)c=='\n'){ if(cnt<2){ String[] coord=strtmp.split(","); startEnd[cnt]=new Node(Integer.parseInt(coord[0]),Integer.parseInt(coord[1])); cnt++; strtmp=new String(); } else{ vec.add(strtmp); strtmp=new String(); } } else{ strtmp=strtmp+(char)c; } }while(c!=-1); strtmp=strtmp.substring(0,strtmp.length()-1); vec.add(strtmp); map= new char[vec.size()-1][]; for(int i=0; i<vec.size()-1; i++){ map[i]=vec.elementAt(i).toCharArray(); } show_build(map); return vec; } public void calc() { try_node(startEnd[0]); } public void try_node(Node n) { Node n2 = new Node(-1,-1); n2.F=map.length*map[1].length; for(int i=1; i<5; i++){ /*Là, pour éviter la redondance de code j'ai numéroté les cases adjacentes de 1 à 4 et j'ai bidouiller des formules qui donnent les variations de x et de y en fonction numéro de case, et j'ai fourré le tout dans un "for*/ int modX=(i%2)*(int)Math.pow(-1,(-i/3)); int modY=((i+1)%2)*(int)Math.pow(-1,(-i/4)); System.out.println(passable(n.x+modX,n.y+modY)); if (passable(n.x+modX,n.y+modY)) { Node n3 = new Node(n.x+modX,n.y+modY); n3.parent = n; //J'ai viré la distance de AN parce qu'elle faisait faire un peu n'importe quoi. n3.F = calc_manhatan(n3); if (n2 != null&&n3.F <= n2.F) { System.out.println("n2:"+i); n2=n3; } } if (n2 != null) { if (n2.x==startEnd[1].x&&n2.y==startEnd[1].y) { System.out.println("QSD"); } else { map[n2.x][n2.y] = '5'; show_build(map); try_node(n2); } } } public int calc_manhatan(Node n) { return (int) (Math.abs(startEnd[1].x - n.x) + Math.abs(startEnd[1].y - n.y)); } public boolean passable(int i, int j) { if (i >= 0 && j >= 0 && i < map.length && j < map[0].length) return map[i][j] == '0' || map[i][j] == '1'; return false; } public static void main(String[] args) { Path p=new Path(); p.lectureMap("map.txt"); System.out.println("START"); p.calc(); show_build(p.map); } public static void show_build(char[][] room) { for (int i = 0; i < room.length-1; ++i) { System.out.println(); for (int j = 0; j < room[i].length-1; ++j) { switch (room[i][j]) { case '0': System.out.print("."); break; case '1': System.out.print("O"); break; /*J'ai modifié le code pour le départ (3), pour en retirer la passabilité sinon dans certains cas le chemin peut revenir en arrière.*/ case '3': System.out.print("0"); break; case '2': System.out.print("#"); break; case '5': System.out.print("H"); break; } } } } }