Résoudre un labyrinthe avec le "depth first search"
Projet gus05 de développement Java :: Chantiers :: Chantiers techniques :: Traitement des données :: Intelligence artificielle :: Algos pour les labyrinthes
Page 1 sur 1
Résoudre un labyrinthe avec le "depth first search"
Voici une entité pour permet de trouver le chemin dans n'importe quel labyrinthe en utilisant la technique basique du "Depth First Search".
gus.math.maze.solve.algo.depthfirstsearch
Voici une petite vidéo de démonstration sur un exemple de labyrinthe pour voir ce que cela donne.
Si vous êtes intéressé par m'aider à mettre en place et tester d'autres algorithmes, n'hésitez pas à vous manifester !!
gus.math.maze.solve.algo.depthfirstsearch
- Code:
package gus05.entity.gus.math.maze.solve.algo.depthfirstsearch;
import gus05.framework.core.Entity;
import gus05.framework.features.Register;
import gus05.framework.features.Retrieve;
import gus05.framework.tools.DefaultSupport;
public class DepthFirstSearch extends DefaultSupport implements Entity, Register, Retrieve, Runnable {
public String getName() {return "gus.math.maze.solve.algo.depthfirstsearch";}
public String getCreationDate() {return "2011.08.16";}
private boolean[][] maze;
private int[] start;
private int[] end;
private int maze_X;
private int maze_Y;
private int[][] path;
private int index;
public void register(String key, Object obj) throws Exception
{
if(key.equals("maze"))
{
initMaze((boolean[][]) obj);
return;
}
if(key.equals("start"))
{
start = (int[]) obj;
if(start.length!=2) throw new Exception("Invalid size for start int[]: "+start.length);
return;
}
if(key.equals("end"))
{
end = (int[]) obj;
if(end.length!=2) throw new Exception("Invalid size for end int[]: "+start.length);
return;
}
throw new Exception("Unknown key: "+key);
}
public Object retrieve(String key) throws Exception
{
if(key.equals("path")) return finalPath();
if(key.equals("location")) return path[index];
if(key.equals("keys")) return new String[]{"path","location"};
throw new Exception("Unknown key: "+key);
}
public void run()
{
if(!maze[end[0]][end[1]])
{searchOver();return;}
path = new int[(int)(maze_X*maze_Y*0.5)][2];
index = 0;
handleNewPosition(start);
keepSearching();
}
private void keepSearching()
{
int[] move = findNextMove();
if(move!=null)
{
index++; // go forward
handleNewPosition(move);
if(isEnd(move)) {searchOver();return;}
moved();
keepSearching();
}
else // cul-de-sac
{
index--; // go backward
if(index==-1) {searchOver();return;}
moved();
keepSearching();
}
}
private void handleNewPosition(int[] p)
{
path[index] = p;
maze[p[0]][p[1]] = false;
}
private int[] findNextMove()
{
int[][] v = new int[][]{{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
int x = path[index][0];
int y = path[index][1];
int k = 0;
int k1 = -1;
int dmin = maze_X+maze_Y;
if(x>0 && maze[x-1][y])
{
v[k] = new int[]{x-1,y};
int d = distanceToEnd(v[k]);
if(d<dmin) {k1 = k;dmin = d;}
k++;
}
if(x<maze_X-1 && maze[x+1][y])
{
v[k] = new int[]{x+1,y};
int d = distanceToEnd(v[k]);
if(d<dmin) {k1 = k;dmin = d;}
k++;
}
if(y>0 && maze[x][y-1])
{
v[k] = new int[]{x,y-1};
int d = distanceToEnd(v[k]);
if(d<dmin) {k1 = k;dmin = d;}
k++;
}
if(y<maze_Y-1 && maze[x][y+1])
{
v[k] = new int[]{x,y+1};
int d = distanceToEnd(v[k]);
if(d<dmin) {k1 = k;dmin = d;}
k++;
}
return k1==-1?null:v[k1];
}
private int distanceToEnd(int[] p)
{return Math.abs(end[0]-p[0]) + Math.abs(end[1]-p[1]);}
private boolean isEnd(int[] p)
{return p[0]==end[0] && p[1]==end[1];}
private int[][] finalPath()
{
if(path==null || index==-1) return null;
int[][] path1 = new int[index+1][2];
for(int i=0;i<index+1;i++) path1[i] = path[i];
return path1;
}
private void initMaze(boolean[][] m) throws Exception
{
maze_X = m.length;
if(maze_X==0) throw new Exception("Invalid maze_X value = 0");
maze_Y = m[0].length;
if(maze_Y==0) throw new Exception("Invalid maze_Y value = 0");
maze = new boolean[maze_X][maze_Y];
for(int i=0;i<maze_X;i++)
for(int j=0;j<maze_Y;j++)
maze[i][j] = m[i][j];
}
private void moved()
{send(this,"moved()");}
private void searchOver()
{send(this,"searchOver()");}
}
Voici une petite vidéo de démonstration sur un exemple de labyrinthe pour voir ce que cela donne.
Si vous êtes intéressé par m'aider à mettre en place et tester d'autres algorithmes, n'hésitez pas à vous manifester !!
Sujets similaires
» Rechercher la cible la plus proche avec le "Breadth First Search"
» Synology : Paramétrer MySQL pour résoudre le soucis SQL "PacketTooBigException"
» Changer le wallpaper avec JNA
» Afficher des images avec Java
» SSH avec l'API Java Secured Channel
» Synology : Paramétrer MySQL pour résoudre le soucis SQL "PacketTooBigException"
» Changer le wallpaper avec JNA
» Afficher des images avec Java
» SSH avec l'API Java Secured Channel
Projet gus05 de développement Java :: Chantiers :: Chantiers techniques :: Traitement des données :: Intelligence artificielle :: Algos pour les labyrinthes
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|
Mar 16 Sep - 12:01 par Gus
» Présentation du jeu Vindinium
Jeu 20 Fév - 15:32 par Gus
» Rechercher la cible la plus proche avec le "Breadth First Search"
Jeu 20 Fév - 13:06 par Gus
» Impression d'écran avec sélection de zone
Jeu 20 Fév - 12:12 par Gus
» Envoyer un mail par un compte Gmail
Jeu 25 Avr - 14:04 par Gus
» Streaming : comment télécharger les vidéos
Lun 4 Fév - 19:59 par Gus
» Synology : installer ipkg
Mar 22 Jan - 21:22 par Gus
» Trouver le type de lecteur avec JNA
Mer 9 Jan - 23:11 par Gus
» Adresse ip publique et adresse ip privée, Internet box et UPnP
Mer 9 Jan - 21:02 par Gus
» Accéder au numéro de série du lecteur par un script vb
Mer 9 Jan - 19:31 par Gus