DxLib 小技4

15.あたり判定入門

概要: どんな場合でも以下のような感じ･･･(2Dゲームでは･･･)
この処理をいかに少なくするかで、処理速度に差が出る。
この処理を少なくする方法は今度書こう！
以下のソースはDxExより･･･DxExはDxLibのライセンスと同じです。

///ちょっとした　コリジョンをチェックする場合　数回だけとか？
inline bool CheckCollision(RECT &a,RECT &g){
	if(a.right<g.left || a.left>g.right || a.top>g.bottom || a.bottom<g.top)
	{//当たっていない
		return false;
	}else{//当たっている
		return true;
	}
}

inline bool CheckCollisionDot(int x,int y,int x2,int y2){
	RECT r={x,y,x+1,y+1};//2004/05/17:一部修正
	RECT r2={x2,y2,x2+1,y2+1};
	return CheckCollision(r,r2);
}
///大量にコリジョンをチェックする場合　例えば forループ内
inline bool CheckCollisionMaybeFast(RECT &r1,RECT &r2){
	LONG a1 = r1.left - r2.right;
LONG a2 = r2.left - r1.right;
	if((a1 & a2) >= 0)
		return false;
	return true;
	/*
	LONG a1 = -16 - p[i].x;
	LONG a2 = p[i].x - (640+16);
	LONG a3 = -16 - p[i].y;
	LONG a4 = p[i].y - (480+16);
	if((a1 | a2 | a3 | a4) < 0)
		res[i] = 0;
	else
		res[i] = 1;
	*/
}
inline bool CheckCollisionX(RECT &a,RECT &g){
	if(a.right<g.left || a.left>g.right)
	{//当たっていない
		return false;
	}else{//当たっている
		return true;
	}
}
inline bool CheckCollisionY(RECT &a,RECT &g){
	if(a.top>g.bottom || a.bottom<g.top)
	{//当たっていない
		return false;
	}else{//当たっている
		return true;
	}
}

参考,関連資料:

TAKABO SOFT NETWORK Programming DirectXゲーム製作講座座標同士の当たり判定
TWINTAIL LOVERS Luna のソース内の LunaCollision
暁のコーダ部屋　矩形判定,高速な矩形判定
BM98'S ROOMつう＝＞Programming Tips1024 Tips71.点と矩形との領域判定の高速化

2004/05/17:CheckCollisionDotのバグを修正

16.ファイルパッキング入門

ちょーっとファイルパッキング（ファイルを一つのファイルにまとめること）をしたくなったのでファイルパッキングの事についてメモってみようと思う。
独自ファイル形式を作る場合、以下のような要素が必要だと私は思う。

ヘッダー：ファイルの情報についてをファイルの先頭に書いておく
データ部：ヘッダからの情報に則している数列

と基本を確認したところでフォルダを固めたい。
これに必要な要素は ヘッダ部

ファイル名
ファイルサイズ
ファイルはデータ部の何処にあるか
特殊情報（これは何で圧縮されているのかとか、CRCとかSHA1とかの確認情報とか）

データ部

ヘッダ情報に即した数列のみ。

データ構造

struct header{
	///バージョン情報（決まり文句･･･？)
	UINT version;
	///ファイル数
	ULONGLONG file_num;
};
struct file{
	///ファイル名
	BYTE filename[dkcdMAX_PATH];
	///ファイルサイズ
	ULONGLONG filesize;
	///オフセット
	ULONGLONG offset;
	///crc32left(CRC値)
	ULONG crc32lest;
};
/*
簡易ファイル構造
header は 先頭に1個
file は header::file_num個ある。
データ部 は header::file_num個ある。
*/

フローチャート

headerを読み込む
sizeof(file) * header::file_numを読み込む
１、２で得た情報を元にデータ部を復元できるようにする。

と言うことでこんな感じにするため作ってみた。
しか～し、まだバグが取れていない可能性が＾＾；
dkutilライブラリに入ってます。

後からみてみると、入門といいますか、私専用備忘録のようで＾＾；すまんこってす。

17.メモリ管理あれこれ

どうも～、最近、タイチョ～ヨクナ～なd金魚です。
カヨーにコクリツヴョーインニイカナクテハ。
と、個人話はこれくらいにして、今回はメモリ管理のお話。
例えばmalloc()とか呼び出した後、必ずfreeが必要ですよね。（　new と delete も同じですね＾＾）
で、関数内で以下のような関数があるとします。

