リアルタイムストラテジーの話

**名無しさん＠お腹いっぱい。** · 01/11/17 12:31

age of empireとかstarcraftみたいな
リアルタイムストラテジーの開発の話題

**検証3/3** · 2008/01/04(金) 22:19:55

２２２２４４３３
２２２ ■■■■３
２２６６６ ■５５
２２ ■■７ ■■■
２２ ■８１１１１
２ ■■■１１１ ■
２２ ■■１１１１
■２ ■９１１１１

１）4x4の右下の１に対応
２）2x2の左上の０、１の部分に対応
３）2x2の右上

得られたグラフ

２－４－３－５
└６－７－１－８
　　　　　　 └－９

なんとなく最初よりマシになったような気もするが、
これは「へこみのない空間に分割する」を満たしていないので、
A*適用後の経路探索が遅くなったりするのかも・・・？？？

改行が多すぎて3レスになってしまった。検証終わり。

**名前は開発中のものです。** · 2008/01/04(金) 22:30:10

あ、ごめんなさい。50％ではだめでした。
壁の数がセルの幅未満だったら（4x4なら4未満だったら）、に訂正しておきます。
（幸運にも上の例では結果は変わらず）

**名前は開発中のものです。** · 2008/01/04(金) 23:24:17

>>595
ざっとみた限りでとりあえず気づいた問題となりそうなこと

・４ｘ４の荒いグリッド内に3以下の壁で閉区間になっている可能性があるので、その荒さのみでは判断できない

□□■□
□□□■
□□□□
□□□□

・塗りつぶした区画の面積の幅が大きく、また縦や横に長くなる可能性があるので、経路を探索結果が最短でない可能性がある。（このあたりが凹みのない形にこだわる理由だと思う。たぶん方形または円に近い形での分割が理想）

**名前は開発中のものです。** · 2008/01/04(金) 23:44:09

実際にRTS作るとしたら閉鎖された領域対策は
経路探索するとき探索したノード数が一定以上になったら強制的に終了って感じにするかな。

**名前は開発中のものです。** · 2008/01/05(土) 00:59:27

評価ありがとう。
やっぱり方形か円のほうが都合がいいんだね。
速度を無視するなら簡易ライフゲームを使うとかなり最適に近い分割ができるかも。
全ての地点に種を蒔いて、風船みたいに膨らませてゆく。全部が限界まで膨らんだら、
大きい順に被ってないものを確定させて、残った空間で繰り返し。

遅いかもだが、他アルゴリズムとの比較には使えそう。

**名前は開発中のものです。** · 2008/01/05(土) 01:25:45

全ての点を使うかわりに、壁と壁の中央線の交点を使えば速くなるのかにゃー。

**名前は開発中のものです。** · 2008/01/12(土) 11:51:10

地形やユニット、建物をどんな形で持てばいいのかがわからない・・・
衝突判定によく使われるだろうから、マップを大き目のメッシュに区切って
その範囲にあるオブジェクトごとにまとめる方法しか思いつかないんだけどなにかいい方法ないかな

**名前は開発中のものです。** · 2008/01/12(土) 19:20:27

地形建物は位置固定だから、単純にX*Yサイズの配列でいいと思うけど、ユニットは位置がどんどん変化するし、かなり偏りがあると思うから、衝突判定にいい感じに使えるようにインデックスつきの配列か、木構造に入れるのがいいんじゃないか？

**名前は開発中のものです。** · 2008/03/12(水) 04:48:44

移動先を指定したら、そこへ向けて探査機を走らせる
移動不可能地形を踏んだらその座標を記憶(a,b)
そのまま真っ直ぐ進んで再び移動可能地形を踏んだらその座標を記憶(c,d)して止まる
(a,b)と(c,d)の中間地点にジャンプしてそこからもともとの移動方向の左右90°方向に
腕を伸ばしていき、その先端が先に移動可能地形を踏んだら、先端の座標を
中継地点として記憶(e,f)、直前の点と向かっていた点の間に挿入
母機に戻って、今度は母機－(e,f)－移動先の順で以下ループ
移動先まで一度も移動不可能地形を踏まなかったらループ脱出、母機がトレース

検索に時間かかるけど、これでかなり複雑な地形も避けれた

**名前は開発中のものです。** · 2008/03/12(水) 09:19:36

その方法だと移動不可能地形の中にくりぬいたように移動可能地形があると、ルートが検索できなくならないか？

**名前は開発中のものです。** · 2008/06/04(水) 19:44:06

新しい　gamedeve 一応かきかき
TopPage - game-develop.com wiki
http://wiki.game-develop.com/

