источник:
В прошлом году (первый семестр средней школы) я любил писать небольшие игры, поэтому я хотел попробовать написать лабиринт.
Эффекты программы:
Нажмите пространство, чтобы отобразить путь:
Процесс мышления:
Лабиринт состоит из сетей, требующих только одного пути от входа к выходу.
Подумав о различных структурах данных, кажется, что деревья являются более подходящими, только с одним путем от корневого узла до каждого дочернего узла. Предполагая, что вход является корневым узелом, а выход - это узел дочернего узела на дереве, тогда путь от корневого узла к детскому узлу определенно уникален.
Поэтому, если дерево может быть построено, чтобы покрыть все сетки, может быть создан лабиринт.
Кроме того, требуется, чтобы родительские и дочерние узлы дерева должны были быть смежными сетками на границе раздела.
При отображении интерфейса, если края, разделяемые между родительским узлом и узлом дочерних, не нарисованы, а другие края нарисованы, можно нарисовать лабиринт.
Тогда я подумал о том, как реализовать такое дерево.
Первые два вопроса:
1. Как представляются деревья?
2. Как построить это дерево?
1. Как представляются деревья?
Предполагая, что это дерево реализовано как написание бинарного дерева, каждый узел дерева должен хранить координату (x, y) для представления сетки, а четыре указателя должны храниться. Некоторые указатели пусты, некоторые не пустые, а указатели, которые не являются пустыми точками на дочерние узлы, а дочерние узлы сохраняют координаты соседней сетки. Самая большая проблема с этим заключается в том, что невозможно определить, находятся ли все сетки на дереве. Возможно, двумерный массив также используется в качестве массива флагов.
Предположим, вы используете двухмерный массив для представления сетки лабиринта. Каждый элемент массива хранит ссылку на родительский узел, который также может сформировать виртуальное дерево. Таким образом, двумерный массив N*N представляет n*n сетки, и каждый элемент массива (решетчатая) имеет ссылку на родительский узел. Кроме того, чтобы легко получить координаты сетки, также должна быть сохранена координатная информация.
2. Как построить это дерево?
Сначала выберите сетку в качестве корневого узла. Чтобы сделать форму лабиринта достаточно случайной, я решил случайным образом генерировать координату в качестве корневого узла. На самом деле, также можно выбрать определенный координат.
Тогда как добавить узлы в это дерево?
Я взял здесь много обхода. Сначала я подумал об алгоритме, который сейчас похож на возврат (я не знал алгоритма отступления в то время ...), но сложность времени очень высока. Возможно, когда лабиринт составляет 64*64, алгоритм не даст никаких результатов.
Затем метод поиска глубины сканирования также возвращается. Каждый раз, когда я сканирую, я нахожу узел в нынешнем дереве, чтобы увидеть, находится ли его соседняя сетка в дереве. Если это не в дереве, добавьте соседнюю сетку в дерево. Если это уже на дереве, посмотрите на следующую соседнюю сетку. Если все соседние сетки узла находятся в дереве, найдите следующий узел и продолжайте одну и ту же операцию. Кроме того, чтобы сделать лабиринт случайным образом сгенерированным, начальная позиция сканирования просто случайна. Тем не менее, пути в лабиринте, генерируемых этим методом, всегда недостаточно глубоки, чтобы иметь извилистый и глубокий эффект, который я хочу. В конце концов, это аналогичный метод поиска в ширину. Более того, это всегда полагается на грубую силу, а алгоритм не достаточно умный и краткий.
Наконец, я наконец подумал об использовании углубленного поиска. Полем Вероятно, потому что я изучал структуру данных в течение года и не практиковал ее слишком много, я никогда не думал об этом первом методе, о котором я должен думать. Полем
Случайно выберите сетку в качестве корневого узла, начните с нее и поиск в глубине и откройте путь, пока не будет никакого способа пойти, отступить один шаг, изменить другой путь, а затем идите, чтобы пойти, сделайте один шаг назад, измените другой ... Этот цикл продолжается, пока не будет никакого пути. Полем Полем На самом деле, это все еще возвращается.
В программе следующим процессом является (см. Функцию CreateMaze () в коде для деталей):
Случайно выберите сетку в качестве корневого узла и вставьте ее в стек.
Затем выполните следующий цикл, когда стек не пуст:
Уберите сетку, установите свой флаг INTREE на 1, затем подтолкните все его соседние сетки, которые не находятся в дереве в стек (рассказы случайным образом), и пусть отец этих соседних сетей указывается на сетку.
После решения этих двух задач остальная часть рисунка лабиринтов, отображения путей и движущихся шариков относительно просты.
Код
Упаковка; импорт java.awt.color; import java.awt.graphics; import java.awt.event.keyadapter; import java.awt.event.keyevent; import java.util.random; import java.util.stack; импорт javax.wing.jframe javax.swing.jpanel; классная решетка {статическая конечная int intree = 1; статический конечный int notintree = 0; частный int x = -1; private int y = -1; private int flag = notintree; частная решетчатая отец = null; публичная решетка (int xx, int yy) {x = xx; y = yy; } public int getx () {return x; } public int gety () {return y; } public int getflag () {return flag; } public Stictice getFather () {return отца; } public void setfather (решетка f) {отец = f; } public void setFlag (int f) {flag = f; } public String toString () {return new String ("(" + x + "," + y + ")/n"); }} public Class Maze расширяет JPanel {Private Static Final Long Long SerialVersionUID = -8300339045454852626L; Частный int num, ширина, заполнение; // ширина ширина и высота каждой сетки частной решетки [] [] лабиринт; Private Int Ballx, Bally; Частный логический ролик = false; Лабиринт (int m, int wi, int p) {num = m; ширина = wi; Padding = P; Maze = новая решетка [num] [num]; for (int i = 0; i <= num- 1; i ++) для (int j = 0; j <= num- 1; j ++) maze [i] [j] = новая решетка (i, j); createMaze (); SetKeyListener (); this.setFocusable (true); } private void init () {for (int i = 0; i <= num- 1; i ++) для (int j = 0; j <= num- 1; j ++) {maze [i] [j] .setfather (null); Maze [i] [j] .setflag (lattice.notintree); } ballx = 0; bally = 0; DrawPath = false; createMaze (); // setKeyListener (); this.setFocusable (true); Repaint (); } public int getCenterx (int x) {return Padding + x * width + width / 2; } public int getCentery (int y) {return padding + y * width + width / 2; } public int getCenterx (решетчатая p) {return padding + p.gety () * width + width / 2; } public int getCentery (решетка p) {return padding + p.getx () * width + width / 2; } private void checkiswin () {if (ballx == num- 1 && bally == num- 1) {joptionpane.showmessageDialog (null, «Вы выигрываете!», «Вы вышли из лабиринта»., joptionpane.plain_message); init (); }} синхронизированный private void move (int c) {int tx = ballx, ty = bally; // System.out.println (c); Switch (c) {case keyEvent.vk_left: ty--; перерыв; case keyevent.vk_right: ty ++; перерыв; case keyevent.vk_up: tx--; перерыв; case keyevent.vk_down: tx ++; перерыв; case keyevent.vk_space: if (drawpath == true) {darlpath = false; } else {trankpath = true; } перерыв; по умолчанию:} if (! isoutofborder (tx, ty) && (maze [tx] [ty] .getfather () == maze [ballx] [bally] || maze [ballx] [bally] .getfather () == mate [tx] [ty])) {ballx = tx; bally = ty; }} private void setKeyListener () {this.addkeistener (new KeyAdapter () {public void Keypressed (KeyEvent e) {int c = e.getKeyCode (); Move (c); Repaint (); CheckIswin ();}}); } private boolean isoutofborder (решетка p) {return isoutofborder (p.getx (), p.gety ()); } private boolean isoutofborder (int x, int y) {return (x> num - 1 || y> num - 1 || x <0 || y <0)? Верно: Неверно; } частная решетка [] getneis (решетчатая p) {final int [] adds = {-1, 0, 1, 0, -1}; // Порядок -верхний, справа, влево, если (isOutofborder (p)) {return null; } Решетка [] ps = новая решетка [4]; // Порядок - верхний, справа, слева, int xt; int yt; for (int i = 0; i <= 3; i ++) {xt = p.getx ()+добавляет [i]; yt = p.gety () + добавляет [i + 1]; if (isOutofborder (XT, yt)) продолжить; ps [i] = maze [xt] [yt]; } return PS; } private void createEmaze () {randing random = new random (); int rx = math.abs (random.nextint ()) % num; int ry = math.abs (random.nextint ()) % num; Stack <lattice> s = новый стек <statice> (); Решетка p = лабиринт [rx] [ry]; Решетка neis [] = null; S.Push (P); while (! s.isempty ()) {p = s.pop (); P.Setflag (решетка. Интри); neis = getneis (p); int ran = math.abs (random.nextint ()) % 4; for (int a = 0; a <= 3; a ++) {ran ++; ran %= 4; if (neis [ran] == null || neis [ran] .getflag () == lattice.intree) продолжить; S.Push (Neis [Ran]); neis [ran] .setfather (p); }} // changeFather (Maze [0] [0], null); } private void изменение ofather (решетка p, решетка f) {if (p.getfather () == null) {p.setfather (f); возвращаться; } else {changefather (p.getfather (), p); }} private void clearfence (int i, int j, int fx, int fy, graphics g) {int sx = padding + ((j> fy? j: fy) * ширина), sy = padding + (i> fx? if (sx! = dx) {sx ++; dx--; } else {sy ++; dy--; } g.drawline (sx, sy, dx, dy); } Protected void PaintComponent (Graphics G) {super.paintComponent (g); for (int i = 0; i <= num; i ++) {g.drawline (adding + i * width, padding, padding + i * width, padding + num * width); } for (int j = 0; j <= num; j ++) {g.drawline (накладка, прокладка + j * ширина, прокладка + num * width, padding + j * width); } g.setcolor (this.getbackground ()); for (int i = num-1; i> = 0; i--) {for (int j = num-1; j> = 0; j--) {решетка f = maze [i] [j] .getfather (); if (f! = null) {int fx = f.getx (), fy = f.gety (); Clearfence (i, J, FX, Fy, G); }}} g.drawline (прокладка, прокладка + 1, накладка, прокладка + ширина - 1); int last = padding + num * width; G.Drawline (последний, последний - 1, последний, последний - ширина + 1); g.setcolor (color.red); G.Filloval (getCenterx (Bally) - ширина / 3, getCentery (ballx) - ширина / 3, ширина / 2, ширина / 2); if (drawpath == true) drawpath (g); } private void DrawPath (Graphics g) {color path_color = color.orange, both_path_color = color.pink; if (drawpath == true) g.setcolor (path_color); иначе g.setcolor (this.getbackground ()); Решетка p = лабиринт [num - 1] [num - 1]; while (p.getfather ()! = null) {p.setflag (2); p = p.getfather (); } g.filloval (getCenterx (p) - ширина / 3, getCentery (p) - ширина / 3, ширина / 2, ширина / 2); p = лабиринт [0] [0]; while (p.getfather ()! = null) {if (p.getflag () == 2) {p.setflag (3); g.setcolor (both_path_color); } g.drawline (getCenterx (p), getCentery (p), getCenterx (p.getfather ()), getCentery (p.getfather ())); p = p.getfather (); } g.setcolor (path_color); p = лабиринт [num - 1] [num - 1]; while (p.getfather ()! = null) {if (p.getflag () == 3) break; G.Drawline (GetCenterX (P), GetCenery (P), GetCenterx (p.getFather ()), GetCentery (p.getfather ())); p = p.getfather (); }} public static void main (string [] args) {final int n = 30, ширина = 600, прокладка = 20, lx = 200, ly = 100; Jpanel p = новый лабиринт (n, (ширина - накладка - накладка) / n, накладная); Jframe frame = new jframe ("Maze (показывать или скрыть пути с помощью космической линии)"); Frame.getContentPane (). Add (P); frame.setDefaultCloseoPeration (jframe.exit_on_close); Frame.setSize (ширина + прокладка, ширина + прокладка + прокладка); Frame.SetLocation (LX, LY); Frame.SetVisible (true); }}