ULL Top
Thothgo

RRT

RRT(Rapidly exploring random tree)をJavaScriptで可視化しました.
Urusu Lambda

RRT Control GUI

You can move obstacles and add too.

Blue Point : Randomly sampled point
Orange Point : Tree Nodes
Red Point : Goal
Green Point : Start

FPS:

How?(English)

It is very easy.
  1. Sample One Random Point in Space. (Blue Point Above)
  2. Find nearest node from already created nodes
  3. Get diff vector between above two point and clip to max length
  4. If it intersect with obstacle, start from first. If not, go next
  5. Add new node which is within max length from nearest node to tree (Orange Point Above)
  6. If the new node is enough near to goal? end. If not, start from first

How?(日本語)

非常に簡単に実現できます.
詳しくはここ
  1. 空間上に一つランダムに点を打ちます. (青い点)
  2. すでに作られたツリーから1.で作った点に最も近いものを選びます.
  3. 予め決めた長さでクリップするようにします.
  4. クリップした長さで障害物に打つかれば、1.からそうでなければ次に進みます.
  5. 新しい点をツリーに追加します. (黄色い点)
  6. 十分ゴールに近ければ, 終了. そうでなければ1.から戻す.