概要

格子点を結んでできる凸多角形のうち、内部にぴったり1つの格子点を含むものを標準多角形と呼びます。今回開発したブラウザゲーム Solo-Cat では、標準多角形が包含関係の列で全てつなげられるという数学的事実を、ブラウザ上で直感的に体験できます。実際のプレイ映像は、以下のような感じです。少しゲーム性を加えたものをこちらに公開していますので、試しに遊んで頂けると幸いです。

この作品の背景には、極小モデル理論という数学があり、3次元以上でも同様のことが出来るかどうかは未解決の問題です。理論的背景については別のところで紹介しているので、以下では、開発における苦労話を紹介します。

開発について

いきさつ

この開発は、2022年度の京都大学 MACS 教育プログラムにおける研究活動の一環として行ったものです。スタディーグループのテーマである「XRで見る・3Dで触る先端科学」に合わせ、当初の目標は 3次元以上の標準多面体を扱うことでした。しかし、現時点までに実装できたのは2次元までです。そこで、これも広い意味での XR なのだと言い張ることにしました (笑)。実際には、2次元でも作ってみたら新感覚のパズルゲームのようで、意外に面白いものになった気がします。

開発環境

ブラウザで誰でも簡単にアクセスできるように、JavaScript を使用して開発しています。最初はプレーンな Javascript でコーディングしていましたが、プロジェクトの規模が大きくなりモジュールの利用が必要になったため、Node.js と webpack を導入しました。また、結局コンパイルはすることになったので、より堅牢な言語である TypeScript に移行しました。機能を追加していく過程で EventEmitter を使い始めたら、イベント駆動型プログラミングの考え方から抜け出せなくなった気がします。以下は、package.json の一部です。

  "devDependencies": {
    "@types/events": "^3.0.0",
    "@types/jest": "^29.5.0",
    "@typescript-eslint/eslint-plugin": "^5.57.0",
    "@typescript-eslint/parser": "^5.57.0",
    "eslint": "^8.37.0",
    "file-loader": "^6.2.0",
    "jest": "^29.5.0",
    "ts-jest": "^29.0.5",
    "ts-loader": "^9.4.2",
    "typescript": "^5.0.2",
    "webpack": "^5.76.2",
    "webpack-cli": "^5.0.1",
    "webpack-dev-server": "^4.13.1"
  }

多角形の計算について

可視化の準備段階として、点集合の凸包の計算や頂点の探索、含まれる格子点の列挙など、基本的な多面体の操作を実装する必要がありました。整凸多面体を扱うソフトウェアとしてはSageMathに含まれる PALP の他、PORTA なども非常に便利なのですが、フロントエンドへの統合が仰々しく感じられたため、自前で実装を行いました。

点集合の凸包を求めるアルゴリズムは色々あって奥が深いようです。今回は直感的で分かりやすいギフト包装法 (Gift wrapping algorithm) を採用しました。以下はPolygonクラスの頂点を探索するメソッドであるcalcVertices()の該当部分です。Vectorクラスやそれを継承するPointクラスについては立ち入りませんが、x (x成分), y (y成分), sub (ひき算), squareLength (2乗和) などは、読んで字のごとくです。

  calcVertices(): Point[] { 
    const points = this._points;

    // set the lowest and left-most vertex as firstPoint (the base point)
    let firstPoint = points[0]; 
    points.forEach(
      point => {
        if (firstPoint.y > point.y || (firstPoint.y === point.y && firstPoint.x > point.x)){ 
          firstPoint = point; 
        }
      }
    );
    
    // compute the left-most vertex viewed from the base point (as nextPoint)
    function next(points: Point[], basePoint: Point) {
      let nextPoint = points[0];
      for (const point of points) {
        if (basePoint === nextPoint) {
          nextPoint = point;
        } else {
          const delta1 = Vector.sub(basePoint, nextPoint);
          const delta2 = Vector.sub(basePoint, point);
          const crossProduct =  delta1.x * delta2.y - delta2.x * delta1.y;
          const squareLength1 = delta1.squareLength();
          const squareLength2 = delta2.squareLength();
          if (crossProduct > 0 || (crossProduct === 0 && squareLength2 > squareLength1)) {
            nextPoint = point;
          }
        }
      }
      return nextPoint;
    };

    // list up all vertices by switching the base point
    const resultVertices: Point[] = [];
    let vertex = firstPoint;
    do {
      resultVertices.push(vertex);
      vertex = next(points, vertex);
    } while(firstPoint != vertex);
    return resultVertices;
  }

