DOMANDA Generazione labirinti

Giacomo Furlan

Utente Attivo
328
84
CPU
AMD Ryzen 2700x @ 4.1 Ghz
Dissipatore
BeQuiet! SilentLoop 360mm
Scheda Madre
Gigabyte X470 AORUS Gaming 7 WIFI AMD X470
Hard Disk
Corsair MP500 480GB
RAM
G.Skill Trident F4-3600C16D-16GTZ 16GB DDR 4 @ 3466 Mhz (1.42V 14-15-15-15-36)
Scheda Video
MSI GeForce RTX 2080 Gaming X Trio
Scheda Audio
Focusrite Saffrire 6 USB
Monitor
AOC Professional U3477PQU 34" 21:9
Alimentatore
EVGA SuperNOVA 650 G3, 80 Plus GOLD 650W
Case
Sharkoon TG5
Sistema Operativo
Windows 10, Fedora 31
Ciao a tutti!

Stavo pensando ad un progetto che, data una matrice di dimensioni N, M, ed uno o più punti P (partenza), riesca a generare le seguenti informazioni:

  1. un punto di arrivo A, il più distante tra i punti P (calcolo distanza blocco per blocco in brute force per determinare la distanza massima? Altri algoritmi più intelligenti?)
  2. una strada che congiunga i punti P al punto A (immagino si possano sfruttare i glifi, ma non ho mai sviluppato in tal proposito)
  3. una serie di vicoli ciechi (altrimenti che labirinto sarebbe? :D) (no idea)

Alcuni vincoli:
  1. il percorso deve essere percorribile in verticale o orizzontale, non obliquo (es. path 1,1 -> 2,2 deve passare necessariamente da 1,2 o 2,1), forse ignorabile per punto (2) (vedi sotto)
  2. il percorso deve essere sempre largo 2 punti (minimo 2x2), anche se questo immagino sia semplice da aggirare: raddoppiando la superficie di gioco.
  3. i percorsi generati da P ad A non possono contorcersi "troppo" (nel senso che non possono girare su sé stessi), potrebbe venire incontro il vincolo (4)
  4. ci dev'essere un rapporto tra blocchi "chiusi" e blocchi "aperti", in modo da evitare un labirinto troppo facile (vedi la meta da distante), oppure troppo corto (poche diramazioni perché tutto "chiuso")

Idea pratica: uno o più giocatori si ritrovano all'interno di questa struttura; al comando d'inizio il percorso viene generato e si alzano i muri attorno ai giocatori, i quali devono trovare la via d'uscita. L'algoritmo del labirinto genera i percorsi, mentre il server crea i muri. Successivamente sui muri (o in terra) possono essere applicate delle trappole.

Avete voglia di darmi una mano? :D
 
  • Mi piace
Reactions: Mursey

BAT00cent

Moderatore Incredibilmente Cattivo
Staff Forum
Utente Èlite
2,586
1,280
CPU
Neurone solitario
Dissipatore
Ventaglio azionato a mano
Scheda Madre
Casalinga
RAM
Molto molto volatile
Scheda Video
Binoculare integrata nel cranio
Alimentatore
Pastascituta, pollo e patatine al forno
Internet
Segnali di fumo e/o tamburi
Sistema Operativo
Windows 10000 BUG
Forza bruta no, a occhio e croce ti serve conoscere un po' di teoria dei grafi, avere una matrice rappresentativa di un grafo aciclico e, per il problema della distanza minima, applicare l'algoritmo di Dijkstra.
Nulla di eccessivamente complicato, tuttavia devi prima fare un po' di teoria, non è un argomento dove ti siedi e scrivi direttamente il codice (per. es. l'alg di fijkstra è "sempice da calcolare" a mano, un po' meno da scrivere)
 
Ultima modifica:
  • Mi piace
Reactions: Giacomo Furlan

Giacomo Furlan

Utente Attivo
328
84
CPU
AMD Ryzen 2700x @ 4.1 Ghz
Dissipatore
BeQuiet! SilentLoop 360mm
Scheda Madre
Gigabyte X470 AORUS Gaming 7 WIFI AMD X470
Hard Disk
Corsair MP500 480GB
RAM
G.Skill Trident F4-3600C16D-16GTZ 16GB DDR 4 @ 3466 Mhz (1.42V 14-15-15-15-36)
Scheda Video
MSI GeForce RTX 2080 Gaming X Trio
Scheda Audio
Focusrite Saffrire 6 USB
Monitor
AOC Professional U3477PQU 34" 21:9
Alimentatore
EVGA SuperNOVA 650 G3, 80 Plus GOLD 650W
Case
Sharkoon TG5
Sistema Operativo
Windows 10, Fedora 31
Grazie Andretti60, in effetti sono andato a vedere proprio lì se c'era qualcosa di già "masticato" :D