GameDevWikiを何とかするスレ
http://pc11.2ch.net/test/read.cgi/gamedev/1156117275/

**名前は開発中のものです。** · 2008/12/13(土) 08:25:05

コサックスとかって当たり判定はどうしてんだろ

**名前は開発中のものです。** · 2009/02/14(土) 09:00:22

保守

**名前は開発中のものです。** · 2009/02/14(土) 12:15:06

>>605
空間をうまいことユニット量の扁りに合わせてインデックス付けして、とかじゃない？

**ううううううううう** · 2009/03/20(金) 13:40:37

みんな死ね

**名前は開発中のものです。** · 2009/03/20(金) 15:23:24

私は死んだ。スイーツ（笑）

**名前は開発中のものです。** · 2009/03/22(日) 17:24:58

res

**名前は開発中のものです。** · 2009/04/16(木) 22:46:15

改めて読み直すと、このスレ結構役立つなぁ

**名前は開発中のものです。** · 2009/08/11(火) 22:42:15

ほしゅ。
RTSっていろんな技術の集大成みたいなプログラムだな。

**名前は開発中のものです。** · 2009/08/12(水) 20:31:40

ゲームジャンルの中でも最も難しい部類に入るだろうな

**名前は開発中のものです。** · 2009/08/15(土) 14:15:27

海外でRTSツクールとか作られてないのかな

**名前は開発中のものです。** · 2009/08/15(土) 18:31:11

ツクールなんぞ最低だろ

**名前は開発中のものです。** · 2009/08/16(日) 17:59:36

RTSのアイデアをそれなりに実現できるなら、人によってはツクールもありだろうけど、RTSってゲームシステムが最も重要な要素だから、
ゲームシステムを自由にカスタマイズできるツクールなんてできるわけないので(処理速度要求されるRTSでは特に)、実現不可能だろうね。
絵とシナリオだけ差し替えたRTSなんてなんの面白みもない。

**名前は開発中のものです。** · 2009/08/17(月) 10:34:20

あったとしてもMOD的なものになりそうだね

**名前は開発中のものです。** · 2009/08/22(土) 23:57:29

もう７年ほどRTSを個人制作してる俺だが、
RTSでよく使うシステム…ﾕﾆｯﾄ選択とか管理とか指示とか地形、視界、経路探索、AI諸々のスクリプトサンプルを
シリーズで出そうとしたことがある
全部まとめるとblizzard式ウォーシミュの骨格が出来る予定だったが…

本体のほうでやることが多すぎて手がつけられませんでしたとさ

**名前は開発中のものです。** · 2009/08/23(日) 06:49:23

よく分からないが、ツールを作ろうとしたの？

**名前は開発中のものです。** · 2009/08/23(日) 15:00:05

>>614
俺、昔　ＲＰＧツクール2000でRTS作ってたよｗｗ

今となっては良い黒歴史だ。

**名前は開発中のものです。** · 2009/09/17(木) 23:09:29

Ａ＊で、広大なマップの経路を求めたいんだけど、
どういう方法が良いんだろうか。

２５６ｘ２５６くらいなら素直にできなくもないが、
１０２４ｘ１０２４くらいになると絶望的。
中継点置いたり、ノード数を減らすしか無いのかな。
動的マップだと方法が思いつかん・・・。

**名前は開発中のものです。** · 2009/09/17(木) 23:44:00

動的マップって地形が変化するって事？

**名前は開発中のものです。** · 2009/09/18(金) 07:32:11

>>622
建物や壁が建ったりする事。
グリッド単位のA*なら、塞ぐだけで良いんだけど、
マップがでかくなると計算量が爆発してしまう。
普通のRTSはどうやって管理してるのかなぁ・・・。

**名前は開発中のものです。** · 2009/09/18(金) 09:06:43

おれもそこで行き詰った
基本的には中継点設置とノード粒度の粗化が効果的な気がする
どっちの場合も、動的変化時の再設置or再計算のアルゴリズムが単純にならないんだよな

他には、一回計算した経路探索結果を記録しておいて後から使う方法とか
これも動的に変化した場合の対応が面倒そうなのは変わらないんだけどね

**名前は開発中のものです。** · 2009/09/18(金) 10:00:07

みんなユニット同士の衝突回避はどうやってるの？
ぼくは経路探索と障害物回避は別アルゴリズムでやるのが良いと思ってるのだが
建物とか壁とか木とかは、ユニット同士の衝突回避ができてれば同じ方法でいけないか？

**名前は開発中のものです。** · 2009/09/18(金) 10:29:24

障害回避は、経路の探索はできないんだよね。
そうだとすると、地形が変化してが経路が分断・接続された場合に、
実際の状況と異なって、行けないor行けるを判定できないよね？

