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

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

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

**名前は開発中のものです。** · 2007/03/25(日) 12:02:42

>>532
見つけることができました。ありがとうございます。

**名前は開発中のものです。** · 2007/03/25(日) 12:05:24

つーか、このスレの上のほうにアドレスあった気がするけど

**名前は開発中のものです。** · 2007/03/26(月) 00:22:08

そういやファルコムのモナークモナークはRTSに入るのかな。

**名前は開発中のものです。** · 2007/03/26(月) 17:14:07

>>527
アハリスは、内政要素がないからRTSとは言えないな。

**名前は開発中のものです。** · 2007/03/27(火) 10:03:12

>>536
内政要素なくてもRTSはRTSだと思うけど
アハリスは知らんが

**名前は開発中のものです。** · 2007/03/27(火) 10:04:21

アハリスって、コサックスが元ネタの奴かｗ
どうみてもRTSですｗ

**名前は開発中のものです。** · 2007/03/27(火) 11:19:49

>>536が言いたいのは

strategy = 戦略
tactics = 戦術

とした時にRTSは戦略だから内政無いとおかしいってことだろ
strategyには意味として戦術も戦略も含まれてるからどっちでもいい気もする
個人的にはジャンルのくくりなんてそもそもどうでもいいと思うが

**名前は開発中のものです。** · 2007/03/27(火) 11:31:21

そんなくだらん話より、技術的な話をしたいんだ！
と、うちの犬が言ってました。

**名前は開発中のものです。** · 2007/03/27(火) 17:14:07

そんな風にあいまいにしておくと、そのうち
自機がパワーアップするシューティングも、ＲＴＳだと言えるようになってしまうのだが

**名前は開発中のものです。** · 2007/03/27(火) 18:03:41

言えるようになって制作に何か問題でも出るのか？

下らん定義づけはゲハでやれ

**名前は開発中のものです。** · 2007/03/28(水) 00:11:58

ずいぶん前に、現物のゲームがどーしたこーしたを話すスレを
別に誰かが用意してなかったっけ？
それ以降、こっちのスレは技術的な話をすることになったはず

**名前は開発中のものです。** · 2007/03/28(水) 00:33:33

今のところ無くてもそれほど困らない機能なんだけどさ、
マップをランダム生成するときに特に深く考えずに中点変位とかで
作ると自然といえば自然な地形にはなってくれるんだけどさ
いい具合に崖があったりとか谷があったりとか、
説明しにくいんだけどアクセントがつきにくい気がするんだけど
普通、どうやって地形生成してるんだろ？

**名前は開発中のものです。** · 2007/03/29(木) 19:00:32

来月PS2で出るグリムグリモアってのがRTSだな。

**名前は開発中のものです。** · 2007/03/29(木) 21:16:18

技術的な話でないものはこちらでお願い。

RTS のデザインについて（実装技術は除く）
http://pc11.2ch.net/test/read.cgi/gamedev/1007303109/

**名前は開発中のものです。** · 2007/04/03(火) 18:07:24

まぢれす
ＡＩなんか誰にも作れない。

**名前は開発中のものです。** · 2007/04/04(水) 03:37:21

>>547
いったい誰にﾏｼﾞﾚｽしてるんだ？

**名前は開発中のものです。** · 2007/04/05(木) 19:19:40

オブジェクトや地形ってどう管理すればいいの・・・
経路探査を遅くしたくないから2次元にしてみたいんだけど恐ろしくメモリ食っちゃう

**名前は開発中のものです。** · 2007/04/05(木) 19:35:20

むしろ、経路探索をどう処理しているか気になる

戦術シムのなら作ったんだけどなー
RTSでもマップをヘックスとかスクウェアとかに分割してやるんだろうか

**名前は開発中のものです。** · 2007/04/06(金) 12:58:59

>>549
どういうやり方やってるのかわからないけど、メモリの使用量と、処理量はトレードオフだから、現実的に利用できる落としどころを見つけて、後は最適化がんばるしかないんじゃないの？

**名前は開発中のものです。** · 2007/04/12(木) 00:18:57

>>544

中点変異ってダイヤモンド・スクエアアルゴリズムのこと？
ダイヤモンド・スクエアアルゴリズムだとheightの取り幅によるけど、
平坦か、とげとげした地形になりがちのような気がする。

