package model.world.graphs; import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; import model.world.graphs.RandomCollection.RandomCollection; import model.world.Direction; import model.world.Position; import utils.Utils; public class MappedGraphBuilder { static private boolean marque[][]; static private MappedGraph mappedGraph; /** * @param sizeX Width of the grid * @param sizeY Height of the grid * @param root Algorythm entry point, (should be random) * @param nbNode The portion of node you want (in %) * @param complexityNode This variable is used to impact the average number of branch per node (in %) * @return MappedGraph instance * @author halonso * @see model.world.graphs.MappedGraph * @since 2017-17-11 * Function to retrieve a random perfect connexe graph. The complexity of the graph obtained can be adjusted. * Quick idea how it work : we explore the map as a growing plant. At each moment, the vertex explored have nbNode chance to transform into node, * then others branchs have their chances to go. */ static public MappedGraph build(int sizeX, int sizeY, Position root, int nbNode, int complexityNode) { mappedGraph = new MappedGraph(sizeX, sizeY); marque = new boolean[sizeX][sizeY]; int totalVertex = sizeX * sizeY; mappedGraph.initializeVertex(); LinkedList randomDirection = new LinkedList<>();//random direction generator randomDirection.add(Direction.LEFT); randomDirection.add(Direction.RIGHT); randomDirection.add(Direction.TOP); randomDirection.add(Direction.BOT); RandomCollection recursionContainer = new RandomCollection(totalVertex);//recursion fifo markPosition(root); recursionContainer.add(root); int cpt = 0; int doneIterator = 0; int nbBlock=0; return RecursionEntryPoint(sizeX, sizeY, recursionContainer, randomDirection, nbNode, complexityNode, cpt, totalVertex, doneIterator,nbBlock); } static private MappedGraph RecursionEntryPoint(int sizeX, int sizeY, RandomCollection recursionContainer, LinkedList randomDirection, int nbNode, int complexityNode, int cpt, int totalVertex, int doneIterator, int nbBlock) { while (!recursionContainer.isEmpty()) { Position actu = recursionContainer.pop(); cpt++; Collections.shuffle(randomDirection);//generating new iteration order each time Iterator iterator = randomDirection.iterator(); int toAdd = 1; int rand = Utils.nextInt(100); if (rand < nbNode) {//choisit comme étant un noeud toAdd++; for (int i = 0; i < 2; i++) { rand = Utils.nextInt(100); if (rand < complexityNode) {//gagne une branche toAdd++; } } } while (toAdd != 0 && iterator.hasNext()) { Direction direction = iterator.next(); Position neighbour = mappedGraph.getValidAdj(actu, direction); if (neighbour != null && !done(neighbour)) { mappedGraph.addEdge(actu, neighbour); markPosition(neighbour); recursionContainer.add(neighbour); toAdd--; } } } if (cpt == totalVertex) { System.out.println("The construction of the graphe blocked "+ nbBlock+ " times."); return mappedGraph; } else {//Il reste des cases isolés while (doneIterator < totalVertex) {//on itere sur le graphe pour trouver une case non marqué int y = doneIterator / sizeX; int x = doneIterator % sizeX; Position cleanPosition = new Position(x, y); if (!done(cleanPosition)) {//On a trouvé une case non atteinte for (Direction dir : Direction.values()) {//On cherche un voisin atteint Position neightboor = mappedGraph.getValidAdj(cleanPosition, dir); if (neightboor == null || !done(neightboor)) {//Si non valide ou non atteint, on cherche un autre continue; } mappedGraph.addEdge(neightboor, cleanPosition); markPosition(cleanPosition); recursionContainer.add(cleanPosition); return RecursionEntryPoint(sizeX, sizeY, recursionContainer, randomDirection, nbNode, complexityNode, cpt, totalVertex, doneIterator, nbBlock+1); } } doneIterator++; } } return RecursionEntryPoint(sizeX, sizeY, recursionContainer, randomDirection, nbNode, complexityNode, cpt, totalVertex, 0, nbBlock);//Certaine cases peuvetn passer entre les mailles du filet } static private void markPosition(Position pos) { marque[pos.x][pos.y] = true; } static private boolean done(Position pos) { return marque[pos.x][pos.y]; } }