自己参照構造体のリスト処理について

[桃印]

　以前、矩形と円形の当たり判定でこちらのお世話になった者です。
　ゲーム製作において再び疑問点が浮上しましたので、質問させていただきます。

　現在龍神録の館を利用しつつＳＴＧを製作しているのですが、アレンジするにあたって通常では定数でグローバル宣言されている弾の構造体を、リスト処理で際限なく生成できるようにしようと思いました。
　色々な資料を参考にしつつプログラムを組んだのですが、どうも構造体の宣言部分で躓いてしまう問題が発生しました。

　構造体を宣言するヘッダ<struct.h>において、以下のように宣言すると大量にエラーが発生（ソースから呼び出されるたびにエラーが出ている？）してしまいます。
　たとえばこのような変数を持つ構造体を宣言する場合、

//弾の構造体
typedef struct{
	int	flag;	//フラグ
	double range;	//当たり判定の半径
	double x, y;	//座標
	double spd;	//速度
	double angle;	//角度
	bullet_t *next;	//自己参照構造体
}bullet_t;
EXTERN bullet_t *head;//先頭ポインタ

　とすると『error C2143: 構文エラー : ';' が '*' の前にありません。』『error C4430: 型指定子がありません - int と仮定しました。メモ: C++ は int を既定値としてサポートしていません』というようなエラーが大量に発生します。
　おそらく記述の方法がおかしいのだと思います。一応別の宣言方法などども試してみました。

//弾の構造体
struct bullet_t{
	int	flag;	//フラグ
	double range;	//当たり判定の半径
	double x, y;	//座標
	double spd;	//速度
	double angle;	//角度
	struct bullet_t *next;	//自己参照構造体
}
EXTERN struct bullet_t *head;//先頭ポインタ

　しかしこのようにした場合も、『error C2236: 予期しない 'struct' 'eff_t' です。';' が入力されていることを確認してください。』というエラーが出てしまいます。

　宣言が出来なければプログラム以前の問題で、解決するだけの知識もなくすっかりお手上げ状態となっています。
　どうかご教示いただけたら幸いです。

　使用ライブラリ：ＤＸライブラリ
　コンパイラ：Visual C++ 2008 Express Editions
　※質問内容が不十分の場合はお申し付けください

[御津凪]

//弾の構造体
struct bullet_t{
	int	flag;	//フラグ
	double range;	//当たり判定の半径
	double x, y;	//座標
	double spd;	//速度
	double angle;	//角度
	struct bullet_t *next;	//自己参照構造体
}; // ←ここに';' が無いのが問題だと思います。
EXTERN struct bullet_t *head;//先頭ポインタ

[kazuoni]

>前者
http://ysserve.int-univ.com/sugsi/Lectu ... 01-04.html
このあたりが分かりやすいかもしれないです。

[桃印]

　御津凪さん、kazuoniさん、回答ありがとうございます！

＞御津凪さん
　うわあー凡ミスー！　すいません、しっかり確認しておくべきでした。申し訳ないです；
　ちゃんと;を入れてあげたところ、正しくポインタとリスト処理が機能することができました！
　ありがとうございました！

＞kazuoniさん
　なるほど、そういう宣言方法もあるのですね。
　ありがとうございました！

　しょっぱいミスでお手を煩わせて申し訳ありませんでした！　以後気をつけます……。　

[桃印]

　度々申し訳ありません、　同じく自己参照構造体のリスト処理についてです。
　皆様のお陰で構造体の宣言は出来たのですが、実際にそれらを使ったプログラムを組んでみたところ、上手く処理することができませんでした。
　リスト構造については参考書やネットで検索して知識をつけているつもりなのですが、それらを龍神録プログラムに組み込む方法が分かりません。具体的には「動的に確保したメモリをリストの最後尾に追加」する方法と、また通常の龍神録の館で行われているような「繰り返しによる出力」の方法です。

