CodingTrain / CodingTrain/Suggestion-Box

Coding Challenge: GJK algorithm

オープン
#999 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
言語のデータがありません
スター
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

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。