はじめに
この記事は新歓ブログリレー2026、40日目の記事です。
こんにちは、25Bの@fken_57です。アルゴリズム班とゲーム班を7:3くらいの比率でやっていたりします。
さて、今日はアルゴリズムをいかにゲームに活かすかについて考えていきたいと思います。これを考えていくことで、ゲーム班をやっている人に、逆にアルゴリズムの魅力を伝えていきたいなぁという目的、そして新入生にアルゴリズムの魅力を伝えたいなぁが目的です。
問題1
今回考えていくのは迷路をどうやって構築するかの問題です。ただ、迷路の生成と言えば、グリッド迷路を想起すると思いますが、今回は少し違ったテイストの問題を考えていきたいと思います。
都市に10個くらいの交差点と10個くらいの道路がある。あなたはこれらの道路のうち一部を通行止めにして都市の中に迷路を生成する実装を任された。要件は「どの交差点からどの交差点へも到達可能」「自明なルートがない」こと。
これを実装するときにあなたはきっとこう思うでしょう。
「10個の交差点と10個の道路くらいならUnity上のエディターの手作業でできるわ！」その通りです。10個くらいなら自分でできます。「やっぱアルゴリズムなんてなくてもゲームはできる！」このように簡単なゲームならアルゴリズムなんてなくて腕力を使えば実装できます。
問題2
あなたは、先ほどのようにして実装した迷路ゲームがとてもつまらないことに気付きました。さぁここから面白くするために高橋君は次のことを追加しようかなと考えました。
- まず大きさが小さすぎるので、交差点の数を1000個にしてみたい
- さらに、迷路を毎回ランダムに生成できるようにしたい
つまり先ほどの問題は、
都市に1000個の交差点と1000個の道路がある。あなたはこれらの道路のうち一部を通行止めにして都市の中に迷路を生成する実装を任された。要件は「どの交差点からどの交差点へも到達可能」「自明なルートがない」「迷路は毎回ランダムに生成される」
に変更される。
これを実装するときに、「また手作業でやろう」というのは無理がありますし、仮にとんでもない時間をかければ実装できるかもしれませんが、もし迷路の交差点の数を5個くらい変えたいみたいな変更にとんでもなく脆いという弱点があります。
ここでやっとアルゴリズムの出番が来ます。まずは、この問題をよりアルゴリズムコンテスト的な文章に直してみましょう。ここでは交差点を点、道路を辺として扱います。
(1000) 個の点と (1000) 個の辺からなる単純無向グラフが与えられる。このグラフからランダムにいくつかの辺を削除して、すべての点が連結であるようなグラフを作成する。ただし、作成したグラフはできるだけ複雑性が高い方がよい。
ここで必要なのは、「ランダム性」という要件と「連結性」という要件であり、「複雑性」は一回後にして考えることができる。ここで満たすのが難しいのはランダム性というよりもむしろ連結性でしょう。ランダム性は適当に消す辺を並び替えればいいので達成が容易であると考えられるからです。
つまり、
1.ランダムに辺をシャッフルする
2.辺を消去して連結性を保つかをなんかしらの方法で判定する
3.もし連結性を保つならその辺を削除し、連結性を保たないならその辺を残す
4.すべての辺に関して2〜3の処理を繰り返す
さあ、肝心の連結性はどのように判定するかが問題です。「すべての辺が無向グラフで連結である」は辺の方向依存性が無いため、言い換えると「ある頂点から任意の頂点へ到達可能」であるかどうかを判定する必要があります。これはDFSやBFSなどの探索アルゴリズムを用いることで実現できます。
よって
1.ランダムに辺をシャッフルする
2.辺を消去して連結性を保つかをDFSまたはBFSで判定する
3.もし連結性を保つならその辺を削除し、連結性を保たないならその辺を残す
4.すべての辺に関して2〜3の処理を繰り返す
C++で実装すると以下のようになります。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
void dfs(int v, vector<vector<ll>>& G, vector<bool>& visited ,vector<vector<bool>>& removed_edges) {
visited[v] = true;
for (int i = 0; i < G[v].size(); i++) {
if (!visited[G[v][i]] && !removed_edges[v][G[v][i]]) {
dfs(G[v][i], G, visited, removed_edges);
}
}
}
int main(){
ll N,M;
cin >> N >> M;
vector<pair<ll,ll>> edges(M);
vector<vector<ll>> G(N);
for(int i=0;i<M;i++){
ll a,b;
cin >> a >> b;
edges[i] = {a-1, b-1};
G[a-1].push_back(b-1);
G[b-1].push_back(a-1);
}
//乱数を利用したソートをする
random_device seed_gen;
mt19937 engine(seed_gen());
shuffle(edges.begin(), edges.end(), engine);
//除去した辺の集合を持つ
vector<vector<bool>> removed_edges(N, vector<bool>(N, false));
for(int i=0;i<M;i++){
ll a = edges[i].first;
ll b = edges[i].second;
// Add the edge to the set of removed edges
removed_edges[a][b] = true;
removed_edges[b][a] = true;
vector<bool> visited(N, false);
dfs(0, G, visited, removed_edges);
if(!all_of(visited.begin(), visited.end(), [](bool x) { return x; })) {
// The graph is not connected
removed_edges[a][b] = false;
removed_edges[b][a] = false;
}
}
for(int i=0;i<M;i++){
ll a = edges[i].first;
ll b = edges[i].second;
if(!removed_edges[a][b]){
cout << a+1 << " " << b+1 << endl;
}
}
}
問題3
高橋君は、この迷路を見て、「まだまだ複雑性と交差点が足りない！」と感じました。
以下の問題を考えることにします。
(200000) 個の点と (200000) 個の辺からなる単純無向グラフが与えられる。このグラフからランダムにいくつかの辺を削除して、すべての点が連結であるようなグラフを作成する。ただし、作成したグラフはできるだけ複雑性が高い方がよい。
高橋君はこう思いました。「問題1-2でもうコードを作ったからそれをそのまま使えばいいじゃん！」と。
いざコードを実行したら高橋君のPCは固まってしまいました。「正しいコードを書いたのに…」
確かにコードは正しいですが、辺の消去の判定に大きさ の2次元メモリを使っているからメモリ使用量が多すぎます。また、そこを改善したとしても根本的にアルゴリズムの問題があります。この実装の計算量はM回のループの中で となります。
さぁ、どうやって計算量を改善すればいいのでしょうか？
まず競技プログラミング的に「削除」という動作は、あまりいい性質が存在しないことが多いです。
そこで、「追加」という軸に転換して考えてみましょう。
「初めに個の点と 個の辺からなる単純無向グラフが与えられる。 個の辺の候補が与えられます。候補の中から辺を追加して、すべての点が連結であるようなグラフを作成する。ただし、作成したグラフはできるだけ複雑性が高い方がよい。」
ここで、「複雑性」について考えると、できるだけ難易度が高い方がよいでしょう。それを考えると「これ以上辺を消去したら連結性が保たれなくなる」状態にする必要があって、この状態は「最小全域木」の状態を考えればいいのです。これで計算量が にまで改善されますが、まだまだ改善することができます。
ここで「ランダム性」について考えると、「各辺に重みをランダムに割り当てて、そこから重みが小さい順に辺を追加していく」ことで、ランダムな迷路を生成できます。ただ、本当にランダムなら「重みをランダムに割り当ててソートする」なんて冗長なことをしなくても、そもそも「辺をランダムな順番に並び替えて、残りは最小全域木の辺追加のロジックだけやる」ようにします。
1.ランダムに辺をシャッフルする
2.辺を追加して、すでにその2点が同じ連結成分かを何らかの方法で判定する
3.もし追加したときに既にその2点が同じ連結成分なら追加しない、そうでなければ追加をする。
4.すべての辺に関して2〜3の処理を繰り返す
ここで、2点が同じ連結成分であるかは、Union Findで判定することができ、この方法は計算量を効率的に保つことができます。グループ化、マージ でできてしまいます。
よって、利用する手法は以下の手順で書き下すことができます。
1.ランダムに辺をシャッフルする
2.辺を追加して、すでにその2点が同じ連結成分かをUnion Findで判定する
3.もし追加したときに既にその2点が同じ連結成分なら追加しない、そうでなければUnion Findで2つの点をマージした後に追加をする。
4.すべての辺に関して2~3の処理を繰り返す
C++で実装すると以下のようになります。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
vector<pair<ll,ll>> ReturnSpanningTree(vector<pair<ll,ll>>& edges, ll N){
dsu t(N);
vector<pair<ll,ll>> tree;
for(auto e : edges){
ll u = e.first, v = e.second;
if(!t.same(u, v)){
t.merge(u, v);
tree.push_back(e);
}
}
return tree;
}
int main(){
ll N,M;
cin >> N >> M;
vector<pair<ll,ll>> edges(M);
for(int i=0;i<M;i++){
ll a,b;
cin >> a >> b;
edges[i] = {a-1, b-1};
}
random_device seed_gen;
mt19937 engine(seed_gen());
shuffle(edges.begin(), edges.end(), engine);
auto tree = ReturnSpanningTree(edges, N);
for(int i=0;i<tree.size();i++){
cout << tree[i].first + 1 << " " << tree[i].second + 1 << endl;
}
}
なんと、ACLibraryを活用することによって、簡潔に点の総数に対して で一般的なグラフに関する迷路を生成することができました。このように最初は手作業でやっていた迷路の生成も、効率的なアルゴリズムを用いることで簡単に実現できるようになりました。あとは迷路の形状に合わせて、グラフを構築してC#で実装すれば、高橋君が作りたい迷路が完成することになります。
実際にC#でコードを書いて、Unityで動かしてみた
実際にC++で書いたロジックをC#に移植して、迷路を生成してみました。
写真は大きさ縦100横100の迷路になります。
また、縦1000横1000()の迷路を生成させる無茶ぶりも行いましたが、10秒くらいで迷路を生成することに成功しました！ボトルネックはおそらくUnityのGizmo自身の重さだと思います。
画像は、サイズが大きすぎてもはや豆腐に見える迷路の一部分を切り出したものです。
まとめ
今回はアルゴリズムを用いて迷路を生成する方法について考えました。最初は手作業でやっていた迷路の生成も、最初に基礎的なグラフ探索アルゴリズムを用いることで、生成を に改善することができました。さらに、アルゴリズム的な視点から主題を換言することによって、 に改善することができました。
要するに今回言いたいことは、「アルゴリズムを用いることで、自分が表現したいより複雑なロジックもゲーム中に組み込み可能である」ということです。
アルゴリズムを学ぶことで自分のしたい表現をあきらめることなく、より魅力的なゲームを創り出すことができます！
最後に
アルゴリズムなんて、「自分なんかには難しいよ」「ハードル高いよ」っておもっている人も多いかもしれませんが、一度触れてみると意外と面白いし、何より誰でも楽しさが感じられるようになります。
是非新入生やアルゴリズムに興味持ってるけどなかなか挑戦できてない人も、このブログをきっかけに、是非AtCoderとかの競技プログラミングなどに挑戦してみてほしいです！！
明日(4/15)の新歓ブログリレーの担当は@Haru_18です。お楽しみに～