　前者はリストの先頭ポインタを関数に与え、while分でNULLに行き当たるまでループさせ、そこに動的確保したメモリのポインタを代入することでできると思っているのですが、具体的なアルゴリズムが分かりませんでした。
　後者は、表示段階よりも前の処理で弾を移動制御する部分においてポインタの「現在位置（上手い表現が出てきません；）」をリスト最後尾まで移動してしまっており、表示処理の繰り返しに入る前の判断式while(bullet != NULL)の時点ではじかれてしまい表示処理に入ることができません。移動制御においてグローバル宣言されたリストを直接操作しなければ良いのでは、とは思うのですが移動制御は構造体内の変数を変更する処理（座標の代入とか）があるので直接操作してしまっています。扱っているのはポインタなので、通常の構造体のように直接操作する必要はないと思うのですが、ポインタについて理解が不十分なためどうしたらいいか分からないのです。

　自分でも良く分からなくてソースもわやくちゃなので具体例を挙げることができないのですが、方法論だけでも教えていただけたら幸いです。

[SCI]

拙いコードで申し訳ないですが、自分の勉強も兼ねてリスト構造のサンプルを作ってみました。
理解の手助けになれば幸いです。

[御津凪]

前者の方法は SCI さんの添付されたコードの通りで実装できます。


後者においては、以下のような方法で処理すると良いかもしれません。

// sHead という struct bullet_t *型のグローバル変数があると仮定
void BulletMove( void ){
    struct bullet_t *blt = sHead; // 一時変数にて作業。グローバル変数は基本弄らない。
    while( blt != NULL ){         // blt が NULL でない間、

        /* blt に対する処理 */

        blt = blt->next;          // 次のデータへ移動する。
    }
}

こうすればグローバル変数を操作することなく処理できます。
描画時でも同様に一時変数で作業を行なえば問題ないでしょう。

[桃印]

　SCIさん、御津凪さん、回答ありがとうございます。

＞SCIさん
　わざわざサンプルまで作っていただいてありがとうございます。
　とても読みやすいコードで参考になりました！
＞御津凪さん
　なるほど先頭ポインタを明け渡せばいいのですね。ポインタなので一時変数でもそのポインタをいじることには変わりないと。勉強になりました～。

　さて、こちらコードを元に「リスト最後尾に新しい構造体を追加し、その構造体のポインタを返す関数」を作成してみました。が、上手く動きません……どうやらリスト先頭がNULLのまま変わらずになっているようで、下記の御津凪さん案参考の繰り返しにも入ることができません。
　ソースはこんな感じです。

bullet_t *bullet_set()
{
	bullet_t *p = new bullet_t;		// 新しいデータ
	bullet_t *pCur = head;		// リスト上の現在の位置

	// 新しいデータの初期化
	memset(p, 0, sizeof(bullet_t));//この初期化は正しい？　正しくない？
	p->next = NULL;
	
	if (pCur)	// 先頭があったら
	{
		//最後尾までpCurを動かす。
		while (pCur->next) pCur = pCur->next;
		
		pCur->next = p; // 最後尾の次に、新しいデータを追加
	}
※	else		// 先頭がなかったら
	{
		head = p;	// 新しいデータを先頭にします。
	}
	return p;
}

　そして、return で戻したポインタに

bullet_t *p;
	p = bullet_set(head);
	p->x		=100;
	p->y		=100;
	p->size		=2.0;

　のような方法で弾をセットしていきます。

　しかし調べてみたところ、何度弾がセットされてもbullet_set関数の※の部分の処理に飛んでしまいます。
　それはif(pCur)のelse――もといif (pCur == NULL)であるからですよね。処理を繰り返しているとプログラムが凄く重くなるので、メモリは確保されているがポインタ受け渡しが上手くいっていないようです。
　また、セット時の構造体初期化は龍神録の通りにmemset関数で0を代入したので良いのでしょうか？（一応この処理がなくてもエラーは出ませんでしたが……）。
　先頭ポインタを参照して一時変数でいじるというのは理解しましたので、この処理で正しくポインタさえ代入できてしまえば、リスト構造での弾宣言ができると思うのですが……どうしたら良いのでしょうか……。

