HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2009
0508
cd矩形と線分の接触判定4解決


cd

リンク

2009/5/8(Fri) 00:00:45|NO.25037

矩形と線分の接触判定が必要です。

調べた結果、
http://hspdev-wiki.net/?%BE%D7%C6%CD%C8%BD%C4%EA#md52a044
に辿り着きましたが、HSP2用でありアルゴリズムの説明もよく分かりません。
(HSP3から始めたためHSP2がよく分かりません)

矩形は左上X,Y座標と右下X,Y座標、線分はA点とB点のX,Y座標を使用します。
(矩形に線分が)接触しているかどうかのみで、実際に交点座標(?)を求める必要はありません。
DLLは使わずに、できるだけ高速な物が必要です。

どなたか、矩形と線分の接触判定を行うモジュールをご存知ではないですか?



この記事に返信する


inovia

リンク

2009/5/8(Fri) 00:54:47|NO.25040

開発Wikiのサンプルを3.xに対応させてみました。
http://homepage2.nifty.com/MJHS/dotou_hsp/module/st_sample01.hsp



cd

リンク

2009/5/8(Fri) 22:38:41|NO.25043

ありがとうございます。
機能としては十分なのですが、ちょっと動作速度に問題があります。

広いエリアにリアルタイムに線を大量に引く必要があり、ウインドウ外の描画を省略するため、
ウインドウ(矩形)に触れる線かどうか判定しようと思ったのですが。
(ウインドウに表示される線なら描画、ウインドウ外の見えない線なら(高速化のため)描画省略。)

つまり、単純にHSPのline命令よりも高速に判定する必要があります。
HSPの描画系は演算より遅いですが、line命令よりも高速に判定するのは至難の技です。
「判定するより 見えない線も描いたほうが速いじゃん」ってなると困ります。

矩形と線分の高速な接触判定という事で、ちょっとHSPからは離れてしまいますが、
HSPのline命令よりも高速に判定するには、どのようなアルゴリズムが必要でしょうか?



SYAM

リンク

2009/5/8(Fri) 23:28:17|NO.25044

全然違うアプローチなので応用できるかわかりませんが、「描画対象を絞り込む」という話であればこんな方法があります。
おもいっきり大雑把にいうと

全体を

AB CD

とすると、

・現在位置がA
 ・向きが東→B
 ・向きが西→なし
 ・向きが南→C
 ・向きが北→なし
・現在位置がB
 ・向きが東→なし
 ・向きが西→Aだけ描く
 ・向きが南→D
 ・向きが北→なし
・現在位置が(以下略)

……のようなテーブルができますね。これだと4エリアと4方向しかないですが、もっと細かくして配列にしてあればリアルタイムに計算をしなくてもよくなります。
もちろん大雑把な結果になってしまいますが、ほぼ瞬時に計算の対象を絞り込むことはできます。


実際、大昔のゲームでもこうして描画対象を絞り込んでいたようです。
空間をいくつものエリアに分けて、エリアごとに、そのエリアから視界に入る可能性のあるエリアのリストを用意しておいてその他のエリアは処理しないようにしたのです。



cd

リンク

2009/5/10(Sun) 21:22:07|NO.25105

ありがとうございます。
ただ、ちょっとエリアが広いので条件の作成が大変そうです。


変に計算するより、描画しちゃった方が早い気がしてきました。
高速な接触判定は諦めます。

皆さんありがとうございました。



ONION software Copyright 1997-2021(c) All rights reserved.