Hatena::Groupgamehell

ゲームプログラムめも日記 このページをアンテナに追加 RSSフィード

けんもほろろ  / オススメゲームプログラム本  / 作ったもの置き場  
ゲーム開発のデザパタまとめ  / めも日記まとめ  

2005-06-17

[]DDA DDA - ゲームプログラムめも日記 を含むブックマーク はてなブックマーク - DDA - ゲームプログラムめも日記 DDA - ゲームプログラムめも日記 のブックマークコメント

はじめに

DDA(デジタル微分解析器)とは、画像処理で「線分を高速に描画」するアルゴリズムのことです。

 

2点を指定して直線を引く場合、平均変化率(傾き)を求める必要があります。

傾きはほとんどの場合、実数になりますよね。

 

しかし、昔のPCは実数演算がサポートされていなかったり、とても遅かったりしました。

 

そこで、実数を使わずに線分を描画するには?

ということで編み出されたのがDDAなのです。

 

「線分描画?そんなものゲームに使えるの?」

 

と思われるかもしれませんが、

例えば、敵機が自機を狙う「狙い撃ち弾」などに利用することができます。

(参考: シューティングゲームアルゴリズムマニアックス (C magazine)

DDAを使わない場合

例えば、敵機が(90, 100)、自機が(140, 190)にいるとします。

その場合、「狙い撃ち弾」の移動量を求める式は、

傾きを求めると、

\frac{dy}{dx}=\frac{190-100}{140-90}=1.8

となり、

y=1.8x

となりますね。

 

しかし、実数を使ったり、掛け算を使ったり、割り算を使ったりと、

なかなか重たい処理になってしまいます。

DDAの考え方

そこで、DDAの考え方は以下のようになります。

  1. x方向の差分、y方向の差分を求める。
  2. 差分の大きいほうを動かす。
  3. 動かさなかった方向の差分を「誤差」として蓄積する
  4. 「誤差」≧「動かした方向の差分」であれば、
    1. 「動かさなかった方向に動かす」
    2. 「誤差」-=「動かした方向の差分」
  5. 2に戻る

 

ポイントは、傾きを求める方法では、常に「x方向を動かしてyの移動量を求める」

という方法をとっていましたが、

DDAでは、「差分の大きい方を動かす」という方法を使うことです。

もう一つのポイントが、「誤差」です。

片方の方向へ動かしたときに、動かさなかった方向を「誤差」とする考え方です。

 

先ほどの例でDDAを使ってみます。

dx=140-90=50

dy=190-100=90

dy>dxなので、y方向に動かします。

低速弾であるとし、1フレームで1ピクセル移動するとします。

eは誤差です。

x9090919192
y100101102103104
e050100-9060110-90

表ではちょっとわかりにくいかもしれませんが、

y方向へ移動→誤差の蓄積→x方向の移動量の決定

という流れになっていることを意識すれば、それほど難しくないと思います。

 

このように、DDAは整数と足し算・引き算しか使わないので、とても高速に処理を行えます。

ゲーム開発では、常に最適化を求められるので、ゲームプログラマーを目指すなら必須の知識ですね。

ソースコード

C++でDDAを実装した場合は、以下のようになります。

移動テーブルを求めます。

vector<VECTOR2D> moveDDA(VECTOR2D vec1, VECTOR2D vec2)
{
	vector<VECTOR2D> ret;
	VECTOR2D vecD = vec2 - vec1; // 差分を求める
	int e = 0; // 誤差

	if(vecD.x > vecD.y)
	{
		for (int y = vec1.y, x = vec1.x; x < vec2.x; x++)
		{
			e += vecD.y;
			if (e > vecD.x)
			{
				e -= vecD.x;
				y++;
			}
			ret.push_back(VECTOR2D(x, y));
		}
	}
	else
	{
		for (int x = vec1.x, y = vec1.y; y < vec2.y; y++)
		{
			e += vecD.x;
			if (e > vecD.y)
			{
				e -= vecD.y;
				x++;
			}
			ret.push_back(VECTOR2D(x, y));
		}
	}
	return ret;
}

…ただ、このソースはvec1>vec2となった場合には、うまくいかないので、

差分を絶対値にしたり、条件式を増やすなどして、調整する必要があります。

[]色々とリンク集 色々とリンク集 - ゲームプログラムめも日記 を含むブックマーク はてなブックマーク - 色々とリンク集 - ゲームプログラムめも日記 色々とリンク集 - ゲームプログラムめも日記 のブックマークコメント

個人的にゲーム作成に役立つとおもったリンク集

【インフォシーク】メンテナンスのお知らせ
ゲーム製作の超基本的な知識や、企画書について書いてあります。
Infoseek[インフォシーク] - 楽天が運営するポータルサイト
「Tips」のタスクユーティリティクラスの作り方が参考になります。
FrontPage - FreeStyleWiki
「3DCGプログラミング」の解説がとっても分かりやすいです。

[]DirectX再入門2 DirectX再入門2 - ゲームプログラムめも日記 を含むブックマーク はてなブックマーク - DirectX再入門2 - ゲームプログラムめも日記 DirectX再入門2 - ゲームプログラムめも日記 のブックマークコメント

ビューポート

デバイスから取得。

アスペクト比を求めるのに使用。

光源(D3DLIGHT9)

光源の種類

.Type

マテリアル

ポリゴンを構成する各頂点がライトからの光をどのように反射するかを設定するパラメータの集まり

  1. Diffuse:やわらかく反射
  2. Specular:金属のようなするどい反射
  3. Power:Specularのパラメータ
  4. Emissive:自分から光る
  5. Ambient:環境の光に反応
法線

光の反射方向

光の方向

.Direction(D3DXVECTOR3)

マテリアルの設定

ID3DDevice::SetMaterial(D3DXMATRIX3*)

それ以降に描画するモデルマテリアルが適用される。

環境

.Ambient

ぼんやり見えるようにするには、パラメータを小さくしておくとよい。