[SCI]

つまり、headがずっとNULLのままなんですね？
memsetは問題ないです。
headがグローバル変数なら、そのコードで書き換えが出来ていると思うのですが、headはグローバルな位置に宣言してありますか？
引数で渡すとしたら、ポインタのポインタにする必要があります。

[桃印]

　SCIさん、素早い回答ありがとうございます。

　headは龍神録コードに則り、struct.hで

typedef struct _bullet_t{
	double x, y;	//座標
	//そのほか色々な変数
	_bullet_t *next;	/* 自己参照構造体 */
}bullet_t;
GLOBAL bullet_t *head;

　このように宣言され、ini.cppのfirst_ini()でhead = NULL;と代入しています。first_iniは初回のみしか実行されませんので、この部分でNULLを代入してしまっているということはないと思います。これでグローバル宣言できていると思うのですが……。

　ポインタのポインタというのは、*演算子が二つ付いてるやつですよね。
　bullet_setの仮引数部分をbullet_set(bullet_t **head)として先頭ポインタを渡すということでしょうか？

[桃印]

　すいません、先頭がＮＵＬＬのままの問題は自己解決しました！
　どうやらコードの解釈を間違えていたようで、変な部分を変更していました。
　正しく修正してみたところ、弾の発生と移動処理、そして描画処理もしっかり行われました！

　が、しかしここでまた問題が……。
　今度は弾消滅の際に「ポインタで受け渡した構造体を消去し、リストを繋げ直す」処理が出来ませんでした。

void eff_free(bullet_t *p)
{
	bullet_t *pCur = p;		// リスト上の現在の位置
	bullet_t *pNext;			// 削除の前にポインタを保存するため
	// リストのすべての要素を解放します。
	pNext = pCur->next;
	delete pCur;
	pCur = pNext;
}

　SCIさんのサンプルにあった消去関数を参考にしたのですが、この方法だと上手く連結が出来ていないようで、一度でも消去の処理が実行されると繰り返しで迎えた移動制御の際にエラーが出てしまいます。エラーの内容がポインタ違反云々なので空のポインタに行き当たってしまったのだと思います（つまり連結が出来ていない）。
　これはSCIさんが仰る「引数で渡すとしたら、ポインタのポインタにする必要があります」という部分が関わっていると思うのですが……多重間接参照がどう使ってやればいいのかがわかりません。受け渡した指定のポインタをbullet_t **pなりで受け取ってやるのでしょうか？

[SCI]

実は、今回作ったリストは「単方向リスト」と言うもので、途中の要素を削除したり、途中に要素を挿入したりするには「双方向リスト」を作る必要があります。

今回の構造体は「自分の次」だけ分かっている状態ですよね？
途中の要素を削除するには、「前」と「次」を繋がなければならないので、「自分の前」というデータも持っている必要があるんです。

さっきのソースをいじって双方向リストに作り変えることも出来るんですが、ここまで大丈夫ですか？

[SCI]

さっきのコードに「指定したデータを削除する関数」を追加しました。バグがあったらごめんなさい（泣
途中に追加する処理は入れてませんが、削除するときと同じように、NULLポインタに注意しながらつなぎかえることで実現できます。

また、環状リスト（って言うのかな？）やダミーを使ったり、先頭ポインタだけでなく最後尾ポインタも保存したりという方法もあります。

//でわ、私はもう寝ちゃいます。。

[BEMANI]

プログラム書いていて、頭の中で処理が出来なければ
絵にかいてみることをお勧めします。
簡単な絵で結構です。
頭の中が整理できて、結構やりやすいですよ＾＾
やりたいことを絵に書いてみました。

エラーの原因なんですけど、
// リストのすべての要素を解放します。
pNext = pCur->next;
delete pCur;
pCur = pNext;