void create(){
 void *ptr = malloc(1024(;
}

かなり極端な例ですが、この関数はfreeをptrに施していないため、呼び出す度に1024バイトのメモリがリークしてしまいます。
つまり、開放されないのでアプリケーションを実行している最中はメモリの使用量が呼び出すたびに増えていって使用できるメモリ領域が少なくなってしまう（なくなってしまう）かもしれないのです。メモリが少なくなると当然、アプリケーションの実行速度にも影響するわけで、このような間違いはしたくないのです。*1
でも、やっぱり人である限り間違うのですよ。
ですので、このような事を起きないようにするのに、やっぱり既にいろいろな方法があるのですね。
私の教訓？鼻血boostのこんばんわコラムでも書きましたが欲しいものは既にできている。
車輪の際発明はしない！！
作るだけ時間の無駄！
(しかし、車輪の際発明でも、ある程度の勉強にはなったり、新しいアプローチをしたりもできるが）

という事でプログラムの先生方々のライブラリを使い倒す！
これに限る！！！
個人的に感銘を受けたイイ感じのを紹介したいと思いmath.

boost::shared_ptr
いわいるスマートポインタ結構、イイカンジ。
詳しくはLet's boostとかググって見よう
yaneSDK3rdのsmart_ptr
これもスマートポインタ。個人的にはこちらの方が好きだったりする。
詳しくはやねうらお氏のHPとかまたはググって見るとか
boost::pool
boostのpool系ライブラリ。
これはちょっと使い方が特殊。
詳しくはLet’s boost等で。Google result
ignis smart_ptr
BREW用smart_ptrのようです。すごくスマートにまとめられています。なんかとても軽そうに見えます。
えんら氏の日記にダウンロードできるようです。 http://d.hatena.ne.jp/enra/20040420 ちょっと書き換えればWindowsでも動かせると思います。
crtdbg.h
完全に手動型のメモリリーク検出ライブラリ。
自動的にメモリの開放は行ってくれない。メモリリークの場所とかしか教えてくれない。でも、事実、C言語のみでのプログラムでは結構重宝。
他にもメモリリーク検出ライブラリは出回っているそうだが･･･、私は今のところ之しか知らない。(2003/05/22)
ＶＣに標準でついてくる。（と思った。）
くわしくはcrtdbg memo
Boehm GC
通称 Boehm GC 正式な名前は長すぎるので覚えられない＾＾；
いわいるガーべジコレクタ。処理は重いが、最近のＰＣであればあまり負担にならないとかなるとか。
メンドクサガリには便利。だけど、私は昔はまったけど今はキライ。
詳しくはBoehm GC のページへ
scoped系
勝手にscoped系と私が関連付けてしまっていますが、簡単に言うとデストラクタでdeleteする奴。＾＾；です。
例えば、boostではscoped_arrayと scoped_ptrがありますね＾＾； dkutilではscoped_buffer やscoped_criticalsectionなんてのもあります。
今開発中(2003/05/22)のDxExにはscoped_drawarea（スコープアウト時にSetDrawAreaで設定した領域を元に戻す）とか scoped_init（スコープアウト時にDxLib_Endを呼び出す）とかがついていたりします。（実際あまり使い物にならないかもしれないけど＾＾；
極論：Ｄ言語にしろ！（爆
Ｄ言語はデフォルトでガーベジコレクター付です。
もうこんなメモリリークに関する事とはオサラバです。

では、mallocとかnewとかのメモリ管理については分かったけど、これをDxLibに応用できないの？
そうですね。そこが今回の肝です。
でももう眠いし･･･（只今３時･･･。
まぁ、ちょっとアイディアだけでも

スマートポインタとLoadGraph DeleteGraphを関連付けさせる。
LoadGraphとDeleteGraphを用いたscoped系のクラスを作ってみる。

って事で出来た。since 2004/05/24

smart_graph_handle.h(開発中のdxexより)

(boostが必要です。)

/*!
@brief DeleteGraphを使用しなくてOKなグラフィックローダー
@auther d金魚
@since 2004/05/23
@note
boostが必要になります＾＾；すまそん。

<h5>Licence</h5>
dxexライブラリに入っているソース一式のライセンスは一応、BSD Licenceだけど、
とりあえず、面倒なのでこれに限りNYSL(public domain)って事で。

*/
#ifndef smart_graph_handle_dxex__hpp_
#define smart_graph_handle_dxex__hpp_

//#include "DxExDxLibCache.h"

#include <boost/shared_ptr.hpp>
#include <vector>
#include <DxLib.h>

namespace dxex{

namespace policy{

struct smart_graph_loader_policy{
 int LoadGraph(const char *filename,int flag=1){
  return ::LoadGraph(filename,flag);
 }
 int LoadDivGraph( const char *FileName , int AllNum ,
       int XNum , int YNum ,
       int XSize , int YSize , int *HandleBuf )
 {
  return LoadDivGraph(FileName,AllNum,XNum,YNum,XSize,YSize,HandleBuf);
 }
 int DeleteGraph(int GrHandle,int LogOutFlag=0){
  return ::DeleteGraph(GrHandle,LogOutFlag);
 }
};

template<
 class LOADER_POLICY=smart_graph_loader_policy,
 class VECTOR__=std::vector<int>
>
class smart_graph_handle_base : public VECTOR__ , LOADER_POLICY
{
public:
 typedef VECTOR__ vector_type;
 typedef LOADER_POLICY policy_type;
 
 smart_graph_handle_base(const char *filename){
  LoadGraph(filename);
  }
 
 smart_graph_handle_base(const char *FileName , int AllNum ,
       int XNum , int YNum ,
       int XSize , int YSize )
 {
  vector_type::resize(AllNum);
  LoadDivGraph(FileName,AllNum,XNum,YNum,XSize,YSize,&vector_type::at(0));
 }

~smart_graph_handle_base(){

clear();

}
 int getHandle()const{
  return vector_type::at(0);
  }
 const int *getHandles()const{
  return &vector_type::at(0);
 }
 void clear(){
  if(vector_type::empty()){
   return;
  }
  vector_type::iterator it = begin();
  for(;it != end();it++){
   policy_type::DeleteGraph((*it),FALSE);
  }
  vector_type::clear();
 }

};

}//end of policy namespace

/*!
int handle = LoadGraph()
のhandleの管理を楽にするオブジェクト
いちいちDeleteGraphしなくてイイのがGood!!
*/
class smart_graph_handle{
public:
 typedef policy::smart_graph_handle_base<> policy_type;
 typedef boost::shared_ptr<policy_type> smart_graph_handle_base_ptr;
 typedef smart_graph_handle self_type;
private:
 smart_graph_handle_base_ptr mp;
 typedef policy_type obj_type; 
public:
 smart_graph_handle(const char *filename){
  mp.reset(new obj_type(filename));
  }
 
 smart_graph_handle(const char *FileName , int AllNum ,
       int XNum , int YNum ,
       int XSize , int YSize )
 {
  mp.reset(new obj_type(FileName,AllNum,XNum,YNum,XSize,YSize));
 }
 smart_graph_handle(const self_type &x){
  (*this) = x;
 }

~smart_graph_handle(){
  mp.reset();
 }
 int getHandle()const{
  return mp->getHandle();
  }
 const int *getHandles()const{
  return mp->getHandles();
  }
 ///getHandles()で得た配列はどこまでアクセスしてよいかを返す。
 size_t size()const{
  return mp->size();
  }
 ///ハンドルをクリアする。
 void clear(){
  mp->clear();
 }
 ///リロードする。前保存していたグラフィックは削除される。
 void reload(const char *filename){
  mp.reset(new obj_type(filename));
  }
 ///reload(const char *)のLoadDivGraph()版
 void reload(const char *FileName , int AllNum ,
       int XNum , int YNum ,
       int XSize , int YSize )
 {
  mp.reset(new obj_type(FileName,AllNum,XNum,YNum,XSize,YSize));
 }

self_type operator=(const self_type &x){
  mp = x.mp;
  return (*this);
 }
 
};

}//end of namespace

#endif

smart_graph_handleのサンプル

追記：
2004/05/24:smart_graph_handle.hとそのサンプルを掲載
2004/06/25:ポリシークラスのDeleteGraphがスタックオーバーフローしてしまう所を修正

*1:まぁ、詳しくはメモリリークとかググって見て＾＾；

18.暗号化基礎

基礎とかサブタイトルに使っているけど、暗号論の基礎とかそういうのじゃないので＾＾；
暗号化のソースの使い方みたいな？スマンのぉ。期待はずれで。

超簡易暗号化に関しては偽装化入門にて･･･。
ゲームで使う暗号化とかはゲームに使う画像とかを見られなければOKなんですよね。
まぁ、強いて言えば、暗号化と言うより、偽装化の方が合っているかもしれません。
しかし、何だかんだいって、やっぱり、個人的に作ったヘンな暗号より、伝家の宝刀の方が実績もあって凄くイイのです。
暗号の歴史によると、個人的に作ったヘンな暗号や暗号の理論を組み合わせたりした方法は結構、破られちゃったりすることがあるそうで。
やっぱり、こういうのは数学者や専門家に任せるのがイイです＾＾；
って、事で。今回はいろんなソフトでかなり使われているアルゴリズムの紹介でも。
その名も
Arcfour
詳しくはこちらでソースを公開しています。
http://d.hatena.ne.jp/studiokingyo/20040630

で、例のArcfourのソースの使い方はこちら。
http://d.hatena.ne.jp/studiokingyo/20040707#p5

さらに、サンプルソース

その他には
暗号化特集
ファイル単位で暗号化するときのコツとして、偽装化の所でも触れていますが、ファイルヘッダのみ暗号化して処理速度を稼ぐことです。 まぁ、ファイルの先頭から1KBくらい暗号化しておけば大丈夫だと思いますよ。
ファイルを１つのファイルにまとめるファイルパッキング機構とかでは、どうなんでしょうね？パッキングという行為自体ですでに偽装化は終了しているし･･･。しかし、何だかんだいって、解析ツールの類はファイルヘッダのパターンを元に、いろいろ解析するものがほとんどですので
(ファイルのデータの並び方を元に試行錯誤するツールは今の所、聞いた事がない。)
ファイルパッキングでも、解析されるときはされるので、いちおうパッキングするファイルひとつ、ひとつ、ヘッダ部分のみ暗号化して、それをパック化が良いと思うのですが、水曜どうでしょう？
あとは、自力で･･･、え、無責任？

詭弁のような･･･でも間違っていないと思うお話

さて、さて、暗号化のお話（というか殴り書きに近いナァ･･･スマンもともと良くわかってません。 m(_ _)m）をした所で･･･。
その暗号化の恩恵を預かるために、一番使いどころがあると思うところは･･･。なにがなんでもファイルセーブ、ロード時だと思うんですよ。
で、いきなりですが、ファイル構造

-元データのメッセージダイジェスト ハッシュ値
-暗号化済みデータ

さてさて、ここでメッセージダイジェストのハッシュが出てきました。
ハッシュとかは、C言語のアルゴリズムの教科書とかに書いていますが･･･。
それとは一味違うタイプです。MD5やSHA1とかRIPE-MDとか聞いた事ありませんか？
これらの特性として、なんと、ハッシュ値を逆算しにくいのだそうです。
詳しくは「Google」や「やね本２」にお願いするとして・・・。

処理の流れ process

早速、個人的な処理の流れの解釈と偏見を･･･。

セーブ
-ファイルに保存するすべてのデータをハッシュ関数に食わせる。
-ハッシュ値をいただく。
-ファイルに保存するすべてのデータを暗号化する。
-ハッシュ値を保存
-暗号化したデータを保存
ロード
-ファイルに保存した暗号化したデータをメモリ上にロード
-メモリ上にロードしたデータを複合化する
-複合化したデータをハッシュ関数に食わせる
-ハッシュ値をいただく。
-ファイルに保存してあるハッシュ値とさっき取得したハッシュ値をくらべる。
（ここでハッシュ値が違う場合は、セーブデータが改竄されていると判断できる。）

スマン、上手く説明できないわ･･･。介錯を頼む･･･。

で、このメッセージダイジェストのアルゴリズムではMD5が有名ですが、何かと欠陥が仄めかされているのでSHA1を使うのが良いかな？と思います。
ちなみにSHA1のソースコードはSYN氏のHPに掲載されています。SYN氏に感謝 m(_ _)m

さらに、メッセージダイジェストとか知りたい場合は検索するとか私の日記での暗号化とかのメモを頼りに情報を集めて見てください。

ソースコード source code

あ、そうですね。めいんでぃっしゅのソースです。

ちょっと注意

前回の暗号化のお話でコツは「ヘッダだけ暗号化した方が処理が少なくて良いかもよ～」と言っていましたが、それはリソースファイルの話(グラフィック（BMP）とか音楽ファイル（mid,wav)とか）であって、セーブデータに関してはすべてのデータを暗号化してください。
例えば、セーブデータをプレーンなまま保存してしまったとしましょう。

ファイル構造

-ハッシュ値
-プレーンなままのセーブデータ

例えば、プレーンなままのセーブデータの部分を改竄して、さらに ハッシュ値の部分まで改竄してしまうかもしれません。
案外、ハッシュ値の長さからアルゴリズムが特定出来ちゃうかもしれないのですよ＾＾；（独断と偏見だが･･･）

もっとスマートな実装は？

ちなみに、どうしてもプレーンなままファイルに保存したい！！って場合には･･･。ちょっと考えてみた結果、ハッシュを生成するときに「ゴミ値」も混ぜるのが効果的ではないかな？と考えてしまいました。
で、結果的にはこちらの方が･･･なにかと計算量は少なくて済みそうなのですが^^;;;;
こっちの方がスマートな実装なのかナァ？

とまぁ、こんな野巫なお話でしたが･･･、ちょっとでも、見込みがあると、この文章を読んでいただいたならば、私としてもこんなにありがたい事はありません。m(_ _)m

間違いがありましたら指摘してくださるとうれしいです。m(_ _)m

DxLibFanに戻る DxLibのダウンロードは以下から

DxLib Copyright(C) 山田　巧

The program using DxLib.
The text of this page.

SEO		[PR] 爆速!無料ブログ無料ホームページ開設無料ライブ放送

DxLib 小技4

15.あたり判定入門

16.ファイルパッキング入門

17.メモリ管理あれこれ

boost::shared_ptr

yaneSDK3rdのsmart_ptr

boost::pool

ignis smart_ptr

crtdbg.h

Boehm GC

scoped系

極論：Ｄ言語にしろ！（爆