Conosco l'algoritmo di Dijkstra, studiato eoni fa all'università :D buona idea.

Su internet ho trovato vari algoritmi per generare labirinti, uno dei quali mi sembra relativamente semplice da implementare: l'algoritmo di Prim randomizzato (modificato).

L'algoritmo si basa su questo principio (da quanto ho capito):
  1. Riempi tutto l'ambiente di muri (a meno del punto d'ingresso)
  2. Prendi una parete qualsiasi del labirinto (all'inizio ce ne saranno fino a 3) e vedi se dall'altra parte c'è un muro oppure un'altra parte del labirinto: se c'è muro, segna la parte adiacente come parte del labirinto e crea il passaggio
  3. Ripeti fino ad arrivare all'uscita, oppure se non ci sono più mosse disponibili
Ora, in un mondo dove i blocchi possono essere o muro o labirinto e non esistono pareti fra di loro, bisogna modificare l'algoritmo tenendo in considerazione che il candidato blocco è eleggibile se e solo se ci sono almeno due blocchi "muro" attorno a sé adiacenti (es. dx/sx o sopra/sotto), e che non sia a ridosso del labirinto (si "aprirebbe" il labirinto all'esterno) -> vedi allegato.
Post automaticamente unito:

Ecco un primo assaggio della classe che sto sviluppando. In linea di massima dovrebbe funzionare, ma sono veramente poco esperto in Java e devo ancora configurare l'ambiente di test. Potreste darci uno sguardo? :D

Questa prima versione genera un labirinto utilizzando l'algoritmo sopra descritto. Ancora non prende in considerazione la coordinata d'uscita, ma per adesso poco conta (l'idea di base è di fare un retry limitato e riprovare a rigenerare il labirinto).

Sempre in teoria l'algoritmo dovrebbe generare un labirinto che occupa in blocchi-corridoio una percentuale massima come esposto nella firma della funzione.

Coordinate.java
Java:
package name.giacomofurlan.maze;

public class Coordinate
{
    private int x;
    private int y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Coordinate)) {
            return false;
        }

        Coordinate coord = (Coordinate) obj;

        return coord.getX() == this.getX()
            && coord.getY() == this.getY();
    }

    @Override
    public int hashCode() {
        return String.format("%d,%d", this.getX(), this.getY()).hashCode();
    }
}
MazeBlockType.java
Java:
package name.giacomofurlan.maze;

public enum MazeBlockType {
    WALL,
    CORRIDOR;

    public boolean isWall() {
        return this == WALL;
    }

    public boolean isCorridor() {
        return this == CORRIDOR;
    }
}
RandomizedPrim.java
Java:
package name.giacomofurlan.maze;

import java.util.*;

public class RandomizedPrim {
    public static Map<Coordinate, MazeBlockType> generateMaze(int width, int height) {
        Coordinate start = new Coordinate(0, 0);
        Coordinate end = new Coordinate(width - 1, height - 1);

        return generateMaze(width, height, start, end);
    }

    public static Map<Coordinate, MazeBlockType> generateMaze(int width, int height, Coordinate start, Coordinate end) {
        return generateMaze(width, height, start, end, 70);
    }