pCur を delete したあとで、pCur に代入しようとしているのが原因ではないでしょうか？

[桃印]

　CSIさん、BEMANIさん、回答ありがとうございます！

＞CSIさん
　なるほど、やはり双方向でなければいけないのですね。実は元々双方向での考え方でやっていたのですが、どうにも混乱してしまって、こちらで相談するに至ったのです。しかし皆さんの協力のお陰でちょっとずつ理解できてきましたので、CSIさんのサンプルを元にコードを書いてみたいと思います。
　出来ましたらまたご報告させていただきます。

＞BEMANIさん
　わ、これは分かりやすいですね。最初から図にしていれば良かったです。
　最前後の場合を全く考えていなかったので、ここあたりがエラーの原因なのかもしれません。

　それでは早速プログラムを組んでみたいと思います。
　ありがとうございました！

[桃印]

　一応プログラムを組んでみました。
　が、やっぱり削除が出来ておらず、制御・表示系突入時の判断式while(p != NULL)をスルーして突入してしまい、アクセス違反が発生してしまいます。やはり制御と表示はできているので、メモリを開放するだけなですが……。
　一応プログラムを載せておきます。

void free(bullet_t *p)
{
	bullet_t *pCur = p;		// リスト上の現在の位置

	if(pCur->prev == NULL){		//先頭
		head = NULL;
	}
	else{
		pCur->prev->next = pCur->next;
	}

	if(pCur->next == NULL){		//最後尾
		pCur->prev->next = NULL;
	}
	else{
		pCur->next->prev = pCur->prev;
	}

	delete pCur;
}

　なお、弾構造体のセットは

bullet_t *bullet_set()
{
	bullet_t *p = new bullet_t;		// 新しいデータ
	bullet_t *pCur = eff_head;		// リスト上の現在の位置

	// 新しいデータの初期化
	memset(p, 0, sizeof(bullet_t));
	p->prev = NULL;
	p->next = NULL;
	
	if (pCur != NULL)	// 先頭があったら
	{
		//最後尾までpCurを動かす。
		while (pCur->next) pCur = pCur->next;
		
		p->prev = pCur;
		pCur->next = p; // 最後尾の次に、新しいデータを追加
	}
	else		// 先頭がなかったら
	{
		head = p;	// 新しいデータを先頭にします。
	}
	return p;
}

　このような方法で行っています。

[御津凪]

データを削除する時に、対象が先頭データの場合だと head を NULL にしてしまい、リストがなくなってしまいます。
ここは 一つしかない場合（次が NULL のとき）に NULL にして、そうでない時は head を次のデータに移動させます。

また、先頭でも最後尾でもある場合（一つしかないデータ）の処理に問題があります。
（このときにアクセス違反が出ています）

ちなみに、下記のコードは双方向リストを循環的につなげる（最後尾と先頭をつなげる）形式の処理です。

// p を最後尾に追加
void AddList( bullet_t *p ){
    if( head == NULL ){               // head が NULL なら、
        head = p->prev = p->next = p; // head に代入（自分自身を指すようにもする）
    } else {                  // head が NULL でないなら、
                              // （リストの最後尾は head の前のデータ）
        p->next = head;       // p の次を head に
        p->prev = head->prev; // p の前を head の前に
        head->prev->next = p; // headの前の次を p に
        head->prev = p;       // headの前を p に
    }
}

// p を削除
bullet_t *RemoveList( bullet_t *p ){
    if( head == p ){              // 削除対象が head の場合、
        if( head == head->next ){ // 自分自身の循環参照（一つしかない）なら
            delete p;             // 削除。
            head = NULL;          // head を NULL にする。
        } else {                  // 二つ以上ある場合は
            head = head->next;    // head を次のデータにする。
        }
    }
    if( head != NULL ){          // head が NULL でない場合
        bullet_t *ret = p->next; // 戻り値のための一時変数。
        p->prev->next = p->next; // p の前の次を p の次に
        p->next->prev = p->prev; // p の次の前を p の前に
        delete p;                // 削除。
        return ret;              // 削除対象の次のデータを返す。
    }
    return NULL; // データがないので NULL を返す。
}

