HSPTV!掲示板

こんにちは、掲示板の楽しいやりとり拝見してます。
ふと、ゲームのアルゴリズムといいますか、昨年のコンテストで入賞されていた
陣取りゲームを見ていて、わからない部分があるので教えてください。

自分でも作ってみようと意気込んでみたものの
線を引っ張るところ、既存の線との合成はうまくできたのですが
ボスのいない側を判定する部分。そしてその複雑な図形を塗りつぶすという部分。
真っ先に思いついたのは配列をしらみつぶしに調べて位置を特定するというもの。
やってみると処理が重く、リアルタイムゲームとしてはこれでは使えないな。と思いました。
どのように高速に処理するのか分からず、概念だけでも教えてもらえると
ありがたいなと思います。よろしくお願いします。

呼ばれたような気がしたので。

昨年のコンテストの拙作では、取得したエリアの判定に
原始的な塗りつぶしの考え方である、
「シード・フィル・アルゴリズム」という考え方を用いています。
概念はコチラをご覧下さい。
http://fussy.web.fc2.com/algo/algo3-1.htm

ボスのいないエリアの判定、というロジックをどう実装するかは自分も悩みました。
ここは発想の転換です。

ボスの座標を起点に上記アルゴリズムで塗りつぶしを開始します。
塗りつぶしが終了した時点で「塗りつぶされていないエリア」が
ボスのいないエリアになります。

がんばってみてください。

※自分は独学独習でなんとか形にしましたが、ここに出入りしている諸先輩方が
　もしかしたらもっとスマートな方法をご存じかもしれません。

こんばんは。
ああ、ZAPさん作者直々に解説いただきありがとうございます。

なるほど、基本的な考え方としては配列ひとつずつ確認で良さそうですね。
あとは再起などを使って効率よく処理すればよいのでしょうが・・。

なんとなく分かってきたと思うので、また頑張ってみます。
ありがとうございました。

もう解決してるけど
CreatePolygonRgnって言う便利なのがgdi32にあるから
塗りつぶしは簡単に出来たりする
サンプルはもう少しかかる・・・

ちなみに拙作ではプレイフィールドの大きさは
縦２２４×横２２４の配列で管理しており、
表示は配列１要素あたり４ドットで表示しています。
640×480でちょうど２倍拡大です。

この配列１要素がゲームフィールドの仮想的な１ドットに該当し、
そこに入っている数字によって
・取得済みエリア
・未取得エリア
・線が引かれている
・線を引いている途中
といった状態を判別し、ドット単位で描画しています。

最初は仮想プレイフィールドを縦横448ドット
（実画面と同じサイズ）で作成していたのですが
描画コストと処理速度の兼ね合いでこうなりました。

参考になれば。

サンプル作ってるつもりが半分ゲーム作ってる感じになってしまったので
使い方が分かる程度にしたやつ・・・

#module	

#uselib "gdi32.dll"
#cfunc CreatePolygonRgn "CreatePolygonRgn" var, int, int
#func  FillRgn "FillRgn" int, int, int
#cfunc GetStockObject "GetStockObject" int
#func  DeleteObject "DeleteObject" int
#cfunc CombineRgn "CombineRgn" int, int, int, int
#cfunc CreateSolidBrush "CreateSolidBrush" int
#cfunc PtInRegion "PtInRegion" int,int,int
#func SelectObject "SelectObject" int,int
#cfunc CreatePen "CreatePen" int,int,int
#func PolylineTo "PolylineTo" int,var,int
#func MoveToEx "MoveToEx" int,int,int,nullptr 


#deffunc setarea array paa,int na, array pab,int nb
	ha=CreatePolygonRgn( paa,na,1)	//多角形の座標をリージョン化
	hb=CreatePolygonRgn( pab,nb,1)
	tmp=CombineRgn(ha,ha,hb,4)	//ha内にあるhbの領域を取り除く(haに取り除かれたリージョンが返る)

	hBrush=CreateSolidBrush($444444 )	//指定色ブラシ作成($BBGGRR)
	FillRgn hdc, hb, hBrush	//塗り潰し
	DeleteObject hBrush	//使ったブラシ削除

	hBrush=CreateSolidBrush($444400)
	FillRgn hdc, ha, hBrush
	DeleteObject hBrush
	
	arealine paa,na,  pab, nb