例えば、ダイヤモンド・スクエアアルゴリズムで大体の地形を作った後、
1次元フラクタルで溝を掘ったりとか、段階ごとに複数のアルゴリズムを
組み合わせたりすればいいんじゃないか？

**名前は開発中のものです。** · 2007/04/20(金) 01:36:14

>>552
遅いレスですまん。見てなかった。
ダイアモンド・スクエアステップでもいいし、quadtreeっぽいのを作りながら
単純にどんどん分割でもいいんだけど細分化してくことを言ってた。
とげとげ地形は、xz平面の１辺１ｍとした時に高さも１ｍ単位にすると
角度が急になりすぎるんでとげとげになるね。
そこから高さ成分は適当に縮小してあげれば
（y * 0.2とか）なめらか地形になるよね。
高さ8bitだと値の範囲が足りないけど、16bitとか32bit使えばそれなりに幅でるし。

やっぱり、地形作ったあとに谷とか川とかを作る作業が必要なのかな。

**なんとなく張っとく** · 2007/04/24(火) 06:49:27

AI

* FEAR
o http://fear.sourceforge.net/
* PathLIB
o http://pathlib.hildebrand.cz/pathlib.html
* MicroPather
o http://www.grinninglizard.com/MicroPather/

AI Links repositories

* Generation5 - Articles
* GameDev.net -- AI
* AI on the Web
* AngelCode.com - reference database
* Game Research and Technology
* IGDA - AI SIG
* The Game AI Page
* aboutAI.net
* aboutAI.net
* Generation5 - Competition
* AI Center - Site Map
* gameAI_news

[edit]
SDKs

* FEAR :: Foundations for Genuine Game AI
* MetaAgent, A Steering Behavior Template Library - Compiling Meta Agent
* OpenSteer
* OpenAI
* OpenSkyNet

**なんとなく張っとく** · 2007/04/24(火) 06:50:04

General and Specific Architecture Articles

General Architectures

* Half-life AI (MUST READ)
* AI Horizon: Essays on Artificial Intelligence, from the Basics to the Advanced
* AI Halo
* Gamasutra - Features - Handling Complexity in the Halo 2 AI
* Gamasutra -"Decision-based Gameplay Design"
* Complete Game AI: Volume I
* Item Management Systems

PathFinding

* Huge Theorical exhaustive Book on pathfinding
* Terrain analysis on age of empire (MUST READ)
* AI terrain
* Amit's A* Pages
* An optimal pathfinder for vehicles in real-world digital terrain maps
* Smart Moves: Intelligent Path Finding
* Toward More Realistic Pathfinding
* All FPS pathing problems in a presentation
* 3d path
* C++ Group Pathfinding Basic Library and Test Tool
* ASTAR pathfinding algorithm in Ogre - Nice example with source

**なんとなく張っとく** · 2007/04/24(火) 06:52:54

Group AI
* Boids (Flocks, Herds, and Schools: a Distributed Behavioral Model)
Tactic
* Game AI and Tactical AI
Steering
* List : steering Behaviors For Autonomous Characters
Rule-Based System (RBS)
* Rule-Based Systems and Identification Trees
Neural Networks (NN)
* tensor (small NN)
Fuzzy logic (FL)
* aiGuru.com
Finite State Machine (FSM)
* Visual Finite State Machine AI Systems
Decision Tree (DT)
* generation5 - Binary Decision Tree implementation in C++
Emotion
* generation5 - VPI: Virtual Personality Interaction
Lag
* Defeating Lag With Cubic Splines Or AI path moves Cells
Expert Systems
* Expert Systems
Learning Systems
* AI character learning

**名前は開発中のものです。** · 2007/10/15(月) 00:17:15

A*がいまいち理解できないのでageておく

**名前は開発中のものです。** · 2007/10/16(火) 01:37:08

実例で学ぶゲームAIプログラミングがいい感じです。
経路選択から、集団でのAIまでカバーという・・・

障害物ありの2Dマップで、メッシュに区切って、A*での経路選択も解説されてる

サンプルのAIは、アクションゲームよりなので、
そのまんまとはいえないけど、かなり使えると思う