// ループ処理
void MoveList( void ){
    bullet_t *p = head;
    if(p){
        do{
            /* 移動処理 */

            if(/*移動処理内で削除依頼があったら*/){
                p = RemoveList(p); // 削除
            }
            else p = p->next; // 次のデータへ
        }while(p != head);    // 一周するまで繰り返す
    }
}

循環形式の場合だと、最後尾への追加で検索をせずに行なえます。

[SCI]

コンソールばかりではあれなので、実際にDxLibを使って弾を撃つプログラムを作りました。
最小限の内容を詰め込んだので、コンソールのときと見比べてみるとよく分かるかもしれません。

慣れてきたら、いろいろ改造してみるのもいいですね。
・ある程度間隔をあけて撃てるようにする
・発射位置にキャラクターを表示する
・循環リストにする
・リストの先頭にダミーを使う
などなど・・・

[桃印]

　御津凪さん、SCIさん回答ありがとうございます。

＞御津凪さん
　なるほど、リストをつなげて扱うなんて方法もあるんですね。これならリスト自体が動こうと、再び自分まで戻ってきたら一周と判断できますね。
　早速御津凪さんのコードを組み込んでみました。動的にメモリ確保したポインタを取得し、そのポインタに必要数値をセット、そのポインタをAddList関数に渡してリスト登録。制御関数ではリスト一周分を繰り返し、削除したい場合はフラグを立て、フラグが立っていたらRemoveList関数を通し、そうでなければ次のポインタへ。
　動作確認してみたところ、制御・表示ともに動作しました！

　……んですが、なにやら弾がガクガクした動きになります。メモリリークでもして処理落ちしているのかと思いましたが、登録した玉のカウンタを表示してみたところ、どうやら「RemoveList関数を迎えると制御ループを飛び出してしまう（必ずNULLが帰ってきている？）」ようです。
　カウンタを見たところ、玉が発生すると弾構造体数がガンガン増える（当然ですが）→ガクガクしはじめる→弾を止めてみる→ゆっくりと構造体数が減っていく（速度的に１フレームにつき１つづつぐらい？）ようでした。なので、制御構文自体が強制的なループ脱出によって１フレーム１回しか動作してないのかな、と。
　実際、消去フラグを立てなければ、当然構造体は消去されませんでした、ガクつくことはありませんでした……。

　問題部分のコードはこちらです。

bullet_t *RemoveList( bullet_t *p ){
    if( head == p )				// 削除対象が head の場合、
	{
        if( head == head->next )	// 自分自身の循環参照（一つしかない）なら
		{
            delete p;				// 削除
            head = NULL;		// head を NULL にする。
        }
		else					  // 二つ以上ある場合は
		{
            head = head->next;	// head を次のデータにする。
        }
    }
    if( head != NULL )			// head が NULL でない場合
	{ 
        bullet_t *ret = p->next;		// 戻り値のための一時変数。
        p->prev->next = p->next;	// p の前の次を p の次に
        p->next->prev = p->prev;	// p の次の前を p の前に
        delete p;					// 削除
        return ret;					// 削除対象の次のデータを返す
    }
    return NULL; // データがないので NULL を返す。
}

void bullet_main()
{
	int free_flag;
	bullet_t *p = head;

	if(p){
		do{
			//削除フラグの初期化
			 free_flag = 0;

			 //計算処理
			p->x+=cos(p->angle)*p->spd;
			p->y+=sin(p->angle)*p->spd;
			p->cnt++;

			//演出種類ごとの処理
			switch(bullet->knd)//ここら辺は適当で
			{
				case 0:
					if(削除する場合は)
						free_flag = 1;
					break;
			}

			if(free_flag != 0)
				p = RemoveList(p); //削除
			else
				p = p->next;
		}while(p != head);
	}
}

