プロジェクト演習Ⅳ インタラクティブゲーム制作 プログラミング4

Slides:



Advertisements
Similar presentations
Maxent model への挑戦 - 驚きとドキドキ感の理論 - 大野ゆかり Phillips et al. (2006) Maximum entropy modeling of species geographic distributions. Ecological Modeling 190:
Advertisements

ロボット制御のソフトウェ ア: シミュレータ試作 情報理工学部 情報知能学科 H 207051 中谷聡太郎.
あみだくじ AMIDA-KUJI 井上 康博 Statistical analysis on Amida-kuji, Physica A 369(2006)
Othello Let us cling together. メンバー 班長 杉本友宏 プログラマー 京谷貴平 アルゴリズム 佐野祐之 パワーポイント 菊澤遼平 発表 川本敏和.
プロジェクト演習Ⅱ インタラクティブゲーム制作
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第3回 配列(1) 情報・知能工学系 山本一公
人工知能概論 第4回 探索(3) ゲームの理論.
本日のスケジュール 14:45~15:30 テキストの講義 15:30~16:15 設計レビュー 16:15~16:30 休憩
「わかりやすいパターン認識」 第1章:パターン認識とは
ラスタグラフィックス (raster graphics)
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
プログラミング基礎I(再) 山元進.
コンピュータ囲碁の仕組み ~ 将棋との違い ~
Ex7. Search for Vacuum Problem
Ex8. Search for Vacuum Problem(2)
情報理工学部 情報システム工学科 ラシキアゼミ3年 H 岡田 貴大
アルゴリズムイントロダクション第5章( ) 確率論的解析
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
インタラクティブ・ゲーム制作 <プログラミングコース>
第5回C言語講座 ~ポインタと配列.
プロジェクト演習Ⅱ インタラクティブゲーム制作
線積分 T T y y x x 曲線 C 図のように、地上気温Tがx-y平面上に分布しているとする。そのとき、例えば近鉄の線路
シミュレーション論 Ⅱ 第5回 ランダムウォーク.
第四回 ゲーム                 05A1054         前田嵩公.
Handel-Cを用いた ちょっとレトロ な 「よけゲー」 の設計
オーサリングツール&ブラウザの 技術的トピック
C 言語について 補足資料 資料および授業の情報は :
プロジェクト演習Ⅱ インタラクティブゲーム制作 イントロダクション2
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
プロジェクト演習III,V <インタラクティブ・ゲーム制作> プログラミングコース
アルゴリズムとデータ構造 補足資料10-1 「騎士巡回」
インタラクティブ・ゲーム制作 <プログラミングコース>
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
アクションゲームにおけるプレイヤのレベルに応じたマップの自動生成手法の研究
インタラクティブ・ゲーム制作 プログラミングコース 補足資料
ロボットの協調動作の研究: マップ作成とマップ情報を利用した行動計画
プロジェクト演習Ⅱ インタラクティブゲーム制作
プログラミングを 体験しよう 選択情報⑧.
Ex7. Search for Vacuum Problem
プログラミング 4 探索と計算量.
第2回課題 配布した通り.氏名・学生番号を忘れないこと.
プログラミングを 体験しよう 選択情報⑧.
AI かどうか? 木下研究室 David Chen
プロジェクト演習Ⅳ・Ⅵ インタラクティブゲーム制作
疑似乱数, モンテカルロ法によるシミュレーション
プロジェクト演習III,V <インタラクティブ・ゲーム制作> プログラミングコース
「アルゴリズムとプログラム」 結果を統計的に正しく判断 三学期 第7回 袖高の生徒ってどうよ調査(3)
★C++/オブジェクト指向実践企画★ Othelloゲーム作成
Handel-Cを用いた パックマンの設計
プロジェクト演習Ⅳ・Ⅵ インタラクティブゲーム制作
情報工学Ⅱ (第9回) 月曜4限 担当:北川 晃.
プログラミング入門 電卓を作ろう・パートI!!.
本当は消去できていない!? ~データを完全消去する方法~
本当は消去できていない!? ~データを完全消去する方法~
プロジェクト演習III,V <インタラクティブ・ゲーム制作> プログラミングコース
問題 あなたはポケモンGOをやっています. これから5か所のポケモンの巣(ポケモンがよく出る場所)を回って レアポケモンを捕まえに行こうと思っています. しかし,持ち物を見たらハイパーボール1つしかありませんでした. なるべくCPが高い(強い)レアポケモンを 捕まえたいのですが, 何か所目で捕まえれば.
情報工学科 4年 中山直飛 中間発表.
バネモデルの シミュレータ作成 精密工学科プログラミング基礎 資料.
平面走査法を使った 一般線分の 交点列挙アルゴリズム
アルゴリズム入門 (Ver /10/07) ・フローチャートとプログラムの基本構造 ・リスト ・合計の計算
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
cp-15. 疑似乱数とシミュレーション (C プログラミング演習,Visual Studio 2019 対応)
プロジェクト演習Ⅳ・Ⅵ インタラクティブゲーム制作
参考:大きい要素の処理.
第7章 そろそろ int 以外も使ってみよう! ~データ型 double , bool~
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
人工知能概論 第4回 探索(3) ゲームの理論.
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
プロジェクト演習Ⅱ インタラクティブゲーム制作
プログラミング演習II 2004年11月 2日(第3回) 理学部数学科・木村巌.
Presentation transcript:

