bazaarflux/src/main/java/me/lethunderhawk/dungeon/generation/DungeonGridGenerator.java

package me.lethunderhawk.dungeon.generation;

import org.bukkit.Location;
import org.bukkit.Material;
import org.bukkit.World;

import java.util.*;

public class DungeonGridGenerator {

    private final World world;

    private final int gridWidth;
    private final int gridHeight;
    private final int roomSize;
    private final int roomHeight;
    private final int baseY = 99;

    private DungeonRoom[][] grid;
    private final Random random = new Random();

    // Track main path and branches separately
    private final List<DungeonRoom> mainPathRooms = new ArrayList<>();
    private final Set<DungeonRoom> branchRooms = new HashSet<>();

    // Probability that a branch spawns from a room initially
    private static final double INITIAL_BRANCH_CHANCE = 0.4;

    public DungeonGridGenerator(World world, int gridWidth, int gridHeight, int roomSize, int roomHeight) {
        this.world = world;
        this.gridWidth = gridWidth;
        this.gridHeight = gridHeight;
        this.roomSize = roomSize;
        this.roomHeight = roomHeight;
    }

    public void generate() {
        initGrid();
        generateRoomTypes();
        carveRooms();
        carveDoors();
        carvePaths();
    }

    /* =========================
       INITIALIZE GRID
       ========================= */

    private void initGrid() {
        grid = new DungeonRoom[gridWidth][gridHeight];
        for (int x = 0; x < gridWidth; x++)
            for (int z = 0; z < gridHeight; z++)
                grid[x][z] = new DungeonRoom(x, z, DungeonRoomType.REGULAR);
        mainPathRooms.clear();
        branchRooms.clear();
    }

    /* =========================
       GENERATE ROOM TYPES + PATHS
       ========================= */