　移植する際に、どこか解釈を間違えてしまっているのでしょうか。
　ずっと試行錯誤してみましたが、分かりませんでした。度々申し訳ありません；

＞SCIさん
　おお、仕事速いですね～。
　こちらのプログラムを使って、ちょっと色々ためしてみたいと思います！
　まずはポインタが正しく理解できるようにならないとなぁ……。

[御津凪]

（上記のコードを実行できる環境でないので）頭の中でデバッグしていたところ、
先頭（head）のデータが削除される時にループを抜けてしまうようですね。
こちらが用意したコードにバグがあったということです。
すみません。

具体的な現象ですが、

・head を RemoveList 関数で削除
・head が一つ先にずれる
・削除されるのは元 head だったデータ
・その次が head なので、この状況に削除対象データは末尾データと同義になる。
・返されるデータは head になる。
・結果、while から抜ける

といった感じです。

対処としては以下の三箇所を修正してください。

void bullet_main()
{
    int free_flag;
    bullet_t *p = head;
    bullet_t *top;

    if(p){
        do{
            top = head; // 先頭位置の参照を保持
            //削除フラグの初期化
             free_flag = 0;

             //計算処理
            p->x+=cos(p->angle)*p->spd;
            p->y+=sin(p->angle)*p->spd;
            p->cnt++;

            //演出種類ごとの処理
            switch(bullet->knd)//ここら辺は適当で
            {
                case 0:
                    if(削除する場合は)
                        free_flag = 1;
                    break;
            }

            if(free_flag != 0)
                p = RemoveList(p); //削除
            else
                p = p->next;
        }while(p != top);
    }
}

削除処理中に head が変わってもいいように一時変数に保持し、その変数で比較しています。

[桃印]

　御津凪さん、回答ありがとうございました！

　早速コードを組み込んでみました。確かにカクつかず動作します。が、ショットが全て消えた瞬間にアクセス違反が発生しました。
　たぶん最後の最後でtopに空っぽのポインタが入ったんじゃ、と思ったのでtop = head;の直後にif(top == NULL) break;を入れてみたところ、アクセス違反は発生しませんでした。描画・カウント数も正しいものでしたし、メモリリークも発生していませんでした（連続的に発生させてる最中に、タスクマネージャでプログラムの使用メモリがばこばこ増えなかったら大体オッケーでいいんですよね？）。

　ともあれこれで無事リスト構造は完成だと思います。
　何だかほとんど皆さんのお力に頼りきりになってしましましたが、教えていただいたことを参考にさらに勉強していきたいと思いますので、今後また何かあればよろしくお願いいたします。
　でわでわ。

[御津凪]

> 最後の最後でtopに空っぽのポインタが入ったんじゃ

その通りでしたね。やはり脳内デバッグでは無理があったかなと。


> 連続的に発生させてる最中に、タスクマネージャでプログラムの使用メモリがばこばこ増えなかったら大体オッケーでいいんですよね？

大体大丈夫でしょう。

ちなみに、メモリリークが発生しているかチェックする関数が VC++ にあります。
<crtdbg.h> をインクルードし、

_CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF);

を起動直後に読み出すことで、終了時にメモリリークの発生状況を出力ウインドウに出すことが出来ます。
ただ、どのタイミングでメモリリークが発生したかまでは分かりませんが…。

[桃印]

　いやはや、あれだけのことをちゃちゃっとやってのけるのには憧れます。
　私も勉強しないとなーorz

＞_CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF);
　ほうほう、そんな機能もあるのですね。安全に遊んでいただくためにもメモリリークは起こしたくないバグなので、これらを使って注意深く作業していきたいと思います。

　しっかし、まだ半分もできてないＳＴＧなのにメモリ使用量は東方風神録の二倍…一体どんなマジックを使ってるんでしょうかねぇ。弾やエフェクトなど数用意するものをリスト構造に置き換えて、背景などはステージごとに別個で読み込むぐらいしかメモリの節約方法を思いつきませんｗ

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