Xonixは人気のDOSゲームで、
Qixビデオゲームのクローンです。
XonixはすでにJavascriptに数回移植されています。 これまでの既存の実装のオリジナル、おそらく
これに最も近い
もの 。 最初は、実装/変更に合わせて調整しようとしました...しかし、残念なことに、難読化解除後のコードも明らかになりませんでした（少なくとも私にとって）。 さらに、私が理解できる限りでは、そこにあるコードは完全に効果的でないか、完全に古くなっている場合があります。 そのため、すべてをゼロから作成する必要がありました。
その結果、私は写真と答えが付いた「自分の」Xonixを手に入れました。
デモ |
ソースコードコードは非常に膨大であることが判明したため、ここではすべてを説明するのではなく、（私の観点から）最も重要な点のみを説明します。
ご存じのとおり、Xonixの競技場は正方形のセルのグリッドです。 ゲームの開始時（レベル）、フィールドの大部分は長方形の黒い領域（「海」）で占められており、すべての側面がライトフレーム（「土地」）で囲まれています。
私の実装と従来のXonixの主な違いは、黒い領域の背後に各レベルに固有の画像があることです。 このように、Xonixの別の修正版、Sexonixのようなものです。 しかし、私の写真には理由があります。 これは答えられるべき質問の一部です。 したがって、ゲーム全体がクイズになります。
画像の大きさによって黒い領域のサイズが決まります。これはセルのサイズの倍数でなければなりません。 一般に、ゲームのさまざまなレベルの画像はサイズが異なる場合があるため、黒い領域のサイズは、レベルの最初に常に2セルの固定幅を持つライトフレームとは対照的に、レベルごとに異なる場合があります。
すべてのオブジェクト（
カーソルと
ポイント ）の移動はセル内で厳密に行われるため、各瞬間に各オブジェクトは1つのセルを占有します。 競技場のこの構造は、ゲームの実装を大幅に簡素化します。 難易度は、カーソルが「海」を横切るときに形成される「征服された」領域の定義だけですが、それについては後で詳しく説明します。
オブジェクトの動き
「ピクセル」のセルを取ることができるという事実は、動き、バウンス、コリジョンなどの多くの動くオブジェクトを持つゲームでよく見られるほとんどの計算問題を排除します。
Xonixでは、オブジェクトには移動方向のオプションが4つしかありません。カーソルの場合-上/下/右/左、ポイントの場合（両方のタイプ）-同じこと、斜め方向のみ。 これらのオプションを多くの可能な方向に組み合わせて、度単位で設定します。 0から315度まで、45刻みで8つの移動角度を取得します。各角度値は、方向ベクトルの座標のペアに関連付けられています。 その結果、動きの計算に使用する構造が得られます。
コードスニペットdirset = { vecs: { 0: [1, 0], 45: [1, 1], 90: [0, 1], 135: [-1, 1], 180: [-1, 0], 225: [-1, -1], 270: [0, -1], 315: [1, -1] }, get: function(v) { return v in this.vecs? this.vecs[v] : [0, 0]; }, find: function(x, y) { x = x == 0? 0 : (x > 0? 1 : -1); y = y == 0? 0 : (y > 0? 1 : -1); for (var v in this.vecs) { var vec = this.vecs[v]; if (vec[0] == x && vec[1] == y) return parseInt(v); } return false; } };
getメソッドは、指定された角度（度単位）に対応するモーションベクトルを返します。
findメソッドは逆の処理を行います。特定の動きベクトル（必ずしも単位ではない）に対して、対応する角度（度単位）またはそれに最も近い利用可能な角度を返します。
ポイント同士の衝突は無視することができ、単に「通過」させるだけです。 （同じタイプの）すべてのポイントは同じように見えるため、外側からは衝突やリバウンドと違いはありません。
ポイントとカーソルの衝突、「自分の」領域の境界からのポイントの跳ね返りなどを計算するに
は、すべてのセルの
状態行列が必要です。2次元配列
(n+4) * (m+4) 、
ここで、
(n+4) 、
(m+4)はそれぞれセル内の競技場の幅と高さであり、最初のマトリックス要素は競技場の左上隅のセルに対応します。
各要素は対応するセルの状態を保存します。これには2つの兆候が含まれます。所属する領域の種類（海/土地）、およびカーソルが「海」に沿って移動した瞬間に通過するかどうかです。 この状態は、2ビットの
ビットフィールドに格納されます。 これを行うには、それぞれの属性ごとに2つのマスク定数を宣言する必要があります。
var CA_CLEAR = 1 << 0;
最適化のために、状態の配列を2次元ではなく1次元にして、すべての要素が1行目（先頭）から1行ずつ格納されるようにします。 セル座標を配列インデックスと逆変換に変換するには、次の式を使用します。
i = n * (y + 2) + x + 2; x = i % n - 2; y = Math.floor(i / n) - 2
「私たちの」エリアの境界からのポイント（「海」または「陸」）のバウンスを計算するには、ポイント自体のセルをカウントせずに、3つのセルの状態を知る必要があります。 以下の擬似グラフィックを使用すると、これらのセルの位置が、45度の移動角度でのポイントの現在のセルに対して相対的に表示されます。
OOO
OX1
O23
ポイントセルは十字でマークされ、1、2、3の数字が付いた目的のセルは単純に隣接セルを示します。 この場合のポイントの方向は南東に取得されます。これは、グリッドの縦座標軸（Y）が下を向いているためです。
示された3つのセルの少なくとも1つで、領域タイプがポイントタイプと反対の場合、境界からのリバウンドが発生します。 つまり たとえば、ポイントが「海」の場合、これらのセルの1つは「陸」でなければなりません。 さらに、この条件がセル1または2のいずれか（両方ではない）で満たされる場合、
+90または
-90度がそれぞれ移動角度に追加されます。 それ以外の場合、移動角度は逆になります（
+180度）。
他の動きの角度の場合、反発のロジックは明らかにまったく同じになります。
ポイントとカーソルの衝突によりゲームが一時停止し、その後、カーソルと「ランド」ポイントがゲームを開始するために元の位置に戻ります。カーソルは2番目の行の中央のセルに移動します。 。 「海」ポイントの位置は変わりません。
「ランド」ポイントとカーソルの衝突を判断するのは簡単です。 ポイントとカーソルのセルの座標を比較して、ポイントとカーソルの接触を確認するだけです。 「海」のポイントとカーソルの衝突の判定はもう少し複雑です。ポイント自体とカーソルの接触だけでなく、カーソルのトレースのタッチもチェックする必要があります。 これを行うには、セルの状態の2番目のビットを使用します。ポイントに隣接するすべてのセルをチェックします。
「征服された」領域の識別
すでに述べたように、実装が最も難しいのは、「海」から「征服された」領域の定義です。 これらは、カーソルが「海」を横切る結果として形成される閉じた領域であり、その内部には「海」の点はありません。 ほとんどの場合、これにより、利用可能な「海洋」領域を2つの部分に分割（カーソルの後に）して得られる2つの閉じた領域が作成され、そのうち1つだけが「征服」されます（スクリーンショット1を参照）。 しかし、いくつかの、特に複雑なケースでは、「征服された」エリアを含む多くの閉じたものがすぐに形成されます（スクリーンショット2を参照）。 さらに、カーソルトレース自体が閉じた領域を形成している場合もあります（スクリーンショット3を参照）。
スクリーンショット1スクリーンショット2スクリーンショット3そのため、このような閉じた領域をすべて見つけて、それぞれのタイプ（「征服済み」/「非征服済み」）を判別する必要があります。
閉じた領域を見つけるには、近隣のセルを比較するための一般的なアルゴリズムを使用して、すべてのセルを反復処理できます。 たとえば、
ここでの実装方法。
しかし、別の方法があります（最終的に私はそれを選択しました）：カーソルが「海」を横切るときに形成される閉じた領域の輪郭を使用します。
輪郭とは、1つのセルの厚さを持つ閉じたポリラインを意味します。 閉じた領域の輪郭がわかっている場合、その内容を見つけるためだけに残ります。 その中のすべてのセル。 しかし、これらの輪郭を見つける方法は？
閉じた領域の輪郭
一般的なケースでは、カーソルのトレースと部分的に交差する、つまり各回路についてのみ知っています。 少なくとも1つのカーソルトレースセルが含まれます。 ほとんどの場合、スクリーンショット1に示すように、正確に2つの輪郭が形成され、それぞれにカーソルトレース全体（すべてのセル）が含まれます。 ただし、スクリーンショット2のように、このような輪郭が多数存在する場合があり、それらの多くにはカーソルトレースセルの一部しか含まれない場合があります。 さらに、カーソルトレース全体が閉じたループを形成する場合（スクリーンショット3）を考慮する必要があります。 したがって、カーソルトレースデータに基づいて、できるだけ少ないセルをチェックしながら、それに隣接する閉じた領域の輪郭に関するすべての情報を取得する必要があります。
等高線の分布のさまざまなオプションを考慮すると、いくつかのパターンを見つけることができます。 第一に、カーソルトレース全体を含むパスの数は常に2以下です。第二に、カーソルトレースの両側ですべてのパスを2つのグループに分割すると、1つのグループのパスに共通のトレースセルがなくなります。 つまり、カーソルトレースの各セルは、トレースの各側の1つの輪郭にのみ属します。
上記に基づいて、輪郭を見つけるためのアルゴリズムを導き出すことができます。 一般的に、彼はこのように見えます。
カーソルのトレースに属するすべてのセルを、最初から（つまり、動きの開始から）ループします。 各トレースセルについて、2つの隣接するセル（移動方向で左右）の両側を確認します。 セルが「海洋」の場合、これは目的のエリアの1つの輪郭の一部です。 それ以外の場合は、トラックのこちら側に「海洋」セルが見つかるまで検索を続けます。 見つかったセルから、それに隣接する輪郭全体を描くことができます。 これを行うには、まずこのセルからトレースセルの方向に移動し、次に現在のセルの少なくとも片側に常に「ランド」セルが存在する方向に移動する必要があります（この場合、現在のセルは「海洋」でなければなりません）。 トレースセルが見つかるまで、つまり、回路が閉じられるまで続きます。 渡されたセルにポリラインを閉じるのに必要なトレースセルの一部を追加すると、目的の輪郭が得られます。
その後、トレースのセルを検索する外部サイクルを続け、1つのセルから輪郭を見つけるための上記の手順が停止したサイクルから開始します。
トラックの両側で輪郭を見つける手順は、互いに独立して実行する必要があることに注意してください。 これは、トレースのセルを検索するサイクルを、各側で1回ずつ、2回の繰り返しの別のサイクルでラップする必要があることを意味します。
両側に輪郭が見つからない場合があります。 これは、モーショントラックが「海洋」領域の境界に隣接していることを意味します。 この場合、トレース自体のみで構成される単一の閉じた領域があります。
スクリーンショット3から状況がある場合は、見つかったすべてのアウトラインに、カーソル移動のトレース全体によって形成されたアウトラインを追加する必要があります。
閉鎖エリアのコンテンツとタイプ
閉じた領域の輪郭が見つかったので、各回路の対応する領域（それに含まれるすべてのセル）の内容とそのタイプ（「征服された」または「されていない」）を決定する必要があります。 Xonixではカーソルは垂直/水平方向にしか移動できないため、各閉じた領域はサイズの異なる複数の長方形に分割できます。 したがって、閉じた領域の内容を決定するタスクは、その構成長方形を見つけることに削減されます。 ちなみに、これを行うことにより、2つの「鳥を1つの石で」殺すことができます。閉じた領域内のポイントの計算、および「征服された」領域の陰影（またはむしろ消去）を容易にします。
長方形を見つけるには、領域の輪郭の頂点を知るだけで十分です。 多角形の頂点。
主なアイデアは、各反復で最大の幅または高さを持つ突出した長方形を切り取ることです。 ここで言うと、3つの頂点が元のポリゴンに属する長方形を意味します。 これに基づいて、閉領域を長方形に分割するアルゴリズムを導出できます。 次のようになります。
最初の反復で、突出している長方形の一部である、最も長い長さの多角形の辺（セグメント）を見つけます。 そのようなセグメントが複数ある場合は、それらのいずれかを選択します。 見つかったセグメントは、目的の長方形の辺の1つになります。 次に、残りの部分を見つける必要があります。 これを行うには、見つかった側の両端から垂直にセグメントを取得し、最短のセグメントを選択します。 これは、長方形の2番目の辺になります。 3番目の側面を見つけるには、最初の側面に垂直な2番目のセグメントで、指定されたセグメントの2番目の端の（直交）投影を見つける必要があります。 見つかったポイントを最初の辺の対応する端に接続し、3番目の辺を取得します。 ここから、目的の突出した長方形全体を取得します。 次に、元のポリゴンから切り取る必要があります。 これを行うには、最初に見つかったセグメントと2番目に見つかったセグメント、および対応する頂点をポリゴンから削除し、見つかった投影ポイントを追加して、2番目に見つかったセグメントに接続されていた頂点に接続します。 その結果、元の頂点よりも2つの頂点が少ないポリゴンが得られます。
次の反復では、最初の反復と同じ方法で切り捨てられたポリゴンを処理します...など、クリッピングの結果として4つの頂点のポリゴンが得られるまで、つまり 長方形。
検討中のプロセスで切り取られるすべての長方形は、閉じた領域の内容になります。
特定の例で長方形に分割するプロセスを検討してください。
領域の輪郭であるポリゴン
ABCDEFGHIJKL （図1を参照）があるとします。 ステップごとに説明した分割アルゴリズムを適用します。
1.ポリゴン
ABCDEFGHIJKLの最も長い長さの辺を見つけます。 これは4の長さを持つ
CDセグメントです。 突出した長方形の一部ではありません。 したがって、それを無視してさらに調べます。 長さ3の3つのセグメントが見つかりました：
AL 、
FG 、
GH 。
GHは
CDと同じ理由で私たちに適していない。 そのため、セグメント
AL 、
FGます。 それらのいずれかを選択します。
ALましょう。 それに垂直なセグメントは
ABと
KLで、そのうち最短は
ABです。 点
Bのセグメント
KLへの射影を見つけます-これは点
M （図2を参照）。 したがって、カットオフ長方形
ABMLます。 クリッピング後、ポリゴン
CDEFGHIJKMは残ります。
2.最長の長さを持つポリゴン
CDEFGHIJKM辺を見つけます。 これは、長さ3のセグメント
FGです...切り取られた長方形は
FGNE （図2を参照）。 クリッピング後、ポリゴン
CDNHIJKMは残ります。
3.ポリゴン
CDNHIJKMの最も長い辺を見つけます。 これは、すでにおなじみの長さ4の
CDセグメントです...切り取られた長方形は
CDNOです。 クリッピング後、
OHIJKMポリゴン
OHIJKMます。
4.最も長い長さのポリゴン
OHIJKM辺を見つけます。 そのような当事者は2つあります。 これらは、長さ2のセグメント
OHおよび
HIです。最初のセグメントを選択します
OH ...カットオフ長方形は
OHPMです。 クリッピング後、
KPIJ長方形
KPIJます。 今、切断するものは何もありません。 これでアルゴリズムが完成しました。
その結果、閉じた領域のコンテンツを構成する5つの長方形、
ABML 、
FGNE 、
CDNO 、
OHPMおよび
KPIJ （図2を参照）。
図 1図 2閉じた領域が見つかったら、それらのそれぞれのタイプを判別する必要があります（「征服されている」かどうか）。 エリアのタイプは、その中の「航海」ポイントをカウントすることによって決定されます。 領域内のすべてのポイントを数える必要はありません。少なくとも1つのポイントがあるかどうかを調べるだけで十分です。 存在する場合、この領域は「征服」されません（したがって、私たちはそれを消去しません）。「征服された」領域に単一の点があってはならないからです。
一般に、任意の形状のポリゴンに特定の位置（座標）を持つポイントが含まれているかどうかを判断することは非常に困難です。 ただし、このために、このタスクを容易にするために、ポリゴンを長方形に分割します。 任意のポリゴンとは異なり、ポイントが長方形に属するかどうかを判断するのは簡単な作業です。 与えられたポイントの各座標が長方形の境界の対応する範囲に属しているかどうかを確認する必要があるだけです。
したがって、閉じた領域のタイプを決定するタスクは、この領域を構成する各長方形の内側の「海」点を検索することになります。
見つかったすべての「征服された」領域は消去の対象となります。消去はさらに簡単に実装されます。この領域を構成するすべての長方形を消去するだけです（
clearRectメソッドを使用）。
アニメーション、ゲームコントロールなど
タイトルは少し不正です）。 記事はすでに終わりましたので、残念ながら上記のどれもここにはありません。
この記事 （
translation ）に基づいて書いたアニメーションコードと、
この （
translation ）にのみ気付くことができます。
興味のある方のために、以下はゲームのコード全体です。 ただし、その値は疑わしいです。 そこにコメント-猫は泣いた。 しかし、私はうまくいけば基本的なロジックを説明しました。
シムの締めくくり。 ご清聴ありがとうございました。