Petitverse

hanzoさんのグルグル式で走査する補正座標をDATA文で作って置けばいいんじゃないんです？
別スロットに参照するDATA文を計算式を使って生成するようにすればプログラム自体も長くはならないでしょうし

私のサンプルプログラムでは、グルグル走査の補正座標をあらかじめ配列変数に格納しておいて、それを順次参照しながら走査しています。
ときに、プチコン3号の特性として、シーケンシャルなデータ参照は、配列変数よりも、DATA文をREADする方が速いと言う事実があります。つまり、ツララさん推奨方式により、更なる処理の高速化が期待できます。

と言うわけで、実際にやってみました。もし差し支えなければ「YKXKYJHS」をダウンロードしてお試しいただけますでしょうか？（なお、恐縮ながら、前回のサンプルプログラムは既にサーバーから削除しました。）
当方の環境で見る限り、本プログラムは、前回のものよりも速度が1.3倍ほど向上しているようです。

グルグル探査の座標の数値なんですけど
円を描画するのって８分割した扇状の座標の探査優先順さえ分かれば
あとは中心座標に対しての線対称や点対称の座標変換で最も近い４点（X軸かY軸が同じか、２つの軸のベクトルが同値の場合）、もしくは８点が探査できるんですよね。
なのでhanzoさんのDATA文の数値って
探査する矩形範囲の一辺の長さをLとして

DIM PX[0],PY[0],REACH[0]
FOR X=1 TO L
　FOR Y=0 TO X
　　PUSH PX,X:PUSH PY,Y:PUSH REACH,X*X+Y*Y
　NEXT
NEXT
SORT REACH.PX,PY

みたいな、距離でソートする処理で元にする扇形の座標の数値の並びを割り出してたりします？

自分も今作ってる探索系プログラムで視界の処理をするのに
近い順の遮蔽物の座標を求めるのに四苦八苦してたので
グルグル式がすごいヒントになりました、アリシャス！
矩形で直線的に探査してると、どうしても無駄な部分の処理で時間が掛かって
どうしたものか絶賛お悩み中だったのがスッキリしました。

もう解決してると思うけど、だいたい「ドロネー図」のアルゴリズムなのでご紹介。

「ドロネー図」は、たくさんある点のうち点と隣の点を結んでたくさん三角形を作っていく図です。
３つの点から外接円をもとめて、外接円の中に点があればさらに外接円を求めて、という感じで３点を決めていきます。
結果的に点から別の点へはいくつか線ができるけど、どれも短い線になるようになっています。

ドロネー図を書くアルゴリズム
http://blog.webcreativepark.net/2015/10/22-060729.html
https://qiita.com/edo_m18/items/7b3c70ed97bac52b2203
※もっと詳細は「ドロネー図」で検索で (「ボロノイ図」もでてくるけど今回はあまり関係無い)


今回の白点と緑点の場合、白点でドロネー図を作って、緑点からどの三角形に所属しているかを計算し、その三角形の頂点との距離をもとめることで、緑点に一番近い白点が求まります。

ドロネー図をBASICの変数で持つのにはちょっといろいろ面倒なので、みなさんが作ったアルゴリズムで問題なければそれはそれで動いているので特に気にしなくても良いと思います。

※ちゃんとドロネー図を変数で持つなら、頂点の配列(XとY)、辺の配列(始点と終点の配列番号)、三角形の配列(頂点3つか辺3つの配列番号)あたりが必要です

ちょっと面白いこと思い付いたんですけど
ビットを使うってのはどうでしょう。
白い点を表すビットと緑の点があるかないかを表すビットを用意して、
白いやつを上下左右にシフトして白いやつにORします。
そして緑のやつとANDしてTRUEならある。
欠点は距離の種類がユークリッド距離？じゃないこと。

白い点を
00000
00000
00100
00000
00000
緑の点を

01001
00000
10000
00010
00000
とすると
白いやつをシフトしてORすると
00000
00100
01110
00100
00000
で、緑とORすると0(false)
また白をシフトしてORすると
00100
01110
11111
01110
00100
そしてまた緑とANDする…みたいに繰り返せば近い点は見つかりそう。

白点と緑点の距離だけを調べるなら、表示される画面は400x240の配列と同じ扱いなので、画面全部見るよりは緑点の配列（1000個くらい）を見るだけのほうが早くなります。

「ライフゲーム」みたいに400x240の中の点のすべてがお互いに影響するなら画面全部見ないと成り立ちません。

今回は緑点の座標と白点の座標の距離だけなので、点の数だけ配列があれば目的がなりたちます。(他にアルゴリズム用の距離などを覚える配列な必要)

ただ、将来的に点だけじゃなくて400x240の範囲でなにかしようとするなら画面全部みたほうがいいです。


なお、点の集合(今回は緑点全部と白点全部)を、点と点でつないだ辺の集合(近い点どうしなど)をあわせて「グラフ理論」で「グラフ」といいます。
（表に線を書く「グラフ」とはまた別のものです）

「ダイクストラ法」は経路を探索するアルゴリズムですが、「グラフ」から経路を検索します。

アクションゲームなどでの敵が迫ってくるアルゴリズムも、マップチップが点で、上下左右を辺でつなげばグラフになるので、通れる点通れない点のグラフから経路を検索して敵が迫ってくるなど応用出来ます。

> データ構造がプチコンじゃ再現が難しいなんて言わないで
再現こんな感じ？みたいなことを書いてて、自分でもやっぱり再現難しいって思ってるのに言っちゃダメって矛盾してる予感！

>そこはベテランの工夫の見せ所なんじゃないかと思いますけど。
1つ下の段落にどんな配列必要かすでに書いてあるよ！

と、ツッコミ的にレスをいれたところで、消極的意見に対して発言者に意見を言うのは全くもって何も意味が無くて、消極的意見の改善方法を話し合わないと議論として意味が無いのです。

で、今回は構造持つのが大変ってのにちゃんと改善方法を書いているようなので反応しておきます。


プチコンだと複数の変数を１つの型として扱える構造体が無いので、それをどう持つかは各自の作り次第です。

今回書いてあるように固定文字列長で積んでいく方法もアリですし、配列にPUSH/POPするのもアリですし、SLOT2 に書いたりとか、GRP3に座標をRGB値変換してGPSETしておいたりとか、やりかたは人それぞれです。
こういった処理を実装する場合、まずは処理速度が速いか遅いかは別にして、まずは動くところまで持って行くのが大事です。


今回の場合の三角形の情報に何が必要かとか、その情報から何を検索する必要があるかとかはお題によって変わってくるので、データ構造をどのようにアクセスするかは作るモノによって変わってきます。

三角形をループして三点が一致するか調べたり、三角形を一覧から削除したり追加したりするので、まずはそういったアクセスをする処理に何が必要でそれが正しく動かすことが大事です

固定文字列で持つやりかたなら、5個の三角形を持ったときに3つ目が削除された場合にどのような文字列になっているかとか、そこからさらに追加したり検索したりしてちゃんと動くかとかを気にして作らないとダメです
これは配列で持つ方法だったり他の方法でも同じく気にしないとダメです

データ構造を使う側（三角形を検索とか削除するメインの処理側）は、固定文字列や配列の中身は気にせずに、検索だったら検索、削除だったら削除がちゃんと動くということが重要です

固定文字列長のやりかたでも実現は可能で、今回のお題はやる気があるみたいなので(他のスレッドでも外心円を求める式を話題に出してたので)ぜひとも完成させてみてください

[43K8N5G1]
いちおう動いているので置いておきます
BIGで作っているけどNew3DSの3号でも動いてます

どんな処理をしているかは大量に書いているコメントを見てもらうとして、他に説明があったほうがよさそうなことを書いておきます。


最初のほうに点の数とか色とか定義しているので適当に変えても動きます

外接円を表示するデバッグフラグを立てて外接円も表示して見てるだけでも楽しめます

点を動くようにして毎フレームごとにドロネー図を生成しなおしてます

ドロネー図のアルゴリズムとサイトの説明をあわせて解釈し直しているのでちょっと実現方法が違ってます。(ハッシュで分割三角形持ってあとで追加するあたり)

外接円情報は三角形情報と結びつけていて、三角形を配列に追加するときに計算しています

配列が使用済みかどうかは代入しているindex値がマイナスかどうかで見ていますが、一部値と流用しています。(変数定義のコメントに書いています)

描画系は全部ドロネー図用の配列を参照して書いています

ドロネー図生成処理はドロネー図用の配列を更新するだけです

三角形の一覧から線だけを生成するような処理を入れています

画面外の巨大三角形は別に正三角形ではなくても、画面が外接円と三角形の中に収まっていれば良いので画面サイズを元に生成しています。


そもそも三角形重複を削除していくアルゴリズムだと厳密な凸型のドロネー図にはならないパターンが存在しているけど、今回の目的だとあんまり気にしなくて良いかもしれません。
※ドロネー図の定義が、3点の外接円内に他の点が無いことと、外周の線がすべて凸なこと（凹んでない）なので厳密にはドロネー図ではなくなっている

ちょっとビット熱が再燃しかけてる気がするのでビットのやり方について考えてみる。
ビットの利点は探索時間が最短距離に比例すること。つまり遠い点も比較的高速なこと。あと白い点が複数個ある場合でも同時に探索できる。多分。
欠点は出てくる距離がユークリッド距離ではなく、市街地距離であること。
あとプチコンだと実装する上で符号ビットと算術シフトが厄介。前回のコメントが雑な感じなのはそのせい。
実は距離が市街地距離のことの解決策は前回思い付いていて、市街地距離が同じ場合、ユークリッド距離が一番長い点は一番短い点のSQR(2)倍(≒1.5倍)の距離なので、
最初に見つかってから1.5倍探索を続けてその中からユークリッド距離が最小の点を探せばよかったり。その分遅くなるのが嫌で言えなかった。それをやるぐらいなら愚直にやる(全部の点の距離を調べる)方が速そうだし。

まぁともかく気力が回復してきたのでビットのやり方実装してきます。

ちょっと最近似たようなことで悩んでるので来ました。
さすがに愚直にやるのは遅すぎるので調べたら四分木なるものがあるらしいですね。(詳しくは知らない)
あと今回のように2つのグループに分かれてる場合、AABB木なるものがあるらしいですが、物体が移動するのには向いてないとか

四分木+セグ木…