ブラウザゲームで毎フレーム回すネットワーク負荷計算 — BFS木とブロードキャストドメイン

ネットワーク配線をテーマにしたブラウザゲームを作ると、避けて通れない計算が1つある。いま引いてある配線に対して、どのケーブルが何Mbps流れているのかを毎フレーム出すことだ。

これは見た目の演出ではなく、ゲームの根幹である。ケーブルの色も、パケットロスの蓄積も、リンクが切れる判定も、すべてこの数字1つから決まる。逆に言えば、この計算が重かったり、フレームごとに答えがブレたりすると、ゲームが成立しない。

この記事では、hashito.biz で公開している配線パズル パケットワイヤー の実装をもとに、ブラウザで毎フレーム回せる負荷計算の作り方を書く。要点は3つある。BFSで木を作って経路を一意にすること、ブロードキャストドメインを木の走査順で振ること、そして同じ配線からは必ず同じ木ができるように順序を固定することである。

なぜ「毎フレーム最短経路」ではだめなのか

素朴に考えると、末端の機器から外部回線までの経路を出すのだからDijkstraだろう、となる。だが実際にはこれは要件に合っていない。

このゲームの盤面は、ハブやスイッチを置いて機器を繋いだLANである。LANの経路は「毎回いちばん速い道を選び直す」ものではなく、スパニングツリーで一度決まったら、その形のまま流れ続ける。プレイヤーがケーブルを1本足したときに、画面中の全経路が突然引き直されると、何が原因で混んだのかが読めなくなる。

だからここで必要なのは最短経路探索ではなく、根（外部回線）を決めた全域木の構築である。BFSで十分で、しかも計算量は辺の数に対して線形だ。

function buildTree(net) {
  var parent = {}, hop = {}, plink = {};
  var adj = {};
  for (var k = 0; k < net.nodes.length; k++) adj[net.nodes[k].id] = [];
  for (k = 0; k < net.links.length; k++) {
    var l = net.links[k];
    if (l.down) continue;                 // 切れているケーブルは辺として存在しない
    if (adj[l.a]) adj[l.a].push({ to: l.b, link: l.id });
    if (adj[l.b]) adj[l.b].push({ to: l.a, link: l.id });
  }
  // 根は外部回線。ここが存在しない盤面では最初のノードで代用する
  var root = net.nodes[0];
  for (k = 0; k < net.nodes.length; k++) {
    if (net.nodes[k].kind === 'wan') root = net.nodes[k];
  }
  var q = [root.id];
  hop[root.id] = 0; parent[root.id] = -1; plink[root.id] = -1;
  var head = 0;
  while (head < q.length) {
    var cur = q[head++], list = adj[cur] || [];
    // 枝の順番を id で固定しておく（同じ配線なら必ず同じ木になる）
    list.sort(function (x, y) { return x.to - y.to; });
    for (var i = 0; i < list.length; i++) {
      if (hop[list[i].to] !== undefined) continue;
      hop[list[i].to] = hop[cur] + 1;
      parent[list[i].to] = cur;
      plink[list[i].to] = list[i].link;   // 親へ向かうケーブルのid
      q.push(list[i].to);
    }
  }
  return { parent: parent, hop: hop, plink: plink, order: q };
}

注目してほしいのは list.sort(...) の1行である。隣接リストの順番は、ケーブルを引いた順によって変わる。並べ替えずにBFSすると、同じ配線でも保存して読み直すと違う木ができることがある。木が変われば負荷が変わり、色が変わり、切れるケーブルが変わる。ゲームの状態がロードのたびに揺れるということだ。

id でソートするだけでこれは消える。ゲームでも自動テストでも、決定性は後から足せない性質なので、木を作る箇所で最初に固定しておくのが安全である。

もう1つ、hop[nd.id] === undefined は「根から到達できない」を意味する。つまり外部回線まで繋がっていない機器で、オフライン判定はこの1行で足りる。到達性を別のフラグで管理すると必ずズレるので、木の副産物として得るのが良い。

負荷は末端から根へ足し上げる

木ができれば、負荷計算は素直に書ける。末端の機器ごとに、自分から根までの経路上の全リンクへ、その機器の要求帯域を足していく。

for (var k = 0; k < net.nodes.length; k++) {
  var nd = net.nodes[k];
  if (!nd.online || !KINDS[nd.kind].dev) continue;
  var d = demandOf(nd.kind, t, nd.seed) * mul;   // 種類と時刻で変わる要求帯域
  var cur = nd.id;
  var guard = 0;
  while (tree.parent[cur] !== undefined && tree.parent[cur] !== -1 && guard++ < 200) {
    var l = linkById(net, tree.plink[cur]);
    if (l) l.load += d;
    cur = tree.parent[cur];
  }
}

guard++ < 200 を入れてあるのは臆病だからではない。木が正しく作られていれば無限ループは起きないが、データ側が壊れた状態でロードされたときにブラウザのタブごと固まるのは避けたい。毎フレーム回るループでは、上限を持たせておくと事故が事故のまま止まる。