プロジェクト演習Ⅳ インタラクティブゲーム制作 プログラミング4 2012/12/12 AIの基礎 経路探索アルゴリズム

今日の内容 ゲームで扱うAIの初歩 経路探索アルゴリズム 確率の扱い方 ファジィ理論 ミニマックス法 壁にぶつかってゴスゴスしない敵を作ろう 空間分割グラフを作ろう(できるかな?)

AI 特定の選択肢の中からそれっぽく選択 トランプや将棋のような思考AI 一直線では進めない地形から経路を発見 確率をそれっぽく設定し、 乱数をうまく使ってそれっぽく見せる ファジィ理論も併用すると効果的 トランプや将棋のような思考AI ミニマックス法 取り得る選択肢に評価点を付けて、自分に有利、 相手に不利になるような選択肢を採っていく 一直線では進めない地形から経路を発見

とりあえず乱数は 自由に使えるようになろうね srand()で種を初期化 その時点での時刻を使うのが一般的 srand((unsigned int)(timeGetTime()%65536)); rand()が0~RAND_MAXの値を返す 実数にキャストして0.0~1.0の値にする もしくは%演算子で好みの範囲の値にする ただし、バラツキが出るようになるので注意

正規分布は知っておこう 例えば、RPGのダメージがこの分布に従ってばらけると、とてもよろしい感じ 3D6とかが一般的

ファジィ理論 ブーリアンで白黒ハッキリ付けるのではなく、中間の値を許容して良い具合にしようぜ的なサムシングを作り出す何か RPGのダメージで言うなら「大当たり」「中当たり」「カス当たり」が滑らかにブレンドして出力されるようなイメージ 正規分布と=ではないが、ファジィ理論を用いて希望通りの分布を作る手法も存在 AIのようにどっちつかず感を出したいものには有用

ふおー! そっち行きてぇ! ゴスゴスゴスゴスゴス 今回のメインディッシュ ふおー! そっち行きてぇ! ゴスゴスゴスゴスゴス 単に「ターゲットの方向に向かう」だけではゴスゴスする 経路探索が必要! ダイクストラ法とか A*法とかがあります 今回はそれらをベースとしつつ、オリジナルの手法を伝授するよ! GOAL

とりあえず2次元で セルに区切って考えよう シミュレーションRPGみたいですね 実装のことを考えるなら、とりあえずは 2次元配列で 後々のことを考えるとリンクリストの方が使い勝手が良いが、まずは手を動かしやすいやり方でGo S G

そもそも 本当にたどり着けるのか? 右図のようになってしまったらそもそも到達不能である スタート地点から順繰りにセルを辿っていたら分からない… 霊媒師の人「発想を逆転させるのよ! ナルホドくん!」 S G うおー! さおー!

ゴール地点からの距離を 各セルに記録していく! そうすれば、スタート地点から「距離の少ない方」を選んでいけばいいだけ 同じ距離のセルが選択できる場合は、乱数で選ぶか、ゴールへの直線距離が近い方を選ぶなどすればいい 14 15 16 17 18 13 12 S 11 10 9 8 7 6 5 4 3 2 1 G

到達不能な場合は? 経路がない場合は途中で距離埋め処理が打ち切られるので、到達不能であることがすぐに分かる 距離が未記入の隣接セルが無くなった時点で探索終了にすればいい その時点で未記入のセルには到達不能 E S 8 7 6 5 4 3 2 1 G

実装に際してのアレンジ 全部のセルを見通せると千里眼キャラになってしまうので、情報を得られるセルを限定するとか ジャンプなどの特殊アクションで到達できる場所はコストを高めに見積もるとか ゴール地点や障害物が動かない場合は、一度作った距離埋めマップが再利用可能 実際には動くことが多いと思うので、 距離埋め処理は可能な限り高速化すること!

ボンバーマンみたいな マップだったらいいけれど まぁ、斜めるわけです だが2次元格子分割は、こういう場合でも有効 障害物を含むセルを 進入禁止にすればいい ただし、妙にカクカクした動きになるのは 想像付くでしょう セルを細かくしたら、 容量的にも処理的にも 大変よね? S G

じゃあこんな風に 分割すればいいじゃない 次の点がポイント 凸形状にすることで、セル内のどの点からでも隣接セルとの境界地点まで一直線で向かえる 点と線分の最近接点を求めれば一直線ルートはすぐに求まる 各セルが隣接セルのIDと、境界線分の座標を保持すれば、後は格子状の場合と大差ない GOAL

まとめ 乱数とは、とりあえずお友達になろう ゴスゴス君からは卒業しよう まずは2次元の格子で考えて実装してみる 多角形分割は頑張れば自動化できるが、 厳しい場合は事前計算でもOK コンフィギュレーション空間、に注意しよう 経路探索はゲームに限らず使える上に、 「アルゴリズムプログラミング」の神髄でもあるので、是非トライしてみよう!