CodingTrain / CodingTrain/Suggestion-Box
Coding Challenge: GJK algorithm
- 主要言語
- 言語のデータがありません
- スター
- 570
- フォーク
- 85
- PR マージ指標
- 30日以内にマージされた PR はありません
説明
The [Gilbert-Johnson-Keerthi algorithm](https://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm) (known as GJK) is apparently a highly efficient and commonly used method for determining if 2 arbitrary **convex** polygons intersect. From my recent research into it, it seems that a number of papers and articles written about it make it seem more difficult than it is by obfuscating the algorithm with a lot of complicated math. A [video explaining the algorithm](https://caseymuratori.com/blog_0003) was recommended in the book _Game Engine Architecture_ (Jason Gregory), and this video is also linked to on the wikipedia article discussing the algorithm.
I'm proposing that you implement this algorithm as a coding challenge for a few reasons:
1. It's a somewhat 'difficult' algorithm, but not ridiculously so, making it a challenge that's within reach for the majority of your audience. It's also surprisingly ingenious.
2. The functionality would be very useful. I suspect a lot of the folks watching Coding Train are at least somewhat interested in making games and so could benefit from learning about algorithm for doing "collision detection" besides circle-circle and AABB-AABB. No doubt the GJK is also useful for non-gaming sketches. I'm personally interested in using it for a shape-packing sketch, for example.
3. ???
4. Fun!
For simplicity and to make it more useful as a teaching aid, implementing only the 2D case would be enough. Then you don't have to go through the trouble of dealing with all the extra checks required for a tetrahedron.
コントリビューションガイド
このリポジトリのコントリビューションガイドは索引されていません
調査の方向性
実装ファイル、エントリーポイント、テストは指定されていません。まずリンク先のWikipedia記事とCasey Muratoriの動画を読み、その後2D GJKのコーディングチャレンジの範囲を定義してください。チャレンジが凸多角形の交差判定を実装すれば完了です。
索引モデルが issue の本文から書いたものです。
評価
- 領域
- game-dev
- issue の種類
- 機能追加
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 活発さ
- 停滞
- 明瞭さ
- おおむね明確
- 初心者へのやさしさ
- 25/100