    private void generateRoomTypes() {

        // 1) RESET
        for (int x = 0; x < gridWidth; x++)
            for (int z = 0; z < gridHeight; z++)
                grid[x][z].type = DungeonRoomType.REGULAR;

        mainPathRooms.clear();
        branchRooms.clear();

        DungeonRoom start = grid[0][0];
        DungeonRoom end = grid[gridWidth - 1][gridHeight - 1];

        // 2) ERZEUGE EINEN SPANNBAUM ÜBER DAS GANZE GRID
        generateSpanningTree(start);

        // 3) FINDE DEN EINDEUTIGEN WEG VON START → END
        List<DungeonRoom> mainPath = findPathInTree(start, end);
        enforceSingleEntranceForEnd(end, mainPath);
        if (mainPath.isEmpty())
            throw new IllegalStateException("Tree path failed");

        mainPathRooms.addAll(mainPath);

        // 4) ROOM TYPES
        mainPath.get(0).type = DungeonRoomType.START;
        mainPath.get(mainPath.size() - 1).type = DungeonRoomType.BLOOD;

        if (mainPath.size() > 2) {
            int fairyIndex = 1 + random.nextInt(mainPath.size() - 2);
            mainPath.get(fairyIndex).type = DungeonRoomType.FAIRY;
        }
    }
    private void enforceSingleEntranceForEnd(DungeonRoom end, List<DungeonRoom> mainPath) {

        // The room that is actually BEFORE the end on the main path
        DungeonRoom realParent = mainPath.get(mainPath.size() - 2);

        // For every neighbor of the end room:
        for (DungeonRoom n : getNeighbors(end)) {

            // If this neighbor is NOT the real main-path predecessor,
            // cut the connection.
            if (n != realParent && areConnected(end, n)) {
                disconnectRooms(end, n);
            }
        }
    }
    private void disconnectRooms(DungeonRoom a, DungeonRoom b) {
        int dx = b.gridX - a.gridX;
        int dz = b.gridZ - a.gridZ;

        if (dx == 1) {
            a.doors[Direction.EAST.ordinal()] = false;
            b.doors[Direction.WEST.ordinal()] = false;
        }
        else if (dx == -1) {
            a.doors[Direction.WEST.ordinal()] = false;
            b.doors[Direction.EAST.ordinal()] = false;
        }
        else if (dz == 1) {
            a.doors[Direction.SOUTH.ordinal()] = false;
            b.doors[Direction.NORTH.ordinal()] = false;
        }
        else if (dz == -1) {
            a.doors[Direction.NORTH.ordinal()] = false;
            b.doors[Direction.SOUTH.ordinal()] = false;
        }
    }
    private void generateSpanningTree(DungeonRoom start) {
        Set<DungeonRoom> visited = new HashSet<>();
        Deque<DungeonRoom> stack = new ArrayDeque<>();

        stack.push(start);
        visited.add(start);

        while (!stack.isEmpty()) {
            DungeonRoom current = stack.peek();
            List<DungeonRoom> neighbors = getNeighbors(current);
            Collections.shuffle(neighbors, random);

            DungeonRoom next = null;
            for (DungeonRoom n : neighbors) {
                if (!visited.contains(n)) {
                    next = n;
                    break;
                }
            }

            if (next == null) {
                stack.pop();
            } else {
                visited.add(next);
                connectRooms(current, next);
                stack.push(next);
            }
        }
    }
    private List<DungeonRoom> findPathInTree(DungeonRoom start, DungeonRoom end) {
        Map<DungeonRoom, DungeonRoom> parent = new HashMap<>();
        Deque<DungeonRoom> queue = new ArrayDeque<>();
        queue.add(start);
        parent.put(start, null);

        while (!queue.isEmpty()) {
            DungeonRoom cur = queue.poll();
            if (cur == end) break;

            for (DungeonRoom n : getNeighbors(cur)) {
                if (!parent.containsKey(n) && areConnected(cur, n)) {
                    parent.put(n, cur);
                    queue.add(n);
                }
            }
        }

        List<DungeonRoom> path = new ArrayList<>();
        DungeonRoom cur = end;

        while (cur != null) {
            path.add(cur);
            cur = parent.get(cur);
        }

        Collections.reverse(path);
        return path;
    }
    private boolean areConnected(DungeonRoom a, DungeonRoom b) {
        int dx = b.gridX - a.gridX;
        int dz = b.gridZ - a.gridZ;

        if (dx == 1) return a.doors[Direction.EAST.ordinal()];
        if (dx == -1) return a.doors[Direction.WEST.ordinal()];
        if (dz == 1) return a.doors[Direction.SOUTH.ordinal()];
        if (dz == -1) return a.doors[Direction.NORTH.ordinal()];
        return false;
    }

    /* =========================
       GENERATE MAIN PATH (biased random walk)
       ========================= */

    private List<DungeonRoom> generateMainPathRandomWalk(DungeonRoom start, DungeonRoom end) {
        List<DungeonRoom> path = new ArrayList<>();
        DungeonRoom current = start;
        path.add(current);

        while (current != end) {
            List<DungeonRoom> candidates = new ArrayList<>();

            for (DungeonRoom neighbor : getNeighbors(current)) {
                int distCurrent = manhattanDistance(current, end);
                int distNeighbor = manhattanDistance(neighbor, end);

                // Only allow steps that don't increase distance to end and are not already in path
                if (distNeighbor <= distCurrent && !path.contains(neighbor)) {
                    candidates.add(neighbor);
                }
            }

            if (candidates.isEmpty()) {
                // Dead end encountered, restart generation to avoid stuck
                return Collections.emptyList();
            }

            current = candidates.get(random.nextInt(candidates.size()));
            path.add(current);
        }

        return path;
    }

    private int manhattanDistance(DungeonRoom a, DungeonRoom b) {
        return Math.abs(a.gridX - b.gridX) + Math.abs(a.gridZ - b.gridZ);
    }

    /* =========================
       CREATE BRANCHES FROM MAIN PATH
       ========================= */

