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

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

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

**名前は開発中のものです。** · 2007/01/29(月) 00:32:37

>>494
コサックスみたいなの？

**名前は開発中のものです。** · 2007/02/02(金) 20:56:11

>>494
とりあえず土日スレにあった「小サックス2」みたいなのを作ってみれ。

**製作神** ◆3C/O4odLsY · 2007/02/02(金) 20:59:09

あれなかなか楽しめたな

**名前は開発中のものです。** · 2007/02/02(金) 21:13:26

小サックスⅡは、総勢５００人くらいだったか？
本家コサックスⅡは、最大６万４千ユニットが動き回るって触れ込みで
正に１０万に近かったが、３ギガヘルツとゲフォ６でも重すぎて
４千人がやっとだった。

**名前は開発中のものです。** · 2007/02/13(火) 18:56:15

HSPで、画面のスクロールとミニマップまで作れました。
次はBOIDみたいにユニットを集団行動させてみようと思います。

**名前は開発中のものです。** · 2007/02/13(火) 22:00:08

ｶﾞﾝｶﾞﾚ

**名前は開発中のものです。** · 2007/03/10(土) 00:30:06

経路探索から躓く俺（;´Д｀）

**名前は開発中のものです。** · 2007/03/11(日) 02:31:35

>>501
俺も初めて経路探索が必要になった時は躓いたよ。
で、もう一回ツリーからおさらいした。
Ａ＊一択だぜ！って言わずに、いろいろやってみるといいとおもう。

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

オンラインゲーム＆ PCゲーム情報サイト 4Gamer.net
http://www.4gamer.net/news.php?url=/patch/demo/cc3/cc3.shtml

そろそろ、コマコン3でるね・・・

**名前は開発中のものです。** · 2007/03/12(月) 21:06:18

>>137を見本に作ってみたいんだけど
＞node_successor.h = node_successorからnode_goalまでの移動コスト(適当なアルゴリズムで予想する)
ってところは障害物も考慮して計算するのでしょうか？

ただの障害物無視の最短距離で計算すると下のようになって、
さらに障害物を増やすとかなり時間がかかってしまう＼(^o^)／

　　　　　　　　　　 □□□■
　　　　　　　　　□□□□■
○□□□□□□□□□■　　　　　　●
　　　　　　　　　□□□□■　　　　　□
　　　　　　　　　　 □□□□□□□

○ｽﾀｰﾄ　●ｺﾞｰﾙ
□探査した場所　■障害物

**名前は開発中のものです。** · 2007/03/12(月) 21:07:43

「＼(^o^)／」は無視してくださいorz
コピペしてたのを間違って貼っちゃった

**名前は開発中のものです。** · 2007/03/14(水) 10:46:47

AIの話。
http://www.gamedev.net/community/forums/topic.asp?topic_id=436899
興味深い話してる感じだけど、英語苦手でなかなか読み進まないorz
↑の1の要約
「やぁ！RTSをはじめて作ってるんだけどさー、
経路探索とか障害物回避とか編隊行動（？）とか資源の探索＆回収とかは
実装したけど、それをまとめて計画するにはどうすりゃいいんだぜ？」

たまに出てくるinfluence map（影響力マップ？）ってなんだろ？

**名前は開発中のものです。** · 2007/03/14(水) 12:41:45

ZOCの事っぽいと予想

**名前は開発中のものです。** · 2007/03/14(水) 13:40:55

>>507
あ～！言われてみればそんな感じかも。
それにしても、
http://www.gamedev.net/reference/list.asp?categoryid=18#101
みたいな宝の山を前にして読むのに苦労するってのは涙がでるね；

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

やっぱり英語力は必要だよなぁ。

**名前は開発中のものです。** · 2007/03/15(木) 01:00:05

Ｉ　ａｍ　ａ　ｐｅｎ，

**名前は開発中のものです。** · 2007/03/15(木) 07:03:06

>>510
文学的な書き出しだな

**名前は開発中のものです。** · 2007/03/15(木) 07:28:14

>>511
ワラタ

**名前は開発中のものです。** · 2007/03/15(木) 11:08:23

おまいらエキサイト翻訳つかえ

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

心太(ところてん)を日→英、でてきたものを英→日。

**名前は開発中のものです。** · 2007/03/19(月) 09:48:35

>>513
eciteよりlivedoorの翻訳サービスの方がすこし頭いい気がするよ

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

AIを誰でも作れるようにするにはどうしたらいい？

**名前は開発中のものです。** · 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レスになってしまった。検証終わり。