return 

#deffunc arealine  array paa,int na, array pab,int nb
	hPenA=CreatePen(0,0,$ff00 )	//PolylineToはペンを使って描画されるので指定色で作成($BBGGRR)
	hPenB=CreatePen(0,0,$ff)
	SelectObject hdc,hPenA : oldpen = stat	//デバイスコンテキストにペンを設定して今まで設定されてたペンのハンドルを保存
	MoveToEx hdc,paa(3*2),paa(3*2+1)	//多角形を閉じる（最終座標をデバイスコンテキストの現在位置にする）
	PolylineTo hdc,paa,na	//多角形の座標にラインを描く
	SelectObject hdc,hPenB
	MoveToEx hdc,pab,pab(1)	//多角形を閉じない
	PolylineTo hdc,pab,nb
	SelectObject hdc,oldpen //ペンを元に戻す
	DeleteObject hPenA	//ペンを削除
	DeleteObject hPenB
	redraw 1
return 


#defcfunc getareano int x,int y
	if PtInRegion(ha,mousex,mousey) {return 1}	//リージョン内に指定座標があるか判定
	if PtInRegion(hb,mousex,mousey) {return 2}
return 0

#deffunc _exit onexit
	DeleteObject ha
	DeleteObject hb
return
#global

cls 4
areaA=32,32,640-32,32,640-32,480-32,32,480-32
areaB=200,480-32 ,200,300, 250,300, 250,350, 300,350, 300,300 ,400,300 ,400,480-32

//複数の点座標が入ってる配列と点の数を二組指定して、左の領域に右が含まれる部分を取り除いたリージョン作成
setarea areaA,4,areaB,8

color 100,255,100
repeat 4
	pos areaA(cnt*2),areaA(cnt*2+1)
	mes areaA(cnt*2)
	mes areaA(cnt*2+1)
loop

color 255,100,100
repeat 8
	pos areaB(cnt*2),areaB(cnt*2+1)
	mes areaB(cnt*2)
	mes areaB(cnt*2+1)
loop

m="エリア外","areaA","areaB"

repeat
	title m(getareano(mousex,mousey))+ " X:"+mousex+" Y:"+mousey //setareaで左側に指定したのが1、右が2として返る
	await 16
loop

リージョンは 左上座標<= リージョン内座標 <右下座標 となるのでライン上の判定に使うとやっかい

この方法だと1要素づつ領域判定して塗り潰す必要が無くなる
その代わり多角形を引かれたラインで切断して二つに別ける必要がある
斜めは無いなら複雑な多角形になっても塗り潰す判定よりは軽いだろ

いつのまにレスが増えとる（＾＾；


＞ZAPさん

参考資料ありがとうございます。
私もマップ配列は１対１で作るとデータが大きくなるし、処理重くなるし
移動単位が１ドットでは移動の際、ラインに引っかかって動けなくなるような気がしたので
今も内部は２分の１で作ってます。ただ、元々フィールドが広いので、もしかするとさらに変更するかもしれませんが・・。（汗
私の場合、マップ配列を２つ確保し、メイン用、作業用でやってます。


＞暇人さん

いやいや、すごくわかりやすいサンプルまで提供いただきありがとうございます！
今のところ斜め移動は考えていないので大丈夫です。
エリア内外判定も簡単にできるとは・・。なんて便利な。orz

Dripです。
ぜーっと!!さん、こんにちは。横から失礼します。

既に解決済みですが、
QIXのロジックをどこまで簡素化できるか興味が沸いたので挑戦してみました。
簡素化のカギは陣地管理に二次元配列等を使わずパレットモードで画素を文字列として扱うことで
かなりの高速化を実現しています。
塗りつぶしだけ高速化のためにWinAPIに頼りましたがそれ以外はHSPの標準機能のみで行いました。