目次と、サンプルプログラムのダウンロードはこちらから
http://www.oreilly.co.jp/books/9784873113395/

Amazon.co.jp：実例で学ぶゲームAIプログラミング: 本: Mat Buckland,松田晃一
http://amazon.co.jp/dp/4873113393/

**名前は開発中のものです。** · 2007/10/18(木) 11:26:43

>>557
総当りで、無駄を省いたものと思ったらいい。

**名前は開発中のものです。** · 2007/10/21(日) 21:26:00

表紙の動物が気持ち悪い

**名前は開発中のものです。** · 2007/10/23(火) 23:27:40

>>558
この本のソースコード試した人いる？
http://www.wordware.com/files/ai/files/Buckland_AISource.zip

HandyGraphFunctions.hの中のCreateAllPairsTable()が失敗しちゃうんだけど誰かわからないかなぁ。

//グラフ作成
SparseGraph<NavGraphNode<>, GraphEdge> graph( false );
//グリッド作成
GraphHelper_CreateGrid<SparseGraph<NavGraphNode<>, GraphEdge> >( graph, 32, 32, 16, 16 );
//パステーブル作成
std::vector<std::vector<int> > table = CreateAllPairsTable<SparseGraph<NavGraphNode<>, GraphEdge> >( graph );//実行時エラーが出る

Graph_SearchDijkstra<graph_type>::Search()の中のconst Edge* pE=ConstEdgeItr.begin()で
_DEBUG_ERROR("list iterator not dereferencable")が出てるっぽい。

**名前は開発中のものです。** · 2007/12/06(木) 04:12:24

保守

A*がわかりそうでわからない
当分は壁伝いねずみ方式のままだな

**名前は開発中のものです。** · 2007/12/07(金) 15:26:24

質問です
以前、マップを升目で分割するとかいう話が出ましたが、これは
「画面には表示しないが、データ上はターン制シミュのように升目を単位に移動する」
ということですか？

**名前は開発中のものです。** · 2007/12/13(木) 15:25:21

俺はRTS作った事ないからあくまで「自分が作るならこうするだろう」的憶測だけど、
「移動目標地点」を決める時に升目で計算して
おおざっぱな座標が求められればそれでいいんじゃないのかな？

「指定された座標の”近くまで”移動する」って感じで。

**名前は開発中のものです。** · 2007/12/14(金) 21:57:36

何をするのかはだいたい分かりました
それをやれば計算量がそれなりに減るのですか？

**名前は開発中のものです。** · 2007/12/14(金) 22:21:39

それは、君が現在何をやっているかを知りえない私たちにはわからない

**名前は開発中のものです。** · 2007/12/16(日) 00:28:11

というか本当に分かってるのか怪しい。

**名前は開発中のものです。** · 2007/12/30(日) 21:58:55

障害物が固定だと最適化の方法をいくつか思いつくことができるけど、
建物とかあとからあとから頻繁に作られる障害物のことを考えると・・・ほんと難しいな

今のところ、最初に大きく区切ったもので探索して、
通れそうなら小さいメッシュに区切ったもので探索
重くなる場合は何フレームかに分けて・・・AIや描画のことも考えると激重にならないか心配・・・

**名前は開発中のものです。** · 2007/12/30(日) 23:16:19

A*使え。分かんない奴は何がわからないんだ？
そもそも再帰が分かってないんじゃないの？

**名前は開発中のものです。** · 2007/12/30(日) 23:30:08

>>568
そうなんだよね大雑把計算用のマップ作ると障害物が出来たり消えたりしたときに経路が変ったのを大雑把マップに反映させるのが大変
軽いいいアルゴリズムがなかなか思いつかない
市販のゲームはどうやってんだろ

**名前は開発中のものです。** · 2007/12/30(日) 23:59:39

>>569
ちょっと弄ってはいるけどA*を使ってる

ほんと昔のゲームはどうやっていたんだろう

**名前は開発中のものです。** · 2007/12/31(月) 03:33:28

AgeOfEmpire1 とか、適当だよ。
経路あるのに、凹凸があるとすぐに引っかかる。

**名前は開発中のものです。** · 2007/12/31(月) 16:34:44

