起源：
昨年（中学校の最初の学期）、私は小さなゲームを書くのが好きだったので、迷路を書いてみたいと思いました。
プログラム効果：
スペースを押してパスを表示します。
思考プロセス：
迷路はグリッドで構成されており、出口への入り口から1つのパスのみが必要です。
さまざまなデータ構造について考えた後、ルートノードから各子ノードへのパスは1つだけで、ツリーの方が適しているようです。入り口がルートノードであり、出口がツリー内の子ノードであると仮定すると、ルートノードから子ノードへのパスは間違いなくユニークです。
したがって、すべてのグリッドをカバーするためにツリーを構築できれば、迷路を作成できます。
さらに、ツリーの親と子のノードは、インターフェイス上の隣接するグリッドでなければなりません。
インターフェイスを表示すると、親ノードと子ノードの間で共有されたエッジが描かれておらず、他のエッジが描かれていない場合、迷路を描画できます。
それから私はそのような木を実装する方法について考えました。
最初の2つの質問：
1.木はどのように表していますか？
2。この木を構築する方法は？
1.木はどのように表していますか？
このツリーがバイナリツリーの作成のように実装されていると仮定すると、各ツリーノードはグリッドを表すために座標（x、y）を保存する必要があり、4つのポインターを保存する必要があります。いくつかのポインターは空で、一部は空ではなく、空ではないポインターは子ノードをポイントし、子ノードは隣接グリッドの座標を保存します。これを行うことの最大の問題は、すべてのグリッドが木にあるかどうかを判断することが不可能であることです。たぶん、2次元配列もフラグアレイとして使用されます。
2次元配列を使用して迷路のグリッドを表すとします。各配列要素は、親ノードへの参照を保存し、仮想ツリーを形成することもできます。したがって、n*nの2次元配列はn*nグリッドを表し、各配列要素（格子）には親ノードへの参照があります。さらに、グリッドの座標を簡単に取得するには、座標情報も保存する必要があります。
2。この木を構築する方法は？
最初にルートノードとしてグリッドを選択します。迷路の形状を十分にランダムにするために、ルートノードとして座標をランダムに生成することを選択しました。実際、決定された座標を選択しても問題ありません。
次に、このツリーにノードを追加する方法は？
ここでたくさんの迂回路を取りました。最初は、バックトラッキングに似ていると思われるアルゴリズムを考えました（当時のバックトラッキングアルゴリズムはわかりませんでした。）が、時間の複雑さは非常に高いです。おそらく、迷路が64*64の場合、アルゴリズムは結果を生成しません。
次に、深度検索のスキャン方法もバックトラッキングです。スキャンするたびに、現在のツリーにノードがあり、隣接グリッドがツリーにあるかどうかを確認します。ツリーにない場合は、隣のグリッドをツリーに追加します。すでに木にある場合は、次の隣のグリッドを見てください。ノードのすべての隣接グリッドがツリー内にある場合、次のノードを見つけて同じ操作を続けます。さらに、迷路をランダムに生成するために、スキャンの開始位置はランダムです。ただし、この方法で生成された迷路のパスは、私が望む曲がりくねりで詳細な効果を持つほど深くはありません。結局のところ、それは幅の検索と同様の方法です。さらに、これを行うことは常にブルートフォースに依存しているようであり、アルゴリズムはスマートで簡潔ではありません。
最後に、私はついに詳細な検索を使用することを考えました。 。おそらく、私は1年間データ構造を学んでいて、それをあまり練習していないので、私が考えるべきこの最初の方法を考えたことはありません。 。
グリッドをルートノードとしてランダムに選択し、そこから開始して詳細に検索し、行く方法がないまで、もう1つのステップを撤回し、別の方法を変更してから、行く方法がなく、一歩後退し、別のサイクルを変更する方法がありません。 。 。実際、それはまだバックトラッキングです。
プログラムでは、次のプロセスは（詳細については、コードのcreatemaze（）関数を参照）です。
ルートノードとしてグリッドをランダムに選択し、スタックに押し込みます。
次に、スタックが空になっていないときに次のループを実行します。
グリッドを取り出して、ツリーフラグを1に設定してから、ツリーにないすべての隣接グリッドをスタックに押し込み（ストーリーをランダムに）、これらの隣のグリッドの父親がグリッドを指します。
これら2つの問題を解決した後、迷路の残りの部分、パスの表示、および動くボールの描画は比較的簡単です。
コード
パッケージ迷路; Import 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; import javax.swing.javax.swingpane; Import javax.swingpane; javax.swing.jpanel; class lattice {static final int intree = 1; static final int notintree = 0;プライベートint x = -1;プライベートint y = -1; Private int flag = notintree;プライベートラティスファーザー=ヌル; public Lattice（int xx、int yy）{x = xx; y = yy; } public int getX（）{return x; } public int gety（）{return y; } public int getFlag（）{return flag; } public Lattice getFather（）{return父; } public void setfather（lattice f）{father = f; } public void setflag（int f）{flag = f; } public string toString（）{return new String（ "（" + x + "、" + y + "）/n"）; }} public class maze extends jpanel {private static final long serialversionuid = -8300339045454852626l; private int num、width、padding; //幅各グリッドプライベート格子の幅と高さ[] []迷路; Private int Ballx、Bally;プライベートブールドローパス= false;迷路（int m、int wi、int p）{num = m; width = wi;パディング= P;迷路= new Lattice [num] [num]; for（int i = 0; i <= num-1; i ++） createmaze（）; setKeyListener（）; this.setFocusable（true）; } private void init（）{for（int i = 0; i <= num-1; i ++）for（int j = 0; j <= num-1; j ++）{maze [i] [j] .setfather（null）;迷路[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（lattice P）{return padding + p.gety（） * width + width / 2; } public int getCentery（lattice P）{return padding + p.getx（） * width + width / 2; } private void checkiswin（）{if（ballx == num-1 && bally == num-1）{joptionpane.showmessageialog（null、 "you win！"、 "迷路から出てきました。 init（）; }}同期されたプライベートボイド移動（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）{drawpath = false; } else {drawpath = true; } 壊す;デフォルト：} if（！isoutofborder（tx、ty）&&（maze [tx] [ty] .getfather（）== maze [ballx] [bally] || maze [ballx] [bally] .getfather（）== maze [tx] [ty]））{ballx = tx; Bally = ty; }} private void setKeyListener（）{this.addkeyListener（new keyAdapter（）{public void keypressed（keyevent e）{int c = e.getkeycode（）; move（c）; repaint（）; checkiswin（）; checkiswin（）;}}}}）; } private boolean isoutofborder（lattice 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）？ True：false; } private lattice [] getneis（lattice p）{final int [] adds = {-1、0、1、0、-1}; //順序は上、右、左、if（isoutofborder（p））{return null; } lattice [] ps = new Lattice [4]; //順序は上、右、左、int xt; int yt; for（int i = 0; i <= 3; i ++）{xt = p.getx（）+adds [i]; yt = p.gety（） + adds [i + 1]; if（isoutofborder（xt、yt））継続; ps [i] = maze [xt] [yt]; } psを返します。 } private void createmaze（）{random = new Random（）; int rx = math.abs（random.nextint（））％num; int ry = math.abs（random.nextint（））％num; stack <lattice> s = new Stack <Lattice>（）;格子P =迷路[rx] [ry];格子neis [] = null; S.Push（P）; while（！s.isempty（））{p = s.pop（）; P.SetFlag（lattice.intree）; 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（迷路[0] [0]、null）; } private void changefather（lattice P、lattice 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） * width）、sy =パディング +（（i> fx？ if（sx！= dx）{sx ++; dx--; } else {sy ++; dy-; } g.drawline（sx、sy、dx、dy）; }保護されたvoid paintComponent（グラフィックg）{super.paintComponent（g）; for（int i = 0; i <= num; i ++）{g.drawline（padding + i * width、padding、padding + i * width、padding + num * width）; } for（int j = 0; j <= num; j ++）{g.drawline（パディング、パディング + j *幅、パディング + num *幅、パディング + j *幅）; } g.setColor（this.getBackground（））; for（int i = num-1; i> = 0; i-）{for（int j = num-1; j> = 0; j-）{lattice 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（last、last -1、last、last -width + 1）; g.setcolor（color.red）; g.filloval（getCenterx（Bally） - width / 3、getCentery（ballx） - width / 3、width / 2、width / 2）; if（drawpath == true）drawpath（g）; } private void drawpath（グラフィックスG）{color path_color = color.orange、both_path_color = color.pink; if（drawpath == true）g.setcolor（path_color）; else g.setcolor（this.getBackground（））;格子P =迷路[num -1] [num -1]; while（p.getfather（）！= null）{p.setflag（2）; p = p.getfather（）; } g.filloval（getcenterx（p） - width / 3、getcentery（p）-width / 3、width / 2、width / 2）; p =迷路[0] [0]; while（p.getfather（）！= null）{if（p.getflag（）== 2）{p.setflag（3）; G.SetColor（blote_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）、GetCentery（P）、GetCenterx（p.getfather（））、getCentery（p.getfather（）））; p = p.getfather（）; }} public static void main（string [] args）{final int n = 30、width = 600、padding = 20、lx = 200、ly = 100; jPanel P = new Maze（n、（width -padding -padding） / n、padding）; jFrame frame = new JFrame（ "Maze（Show or Hide Paths by Space Bar）"）; frame.getContentPane（）。add（p）; frame.setDefaultCloseoperation（jframe.exit_on_close）; frame.setsize（幅 +パディング、幅 +パディング +パディング）; frame.setlocation（lx、ly）; frame.setVisible（true）; }}