・Shiftキーを押している間、線を引き陣地形成を開始する
・線が陣地にぶつかると線の内部が陣地に変換される
・Shiftキーを離すとプレイヤーは線を引き始めた場所に戻される
・ボスが線に触れるとゲームが終了する
・リアルタイムで陣地のパーセンテージを計算し、60FPSでなおかつ画面を拡大しない

という条件をクリアして130行弱でした。
粗末なコードですが何かの参考になれば本望です。

#define fx 560    //ゲームフィールドサイズX,Y（サイズは４の倍数縛りです）
#define fy 420

//塗りつぶしモジュール
#module
    #uselib "gdi32.dll"
    #cfunc CreateSolidBrush "CreateSolidBrush" int
    #cfunc SelectObject "SelectObject" int,int
    #cfunc ExtFloodFill "ExtFloodFill" int,int,int,int,int
    #func DeleteObject "DeleteObject" int
    #uselib "user32.dll"
    #func ReleaseDC "ReleaseDC" int,int
    #define FLOODFILLBORDER 0
    #define FLOODFILLSURFACE 1

    #deffunc fill int px,int py
    //選択色のブラシ生成
    mref bmscr,67
    nuri=CreateSolidBrush(bmscr(40)),SelectObject(hdc,nuri)
    pget px,py:col=(ginfo_b<<16)+(ginfo_g<<8)+ginfo_r

    tmp=ExtFloodFill(hdc,px,py,col,1)
    if tmp!1:tmp=ExtFloodFill(hdc,px,py,collFLOODFILLSURFACE)
    tmp=SelectObject(hdc,nuri(1))
    DeleteObject nuri:ReleaseDC hwnd,hdc
    return 0
#global

    //領域判定用オフスクリーンバッファ作成
    buffer 4,fx,fy,1
    repeat 256:palette cnt,0,0,255:loop    //使わないパレットを真っ青に
    palette 1,0,0,0            //無地領域（黒）
    palette 2,255,255,255      //プレイヤー陣地（白）
    palette 3,255,0,0          //線の描画領域（赤）
    palette 4,128,0,0    ,1    //一時マスクカラー（茶）
    mref vm,66                 //VRAMを確保
    sdim vm2,fx*fy+1           //VRAMの文字列操作用変数を確保（サイズに+1しないと文字列Null抜けでオーバーフロー）
    sdim vstr,8:repeat 7,1:poke vstr(cnt),0,cnt:loop    //バイナリ検索用文字列を確保
    sdim pst,4,fx*fy           //占有率カウント用配列変数を確保（予め確保しないとsplitが鈍足化する）
    palcolor 2:boxf            //フィールドを無地にセット
    palcolor 1:boxf 3,3,fx-4,fy-4    //周囲3ドット陣地確保（3ドット確保することで画面外チェックの手間を省く）
    
    #define ctype pchk(%1,%2) peek(vm,%1+(fy-(%2)-1)*fx)    //p1,p2の座標の情報を取得するコード
    
    gsel 0
    px=2:py=10                      //プレイヤースタート座標
    bx=100.0:by=100.0:rot=m_pi/4    //ボス座標と移動方向
    ct=0,0    //シフトキー押し下げカウンタとラインを何ドット引いたかのカウンタ