**名前は開発中のものです。** · 2009/09/18(金) 10:31:03

ごめんちょっと一部修正
>そうだとすると、地形が変化してが経路が分断・接続された場合に、
↓
そうだとすると、地形・建物の状態が変化して経路が分断・接続された場合に、

**名前は開発中のものです。** · 2009/09/18(金) 12:55:05

それで良いと思ってる
細い道を建物とかで塞いだ場合、経路探索アルゴリズムの決定によってそこを通ろうとするユニットは建物にひっかかる

もしそうしないと何か気持ち悪いことになりそうな気がする

例えば、現在地と目的地の間に経路Aと経路Bの2つがあったとする
経路Aの方が近道なので、ユニットは経路Aに向かって移動している
敵が建物(またはユニット)で経路Aを塞いだ場合、動的なオブジェクトについても経路探索するならユニットは経路Bに向かうことになる

問題点その1、この時点でユニットは知っているはずのない情報に基づいて行動している
問題点その2、プレイヤーは敵の建物を破壊して進むことを望んでいるかもしれない
　　(アタック移動ならむしろ建物に攻撃するのが正しいのではないか)
問題点その3、敵が経路Aを塞いだり、開けたりすることでユニットは経路Aと経路Bの間を行ったりきたりすることがある

1については、最後に視界に入った障害物の位置を覚えておき、それに基づいて経路探索する方法もあるけど、
例をあげると長くなるので端折るが、それはそれで別の問題が起きる

なので、静的な障害物は経路探索で回避して動的な障害物は別の方法で回避するのがいいのではないかと思った
まあ経路探索以前にユニット同士の衝突回避で詰まってるんだけど

**名前は開発中のものです。** · 2009/09/18(金) 13:02:33

なんで人間は地図見ても爆発しないんだろうな

まあ、する人もいるけどな

**名前は開発中のものです。** · 2009/09/18(金) 13:37:39

問題1と3は同源だな
3は最初に探索した結果に元づいて最後まで歩けばOK(プレイヤーが再指示しない限り再探索しない)
1は自身も言ってるけど、障害物の位置を覚くことで回避でいいんじゃないか？
RTSはプレイヤーごとに目視済みのマップを持っているものが多いし(別の問題ってなんだろう？)
でも、AOE2ではこの問題起こるんだよね。プレイヤーごとの目視済みマップ持ってるはずなのに、
見えない情報による経路探索を行ってる。で実際にチートライクに情報を得るために使用できる
これはAOE2の仕様の欠陥だと思う

2はプレイヤーの選択肢の話
これのポイントは障害物は障害をするためのものってことで相手を通さないことが目的(少なくともその概念で処理する必要がある)。
破壊したい場合もあるだろうが、破壊困難な障害目的のオブジェクトにひたすら攻撃されても困るだろう
いずれにしてもプレイヤーの選択肢に依るもの

もうひとつは、建物だけなく地形もあり得るってこと、木が伐採されて資源にされて通り道ができてるのに、ものすごく遠回りするっておかしくないか？

>>629 それってフレーム問題だよね
人の脳は閾値超えないと意識に上がってこないから、適度に無意識的に無視されてるってことじゃない？

**名前は開発中のものです。** · 2009/09/18(金) 14:47:33

別の問題っていうのは動的な障害物を考慮して経路探索をして解なしになった場合どうするかってこと。
障害物のところまで見に行って情報を更新して、まだ障害物があったら別の障害物を見に行って、そこも残っていたら
また始めの障害物があるか見に行くとかやるのかな。スマートなやり方が思いつかない。

実際、>>628の問題は色々な解決方法があると思う
そもそもぼくが動的なものと静的なものの障害物回避を別アルゴリズムにしようと思ったのは、
経路探索でユニット同士の衝突回避する方法が思い浮かばなかったから…

>>630さんはユニット同士の衝突回避は経路探索でやっているの？
それが一番聞きたかったりする

**名前は開発中のものです。** · 2009/09/18(金) 15:39:49

>動的なものと静的なものの障害物回避を別アルゴリズム

ユニットのごく近い移動の部分は遠いマップの移動の経路探索とは別に処理するのがいいと思う。そこは同じ
静的と動的を分ける線の引きかたが自分とは違うだけのように思えるな

1.ゲームの開始から終わりまで経路の障害として変化しないもの(生成・消滅しない地形)
2.生成も消滅もある。ただし、頻繁ではないもの(建物と生成・消滅する地形)
3.生成も消滅も頻繁で、場所がどんどん移動するもの(ユニット)