長い障害物は地形か壁ぐらいだし
接触したらある程度それに沿って探査するとよさそうなんだけど・・・A*にうまく組み込めない／(^o^)＼

あと、ルートがない場所とかどうやって判断するんだろう
RTSじゃ壁で囲むとかよくありそうだけど

**名前は開発中のものです。** · 2007/12/31(月) 19:49:43

>>573
塗りつぶしアルゴリズムで閉じた領域を探すとかできそうだけど。

**名前は開発中のものです。** · 2007/12/31(月) 19:54:28

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

↑あらかじめ塗りつぶすと、以下のように区画分けができる。
省略しているが、区画IDはその区画の全地点に書かれている。

１ ■２ □□■３ □□□□
■■□□□■□□□□□
□□□□□■□■■■■
□■□□□■□■４ □□
□■□□□■□■□□□
□■□□□■□■□□□

これで、ユニットがある区画IDにいるとして、目的地の区画IDと
同じかどうかによって。移動できるか否かを一瞬で判断できる。

**名前は開発中のものです。** · 2007/12/31(月) 20:21:36

最適化できるポイントとしては、

壁（通り抜けできないオブジェクト）が作られたときに周囲のマスを見て
同じ区画IDを分割してたら、その区画だけ塗り直し。

壁が破壊されたときに違う区画IDを接続してたら、区画IDの小さいほうで
大きいほうを塗り潰す。（IDの連番化のタイミングはお好みで）

A*で探索するときには、開始地点と同じ区画IDの領域しか探索しない。

などがあると思われる。

**名前は開発中のものです。** · 2008/01/01(火) 09:32:52

ためになる

**名前は開発中のものです。** · 2008/01/01(火) 15:29:00

なるほどー

**名前は開発中のものです。** · 2008/01/02(水) 03:08:33

>>558で、A*の解説が載ってるね。

**名前は開発中のものです。** · 2008/01/02(水) 13:26:46

地形とかゲーム中はずっと固定なら最初に処理しておけばいいけど、
オブジェクト作るたびに調べるのは逆に処理が多くなったりしない？

**名前は開発中のものです。** · 2008/01/02(水) 14:09:35

早くする方法あると思うけどそれは表に出てないのかも

**名前は開発中のものです。** · 2008/01/02(水) 15:27:52

>>580
区画の分割で使うアルゴリズムはWindowsのペイントで画像の塗りつぶし処理するときの
アルゴリズムと同じ（シードフィルアルゴリズム）だから、そんなに遅くなることは無いと
思うけど・・・低スペックのPCも動作対象？（汗

具体的な処理の多さ、ゲームシステム的にどんなペースで障害物を作っていくか
（消えていくか）にもよると思う。
たとえばAoE系のRTSでは、森も障害物の一種で、採取されると消えていく。
また、「塔の死角を埋めるため」や「じっくり内政するため」に森と壁を組み合わせて
区画を作っていくこともある。総合的に見ると、イベントとして一番多いのは森の減少だと思う。

つまり、ほぼ森が減るたびに区画分け処理が必要になるはず。
たぶん最近のPCなら速度は問題にならないだろうけど、再帰が何度も走ることによる
メモリの細分化など、ゲーム特有の心配事が出てくる可能性はあるかもしれない。

この場合、森が減っても最低でもX秒の間隔を空けないと区画を更新しないとか、
そういう姑息な逃げ方もある。移動ルートの有無判定に使うなら、数秒くらい遅れても
気にする人はほとんどいないだろうし。

**名前は開発中のものです。** · 2008/01/02(水) 15:45:46

それはAOEなめすぎ

**名前は開発中のものです。** · 2008/01/02(水) 16:43:51

壁壊しても数秒は通れないなんてのはさすがにあり得ない
少なくともAOCでは

**名前は開発中のものです。** · 2008/01/02(水) 17:34:12

区分けの塗り替え方は分かるけど、区分けするかしないかの判断方法が知りたいです

そういえば、なにかのゲームで壁に穴を開けてもすぐに通れなかったことがあった
ストロングホールドだったかな

**名前は開発中のものです。** · 2008/01/02(水) 20:43:29

お風呂入っていたら思いついた・・・
よく考えて質問すればよかった。ｽﾏｿ

**名前は開発中のものです。** · 2008/01/02(水) 23:01:47

