Generación de laberintos I. Algoritmo de Prim's 1.

Autor algoritmo: J. Zong en "Maze Generation with Prim's Algorithm"

 

Código (Prim.java):

package prim;

import java.util.ArrayList;

public class Prim {

    public static void main(String[] args) {  // dimensions of generated maze
        int r = 13, c = 31;

        // build maze and initialize with only walls
        StringBuilder s = new StringBuilder(c);
        for (int x = 0; x < c; x++) {
            s.append('█');
        }
        char[][] maz = new char[r][c];
        for (int x = 0; x < r; x++) {
            maz[x] = s.toString().toCharArray();
        }

        // select random point and open as start node
        Point st = new Point((int) (Math.random() * r), (int) (Math.random() * c), null);
        maz[st.r][st.c] = 'S';

        // iterate through direct neighbors of node
        ArrayList< Point> frontier = new ArrayList< Point>();
        for (int x = -1; x <= 1; x++) {
            for (int y = -1; y <= 1; y++) {
                if (x == 0 && y == 0 || x != 0 && y != 0) {
                    continue;
                }
                try {
                    if (maz[st.r + x][st.c + y] == ' ') {
                        continue;
                    }
                } catch (Exception e) { // ignore ArrayIndexOutOfBounds
                    continue;
                }
                // add eligible points to frontier
                frontier.add(new Point(st.r + x, st.c + y, st));
            }
        }

        Point last = null;
        while (!frontier.isEmpty()) {

            // pick current node at random
            Point cu = frontier.remove((int) (Math.random() * frontier.size()));
            Point op = cu.opposite();
            try {
                // if both node and its opposite are walls
                if (maz[cu.r][cu.c] == '█' && maz[op.r][op.c] == '█') {

                    // open path between the nodes
                    maz[cu.r][cu.c] = ' ';
                    maz[op.r][op.c] = ' ';

                    // store last node in order to mark it later
                    last = op;

                    // iterate through direct neighbors of node, same as earlier
                    for (int x = -1; x <= 1; x++) {
                        for (int y = -1; y <= 1; y++) {
                            if (x == 0 && y == 0 || x != 0 && y != 0) {
                                continue;
                            }
                            try {
                                if (maz[op.r + x][op.c + y] == ' ') {
                                    continue;
                                }
                            } catch (Exception e) {
                                continue;
                            }
                            frontier.add(new Point(op.r + x, op.c + y, op));
                        }
                    }
                }
            } catch (Exception e) { // ignore NullPointer and ArrayIndexOutOfBounds
            }

            // if algorithm has resolved, mark end node
            if (frontier.isEmpty()) {
                maz[last.r][last.c] = 'E';
            }
        }

        // print final maze
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print(maz[i][j]);
            }
            System.out.println();
        }
    }

    static class Point {

        Integer r;
        Integer c;
        Point parent;

        public Point(int x, int y, Point p) {
            r = x;
            c = y;
            parent = p;
        }

        // compute opposite node given that it is in the other direction from the parent
        public Point opposite() {
            if (this.r.compareTo(parent.r) != 0) {
                return new Point(this.r + this.r.compareTo(parent.r), this.c, this);
            }
            if (this.c.compareTo(parent.c) != 0) {
                return new Point(this.r, this.c + this.c.compareTo(parent.c), this);
            }
            return null;
        }
    }
}



Resultado: