経路探索（A*：A-star）アルゴリズムについて

直接CNCには関係ないかもしれませんが、プログラミングではよくテーマになる経路探索について最近調べていました。いくつか探索アルゴリズムがあるようですが、代表的なA*（A-star）アルゴリズムを実際に書いて試してみました。

Gコードを見ると上から順番に加工用の座標が並んでいます。図面上にある複数の座標点をどのような順番で処理していくのかというのが気になっていました。たまに加工中の動作を見ていると、近いところから加工しているように見えますが、突然遠回りしていたりするので、何かしらの判断基準があって、それがどの程度効率よく動いているのかが気になります。
もしGrblのようなソフトをプログラミングするには、こういった加工の順番を処理するプログラムも必要なのかもしれません。例えば、3箇所にドリルの穴を開ける場合、加工開始点から一番近い位置、そして二番目、三番目と移動すれば最短距離になると思いますが、その順番が違えば、無駄な移動が含まれるために加工時間も変わってくるはずです。
もしベクターデータやdxfデータの段階で、その順番がもうすでに決まっていて、Grblはその順番に従って動いているのであれば、Gコード生成プログラムの方にその原因があるのかもしれません。ソフトの中身まで検証していないので、そこまではまだわからないのですが、Gコードのみならず、他の場面においても、探索アルゴリズムは何かの順序を決定する際のプログラムとして汎用性があると思います。

以下が今回プログラムしたアルゴリズムです。このブログ上でも実行可能になっています。
一般的に定義されているA*アルゴリズムになっているかはわかりませんが、自分なりにある程度考えて書いて見ました。

＊表示画面内を空クリックしてから（フォーカスを与えてから）、キーを押して下さい。

・緑：スタート（ドラッグで移動可能）
・赤：ゴール（ドラッグで移動可能）
・グレー：壁（クリックで壁の有無を切り替える）
・黒：通路（クリックで壁の有無を切り替える）
・↑（UP）キー：グリッドを増やす（最大160x160グリッド）
・↓（DOWN）キー：グリッドを減らす（最小10x10グリッド）
・Nキー：リセット
・その他のキーで探索開始/一時停止
追記：
画面下部に[START/PAUSE][RESET][MORE GRIDS][LESS GRIDS]ボタンを追加しておきました。

＊緑丸は現在の探索位置、薄緑は探索済みエリアです。
＊初期状態で緑（スタート）か赤（ゴール）がグレーの壁に囲まれて入れば、すでに手詰まりです。移動可能な方向は上下左右だけです（斜め移動は禁止）。初期状態で手詰まりの場合は、クリックで壁を消すか、ドラッグで緑か赤の位置を変更するか、Nキーでリセットしてください。
＊ProcessingのコードをProcessing.jsを使って表示しているので、バグがあるかもしれません。


このアルゴリズムについての説明はこちらのページにあります。