移動可否判定だけのための区画分けするなら、実際に移動が指示されたときだけ
やればいいという投げやりな最適化もある。この方法なら、細かい森や壁の増減は
パフォーマンスに影響しない（はず）。

**名前は開発中のものです。** · 2008/01/04(金) 16:18:54

作成したオブジェクトに隣接している空白マス同士全て繋がっていれば、区分けの必要はないと判断できるから
隣接した空白マスから探索を始めて、全て繋がっているか調べればいいんじゃ？
"探索は通り抜けられないオブジェクト沿いにする"って条件をつければ探索するマスも少なくて済みそう。
これならどうだろう？

**名前は開発中のものです。** · 2008/01/04(金) 16:32:34

そもそもその方法って、探索対象から閉区間を除外するってだけだから、閉区間がないマップだとメリットがないよね
閉路をA*でまともに探索したら全探索になるからそういう意味では意味もあると思うけど、RTSのマップって閉区間への移動ってあんまり多くない気もするしなあ

http://www.o440.info/developing/findpath/

ここでやってるようなやり方でオブジェクトが頻繁に変更されても対応できるようなのがベストだと思うんだが

**名前は開発中のものです。** · 2008/01/04(金) 21:20:34

>>589
そのページを見て思ったこと。
長方形にこだわる理由が薄いと思った。

そのページの手法とシードフィル（塗りつぶし）と比較すると、シードフィルは
常に高さ1の長方形を利用する、再帰的な空間分割アルゴリズムとみなせる。

なので、もし閉空間が無いマップなら、（たぶん）再帰の順序を記録していけば
一回でグラフ化までやれるはず。
（閉空間がｎ個ある場合は何も考えずに書くとｎ回の全検索が要るかもしれないが）

ただ、あんまり細切れの空間にしてしまうとA*を高速化するという
本来の目的から離れてしまう可能性がなきにしもあらず。

いくつかの「高さ1の長方形」を結合して「高さnの長方形＋小さな空間」に
することで、全体的に見てそのページのアルゴリズムの欠点（空間分割の遅さ）
を改善できるんじゃないかと思った。

**名前は開発中のものです。** · 2008/01/04(金) 21:57:06

つづき。

共通しているのは、凸凹が多いマップだと空間分割が遅くなる（または
小空間の結合がうまくいかない）だろうということ。
それでも、壁や木などのユニット以外の障害物が相手ならば有効だと思う。

----

しかし、ユニット（動く小さな障害物）を含めて処理しようとすると
マップは凸凹だらけになってしまい、空間分割をかなりの頻度で
行う必要が出てきてしまうのではないか？

なので、少し荒いマップ（4x4程度の大きなセル）を用意して
「障害物の密度」を集計し、50％とかの閾値を越えたら「壁」、以下なら「道」と
いうことにしてしまい、そっちの荒いマップで空間分割＆グラフ化
→分割漏れのセルを周囲の空間グラフに結合。

みたいな最適化が必要になってくるのでは・・・
ただ、荒いマップを使う場合、アルゴリズムとして評価するのが
難しくなってしまうというデメリットがあるのでおいらも分からん・・・

**検証1/2** · 2008/01/04(金) 22:14:49

少し考えてみる・・・。以下のような8x8のマップがあるとする。■は壁。

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

これを左上から単純に塗っていくと以下のようになる。

１１１１１１１１
２２２ ■■■■Ｅ
３３３３３ ■ＦＦ
４４ ■■９ ■■■
５５ ■ＡＡＡＡＡ
６ ■■■ＢＢＢ ■
７７ ■■ＣＣＣＣ
■８ ■ＤＤＤＤＤ

悪くはないが、左上、右下などに疑問が残る結果となった。

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

次に、4x4、2x2の荒いマップを考え、個々のセルに対応する
壁の個数を集計する。

・4x4のマップ(各セルの最大は16)
３　７
８　１

・2x2のマップ(各セルの最大は4)
０１２１
０２２２
１３０１
１３００

それぞれ、閾値を50％（8、2）とし、それに満たない領域は
「壁が無い」と見做して優先的に塗る。それ以外は普通に塗る。

**検証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*でやろうとするとえらいことになる問題、の話とは少し違う話だね