計算量は「機器数 × 木の深さ」である。盤面が数百ノードでも、深さはせいぜい十数なので、60fpsの1フレーム予算のなかで十分に収まる。

ブロードキャストドメインを木の順で振る

ここからがネットワークらしい部分である。実際のLANでは、末端から外へ出ていく通信のほかに、同じブロードキャストドメイン内の全リンクに一律で乗る同報通信がある。ARPやDHCPの類だ。台数が増えるほど、誰も外部と通信していなくても線が埋まっていく。

パケットワイヤーではこれを、スイッチの「分割」機能でドメインを切れる形で再現している。実装はこうなる。

// ドメイン（同報通信の届く範囲）。split が立ったスイッチで切れる。
function domainsOf(net, tree) {
  var dom = {};
  dom[tree.order[0]] = 0;
  var next = 1;
  for (var k = 1; k < tree.order.length; k++) {
    var id = tree.order[k];
    var p = tree.parent[id];
    var nd = nodeById(net, id);
    if (nd && nd.kind === 'sw' && nd.split) dom[id] = next++;  // ここで新しい島が始まる
    else dom[id] = dom[p];                                      // 親と同じ島
  }
  return dom;
}

tree.order はBFSのキューそのもの、つまり親が必ず子より先に来る順序である。これを使って先頭から舐めるだけで、親のドメイン番号を参照するときには必ず確定済みになる。再帰も visited 管理も要らない。

そのうえで、同報通信を全リンクに乗せる。

for (var k = 0; k < net.links.length; k++) {
  var l = net.links[k];
  if (l.down) continue;
  if (dom[l.a] === undefined || dom[l.b] === undefined) continue;
  var da = dom[l.a], db = dom[l.b];
  // 境界をまたぐ線は、上流（親）のドメインに属する。
  // 分けたスイッチの上り口は、親側のネットワークに刺さっている口だから。
  // ドメイン番号は木の順に振るので、親のほうが必ず小さい。
  var dd = (da === db) ? da : Math.min(da, db);
  l.load += BCAST_PER_DEV * (domCount[dd] || 0) * mul;
}

Math.min(da, db) で親側を選べるのは、ドメイン番号をBFS順に採番しているからである。番号の大小に意味を持たせるのは一般には危うい設計だが、ここでは「木の順に振る」という不変条件が前提として成立しており、コメントでその根拠を残してある。この手の暗黙の前提は、コメントを書かないと半年後の自分が必ず壊す。

定員と使用率

最後に、リンクとノードの使用率を出す。ケーブルには定員（LINK_CAP = 200、太いケーブルは LINK_CAP_BIG = 700）があり、ハブやスイッチには内部バスの定員がある。

var KINDS = {
  wan:     { ports: 4, bus: 900, dev: false },
  hub:     { ports: 4, bus: 240, dev: false },
  sw:      { ports: 8, bus: 900, dev: false },
  pc:      { ports: 1, bus: 0,   dev: true  },
  printer: { ports: 1, bus: 0,   dev: true  },
  cam:     { ports: 1, bus: 0,   dev: true  }
};

ハブのバスが240、スイッチが900という差が、そのままゲームの学習内容になっている。ハブは繋がっている全ポートの通信が1本のバスを共有するので、台数が増えると急に詰まる。スイッチは分割もできるしバスも太い。安いハブで繋いでいくと、ある台数を超えたところで盤面が一斉に赤くなる、という体験が数値から自然に出てくる。

使用率が1を超えたリンクはパケットロスを蓄積し、LOSS_LIMIT = 6.0 を超えるとケーブルが落ちる。落ちたケーブルは次のフレームの buildTree で辺から外れるので、木が組み替わり、負荷が別の経路へ移る。障害が伝播するという挙動を、特別なコードなしに木の再構築だけで表現できているところが、この設計のいちばん美味しい部分である。

実際に試す

上の負荷計算だけを切り出して、Node.jsでそのまま動かせる形にした。Node 18以降であれば、追加パッケージなしで動く。

node --version   # v18 以上を確認

load.js として保存する。

// load.js  —  BFS木 + ブロードキャストドメインで各リンクの使用率を出す
const LINK_CAP = 200, BCAST_PER_DEV = 1.1;

function buildTree(nodes, links) {
  const adj = {};
  nodes.forEach(n => (adj[n.id] = []));
  links.forEach(l => {
    if (l.down) return;
    adj[l.a].push({ to: l.b, link: l.id });
    adj[l.b].push({ to: l.a, link: l.id });
  });
  const root = nodes.find(n => n.kind === 'wan') || nodes[0];
  const parent = { [root.id]: -1 }, hop = { [root.id]: 0 }, plink = { [root.id]: -1 };
  const order = [root.id];
  for (let head = 0; head < order.length; head++) {
    const cur = order[head];
    adj[cur].sort((x, y) => x.to - y.to);       // 決定性のための固定
    for (const e of adj[cur]) {
      if (hop[e.to] !== undefined) continue;
      hop[e.to] = hop[cur] + 1;
      parent[e.to] = cur;
      plink[e.to] = e.link;
      order.push(e.to);
    }
  }
  return { parent, hop, plink, order };
}

