[wizs] 隨機地圖的生成

看板mud_sanc (Sanctuary - 聖殿)作者laechan (揮淚斬馬雲)時間7年前 (2018/11/17 16:45)推噓0(0推 0噓 6→)

留言6則, 1人參與討論串1/6 (看更多)

這東西我有想過怎麼做比較好，它大致有兩種做法一、生成 m x n 格圖，然後依一定的規則隨機挖空二、先生成一個點，然後採遞迴做法(設定邊界)讓它向外隨機擴散若是第一種做法，「規則」雖是重點，但其實規則也沒那麼重要，因為可以用 re-check 來確保點與點之間至少都存在兩個連結。 (不過這個 re-check 會寫得很複雜，所以還是回到確立規則上) 若是第二種做法，倒是不一定要用遞迴，比方讓它每一秒自我呼叫一次時就擴散一次，這樣差不多就能達到要求，缺點是它很難避免「中心點」的存在，而並非所有地圖都有中心點。根據以上，初步結論看起來是採第一種做法。但是上面兩種方法我都不想用。 ====== 假設以下格圖以及我最終希望看到的格圖 x-x-x-x-x x-x-x x | | | | | | | x-x-x-x-x x-x x | | | | | | | x-x-x-x-x x-x-x x | | | | | | | x-x-x-x-x x-x-x-x 實際上依我先前規劃的各種隨機做法，都不可能產生右邊的格圖，除非我制定一種規則叫做先決定起點與終點，然後再令它去爬，才有可能，這東西看似複雜，其實它有簡單的做法: 比方起點是 (0,0) 終點是 (4,0) 這樣的設計，題目就變成這兩點之間在邊界範圍 4, 3 之下可拉出多少條線的問題: starts=({0,0}); ends=({4,0}); // 首先決定下一點是往右還是往下 random(2)==1 ? nexts=({0+1,0}); : nexts=({0,0+1}); starts+=({nexts}); s=1; over_bound=0; // 然後就可以隨機了 while(starts[s]!=ends) // 實際上不會這樣子寫 { x=starts[s][0]-starts[s-1][0]; y=starts[s][1]-starts[s-1][1]; // 這裡只有一個規則: 不能走回頭路 if(random(2)==1) // 橫移 { if(x!=0) // 代表上次是橫移 { // 就只能往同方向再橫移 nexts=({starts[s][0]+x,starts[s][1]}); } else // 上次不是橫移, 那往哪個方向都可 nexts=({random(2)==1 ? starts[s][0]-1 : starts[s][0]+1,starts[s][1]}); } else // 直移 { if(y!=0) // 代表上次是直移 { // 就只能往同方向再直移 nexts=({starts[s][0],starts[s][1]+y}); } else // 上次不是直移, 那往哪個方向都可 nexts=({starts[s][0],random(2)==1 ? starts[s][1]-1 : starts[s][1]+1}); } // 先檢測 nexts 有沒有在 starts 內, 有的話就是重跑 if(member_array(nexts,starts)!=-1) continue; // 檢測 nexts 有沒有超過邊界 if(nexts[0]<0 || nexts[0]>4 || nexts[1]<0 || nexts[1]>3) { over_bound++; if(over_bound>10) // 保險值 break; // 中斷 continue; // 在保險值內就再一次 } // 都沒超過邊界就是安全的 starts+=({nexts}); s++; over_bound=0; // 繼續跑迴圈 } // 最後列出跑出來的 starts write(identify(starts)+"\n"); 以下是跑出來的幾次結果: ({ ({ 0, 0 }), ({ 1, 0 }), ({ 2, 0 }), ({ 3, 0 }), ({ 4, 0 }) }) 這個再明顯不過就是一直橫移過去 x-x-x-x-x ({ ({ 0, 0 }), ({ 0, 1 }), ({ 0, 2 }), ({ 1, 2 }), ({ 2, 2 }), ({ 3, 2 }), ({ 3, 1 }), ({ 3, 0 }), ({ 4, 0 }) }) x x-x | | x x | | x-x-x-x ({ ({ 0, 0 }), ({ 0, 1 }), ({ 0, 2 }), ({ 0, 3 }), ({ 1, 3 }), ({ 2, 3 }), ({ 3, 3 }), ({ 4, 3 }), ({ 4, 2 }), ({ 4, 1 }), ({ 4, 0 }) }) x x | | x x | | x x | | x-x-x-x-x ({ ({ 0, 0 }), ({ 1, 0 }), ({ 1, 1 }), ({ 0, 1 }), ({ 0, 2 }), ({ 0, 3 }), ({ 1, 3 }), ({ 1, 2 }), ({ 2, 2 }), ({ 3, 2 }), ({ 3, 3 }), ({ 4, 3 }), ({ 4, 2 }), ({ 4, 1 }), ({ 4, 0 }) }) x-x x | | x-x x | | <= 這張大致就是我們要的形式 x x-x-x x | | | | x-x x-x 上面打了一堆其實重點是: 一、單一路線型隨機地圖是可行的二、過往我要自己產生 m x n 的圖後再自己挖洞，現在可以讓程式幫我挖。三、原本需要自己選出哪一張地圖較適合，現在可以用「產生出幾％以上的點」來做為一種指標，例如以上面產生的那張圖為例為 15點/總共20點 = 75％，15 點其實就像一張正常的地圖了的意思。這時甚至可以設定讓它跑出更多的點，例如以下是 17 點: ({ ({ 0, 0 }), ({ 1, 0 }), ({ 1, 1 }), ({ 0, 1 }), ({ 0, 2 }), ({ 0, 3 }), ({ 1, 3 }), ({ 2, 3 }), ({ 2, 2 }), ({ 2, 1 }), ({ 2, 0 }), ({ 3, 0 }), ({ 3, 1 }), ({ 3, 2 }), ({ 4, 2 }), ({ 4, 1 }), ({ 4, 0 }) }) x-x x-x x | | | | x-x x x x | | | | x x x-x | | x-x-x 以上只是先證明這構想是可 work 的，後面的回文都會以上面為基礎繼續下一步的 write & run。 PS、這東西如果我不是先前持續在寫 code 以及最近清淡飲食，要寫出來有點難度。 Laechan -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.117.106.224 ※ 文章網址: https://www.ptt.cc/bbs/mud_sanc/M.1542444349.A.5C0.html

→