*main
    stick ky,15:getkey shift,16    //十字キーとShiftキーの状況を取得
    
    repeat 2    //プレイヤー速度2ドット分、プレイヤーの移動処理を繰り返す
        if shift:{
            if ct>-1:{        //線を引き終わっていなければ
                if ct=0:start=px,py:native=1,px,py          //線を引き始めた座標を確保
                gsel 4:palcolor 3:pset px,py:gsel 0:ct++    //自分の座標に線の色を置く
                prm(2)=1,3    //線引き時、移動できる場所のIDと周囲になければならないIDを指定
            }else{
                prm(2)=2,1    //線を引き終わった状態で、移動できる場所のIDと周囲になければならないIDを指定
            }
        }else{
            //線引きが中止された。線を無地で塗りつぶし、プレイヤーを引き始め座標に戻す
            if ct>0:px=start:py=start(1):gsel 4:palcolor 1:fill px,py:palcolor 2:pset px,py:gsel 0
            prm(2)=2,1    //通常移動時、移動できる場所のIDと周囲になければならないIDを指定
            ct=0,0        //通常移動時は常に線引きカウンタと引いたドット数をクリアしておく
        }
        prm=0
        if ky=1:prm=px-1,py
        if ky=2:prm=px,py-1
        if ky=4:prm=px+1,py
        if ky=8:prm=px,py+1
        if prm:{    //移動がリクエストされたら
            gosub *chk
            //移動に成功した
            if ans:{
                px=prm:py=prm(1)    //プレイヤーを移動
                if shift:ct(1)++    //線を引いている場合は、引いたドット数を加算
    
                //もし線を引いているとき赤線に密接しない場所に移動したらその座標を確保し続ける。
                if native:if ans<3:native(1)=px,py:else:native=0,px,py
    
            //移動に失敗し、なおかつ線を引いている最中で、線を引き終わってなく、１ドット以上移動に成功していれば
            }else:if shift!0 & ct>-1 & ct(1)>0:{
                if pchk(prm,prm(1))=2:{    //線を引こうとした座標が自分の陣地だったら線の中を塗りつぶす処理を開始
                    gsel 4:palcolor 4:fill bx,by    //ボスを中心にマスクカラーで塗りつぶす
                    memcpy vm2,vm,fx*fy             //現在のフィールドの状態を文字列に取得
                    strrep vm2,vstr(1),vstr(2)      //無地を全て陣地に置換
                    strrep vm2,vstr(3),vstr(2)      //線を全て陣地に置換
                    strrep vm2,vstr(4),vstr(1)      //マスクを全て無地に置換
                    memcpy vm,vm2,fx*fy             //陣地の状態を文字列からVRAMに転送
                    gsel 0
                    px=prm:py=prm(1):ct=-1    //プレイヤーの座標を移動先に設定し、線を引き終わった事を通知（ct=-1）
                    //がっ、移動先が壁の中だった場合、最初に線と交わった場所に飛ばす
                    prm=px,py,2,1:gosub *chk:if ans=0:px=native(1):py=native(2)
                    
                    split vm2,vstr(1),pst    //画面内の無地領域のドットを数える（なんと一行！）
                    title "占有率："+(100.0-double(stat-1)/((fx-6)*(fy-6))*100)+"%"    //ドット数から占有率計算
                }
            }
        }
    loop
    repeat 2    //ボス速度2ドット分、適当なボスの移動処理を繰り返す
        tmp=pchk(bx+sin(rot),by+cos(rot))
        if tmp=3:dialog "ミス！":end    //ボスがラインに触れたのでおわり
        if tmp=1:{    //ボス、移動に成功
            bx+=sin(rot):by+=cos(rot)
        }else{        //ボス、移動に失敗、角度を変更
            rot+=m_pi/2
        }
    loop
    redraw 0:color 64,64,64:boxf    //ここから描画を開始。背景クリア
    prm=(ginfo_winx-fx)/2,(ginfo_winy-fy)/2    //フィールド描画座標を計算
    pos prm,prm(1):gmode 0,fx,fy:gcopy 4,0,0   //ゲームフィールド描画（★画像背景等使いたい場合はバッファ増やして要工夫）
    gmode 0,8,8:color ,255:grect prm+px,prm(1)+py    //プレイヤー描画
    gmode 0,10,10:color 255:grect prm+bx,prm(1)+by   //ボス描画
    redraw 1:await 15
    goto *main