    public static Map<Coordinate, MazeBlockType> generateMaze(int width, int height, Coordinate start, Coordinate end, int fillPercentage)
    {
        HashMap<Coordinate, MazeBlockType> maze = new HashMap<>();

        // First of all fillCorridor the maze with walls
        // Create two more rows and two more columns
        // The starting point will be within the so created "frame"
        for (int x = 0; x < width+2; x++) {
            for (int y = 0; y < height+2; y++) {
                maze.put(new Coordinate(x, y), MazeBlockType.WALL);
            }
        }

        // Adapt to maze's resize
        start.setX(start.getX()+1);
        start.setY(start.getY()+1);
        end.setX(end.getX()+1);
        end.setY(end.getY()+1);

        int blocksToTransform = width * height * fillPercentage / 100;
        ArrayList<Coordinate> eligibleCorridorBlocks = new ArrayList<>();

        // Set the starting block as corridor
        fillCorridor(start, eligibleCorridorBlocks, maze);

        Random rand = new Random();
        for (int i = 1; i < blocksToTransform; i++) {
            Coordinate startingPoint = eligibleCorridorBlocks.get(rand.nextInt(eligibleCorridorBlocks.size()));

            ArrayList<Integer> attemptedDirections = new ArrayList<>(); // 0 top, 1 bottom, 2 right, 3 left
            do {
                Integer direction;
                do {
                    direction = rand.nextInt(4);
                } while (attemptedDirections.contains(direction));

                Coordinate candidateCoord;
                switch (direction) {
                    case 0: // Top
                        candidateCoord = new Coordinate(startingPoint.getX(), startingPoint.getY() + 1);
                        break;
                    case 1: // Bottom
                        candidateCoord = new Coordinate(startingPoint.getX(), startingPoint.getY() - 1);
                        break;
                    case 2: // Right
                        candidateCoord = new Coordinate(startingPoint.getX() + 1, startingPoint.getY());
                        break;
                    case 3: // Left
                        candidateCoord = new Coordinate(startingPoint.getX() - 1, startingPoint.getY());
                        break;
                    default:
                        throw new RuntimeException(String.format("Unhandled direction %d", direction));
                }

                if (canBeCorridor(candidateCoord, maze)) {
                    fillCorridor(candidateCoord, eligibleCorridorBlocks, maze);
                    break;
                }

                attemptedDirections.add(direction);
            } while (attemptedDirections.size() < 4);
        }

        return maze;
    }

    private static void fillCorridor(
            Coordinate coordinate,
            List<Coordinate> eligibleCorridorBlocks,
            Map<Coordinate, MazeBlockType> maze
    ) {
        if (!maze.containsKey(coordinate)) {
            throw new RuntimeException("Trying to fillCorridor an out-of-bound block!");
        }
        maze.put(coordinate, MazeBlockType.CORRIDOR);

        // Avoid inserting into the transformed blocks a useless candidate
        if (canBeStartingPoint(coordinate, maze)) {
            eligibleCorridorBlocks.add(coordinate);
        }
    }

    private static boolean canBeCorridor(Coordinate coordinate, Map<Coordinate, MazeBlockType> maze) {
        int originalX = coordinate.getX();
        int originalY = coordinate.getY();

        List<MazeBlockType> neighbours = new ArrayList<>();
        neighbours.add(maze.get(new Coordinate(originalX, originalY + 1))); // top
        neighbours.add(maze.get(new Coordinate(originalX, originalY - 1))); // bottom
        neighbours.add(maze.get(new Coordinate(originalX + 1, originalY))); // right
        neighbours.add(maze.get(new Coordinate(originalX - 1, originalY))); // left

        for (MazeBlockType type : neighbours) {
            // An edge block can't be a corridor
            if (type == null) {
                return false;
            }
        }

        /*
        * | |L|L| |
        * | |L|?| | <== no, no 2 adjacent "wall" blocks
        * | |X|?| | <== yes, top/bottom "wall" blocks detected
        * | |L| | |
        * | |?| | | <== yes, right/left "wall" blocks detected
        * | | | | |
        *
        * */

        return (neighbours.get(0).isWall() && neighbours.get(1).isWall())
                || (neighbours.get(2).isWall() && neighbours.get(3).isWall());
    }

    private static boolean canBeStartingPoint(Coordinate coordinate, Map<Coordinate, MazeBlockType> maze) {
        int originalX = coordinate.getX();
        int originalY = coordinate.getY();

        List<Coordinate> neighbours = new ArrayList<>();
        neighbours.add(new Coordinate(originalX, originalY + 1)); // top
        neighbours.add(new Coordinate(originalX, originalY - 1)); // bottom
        neighbours.add(new Coordinate(originalX + 1, originalY)); // right
        neighbours.add(new Coordinate(originalX - 1, originalY)); // left

        for (Coordinate candidate : neighbours) {
            if (maze.get(candidate) == null) {
                continue;
            }

            if (canBeCorridor(candidate, maze)) {
                return true;
            }
        }

        return false;
    }
}
 

Allegati

Ultima modifica:

Entra

oppure Accedi utilizzando

Hot del momento