    private void createBranches(DungeonRoom from, double chance) {
        if (chance < 0.1) return; // Stop recursion

        List<DungeonRoom> neighbors = getNeighbors(from);
        Collections.shuffle(neighbors, random);

        for (DungeonRoom neighbor : neighbors) {
            if (mainPathRooms.contains(neighbor) || branchRooms.contains(neighbor))
                continue;

            if (random.nextDouble() < chance) {
                branchRooms.add(neighbor);
                neighbor.type = DungeonRoomType.REGULAR;
                connectRooms(from, neighbor);
                createBranches(neighbor, chance * 0.6);
            }
        }
    }

    /* =========================
       GET GRID NEIGHBORS (N, E, S, W)
       ========================= */

    private List<DungeonRoom> getNeighbors(DungeonRoom room) {
        List<DungeonRoom> neighbors = new ArrayList<>();
        int x = room.gridX;
        int z = room.gridZ;

        if (x > 0) neighbors.add(grid[x - 1][z]);
        if (x < gridWidth - 1) neighbors.add(grid[x + 1][z]);
        if (z > 0) neighbors.add(grid[x][z - 1]);
        if (z < gridHeight - 1) neighbors.add(grid[x][z + 1]);

        return neighbors;
    }

    /* =========================
       CONNECT ROOMS BY SETTING DOORS
       ========================= */

    private enum Direction {
        NORTH, EAST, SOUTH, WEST
    }

    private void connectRooms(DungeonRoom a, DungeonRoom b) {
        int dx = b.gridX - a.gridX;
        int dz = b.gridZ - a.gridZ;

        if (dx == 1) {
            a.doors[Direction.EAST.ordinal()] = true;
            b.doors[Direction.WEST.ordinal()] = true;
        } else if (dx == -1) {
            a.doors[Direction.WEST.ordinal()] = true;
            b.doors[Direction.EAST.ordinal()] = true;
        } else if (dz == 1) {
            a.doors[Direction.SOUTH.ordinal()] = true;
            b.doors[Direction.NORTH.ordinal()] = true;
        } else if (dz == -1) {
            a.doors[Direction.NORTH.ordinal()] = true;
            b.doors[Direction.SOUTH.ordinal()] = true;
        }
    }

    /* =========================
       CARVE ROOMS
       ========================= */

    private void carveRooms() {
        for (int x = 0; x < gridWidth; x++) {
            for (int z = 0; z < gridHeight; z++) {
                DungeonRoom room = grid[x][z];
                Location center = gridToWorld(x, z);
                carveRoom(center, room.type);
            }
        }
    }

    private void carveRoom(Location center, DungeonRoomType type) {
        int half = roomSize / 2;

        for (int dx = -half; dx <= half; dx++) {
            for (int dz = -half; dz <= half; dz++) {
                for (int y = 0; y < roomHeight; y++) {
                    Location loc = center.clone().add(dx, y, dz);

                    if (y == 0 || y == roomHeight - 1) {
                        loc.getBlock().setType(Material.STONE);
                        continue;
                    }

                    if (dx == -half || dx == half || dz == -half || dz == half) {
                        loc.getBlock().setType(Material.STONE);
                        continue;
                    }

                    loc.getBlock().setType(Material.AIR);
                }
            }
        }

        // Place visible marker block on top center (one block above floor)
        Location markerLoc = center.clone().add(0, roomHeight + 3, 0);

        if (type == DungeonRoomType.START) {
            markerLoc.getBlock().setType(Material.GREEN_CONCRETE);
        } else if (type == DungeonRoomType.BLOOD) {
            markerLoc.getBlock().setType(Material.RED_CONCRETE);
        }
    }

    /* =========================
       CARVE DOORS BETWEEN CONNECTED ROOMS
       ========================= */

