這東西我有想過怎麼做比較好，它大致有兩種做法
一、生成 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