Solved Need some help with custom dungeon algorithm

Discussion in 'Spigot Plugin Development' started by JoshC, Mar 4, 2020.

  1. Hi,

    In the past week I've been developing a plugin which a user can create dungeon "modules". These modules are so to call rooms of a dungeon. Each room of the dungeon has their corresponding gates. I've finally come to the part in where I'm generating a random dungeon. With a 90% succes.

    What currently is happening is that the dungeon is almost properly being generated except for a few modules. Some modules end up to the outside and are not closed off. In my code I'm using recursive looping to loop through each gate of each module and then check whether it has a module next to it or not. If it doesn't it spawns a new random module from a given list with gates.

    As for my code to generate the dungeon:
    Dungeon which spawns in the first module
    Code (Java):

    public class Dungeon {

        private Main main;

        private List<DungeonModule> connectors;

        public Dungeon(Main main) {
            this.main = main;
        }

        public void generate(Location startingLoc) {
            // Devide modules up
            DungeonModule spawnRoom = null;

            connectors = new ArrayList<>();

            // Loop through all modules and sort them by type
            for (DungeonModule listedModule : DungeonManager.getAllModules()) {
                if (listedModule.getModuleType() == ModuleType.SPAWN_ROOM) spawnRoom = listedModule;
                if (listedModule.getModuleType() == ModuleType.CONNECTOR) connectors.add(listedModule);
            }

            if (spawnRoom == null) return;

            // place spawn room
            DungeonModule spawnedSpawnRoom = DungeonManager.instantiate(spawnRoom, startingLoc);

            spawnedSpawnRoom.setup(connectors);
        }
    }
     
    Module code:
    Code (Java):
    public class DungeonModule {

        private String yamlPath;
        private String schematicPath;
        private String name;

        private Location spawnPoint;

        private List<Gate> gates3;
        private List<Gate> gates5;
        private List<Gate> gates7;
        private List<Gate> gates9;
        private List<Gate> gates11;
        private ModuleType moduleType;

        private List<DungeonModule> connectors;

        public void setup(List<DungeonModule> connectors) {
            this.connectors = connectors;

            instantiateNewModuleToGates(gates3);
            instantiateNewModuleToGates(gates5);
            instantiateNewModuleToGates(gates7);
            instantiateNewModuleToGates(gates9);
            instantiateNewModuleToGates(gates11);
        }

        private void instantiateNewModuleToGates(List<Gate> gates) {
            if (gates == null) return;
            if (gates.size() == 0) return;

            for (Iterator<Gate> iterator = gates.iterator(); iterator.hasNext();) {
                Gate gate = iterator.next();
                gate.instantiateNewModule(this);
            }
        }

        public String getYamlPath() {
            return yamlPath;
        }

        public String getSchematicPath() {
            return schematicPath;
        }

        public String getName() {
            return name;
        }

        public Location getSpawnPoint() {
            return spawnPoint;
        }

        public void setYamlPath(String yamlPath) {
            this.yamlPath = yamlPath;
        }

        public void setSchematicPath(String schematicPath) {
            this.schematicPath = schematicPath;
        }

        public void setName(String name) {
            this.name = name;
        }

        public void setSpawnPoint(Location spawnPoint) {
            this.spawnPoint = spawnPoint;
        }

        public List<Gate> getGates3() {
            return gates3;
        }

        public void setGates3(List<Gate> gates3) {
            this.gates3 = gates3;
        }

        public List<Gate> getGates5() {
            return gates5;
        }

        public void setGates5(List<Gate> gates5) {
            this.gates5 = gates5;
        }

        public List<Gate> getGates7() {
            return gates7;
        }

        public void setGates7(List<Gate> gates7) {
            this.gates7 = gates7;
        }

        public List<Gate> getGates9() {
            return gates9;
        }

        public void setGates9(List<Gate> gates9) {
            this.gates9 = gates9;
        }

        public List<Gate> getGates11() {
            return gates11;
        }

        public void setGates11(List<Gate> gates11) {
            this.gates11 = gates11;
        }

        public void setModuleType(ModuleType moduleType) {
            this.moduleType = moduleType;
        }

        public ModuleType getModuleType() {
            return moduleType;
        }

        public List<DungeonModule> getConnectors() {
            return connectors;
        }
    }
    And last but not least the Gate code:
    Code (Java):
    public class Gate {

        private Location relativeLocation;

        private GateDirection direction;

        public Gate(Location relativeLocation, GateDirection direction) {
            this.relativeLocation = relativeLocation;
            this.direction = direction;
        }

        private GateDirection getInverted(GateDirection direction) {
            switch (direction) {
                case NORTH:
                    return GateDirection.SOUTH;
                case SOUTH:
                    return GateDirection.NORTH;
                case EAST:
                    return GateDirection.WEST;
                case WEST:
                    return GateDirection.EAST;
                default:
                    return GateDirection.NONE;
            }
        }


        public void instantiateNewModule(DungeonModule module) {
            Location newLocation = calculateNewLocation(module, relativeLocation);

            if (newLocation.getBlock().getType() != Material.AIR) {
                return;
            }

            DungeonModule rightModule = searchForRightModule(module.getConnectors(), getInverted(direction));

            if (rightModule == null) {
                System.out.println("Couldn't find a module with the right direction.");
                return;
            }

            DungeonModule spawned = DungeonManager.instantiate(rightModule, newLocation);

            spawned.setup(module.getConnectors());
        }

        private DungeonModule searchForRightModule(List<DungeonModule> modules, GateDirection requestedDirection) {
            List<DungeonModule> possibleModules = new ArrayList();
            // scan through list of modules and check their gates direction
            // Loop through the given modules
            for (DungeonModule module : modules) {
                // Check if the module contains a gate with the requested direction and then add it to the list of possible modules
                if (checkGates(module.getGates3(), requestedDirection)) possibleModules.add(module);
            }

            if (possibleModules.isEmpty()) {
                System.out.println("Didn't find any possible module to place here.");
                return null;
            }

            return possibleModules.get((new Random()).nextInt(possibleModules.size()));
        }

        private boolean checkGates(List<Gate> gates, GateDirection requestedDirection) {
            if (gates == null) {
                return false;
            }

            // Loop through the gates and once it found a gate with the correct direction it returns true
            for (Gate gate : gates) {

                if (gate.getDirection() == requestedDirection) {
                    return true;
                }
            }

            return false;
        }


        private Location calculateNewLocation(DungeonModule oldModule, Location gateLocation) {
            // Returns a location based on the relative xyz coordinates of the gates
            return new Location(oldModule.getSpawnPoint().getWorld()
                    , oldModule.getSpawnPoint().getX() + (2 * gateLocation.getX())
                    , oldModule.getSpawnPoint().getY() + (2 * gateLocation.getY())
                    , oldModule.getSpawnPoint().getZ() + (2 * gateLocation.getZ())); // todo (probably) instead * 2 for the xyz, use the getxyz of the gate and add that orso
        }



        public Location getRelativeLocation() {
            return relativeLocation;
        }

        public void setRelativeLocation(Location relativeLocation) {
            this.relativeLocation = relativeLocation;
        }

        public GateDirection getDirection() {
            return direction;
        }

        public void setDirection(GateDirection direction) {
            this.direction = direction;
        }
    }
    Instantiate code:
    Code (Java):
    public static DungeonModule instantiate(DungeonModule module, Location loc) {
            module.setSpawnPoint(loc);

            loc.getBlock().setType(Material.DIAMOND_BLOCK);

            index++;

            main.getServer().getScheduler().scheduleSyncDelayedTask(main, new RunnableSpawnModule(main, module, loc),  (index * 2) * 20);

            return module;
        }
    Runnable which is fired:
    Code (Java):
    public class RunnableSpawnModule implements Runnable {

        private Location loc;
        private DungeonModule module;
        private Main main;

        public RunnableSpawnModule(Main main, DungeonModule module, Location loc) {
            this.module = module;
            this.main = main;
            this.loc = loc;
        }

        @Override
        public void run() {
            File file = new File(main.getDataFolder() + "/schematics/" + module.getSchematicPath());

            ClipboardFormat format = ClipboardFormats.findByFile(file);
            try (ClipboardReader reader = format.getReader(new FileInputStream(file))) {
                Clipboard clipboard = reader.read();
                try (EditSession editSession = WorldEdit.getInstance().getEditSessionFactory().getEditSession(new BukkitWorld(loc.getWorld()), -1)) {
                    Operation operation = new ClipboardHolder(clipboard)
                            .createPaste(editSession)
                            .to(BlockVector3.at(loc.getX(), loc.getY(), loc.getZ()))
                            .ignoreAirBlocks(true)
                            .build();
                    Operations.complete(operation);
                }

            } catch (IOException | WorldEditException e) {
                e.printStackTrace();
            }
        }
    }

    Currently the dungeon consists of only a spawnroom and a list of connectors. Planning on expanding on that.

    To get a better picture of what is happening see the following images:
    What I want to happen: Imgur
    What is happening: Imgur
    (both images are generated dungeons by the code)

    Anyone who can help me out figure out this issue I'm having with the open doors to the outside?

    Much appreciated!

    Kind regards,
    JoshC

    Edit v1:
    - Updated code with current version

    Edit v2:
    - Added DungeonManager Instantiate method
    - Added the runnable class

    Edit v3:
    - By adding an identification number to each module to keep track how many gates of the available gates are checked by the code I found out that not every single gate is checked out of all the gates which it should check.
     
    #1 JoshC, Mar 4, 2020
    Last edited: Mar 6, 2020
  2. Some things I found out recently are:
    I created a list to keep track of the spawned modules. And looped through them whenever it's done generating to check if there are open spots. If so fill them. But that doesn't work sadly. I think it has something to do with concurrent modification. Which means that some things are done on a different thread and anothe resource waits on that thread and if the usage is too much it's going to skip it.
     
  3. Does that empty spot only happen in one direction? If the little rooms on the images (below the generated dungeon) are anything to go by, you have 3 rooms which are "ends", but the forth one seems different, maybe because it's meant to be the spawn room? If that's the case, then you don't add it to the list of possible options and all the other possible ends don't fit so it just gives up. Is that maybe the case?
     
  4. Thanks for your reply. But that is sadly not the case. In the first testing phase I thought the same. But I think the current issue is that due to resource starvation that the loop gets interrupted and the big O of the recursive function becomes too big. I came to this conclusion by adding a delay in spawning the modules and when there is a bigger delay the generated dungeon is way smaller with way more openings.

    So another way to solve it I thought, lets add the generate function in each gate class and instantiate a new module when the gate isn't null for instance. And it seems like when there are too much worldedit spawning is happening at the same time that it stops. So I think there is something going on there. I'm not totally sure.
     
  5. Also updated the code to the current status, which is a bit more optimized.
     
  6. The new status is as following:

    I'm instantiating via a delayed task and generate the dungeon with only diamond blocks as middle points for each module (to visualize, in general it is first generated in code). Then every 2 seconds a new module is instantiated on the location of those diamond blocks (these modules are pre given and gates are known) . This seemed to work fine and ruduces a lot of stress on the server. But sadly the result is still the same. Somehow it skips some gates of a module and the other time it doesn't skip the gates.
     
  7. Can't see your DungeonManager class.
     
  8. Ah yeh my fault. Let me update the post. Check back in a minute. Basically the only thing the dungeon manager does is instantiate the module in the world.
     
  9. Can you give the whole class? Because I see there's some type of storage.
     
  10. You mean the function "DungeonManager.getAllModules()"? If so, this just returns a list of all the modules known. And each module contains a list of gates. If you think there is a problem with the amount of gates passing, I assure you that the amount of gates being passed is the right amount. I tested every single module in the list individually and next to that I spawn them in while messaging the amount of gates of each module.

    But never the less here is the part which gets the dungeon module from file:
    Code (Java):
    public static List<DungeonModule> getAllModules() {
            List<DungeonModule> dungeonModules = new ArrayList<>();

            for (String name : fileDungeonModuleList.getYAMLfile().getStringList("module-names")) {
                dungeonModules.add(getModuleByName(name));

            }

            return dungeonModules;
        }



        public static DungeonModule getModuleByName(String name) {
            if (fileDungeonModuleList == null) return null;

            List<String> dungeonNames = fileDungeonModuleList.getYAMLfile().getStringList("module-names");

            if (!dungeonNames.contains(name)) return null;

            File file = new File(main.getDataFolder() + "/module_data/" + name + ".yml");

            if (!file.exists()) return null;

            YamlConfiguration yamlFile = YamlConfiguration.loadConfiguration(file);

            DungeonModule module = new DungeonModule();

            module.setName(yamlFile.getString("name"));
            module.setSchematicPath(yamlFile.getString("schematic"));
            module.setModuleType(getTypeByString(yamlFile.getString("type")));

            module.setSpawnPoint(new Location(null, yamlFile.getInt("spawnpoint.x"), yamlFile.getInt("spawnpoint.y"), yamlFile.getInt("spawnpoint.z")));

            module.setGates3(getGates(yamlFile, "gates.3"));
            module.setGates5(getGates(yamlFile, "gates.5"));
            module.setGates7(getGates(yamlFile, "gates.7"));
            module.setGates9(getGates(yamlFile, "gates.9"));
            module.setGates11(getGates(yamlFile, "gates.11"));

            return module;
        }

        private static ModuleType getTypeByString(String s) {
            switch (s) {
                case "SPAWN_ROOM":
                    return ModuleType.SPAWN_ROOM;
                case "TREASURE_ROOM":
                    return ModuleType.TREASURE_ROOM;
                case "CONNECTOR":
                    return ModuleType.CONNECTOR;
                case "SEMI_BOSS_ROOM":
                    return ModuleType.SEMI_BOSS_ROOM;
                case "BOSS_ROOM":
                    return ModuleType.BOSS_ROOM;
                default:
                    return ModuleType.CONNECTOR;
            }
        }

        private static List<Gate> getGates(YamlConfiguration yamlFile, String gatePath) {
            List<Gate> gates = new ArrayList<>();

            if (!yamlFile.contains(gatePath)) {
                return null;
            }

            for (String key : yamlFile.getConfigurationSection(gatePath).getKeys(false)) {
                Gate gate = new Gate(new Location(null, yamlFile.getInt(gatePath + "." + key + ".x"),
                        yamlFile.getInt(gatePath + "." + key + ".y"),
                        yamlFile.getInt(gatePath + "." + key + ".z")),
                        GateDirection.stringToDirection(yamlFile.getString(gatePath + "." + key + ".direction")));
                gates.add(gate);
            }

            return gates;
        }
     
  11. Great news, I've kinda solved the issue. How I did it was by just deleting all the code I had to generate the dungeon and started over. This time I first generated in objects without relying on spawning objects. This way the dungeon is pregenerated in the code and then put in a list of all the elements which are needed. When that is done I just simply looped through that list and pasted it in the world.

    For people who are interrested for the logics:
    Code (Java):
    public class Dungeon {

        private Main main;

        private int index;

        private List<DungeonModule> connectors;

        public Dungeon(Main main) {
            this.main = main;
        }

        private List<DungeonPosition> dungeonPositions;

        public void generate(Location startingLoc) {
            // Devide modules up
            DungeonModule spawnRoom = null;

            index = 0;

            connectors = new ArrayList<>();
            dungeonPositions = new ArrayList<>();

            // Loop through all modules and sort them by type
            for (DungeonModule listedModule : DungeonManager.getAllModules()) {
                if (listedModule.getModuleType() == ModuleType.SPAWN_ROOM) spawnRoom = listedModule;
                if (listedModule.getModuleType() == ModuleType.CONNECTOR) connectors.add(listedModule);
            }

            // checks if spawnroom is null
            if (spawnRoom == null) return;

            dungeonPositions.add(new DungeonPosition(new Location(startingLoc.getWorld(), 0, 0, 0), spawnRoom, startingLoc));

            System.out.println("Generating a relative dungeon.");
            generateRelativeDungeon();
            System.out.println("Done generating a relative dungeon. Now we have to generate each module via worldedit in the world");
            generateCompleteDungeon();
        }

        private void generateCompleteDungeon() {
            for (DungeonPosition dungeonPosition : dungeonPositions) {
                index++;
                main.getServer().getScheduler().scheduleSyncDelayedTask(main, new RunnableSpawnModule(main, dungeonPosition.getCorrespondingModule(), dungeonPosition.getWorldLocation()),  index * 20);
            }
        }

        private void generateRelativeDungeon() {
            List<DungeonPosition> newPositions = new ArrayList<>();

            // now check for every module the "gates"
            for (DungeonPosition dungeonPosition : dungeonPositions) {
                for (Gate gate : dungeonPosition.getCorrespondingModule().getGates3()) {
                    // Calculate new relative location
                    Location newRelativeLocation = calculateNewRelativeLocation(dungeonPosition.getRelativeLocation(), gate.getDirection());

                    // Check if there is already a module on this direction
                    if (!hasModuleOnLocation(newRelativeLocation, dungeonPositions)) {
                        if (!hasModuleOnLocation(newRelativeLocation, newPositions)) {
                            // retrieve the gate location and use it to get the inverted direction
                            GateDirection invertedDirection = GateDirection.getInverted(gate.getDirection());

                            // Loop through each connector to see if there is a fitting module to be placed and return a random module
                            List<DungeonModule> possibleModules = new ArrayList<>();

                            // Loop through each connector in the list of connectors
                            for (DungeonModule connector : connectors) {
                                // Check if the list of gates isn't null
                                if (connector.getGates3() != null) {
                                    // Loop through each gate
                                    for (Gate connectorGate : connector.getGates3()) {
                                        // Check whether the gate direction of the current connector module has the same direction of the inverted direction of the original module
                                        if (connectorGate.getDirection() == invertedDirection) {
                                            // adds the connector to the possible modules list
                                            possibleModules.add(connector);
                                        }
                                    }
                                }
                            }

                            // Check if it has found a possible module
                            if (possibleModules.size() > 0) {
                                // Retrieve a random module
                                DungeonModule randomModule = possibleModules.get((new Random()).nextInt(possibleModules.size()));

                                // calculate new world position
                                Location newWorldLocation = calculateNewWorldLocation(dungeonPosition.getWorldLocation(), gate.getRelativeLocation());

                                newPositions.add(new DungeonPosition(newRelativeLocation, randomModule, newWorldLocation));
                            } else {
                                System.out.println("Didn't find any possible module. This should not happen.");
                            }
                        }
                    }
                }
            }

            // check if the list has increased. If
            if (newPositions.size() > 0) {
                dungeonPositions.addAll(newPositions);

                generateRelativeDungeon();
            }
        }

        private Location calculateNewWorldLocation(Location worldLocation, Location relativeGate) {
            // Returns a location based on the relative xyz coordinates of the gates
            return new Location(worldLocation.getWorld()
                    , worldLocation.getX() + (2 * relativeGate.getX())
                    , worldLocation.getY() + (2 * relativeGate.getY())
                    , worldLocation.getZ() + (2 * relativeGate.getZ()));
        }


        private Location calculateNewRelativeLocation(Location relativeModuleLocation, GateDirection direction) {
            int x = (int) relativeModuleLocation.getX();
            int y = (int) relativeModuleLocation.getY();
            int z = (int) relativeModuleLocation.getZ();

            switch (direction) {
                case NORTH:
                    z -= 1;
                    break;
                case SOUTH:
                    z += 1;
                    break;
                case EAST:
                    x += 1;
                    break;
                case WEST:
                    x -= 1;
                    break;
                case NONE:
                    break;
            }

            return new Location(relativeModuleLocation.getWorld(), x, y, z);
        }


        private boolean hasModuleOnLocation(Location relativeDungeonLocation, List<DungeonPosition> positions) {

            // Check the list if it contains any form of xyz location of the relativeDungeonLocation
            for (DungeonPosition dungeonPosition : positions) {
                if (dungeonPosition.getRelativeLocation().getX() == relativeDungeonLocation.getX()) {
                    if (dungeonPosition.getRelativeLocation().getY() == relativeDungeonLocation.getY()){
                        if (dungeonPosition.getRelativeLocation().getZ() == relativeDungeonLocation.getZ()) {
                            System.out.println("There is already a relative position here.");
                            return true;
                        }
                    }
                }
            }

            System.out.println("No relative position found.");
            return false;
        }
     
    • Winner Winner x 1