function domainsOf(nodes, tree) {
  const byId = Object.fromEntries(nodes.map(n => [n.id, n]));
  const dom = { [tree.order[0]]: 0 };
  let next = 1;
  for (let k = 1; k < tree.order.length; k++) {
    const id = tree.order[k], nd = byId[id];
    dom[id] = (nd.kind === 'sw' && nd.split) ? next++ : dom[tree.parent[id]];
  }
  return dom;
}

function computeLoad(nodes, links, demand) {
  const tree = buildTree(nodes, links);
  const dom = domainsOf(nodes, tree);
  const byLink = Object.fromEntries(links.map(l => [l.id, l]));
  links.forEach(l => (l.load = 0));

  const domCount = {};
  for (const nd of nodes) {
    if (tree.hop[nd.id] === undefined) continue;         // 到達できない = オフライン
    if (nd.dev) domCount[dom[nd.id]] = (domCount[dom[nd.id]] || 0) + 1;
  }
  // 1. 末端 → 外部回線
  for (const nd of nodes) {
    if (!nd.dev || tree.hop[nd.id] === undefined) continue;
    let cur = nd.id, guard = 0;
    while (tree.parent[cur] !== undefined && tree.parent[cur] !== -1 && guard++ < 200) {
      const l = byLink[tree.plink[cur]];
      if (l) l.load += demand;
      cur = tree.parent[cur];
    }
  }
  // 2. 同報通信
  for (const l of links) {
    if (l.down || dom[l.a] === undefined || dom[l.b] === undefined) continue;
    const dd = dom[l.a] === dom[l.b] ? dom[l.a] : Math.min(dom[l.a], dom[l.b]);
    l.load += BCAST_PER_DEV * (domCount[dd] || 0);
  }
  return links.map(l => ({
    id: l.id,
    load: Math.round(l.load * 10) / 10,
    util: Math.round((l.load / LINK_CAP) * 100) + '%'
  }));
}

// 外部回線 - スイッチ - PC 6台
const nodes = [
  { id: 0, kind: 'wan', dev: false },
  { id: 1, kind: 'sw',  dev: false, split: false },
  ...Array.from({ length: 6 }, (_, i) => ({ id: 2 + i, kind: 'pc', dev: true }))
];
const links = [
  { id: 100, a: 0, b: 1 },
  ...Array.from({ length: 6 }, (_, i) => ({ id: 200 + i, a: 1, b: 2 + i }))
];

console.log('分割なし:', computeLoad(nodes, links, 25));
nodes[1].split = true;                       // スイッチでドメインを切る
console.log('分割あり:', computeLoad(nodes, links, 25));

実行すると次のようになる。

node load.js

分割なし: [
  { id: 100, load: 156.6, util: '78%' },
  { id: 200, load: 31.6, util: '16%' },
  ...
]
分割あり: [
  { id: 100, load: 150, util: '75%' },
  { id: 200, load: 31.6, util: '16%' },
  ...
]

上流リンク（id:100）の負荷が、分割によって 156.6 から 150 へ下がっている。差の 6.6 は BCAST_PER_DEV * 6台 = 6.6 で、上流リンクに乗っていた同報通信が、スイッチで切られたドメインの内側に閉じ込められたぶんである。末端側のリンクは変わらない。ドメインを分けても、そのドメイン内の同報通信は消えないからだ。

数字を変えて挙動を確かめてみてほしい。PCを20台に増やすと、外部への要求帯域より同報通信のほうが先に効いてくる境目が見える。これがゲーム側では「台数が増えたらスイッチを分ける」という手筋になっている。

まとめ

ブラウザゲームで毎フレーム回す負荷計算は、最短経路探索ではなくBFSによる全域木で作るのが自然だった。理由は性能ではなく、LANの経路がそもそもそういうものだからである。木を作ってしまえば、到達性の判定も、負荷の足し上げも、ブロードキャストドメインの採番も、その副産物として得られる。

実装で気をつける点は2つに集約される。隣接リストの順序を固定して決定性を守ることと、ドメイン番号の大小に意味を持たせるなら「木の順に振る」という前提をコメントで残すことだ。どちらも動いているうちは見えず、壊れたときに初めて分かる種類の問題である。

実際に遊んで挙動を確かめたい場合は パケットワイヤー を触ってみてほしい。ケーブルの色は本記事の util そのもので、赤くなった線が上の計算のどこで詰まっているのかが分かるようになっている。ほかのブラウザゲームも同じ方針で、遊びの裏に1つずつ実装上の主題を置いている。