*chk    //prm,prm(1)の座標は移動できる座標か調べ、移動できればansに1以上が返る。
        //prm=チェック座標X,Y,移動できる場所のID,周囲8マスになければならないID
        //ansにはprm(3)のIDがいくつ見つかったかが代入される。
    ans=pchk(prm,prm(1)):if ans!prm(2):ans=0:return    //移動先が既に移動できるIDじゃなかった
    ans=0    //周囲にいくつ周囲8マスになければならないIDがあるかカウントする
    repeat 9
        if cnt=4:continue
        if pchk(prm-1+cnt\3,prm(1)-1+cnt/3)=prm(3):ans++
    loop
    return

おばんです。

＞Dripさん

うほっ！
笑ってしまいました。

超絶サンプルありがとうございます！
たった１３０行でQixが必要としていることすべてを実現されてしまうなんて・・。

しかも重くないし。

できればサンプルスクリプト、自分のプログラム内に吸収してしまっても
よいでしょうか？
あ、もちろんこれを使用してのコンテスト出品は無いですので。（＾＾；

よかったら返事ください。

Dripです。

ぜーっと!!さん、こんにちは。度々失礼します。

>できればサンプルスクリプト、自分のプログラム内に吸収してしまっても
>よいでしょうか？

このサンプルは誰でも丸ごとコピペして自由にご利用いただいて問題ありません。
（急ごしらえな為、逆に問題な処理がありましたら指摘していただけると助かります；
　著作権は主張しませんがご利用は自己責任の下でお願いいたします。）
ただ注意点として、コードの意味を理解してご利用いただくことを強く推奨いたします。

例として簡単なところでは「(fx-6)*(fy-6)」の「-6」はおまじないでも何でもなく、
フィールドの周囲3ドットを予め陣地にしたからその分引いているだけだったり、
意味を理解しないと計算が狂ってしまいます。
他にも　nuri=CreateSolidBrush(bmscr(40)),SelectObject(hdc,nuri)
なんかは2行に分けて書いたほうが代入の作法としてはより堅実かもしれません。
更に「if tmp!1:」の行は誤字ってる上に無意味ですね；（書くならエラー処理かな）

メモリのオーバーフローについては充分にご注意ください。
VRAMを文字列に変換してHSPの命令で高速に処理することは非常に効率的な反面、
使い方を誤るとメモリ空間のオーバーフローの危険を多いに伴います。
パレットコード0番を利用しない理由は文字列に変換した際にその画素がNull（文字列の終わり）
と認識されてしまうからとか、逆に文字列にコピーした際に末端にNullがないと、
strrep等の文字列操作命令でメモリ空間を破壊してしまう恐れがある、等の
意識がないまま生成されたプログラムは非常に恐ろしいものです。
充分にご注意いただき、充分なデバッグを行ってください。
（サンプルでは「sdim vm2,fx*fy+1」とすることで末端に常にNullを持たせていますが、
　それでも後々誤って1バイト多くmemcpyを実行した途端に安全神話が崩れ去ります。）

また私のコードでは陣地作成後にプレイヤーが壁に閉じ込められた時の処理に問題がありました。
問題を再現するにはボスを線で囲いつつ複数の閉鎖領域を持たせた場合
（ボスの移動処理を消して静止させてから、上から線でヒョウタンというか、
　数字の８を書くように部屋を描き、ボスを上の部屋に閉じ込めてみてください）、
陣地作成後、プレイヤーが壁（下の部屋のあった所）に埋まってしまいます。
埋まったときのワープ地点の条件作成が不完全でした。
（端的に言うと変数nativeの代入処理が全て欠陥で不要です！
　壁に埋まった際（if ans=0:の後処理）は、単純に埋まった座標からボスに向かって
　陣地のグリッドを検索したほうが良さそうです。）

//安全な後処理の例
repeat fx+fy
	tx=px:ty=py
	if px<bx:px++:else:if px>bx:px--
	if py<by:py++:else:if py>by:py--
	if pchk(px,py)=1:px=tx:py=ty:break	//陣地のグリッドを発見、ワープ
loop

長文失礼致しました。
コピペするよりも上記を注意しつつfillモジュールとVRAMの構想を写しながら
自分なりに組み込むのが安全かと思います＾＾；どうぞがんばってください。

ではでは