演算法可視化

碼云倉庫地址：https://gitee.com/CandyWall/alogrithm-visualizer
喜歡的朋友記得點個star喲

本代碼參考慕課網的liuyubobobo老師的一門課《7個經典應用詮釋Java演算法精髓》，并且基于課程中的參考代碼做了一定的完善和個人定制，

以Java語言主講，通過7款經典好玩游戲，真正將演算法用于實際開發，

可視化用到的語言和技術

Java Swing

可視化內容

1. 概率模擬演算法

使用蒙特卡洛演算法模擬計算PI

2. 排序演算法

選擇排序可視化

插入排序可視化

歸并排序可視化

3. 迷宮自動求解迷宮

注：迷宮自動求解游戲添加了鍵盤點擊事件按對應的鍵盤按鍵將觸發相應的操作
- 按數字1：深度優先遍歷演算法生成迷宮
- 按數字2：深度優先遍歷非遞回演算法生成迷宮
- 按數字3：廣度優先遍歷演算法生成迷宮
- 按數字4：隨機佇列遍歷演算法生成迷宮
- 按數字5：增強隨機佇列演算法生成迷宮
- 按數字7：深度優先遍歷遞回演算法求解迷宮
- 按數字8：深度優先遍歷非遞回演算法求解迷宮
- 按數字9：廣度優先遍歷演算法求解迷宮
- 按數字0：清屏，游戲回到迷霧籠罩的狀態
從檔案中讀取迷宮資訊，并且進行可視化；

深度優先遍歷遞回寫法+回溯法求解迷宮可視化；

深度優先遍歷的非遞回寫法求解迷宮可視化；

廣度優先遍歷演算法求解迷宮可視化；

4. 生成迷宮

為了簡單起見，在M行N列的迷宮中，先規定迷宮的入口是(1, 0)，出口是(M-2, N-1)

迷宮生成前的準備作業

下面是61x91規格的迷宮，奇數行和奇數列相交的位置是通路（沒有墻），生成迷宮前需要先產生一個這樣的圖，然后只需要深度優先遍歷所有在奇數行和奇數列相交的路，然后打破兩個路之前的墻即可產生一個迷宮，

深度優先遍歷遞回演算法生成一個迷宮

深度優先遍歷非遞回演算法生成一個迷宮

廣度優先遍歷非遞回演算法生成一個迷宮

創建一個隨機佇列讓迷宮的生成程序更隨機

給未生成部分添加迷霧，讓生成迷宮的程序更具備觀賞性和神秘感

隨機佇列的代碼請參考RandomQueue.java

隨機迷宮的生成程序如下圖所示：

隨機迷宮的求解程序如下圖所示：

增強生成迷宮的隨機性

經過多次迷宮的生成和求解程序來看，迷宮的解路徑大致趨勢是從左上到右下的一條不是很曲折的曲線，隨機性還不夠強，所以優化了隨機佇列的隨機存取元素的代碼，參考EnhancedRandomQueue.java

增強隨機性后迷宮的生成程序如下圖所示：

增強隨機性后迷宮的求解程序如下圖所示：

5. 掃雷

掃雷游戲勝利與游戲結束

游戲結束

注：游戲結束后可按回車重新開局！

勝利

在游戲盤面中隨機30枚雷

隨機演算法好壞評估

演算法目標：將指定數量的雷隨機放在游戲區域中的相同數量的格子中
使用大量次數統計的方法對三種隨機打亂演算法，參考RandomAlgorithmAssessment.java
- arr：待隨機打算順序的陣列；mineNumber：雷的個數（小于陣列長度）
- 隨機演算法1：將每一個格子上的值和隨機的格子上的值進行交換
```
for (int i = 0; i < arr.length; i++) {
    int j = (int) (Math.random() * arr.length);
    swap(arr, i, j);
}
```
- 隨機演算法2：將每一個雷所在的格子上的值和隨機的格子上的值進行交換
```
for (int i = 0; i < mineNumber; i++) {
    int j = (int) (Math.random() * arr.length);
    swap(arr, i, j);
}
```
- knuth演算法：從[i, n)區間中隨機獲取元素，然后和第i個元素交換
```
for (int i = 0; i < arr.length; i++) {
    int j = (int) (Math.random() * (arr.length - i) + i);
    swap(arr, i, j);
}
```
- knuth演算法的另一種寫法，從[0, i+1)區間中隨機獲取元素，然后和第i個元素交換
```
for (int i = arr.length - 1; i >= 0; i--) {
    int j = (int) (Math.random() * (i + 1));
    swap(arr, i, j);
}
```
- 各個演算法在N=10000000，n=10，m=5的情況下（N為統計次數，n為陣列長度，m為陣列中的雷的個數），陣列中的各個位置上出現雷的頻率如下圖所示：

6. 移動箱子游戲給出求解步驟

游戲介紹：

這是一個三消類推箱子游戲，跟傳統的推箱子不一樣，這個推箱子需要你在規定的步數內移動箱子，促使游戲面板中三個相同的箱子連成一行或者一列，可以達成消除的條件，另外游戲設定了重力系統，高出的箱子如果往左或者往右或者它下面的箱子被消除了，都會促使這個箱子向下墜落，墜落以后，又會檢測是否出現新的可消除的連續的三個相連的箱子，游戲封面如下

這是游戲中的某一個關卡：要求在移動一步的條件下消除所有的箱子，

游戲物體符號化

現將上面關卡中的箱子的分布轉換為一個二維字符陣列，連同操作步數一起保存到檔案中，

1
.....
..A..
..B..
..A..
..B..
.BAB.
.BAB.
.ABA.

然后通過代碼來讀取操作步數和二維字符陣列，為了對齊每列的字符，空的位置用點表示，不同種類的箱子用不同的字母表示，

渲染符號化的游戲物體

用代碼讀取后渲染到頁面上如下圖所示，由于沒有原游戲的箱子素材，我就在網上找了一些圖片進行了替換，

查看求解步驟

為了使得求解后的答案更直觀，在每一個箱子中間寫了一個坐標，代表目前這個箱子所在的行和列，

根據控制臺列印出的結果和圖上的坐標，去游戲里面進行相應操作即可通過此關，

交換 (3, 2) 和 (4, 2)
游戲有解！

7. 繪制分形圖

遞回繪制同心圓

在這里插入圖片描述

遞回繪制vicsek（矩形）分形圖

可以按鍵盤上的0到6進行不同遞回次數的分形

初始化默認遞回次數為0，呈現出整個區域都是一個顏色

分別按下鍵盤1-6又可以繪制出如下分形圖

遞回繪制SierpinskiCarpet（矩形）分形圖

遞回繪制SierpinskiTriangle（三角形）分形圖

遞回繪制KochSnowflake（雪花）分形圖

遞回繪制二叉樹分形圖

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275341.html

標籤：其他

上一篇：HO引擎近況20210413

下一篇：Asciidoctor-pdf生成pdf檔案

使用Java Swing實作7個經典應用詮釋演算法精髓