2次元であるため、上記のように凸包と頂点を計算しておけば、隣接する頂点を比較し、多角形を定義する不等式系を求めることができます。これは、PALP のpoly.xや PORTA のtrafに相当する重要な操作なのですが、ずいぶん簡単に実現できました。一方、含まれる格子点の列挙は、多角形を内包する最小の 2次元閉区間の格子点をすべて調べるというブルートフォースな実装をしています。高次元版でリアルタイム処理を実現しようとすると、もっと効率的なアルゴリズムを検討しないと厳しい気がします。

描画について

ブラウザ上の描画には、Canvas を使用しています。今回の実装では、Boardクラスのインスタンス (盤面) を用意しておいて、盤面上の固定された座標を指定することで多角形Polygonや点Pointを配置しています。一方で、Canvas全体に盤面の一部を表示し、ユーザーの入力に基づいて拡大・縮小、平行移動、ユニモジュラ変換などの処理をインタラクティブに反映させます。これらの「見かけの変換」の処理は盤面自体ではなく、表示部分を変化させるという方法で対応しています。ユニモジュラ変換はこのプロジェクトに特有の変換であるため既存のパッケージは利用しづらいのですが、幸いにもそれほど複雑な仕組みではなかったので自前で実装できました。盤面の座標 (ワールド座標) と Canvas の座標 (ビュー座標) の変換は、以下のRendererクラスのメソッドにコードしています。

viewCoord(point: Point){
  const point2 = point.clone();
  this.boardData.offsetMatrix.operate(point2).add(this.boardData.offsetVector);
  return [ this.canvasData.width/2 + point2.x * this.boardData.scaleUnit,
     this.canvasData.height/2 - point2.y * this.boardData.scaleUnit];
}

ここで、boardDataにはユーザーの入力によって変化するオフセットの情報offsetMatrix, offsetVectorや、ビュー座標で見た単位目盛りの大きさscaleUnitを、canvasDataには Canvas のサイズwidth, heightをそれぞれ保持しています。オフセットが無ければ、Canvas の中心が原点になるように変換を定義したということですね。ビュー座標の y 軸が下向きであることにも注意です。

盤面のどの格子点を描画すべきか、ということを決定する次のメソッドは、多角形に含まれる格子点を列挙するPolygonクラスのメソッドvalidPoints()が応用できて、以下のように簡潔にまとまります。初めの頃はPolygonクラスのメソッドを応用するという発想がなくて、目盛りの数scaleNumX, scaleNumYが自然数になるように調整したり、そのしわ寄せで原点がCanvasの中心からずれてしまったり、というようなことに頭を悩ませました。

visiblePoints(): Point[] {
  const scaleNumX = this.canvasData.width/this.boardData.scaleUnit;
  const scaleNumY = this.canvasData.height/this.boardData.scaleUnit;
  const limitLB = new Point(-scaleNumX/2, -scaleNumY/2); // left-bottom
  const limitRB = new Point(scaleNumX/2, -scaleNumY/2); // right-bottom
  const limitRT = limitLB.clone().multiply(-1); // right-top
  const limitLT = limitRB.clone().multiply(-1); // left-top
  const inverseMatrix = this.boardData.offsetMatrix.inverse();
  const offsetVector = this.boardData.offsetVector;
  inverseMatrix.operate(limitLB.sub(offsetVector));
  inverseMatrix.operate(limitRB.sub(offsetVector));
  inverseMatrix.operate(limitRT.sub(offsetVector));
  inverseMatrix.operate(limitLT.sub(offsetVector));
  const visibleSquare =  new Polygon([limitLB, limitRB, limitRT, limitLT]);
  const visiblePoints = visibleSquare.validPoints();
  return visiblePoints;
}

今後の目標

今回の作品ではタブレットでの操作が最も自然に感じられたので、今後は Android/iOS アプリへの対応も検討しています。また、2023年度のスタディグループでは、やはり理論的に興味深い 3次元以上の標準多面体を扱えるように、WebGL や Three.js を活用して今回のプロジェクトを拡張したいと考えています。高次元では多面体のアルゴリズムから見直す必要がありますが、PALP か PORTA を組み込むのが早そうですね。いずれにせよ、少しずつ成果を届けられるように、関連した開発を続けていきたいと思います。