このうちの1.、2.を静的なものとして扱って、3を動的なものとして扱うのがいいんじゃないかという話ね
ユニットは移動だけでなく他にもいろいろな動作を行うので、近い範囲の探索(探査)ってたくさん必要になるのでそっちのほうが頭が痛い
衝突回避(近い距離の探索)はA*でなくてもっと単純な方法でもいいと思うよ

なんだか、>>621の言う遠いmapの移動をA*でやろうとするとえらいことになる問題、の話とは少し違う話だね

**名前は開発中のものです。** · 2009/09/19(土) 09:52:44

ユニット同士はぶつかっても気にせずに
ごりごり押して通ってくでいいんじゃね？

**名前は開発中のものです。** · 2009/09/19(土) 10:22:54

各エリアが部屋みたいなタイプだったら、
入り口に中継ポイント置いて、部屋の中だけ細かく探索すれば良いのかな・・・。
オープンなフィールドタイプだとよく分からん。

>>633
アクションゲーならごり押しでもいい気がするが、
RTSってちゃんと迂回してよけてるよね。
止まってるやつはぶつかって壁沿い移動でも良いかと思ったが、
大勢が接近して動いてるとひっかかる・・・。

**名前は開発中のものです。** · 2010/09/25(土) 22:22:43

http://wma.haoting.com/21z/0/rydeen20090504/1/7af3253cd08d5546_5.wma?tflag=1285420792&pin=f48529d2f206821687e2b82afe97c8c7&ip=60.56.197.145

忍法帖【Lv=9,xxxP】 · 2011/08/15(月) 07:16:23.21

test

**名前は開発中のものです。** · 2011/09/15(木) 03:22:19.28

なんかいろいろ出てるけど、ＡＩ的な行動は重み付けが全ての基本じゃないの？

具体的には、静的な障害物の経路探索の結果得られた経路にそれぞれ経路ポイント
（例えば距離などから算出する重み）がついていて、その経路上に動的なオブジェクトが
いくつかあるなら、それぞれのオブジェクトが持つ重みを経路ポイントに加えていき、もっとも
ポイントの高い（または低い）経路を選択するって方法。

以下大文字は重みで、小文字はその重みに対するＡＩの係数だとすると
D: 目標までの経路が持つ距離の重み
A: 動的な障害物の種類Ａ（例えば強敵）が持つ重み
B: 同B（例えば雑魚）
などとすると、障害物Ａが２個、Ｂが1個ある経路の重みは
重み = D * d + 2*(A * a) + B * b
で得られる。

各オブジェクトの重みを適切に設定することが調整で、ＡＩが支配するキャラクターによる
各行動や判断の際に掛ける係数を決めることがＡＩを編集することになる。

これ以前に必要な目標の設定も、行動の設定も同一の重み計算に帰結させるのが、
基本的なＡＩの設計だと思うけど。

**名前は開発中のものです。** · 2011/11/15(火) 21:00:28.27

このスレまだあったのか

一ヶ月前に衝動的にRTSを作りたくなって作ってみた
http://hnw.go2.jp/RTS10b.zip

見た目は重視せず最低限RTSとしての体裁を取ろうとしたけれど、
A*なんて複雑なものは使ってないしユニットは重なる、戦略級のAIは未搭載と
まだまだ改善点が多い

**名前は開発中のものです。** · 2012/04/24(火) 10:48:03.62

http://toro.2ch.net/test/read.cgi/gamedev/1005866352/

**名前は開発中のものです。** · 2013/09/20(金) 21:23:56.95

10年以上続いてるスレww

経路探索って難しいよね
三角関数使えば出来そうな気がする

**名前は開発中のものです。** · 2014/08/12(火) 08:47:45.86

★2ch勢いランキングサイトリスト★

☆ +ニュース板
・ 2NN
・ 2chTimes
☆ +ニュース板新着
・ 2NN新着
・ Headline BBY
・ Unker
☆ +ニュース板他
・ Desktop2ch
・記者別一覧
☆ 全板
・全板縦断勢いランキング
・スレッドランキング総合ランキング
☆ 実況板
・ 2勢
・ READ2CH
・ i-ikioi

※ 要サイト名検索

**名前は開発中のものです。** · 2015/12/19(土) 14:19:17.40

プログラマはMacを使ってるってマジ？
http://hayabusa3.2ch.net/test/read.cgi/news/1450395043/

**名前は開発中のものです。** · 2016/03/22(火) 00:46:59.04

りあじゅー

**名前は開発中のものです。** · 2017/04/29(土) 14:53:52.59

これかな
https://s.cryuni.com/b.html?code=01ok29fn44oq