Generazione labirinti

[Giacomo Furlan]

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

 

[BAT]

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 Dijkstra è "sempice da calcolare" a mano, un po' meno da scrivere)

 

[Andretti60]

La generazione di labirinti ha generato molti algoritmi partendo dalla teoria dei grafi. Su wiki c’è una bella pagina introduttiva
https://en.m.wikipedia.org/wiki/Maze_generation_algorithm

 

[Giacomo Furlan]

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.
--- i due messaggi sono stati uniti ---
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

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

package name.giacomofurlan.maze;

public enum MazeBlockType {
    WALL,
    CORRIDOR;

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

    public boolean isCorridor() {
        return this == CORRIDOR;
    }
}

RandomizedPrim.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;
    }
}