［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？ ライター：米田 聡 スクウェア・エニックスが2012年11月23日と24日の両日開催した「スクウェア・エニックス オープンカンファレンス」の最後には「AIセッション」が用意されていた。AIセッションは前半と後半に分かれ，前半は「ファイナルファンタジーXIV: 新生エオルゼア」（以下，新生FFXIV）における経路探索の実装に関する実践的な解説，後半はゲームAIの第一人者とも評される三宅陽一郎氏による，Luminous Studio用AIエンジンのやや概念的な話という構成だった。本稿では，まず前半の，より実践的なセッションから紹介してみたい。 テーマは，「MMORPGでマップ上を移動する敵NPCの経路をどう決めるのか」である。複雑で広いマップを有するMMORPGでは，移動する経路を賢く選択
TSPLIB
TSPLIB is a library of sample instances for the TSP (and related problems) from various sources and of various types. Instances of the following problem classes are available. Symmetric traveling salesman problem (TSP) Given a set of n nodes and distances for each pair of nodes, find a roundtrip of minimal total length visiting each node exactly once. The distance from node i to node j is the same
浮動小数点数型と誤差
有限桁 Ｃ言語で扱える実数値は，２進数の有限小数で表された数値である．例えば次のようなものである． 1.5(10) = 1.1(2) 3.25(10) = 11.01(2) 理論的には小数が無限に続く値でも，そのうちの有限個の桁数でその値を表すしかない． 例えば，0.1 を２進数の小数で表すと 0.1(10) = 0.000110011001100110011...(2) と無限に続くが，コンピュータの内部では有限桁で丸められている． このような場合には，本当の値ではなく，近似値でしか表すことができない． 指数表記（浮動小数点表記） 科学計算では非常に大きな実数値や非常に小さな実数値も扱うことがある． そのようなときには，通常の１０進数の表記ではなくて，次のような指数表記で表すれば 無駄な 000...000 という桁を表記しなくてもよくなる． 1234567890000000000000
PopCntの速度再び2011 - 小宮日記
3年ほど前、popcntの速度を調べたことがありますが http://d.hatena.ne.jp/mkomiya/20070905/p1 bitを数える http://vivio.blog.shinobi.jp/Entry/137/ ふと思い出したので、またちょっと調べてみました。 以前は、ビット数少ないとアセンブラ速いけど 表引きC言語は安定してるよね 的な幕引きでしたが、 アセンブラでマジックで計算するコードをサイボウズラボの人が書いていたので、 http://developer.cybozu.co.jp/takesako/2006/11/binary_hacks.html それを加えてみます。 あと、団子の人のSSEコードもあったのでそれも追加。 LS3600さんが、SSE4.2でPopCntの使い方も紹介されてましたが、 今使ってるマシン(core2duo E7500)がSSE4
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
大規模ネットワークの性質と先端グラフアルゴリズム - iwiwiの日記
本日，PFI セミナーにて「大規模ネットワークの性質と先端グラフアルゴリズム」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模ネットワークの性質と先端グラフアルゴリズム View more presentations from iwiwi Ustream の録画もあります． http://www.ustream.tv/recorded/27531606 内容としては，以下のようになっています． 現実世界のネットワークの特徴量と性質 次数分布 平均距離 クラスター係数 その他の特徴量 木っぽさ それらの性質を活用したグラフアルゴリズム セオリー方面 近接中心性の近似 コンパクトルーティング 支配集合問題の近似 プラクティカル方面 最短路 密部分グラフ列挙 可視化 タイトルは 1 年前にやった PFI セミナーと似ていますが，内容はあまりかぶっていません．今回は，グ
Fast inverse square root - Wikipedia
Lighting and reflection calculations, as in the video game OpenArena, use the fast inverse square root code to compute angles of incidence and reflection. Fast inverse square root, sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates , the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number in IEEE
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
楓 software: 平方根の逆数の高精度化
« 逆数の高精度化 | メイン | テクスチャマッピングの高速化 その3 » 2008年02月23日 x86 SIMD Technique:: 平方根の逆数の高精度化 Tweet @jin1016をフォロー 平方根の逆数を求める命令として、_mm_rsqrt_ss / _mm_rsqrt_ps がある。 でも、これは 11bit 精度しかない ( 11bit 精度だと、10 進数で3桁程度 ) 。 と言うことで、11bit 精度で得られた平方根の逆数の近似値をニュートン-ラフソン法 ( Newton-Raphson ) を用いて高精度化する。 SSE のソースコードは以下。 // 22bit 精度で平方根の逆数を求める。 // 1/√x = 3/2 * x0 - 1/2 * a * x0^3 を用いる inline __m128 m128_rsqrt_22bit_ps( const
approximate
これはどの程度の精度があるのでしょうか. まず誤差をどう表すかを考えます. r = 1 / √a を正しい値とします. 単純に |y - r| を誤差としても構いませんが, a が 0 に近いときや大きいときでも同じように評価するために を誤差と定義することにします. 例えば y が11bitまで正しければ ε は 2-11 程度になります. y = r + rε と変形して z に代入します. a = r-2に注意 (r + rε)3 = r3 + 3 r2(rε) + 3 r (rε)2 + (rε)3 となりますが r に比べて rε は十分小さいので3乗の項は無視します. z = 3/2 * (r + rε) - 1/2 * r-2 * (r3 + 3 r2 rε + 3 r (rε)2) = 3/2 * (r + rε) - 1/2 * (r + 3rε + 3 r
C++プログラミング日記 -逆数平方根の近似(2)
前回の「逆数平方根の近似」の続きです。 逆数平方根の近似を利用して平方根関数を実装してみました。 今回の実装ではcrtのsqrt関数と同等にするため0以下の実数に対する処理を加え精度を上げています。 その状態でもcrtのsqrt関数よりかなり高速です。 ついでに逆数平方根関数にも同等の処理を追加しました。 sqrt float sqrt( const float& V ) { if( *(long*)&V <= 0 ) { if( ( *(long*)&V & 0x7FFFFFFF ) == 0 ) return V; long r_bits = 0xFFC00000; return *(float*)&r_bits; } long x_bits = *(long*)&V + 0xFF800000; long y_bits = 0x5F3759DF - ( *(long*)&V >> 1
数値演算のアルゴリズム
３Ｄの計算処理では、「正確性よりも速度を求める」という場合がよくあります（特にリアルタイム）。 そのあたりで使えそうな、数値演算のアルゴリズムをまとめてみました。 sqrt：平方根を求める C言語では"math.h"の「sqrt」で平方根を計算します。 これと同等の機能をするプログラムは以下のようになります。 浮動小数点での平方根の計算 double mySqrt(double x) { double s,last; if(x<=0.0) return 0.0; if (x > 1) s = x; else s = 1; do { last = s; s = (x / s + s) * 0.5; } while (s < last); return last; } 整数での平方根の計算 int myISqrt(int x) { int s, t; if (x <= 0) return 0;
平方根を使わないピタゴラス加算 | Codelogy
二次元座標上の2点間の距離を求めたいとき、複素数の絶対値を求めたいとき、その他いろいろなときに x = √(a2 + b2) という式を使います（これをpythagorean additionと言うそうです）。これを実装するとき、 という文がよく使われますが、この文を無闇に使っていると、あまり嬉しくない事態を引き起こすことになります。 さて、この文ののどこがいけないのでしょうか。 賢明な皆さまはもうお気づきでしょうが、a*a + b*bはオーバーフローを引き起こすおそれがあるのです。変数の値域を保証できるのならともかく、そうでなければ次に挙げる3つの対策のいずれかを採るべきです。 1.式変形 a’ = max( |a|, |b| ), b’ = min( |a|, |b| ) とおくと、 √(a2 + b2) = a’√(1 + (b’/a’)2) と変形できます。この式を使うとオ
fast sqrt
高速根号計算 (fast sqrt algorithm) 概要: C言語のsqrt(float)より精度は若干劣るものの，2倍以上速いsqrtのalgorithm． ググって見つけた物が，非常に面白かったのでまとめておく．精度より速度が求められる場面で活躍する． 参考文献 [1] David Eberly, Fast Inverse Square Root (Revisited), http://www.geometrictools.com/Documentation/ FastInverseSqrt.pdf, 1/2002-. 実装 //---Algorithm float(IEEE754)用------ inline float t_sqrtF( const float& x ) { float xHalf = 0.5f * x; int tmp = 0x5F3759DF
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://a-hisame.hatenadiary.org/entry/20121210/1355078638
あなたの知らないハッシュテーブルの世界
Javaで高速に平方根の逆数を求める
approximate double precision division using SSE2
Fast Inverse Square Root (Revisited)