    private void carveDoors() {
        for (int x = 0; x < gridWidth; x++) {
            for (int z = 0; z < gridHeight; z++) {
                DungeonRoom room = grid[x][z];

                if (x < gridWidth - 1 && room.doors[Direction.EAST.ordinal()]) {
                    DungeonRoom eastRoom = grid[x + 1][z];
                    carveDoorBetween(room, eastRoom, Direction.EAST);
                }

                if (z < gridHeight - 1 && room.doors[Direction.SOUTH.ordinal()]) {
                    DungeonRoom southRoom = grid[x][z + 1];
                    carveDoorBetween(room, southRoom, Direction.SOUTH);
                }
            }
        }
    }

    private void carveDoorBetween(DungeonRoom from, DungeonRoom to, Direction dir) {
        int y = baseY + 1;

        Location fromCenter = gridToWorld(from.gridX, from.gridZ);
        Location toCenter = gridToWorld(to.gridX, to.gridZ);

        int doorX = fromCenter.getBlockX();
        int doorZ = fromCenter.getBlockZ();

        switch (dir) {
            case NORTH -> doorZ -= roomSize / 2;
            case EAST -> doorX += roomSize / 2;
            case SOUTH -> doorZ += roomSize / 2;
            case WEST -> doorX -= roomSize / 2;
        }

        world.getBlockAt(doorX, y, doorZ).setType(Material.AIR);
        world.getBlockAt(doorX, y + 1, doorZ).setType(Material.AIR);
    }

    /* =========================
       CARVE PATHS BETWEEN CONNECTED ROOMS
       ========================= */

    private void carvePaths() {
        for (int x = 0; x < gridWidth; x++) {
            for (int z = 0; z < gridHeight; z++) {
                DungeonRoom room = grid[x][z];

                if (x < gridWidth - 1 && room.doors[Direction.EAST.ordinal()]) {
                    DungeonRoom eastRoom = grid[x + 1][z];
                    carvePathBetweenRooms(room, eastRoom);
                }

                if (z < gridHeight - 1 && room.doors[Direction.SOUTH.ordinal()]) {
                    DungeonRoom southRoom = grid[x][z + 1];
                    carvePathBetweenRooms(room, southRoom);
                }
            }
        }
    }

    private void carvePathBetweenRooms(DungeonRoom from, DungeonRoom to) {
        Location start = gridToWorld(from.gridX, from.gridZ);
        Location end = gridToWorld(to.gridX, to.gridZ);

        int y = baseY;

        int x1 = start.getBlockX();
        int z1 = start.getBlockZ();
        int x2 = end.getBlockX();
        int z2 = end.getBlockZ();

        for (int x = Math.min(x1, x2); x <= Math.max(x1, x2); x++) {
            placePathBlock(x, y, z1);
            placePathBlock(x, y + roomHeight + 10, z1);
        }
        for (int z = Math.min(z1, z2); z <= Math.max(z1, z2); z++) {
            placePathBlock(x2, y, z);
            placePathBlock(x2, y + roomHeight + 10, z);
        }
    }

    private void placePathBlock(int x, int y, int z) {
        world.getBlockAt(x, y, z).setType(Material.STONE_BRICKS);
        world.getBlockAt(x, y + 1, z).setType(Material.AIR);
        world.getBlockAt(x, y + 2, z).setType(Material.AIR);
    }

    /* =========================
       HELPERS
       ========================= */

    private Location gridToWorld(int gridX, int gridZ) {
        int worldX = gridX * (roomSize + 2);
        int worldZ = gridZ * (roomSize + 2);
        return new Location(world, worldX, baseY, worldZ);
    }

    /* =========================
       INNER ROOM CLASS + ROOM TYPES
       ========================= */

    public enum DungeonRoomType {
        START,
        FAIRY,
        PUZZLE,
        MINIBOSS,
        TRAP,
        BLOOD,
        REGULAR
    }

    public static class DungeonRoom {
        public final int gridX, gridZ;
        public DungeonRoomType type;
        public final boolean[] doors = new boolean[4]; // N, E, S, W

        public DungeonRoom(int gridX, int gridZ, DungeonRoomType type) {
            this.gridX = gridX;
            this.gridZ = gridZ;
            this.type = type;
        }
    }
}