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

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

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

**名前は開発中のものです。** · 2007/03/23(金) 19:36:17

openaiとかAIのライブラリを使う、作る、公開する

**名前は開発中のものです。** · 2007/03/23(金) 22:42:50

>>516
どこからがＡＩと言っているのかわかりにくいけど、
コアなところは誰にでも作れるってもんじゃないしなぁ。
誰にでも作れるようにするには教育しかないんじゃないか？

**名前は開発中のものです。** · 2007/03/24(土) 12:36:34

重み付けの、パラメータ変数を外に出して弄らせるのが手っ取り早い

**名前は開発中のものです。** · 2007/03/24(土) 14:36:13

ブックマークがわりにして悪いが、参考になるしいいよな？
A*4beginners: http://www.gamedev.net/reference/articles/article2003.asp
KnowingPath: http://www.gamedev.net/reference/articles/article1841.asp
部隊行動1: http://www.gamasutra.com/features/19990122/movement_01.htm
部隊行動2: http://www.gamasutra.com/features/19990129/implementing_01.htm
AIstep: http://www.gamedev.net/reference/articles/article545.asp
ゲームに脳みそ作れ: http://www.gamedev.net/reference/articles/article574.asp
AIその1: http://www.gamedev.net/reference/articles/article784.asp
AIその2: http://www.gamedev.net/reference/articles/article785.asp
MotionPlanning: http://www.gamedev.net/reference/articles/article1125.asp
CognitiveModelingApproach: http://www.gamasutra.com/features/19991206/funge_01.htm

**名前は開発中のものです。** · 2007/03/24(土) 19:49:29

オブジェクトが多いと当たり判定をするだけでも大変だな
ストホ見たいに城壁を作れるようにするつもりだからやたら多くなる・・・

ほんとRTSは開発の壁が多すぎる（;´Д｀）

**名前は開発中のものです。** · 2007/03/24(土) 19:57:34

完成した暁には腐るほどプレイしてやんよ

**名前は開発中のものです。** · 2007/03/24(土) 20:36:17

>>521
壁おおいよねｗ
これ見てモチベーション維持してくれ
前編 http://www.watch.impress.co.jp/game/docs/20050310/aoe3.htm
後編 http://www.watch.impress.co.jp/game/docs/20050313/aoe3.htm
俺、これ見てがんばってる

**名前は開発中のものです。** · 2007/03/24(土) 22:08:50

empire of 豆腐のソース読みながらがんばる

**名前は開発中のものです。** · 2007/03/24(土) 22:17:32

おまいらそんながんばってもこんなロジックのゲームが
場か売れしちゃうんだぞ

【爆死確定】聖剣伝説ヒーローズオブマナ葬式会場
http://game11.2ch.net/test/read.cgi/handygame/1173165865/l50

まずこの映像をごらんいただきたい。

敵敵□□□□□　　　　　↓↓□□←←←　　　　自□□□□□□
敵敵□□□□□　　　　　↓↓□□←←←　　　　自□□□□□□
□□□□□□□　　　　　敵敵□□□□↑　　　　□□□□□□□
□□□□□□□　　　　　敵敵□□□□↑　　　　□□□自□□□
□□□□□□□　　　　　□□□↑□□↑　　　　□□□□□□□
□□□□□自自　　　　　□□□↑←自自　　　　敵敵□□□□□
□□□□□自自　　　　　□←←←←自自　　　　敵敵自□□□□

実はこれ、「聖剣伝説　ヒーローズ　オブ　マナ」で起こった事を写した決定的瞬間なのである

**名前は開発中のものです。** · 2007/03/24(土) 23:24:01

>>525
スレ見てきた。ヽ('A`)ﾉｳﾝｺｰって言ってる人ばっかで
バカ売れしてるとは思えないんだけど、ほんと売れてんの？

**名前は開発中のものです。** · 2007/03/25(日) 00:47:18

あのスクエニが、こんなポカをやってしまうのが本当なら、
RTSってそんなに難しいのかね？
確かに国産じゃ、あまり出てないけどな（洋ゲーはたくさんあるけど）。
フリー同人じゃ、empire of 豆腐と小サックスくらいか？
外にもあったっけ？

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

俺はGPGを参考にしてA*とメッセージドリブンで普通に出来た

**名前は開発中のものです。** · 2007/03/25(日) 09:28:53

>>526
スクウェアの新作で、聖剣の名前を冠して、
初動1万五千本って売れてないってことだと思う・・・
中古で値段下がりまくりだし、安いから買ってこよう・・・

**名前は開発中のものです。** · 2007/03/25(日) 09:48:11

LOMはよかった気がするよAIは並だった気が

**名前は開発中のものです。** · 2007/03/25(日) 09:49:36

empire of 豆腐ってなんですか？
ググっても見つけられなかったのでよかった教えてください

**名前は開発中のものです。** · 2007/03/25(日) 11:55:17

gl_kanjiの作者が公開してるゲーム
luaが混じってるからluaの言語知識もいるよ

**名前は開発中のものです。** · 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なんてなんの面白みもない。