LevelsGenerator - click to expand!
class LevelsGenerator {
// MIN NODE = SIDE_SIZE * SIDE_SIZE * 0.75
// MAX NODE = SIDE_SIZE * SIDE_SIZE * 0.625
private static final int MIN_NODE_COUNT_INCLUDED = 4;
private static final int MAX_NODE_COUNT_EXCLUDED = 7;
private static final int SIDE_SIZE = 4; // 16 --> min 12 max 10
private static final int MAX_PATH_LENGTH = SIDE_SIZE * 2 - 3; // length of one corner to the opposite one
private final List<Integer> cornerPositions = new ArrayList<>();
private final Set<Integer> downSidePositions = new HashSet<>();
private final Set<Integer> leftSidePositions = new HashSet<>();
private final Set<Integer> rightSidePositions = new HashSet<>();
private final Set<Integer> upSidePositions = new HashSet<>();
private final Set<Integer> innerPositions = new HashSet<>();
private final Set<Integer> allBoardCell = IntStream.range(0, SIDE_SIZE * SIDE_SIZE).boxed().collect(Collectors.toSet());
private final Graph graph = new Graph(SIDE_SIZE);
private boolean lastIteration;
void Execute(List<LevelsData.LevelData> levelsDataFromFiles) {
SetupSidePositions();
var generatedLevels = new ArrayList<LevelsData.LevelData>();
var startLevel = 1;
var endLevel = 1;
var stopwatch = new StopWatch();
stopwatch.start();
for (var level = startLevel; level <= endLevel; level++) {
generateLevels(generatedLevels, levelsDataFromFiles, level);
}
stopwatch.stop();
System.out.println("DONE in " + stopwatch.formatTime());
var levelsData = new LevelsData();
levelsData.levels = generatedLevels.toArray(new LevelsData.LevelData[0]);
System.out.println(new Gson().toJson(generatedLevels.toArray(new LevelsData.LevelData[0])));
}
private void SetupSidePositions() {
cornerPositions.add(0);
cornerPositions.add(SIDE_SIZE - 1);
cornerPositions.add(SIDE_SIZE * SIDE_SIZE - SIDE_SIZE);
cornerPositions.add(SIDE_SIZE * SIDE_SIZE - 1);
for (var i = 1; i < cornerPositions.get(1); i++) {
downSidePositions.add(i);
}
for (var i = SIDE_SIZE; i < cornerPositions.get(2); i += SIDE_SIZE) {
leftSidePositions.add(i);
}
for (var i = cornerPositions.get(1) + SIDE_SIZE; i < cornerPositions.get(3); i += SIDE_SIZE) {
rightSidePositions.add(i);
}
for (var i = cornerPositions.get(2) + 1; i < cornerPositions.get(3); i++) {
upSidePositions.add(i);
}
for (var i = 0; i < SIDE_SIZE * SIDE_SIZE; i++) {
innerPositions.add(i);
}
innerPositions.removeAll(downSidePositions);
innerPositions.removeAll(upSidePositions);
innerPositions.removeAll(leftSidePositions);
innerPositions.removeAll(rightSidePositions);
innerPositions.removeAll(cornerPositions);
}
private void generateLevels(List<LevelsData.LevelData> generatedLevels, List<LevelsData.LevelData> levelsDataFromFiles, int level) {
System.out.println("Starting for level " + level);
var count = 0;
while (true) {
var nextNodesCount = ThreadLocalRandom.current().nextInt(MIN_NODE_COUNT_INCLUDED, MAX_NODE_COUNT_EXCLUDED);
final LevelsData.LevelData levelData = GenerateLevel(level, nextNodesCount);
if (levelData == null) {
continue;
}
if (!generatedLevels.contains(levelData) && !levelsDataFromFiles.contains(levelData)) {
generatedLevels.add(levelData);
System.out.println("*********************************");
break;
}
}
}
private LevelsData.LevelData GenerateLevel(int level, int nextNodesCount) {
var occupiedPositions = new HashSet<Integer>();
var allConnections = new ArrayList<Connection>();
var currentFreeCells = new HashSet<>(allBoardCell);
var pathCells = new HashSet<Integer>(SIDE_SIZE * SIDE_SIZE);
var allCells = new ArrayList<>(allBoardCell);
Collections.shuffle(allCells);
for (int nextPosition : allCells) {
if (occupiedPositions.contains(nextPosition)
|| !currentFreeCells.contains(nextPosition)
|| IsNotAvailablePosition(nextPosition, occupiedPositions)) {
continue;
}
var isFitForOtherPositions = true;
for (var occupiedPosition : occupiedPositions) {
var tempOccupiedPositions = new HashSet<>(occupiedPositions);
tempOccupiedPositions.remove(occupiedPosition);
tempOccupiedPositions.add(nextPosition);
if (IsNotAvailablePosition(occupiedPosition, tempOccupiedPositions)) {
isFitForOtherPositions = false;
break;
}
}
if (!isFitForOtherPositions) continue;
if (occupiedPositions.isEmpty()) {
occupiedPositions.add(nextPosition);
currentFreeCells.remove(nextPosition);
} else {
var occupiedPositionsToChooseFrom = new ArrayList<>(occupiedPositions);
lastIteration = occupiedPositions.size() == nextNodesCount - 1;
Collections.shuffle(occupiedPositionsToChooseFrom);
for (Integer otherPosition : occupiedPositionsToChooseFrom) {
final Map<Integer, Set<Connection>> selectedConnectionsBySize =
graph.performSearch(nextPosition, otherPosition, SetUtils.union(occupiedPositions, pathCells));
if (!selectedConnectionsBySize.isEmpty()) {
final Connection connection = selectedConnectionsBySize.entrySet().iterator().next().getValue().iterator().next();
allConnections.add(connection);
occupiedPositions.add(nextPosition);
currentFreeCells.removeIf(number -> number == nextPosition || connection.getPath().contains(number));
pathCells.addAll(connection.getPath());
break;
}
}
}
if (occupiedPositions.size() == nextNodesCount) {
break;
}
}
if (occupiedPositions.size() != nextNodesCount || !currentFreeCells.isEmpty()) {
return null;
}
var counts = new HashMap<Integer, Integer>();
for (Connection connection : allConnections) {
final int from = connection.getFrom();
final int to = connection.getTo();
counts.merge(from, 1, Integer::sum);
counts.merge(to, 1, Integer::sum);
System.out.println(connection);
}
return new LevelsData.LevelData(level,
SIDE_SIZE + "x" + SIDE_SIZE,
occupiedPositions.toArray(new Integer[0]),
occupiedPositions.stream().map(counts::get).toArray(Integer[]::new));
}
private boolean IsNotAvailablePosition(int nextPosition, Set<Integer> occupiedPositions) {
return NodesCountOnCornerNextToGiven(nextPosition, occupiedPositions) > 1 ||
NodesCountOnSideNextToGiven(nextPosition, occupiedPositions) > 2 ||
NodesCountOnInnerNextToGiven(nextPosition, occupiedPositions) > 3;
}
private int NodesCountOnCornerNextToGiven(int nextPosition, Set<Integer> occupiedPositions) {
var downLeftCorner = cornerPositions.get(0);
var downRightCorner = cornerPositions.get(1);
var upLeftCorner = cornerPositions.get(2);
var upRightCorner = cornerPositions.get(3);
if (nextPosition == downLeftCorner)
return (int) occupiedPositions.stream().filter(index -> index == nextPosition + SIDE_SIZE || (index == nextPosition + 1)).count();
if (nextPosition == downRightCorner)
return (int) occupiedPositions.stream().filter(index -> index == nextPosition + SIDE_SIZE || index == nextPosition - 1).count();
if (nextPosition == upLeftCorner)
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - SIDE_SIZE || index == nextPosition + 1).count();
if (nextPosition == upRightCorner)
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - SIDE_SIZE || index == nextPosition - 1).count();
return 0;
}
private int NodesCountOnSideNextToGiven(int nextPosition, Set<Integer> occupiedPositions) {
if (downSidePositions.contains(nextPosition)) {
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition + 1 ||
index == nextPosition + SIDE_SIZE).count();
}
if (leftSidePositions.contains(nextPosition)) {
return (int) occupiedPositions.stream().filter(index -> index == nextPosition + 1 ||
index == nextPosition - SIDE_SIZE ||
index == nextPosition + SIDE_SIZE).count();
}
if (rightSidePositions.contains(nextPosition)) {
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition - SIDE_SIZE ||
index == nextPosition + SIDE_SIZE).count();
}
if (upSidePositions.contains(nextPosition)) {
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition + 1 ||
index == nextPosition - SIDE_SIZE).count();
}
return 0;
}
private int NodesCountOnInnerNextToGiven(int nextPosition, Set<Integer> occupiedPositions) {
if (innerPositions.contains(nextPosition)) {
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition + 1 ||
index == nextPosition - SIDE_SIZE ||
index == nextPosition + SIDE_SIZE).count();
}
return 0;
}
public class Graph {
private final int sideSize;
private final int verticesInGraph;
private List<Integer>[] adjacencyList;
private final Map<Integer, Set<Connection>> connectionsBySize = new HashMap<>();
Graph(int sideSize) {
this.sideSize = sideSize;
verticesInGraph = sideSize * sideSize;
}
@SuppressWarnings("unchecked")
private void InitAdjList() {
adjacencyList = new ArrayList[verticesInGraph];
for (var i = 0; i < verticesInGraph; i++) {
adjacencyList[i] = new ArrayList<>();
}
}
private void AddEdge(int from, int to, Collection<Integer> unavailableCells) {
if (unavailableCells.contains(from) || unavailableCells.contains(to)) {
return;
}
adjacencyList[from].add(to);
}
private void CollectAllPaths(int from, int to) {
var isVisited = new boolean[verticesInGraph];
var pathList = new ArrayList<>(List.of(from));
FindAllPaths(from, to, isVisited, pathList);
}
private void FindAllPaths(int from, int to,
boolean[] isVisited,
List<Integer> localPathList) {
isVisited[from] = true;
if (from == to) {
List<Integer> path = new ArrayList<>(localPathList);
var originalFrom = path.get(0);
path = path.subList(1, path.size() - 1);
if (path.size() > 0) {
var con = new Connection(originalFrom, to, path);
connectionsBySize.computeIfAbsent(path.size(), k -> new HashSet<>()).add(con);
}
isVisited[from] = false;
return;
}
if (!lastIteration && localPathList.size() > MAX_PATH_LENGTH) {
return;
}
for (var i : adjacencyList[from]) {
if (!isVisited[i]) {
localPathList.add(i);
FindAllPaths(i, to, isVisited,
localPathList);
localPathList.remove(i);
}
}
isVisited[from] = false;
}
public Map<Integer, Set<Connection>> performSearch(int from, int to, Collection<Integer> unavailableCells) {
connectionsBySize.clear();
GatherCombinations(from, to, unavailableCells);
return connectionsBySize;
}
private void GatherCombinations(int from, int to, Collection<Integer> unavailableCells) {
var remainingOccupiedPositions = new HashSet<>(unavailableCells);
remainingOccupiedPositions.remove(to);
InitAdjList();
for (var index = 0; index < verticesInGraph; index++) {
if (index == cornerPositions.get(0)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
} else if (index == cornerPositions.get(1)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
} else if (index == cornerPositions.get(2)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (index == cornerPositions.get(3)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (downSidePositions.contains(index)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
} else if (leftSidePositions.contains(index)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (rightSidePositions.contains(index)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (upSidePositions.contains(index)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (innerPositions.contains(index)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
}
CollectAllPaths(from, to);
}
}
}
}
