手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
キー毎に値を集計する方法 - ひしだまの変更履歴
ひしだまＨＰの更新履歴。 主にＴＲＰＧリプレイの元ネタ集、プログラミング技術メモと自作ソフト、好きなゲームや音楽です。 irofさんとdaiksyさんがTwitter上でキーブレイク処理について話していました。 （リストを項目ごとに集計する→「ブレイク処理」を定形のアルゴリズムとして習いました→こんな解りにくいの、なんで好んで書くんだろう） キーブレイク処理というのは、データをキーでソートしておいて順番に読み込み、キーが同じ値の間に処理（よくあるのが集計）を続ける。キーが違う値になったら（キーがブレイクしたら）集計値を出力し、集計用変数をクリアしてまた処理を続ける。というアルゴリズムです。 ひとつ前のキーの値を保持しておく変数が必要で、最初はそれをどういう値にしておくか、また、ループを抜けた後に最後のキーの集計値を出力する必要があるか、といった辺りも考慮しないといけないので、慣れないと分か
テンポ解析のアルゴリズム
テンポは音量増加量の時間方向の周波数成分から解析します。 まず、音声のスペクトルから音量が増加している部分のみを取り出し、 音量増加量を求めます。音量は音が鳴り始めるとき、主に拍の頭で 増加します。120BPMの曲であれば1分間に120回の割合で音量が増加しているため、 音量増加量の時間方向の周波数成分を求めると120/60=2Hzの成分が検出されます。 多くの場合、最も大きい周波数成分が、正しいテンポか 正しいテンポの2倍または0.5倍になっています。しかし、正しいテンポの 0.75倍、1.25倍、1.5倍の成分が突出していることもあります。 これらのテンポから正しいテンポを抽出するため、WaveToneでは キータップによるテンポ検出と併用できるようになっています。
Clifford Attractors
Attributed to Cliff Pickover Graphics by Paul Bourke February 2004 See also Peter de Jong attractors Contributions from Thomas Burt and Paul Richards. Definition xn+1 = sin(a yn) + c cos(a xn) yn+1 = sin(b xn) + d cos(b yn) where a, b, c, d are variabies that define each attractor. a = -1.4, b = 1.6, c = 1.0, d = 0.7 a = 1.1, b = -1.0, c = 1.0, d = 1.5 a = 1.6, b = -0.6, c = -1.2, d = 1.6 a
LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出 - mixi engineer blog
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの
はてなブログ | 無料ブログを作成しよう
来年も作りたい！ふきのとう料理を満喫した 2024年春の記録 春は自炊が楽しい季節 1年の中で最も自炊が楽しい季節は春だと思う。スーパーの棚にやわらかな色合いの野菜が並ぶと自然とこころが弾む。 中でもときめくのは山菜だ。早いと2月下旬ごろから並び始めるそれは、タラの芽、ふきのとうと続き、桜の頃にはうるい、ウド、こ…
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
JavaScript + Canvas で動くカオスアトラクタ生成器作ってみた - mooz deceives you
カオスアトラクタ by edvakf in hatena を見ていて Canvas でピクセル操作が出来るらしいことを知り、早速カオスアトラクタ生成器を作ってみた。 アクセスは C.H.A.O.T.I.C C.A.N.V.A.S から。 動作は Firefox 3.5 と Google Chrome で確認。処理速度は Chrome の方が 5 倍ほど速いので、一応 Chrome 推奨。 Safari や Opera では未確認。 で、操作説明。 Draw ボタンを押せばカオスアトラクタが描画される。 Settings 右のプルダウンメニューにいくつかプリセットの設定を用意しておいたので、はじめはそちらを試されるのが良いと思う。 Coefficients の値をちょびっとづつ変えていくと、生成される画像が綺麗に変化していってくれる。一期一会な感じが小憎い。画像は Firefox なら右クリ
MySQL InnoDBだけで全文検索 - SH2の日記
実験エントリです。 予習してみる 「転置インデックス」というキーワードで検索して、しばらく勉強してみます。 転置インデックス - Wikipedia mixi Engineers’ Blog » 転置インデックスを実装しよう ASCII.jp：悟空、秘剣「転置インデックス」を手に入れる ｜Googleはなぜ的確に探せるのか？ [を] 転置インデックスによる検索システムを作ってみよう！ 転置インデックスで学ぶ検索エンジンの中身アプリ - 睡眠不足？！ うーんなるほど。分かったような分からないような。 作ってみる とりあえず、Twitter4Jを使ってこんなデータを用意しました。ちなみに人選は漢(オトコ)のコンピュータ道: MySQLerのTwitterアカウントまとめ。を参考にさせていただきました。 5707049458,2009-11-14 20:28:34,sakaik,@hbstudy
Diff algorithm - 枕を欹てて聴く
id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 プログラムの実行時間 業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？ 非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。 TopCoderの制限に関して TopCoderでは、実行時間およびメモリ使
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
マルコフ連鎖で日本語をもっともらしく要約する - ザリガニが見ていた...。
そもそも、マルコフ連鎖とは何なのか？全く聞いたこともなかった。そして、文章を要約するのはとっても高度なことだと思っていて、自分のレベルではその方法を、今まで思い付きもしなかった。 しかし、以下のようなシンプルなRubyコードでそれが出来てしまうと知った時、目から鱗である...。一体、何がどうなっているのだ？コードを追いながら、マルコフ連鎖を利用するという発想の素晴らしさを知った！ 作業環境 MacBook OSX 10.5.7 ruby 1.8.6 (2008-08-11 patchlevel 287) [universal-darwin9.0] mecab utf8環境でインストール済み マルコフ連鎖に出逢う rssを流し読みしていると、以下の日記に目が止まった。（素晴らしい情報に感謝です！） MeCabを使ってマルコフ連鎖 一体何が出来るコードなのか、日記を読んだだけではピンと来なかっ
はてなブログ | 無料ブログを作成しよう
来年も作りたい！ふきのとう料理を満喫した 2024年春の記録 春は自炊が楽しい季節 1年の中で最も自炊が楽しい季節は春だと思う。スーパーの棚にやわらかな色合いの野菜が並ぶと自然とこころが弾む。 中でもときめくのは山菜だ。早いと2月下旬ごろから並び始めるそれは、タラの芽、ふきのとうと続き、桜の頃にはうるい、ウド、こ…
ネットワークプログラムのI/O戦略 - sdyuki-devel
図解求む。 以下「プロトコル処理」と「メッセージ処理」を分けて扱っているが、この差が顕著に出るのは全文検索エンジンや非同期ジョブサーバーなど、小さなメッセージで重い処理をするタイプ。ストリーム指向のプロトコルの場合は「プロトコル処理」を「ストリーム処理」に置き換えるといいかもしれない。 シングルスレッド･イベント駆動 コネクションN：スレッド１。epoll/kqueue/select を１つ使ってイベントループを作る。 マルチコアCPUでスケールしないので、サーバーでは今時このモデルは流行らない。 クライアントで非同期なメッセージングをやりたい場合はこのモデルを使える： サーバーにメッセージを送信 イベントハンドラを登録；このときイベントハンドラのポインタを取っておく イベントハンドラ->フラグ がONになるまでイベントループを回す イベントハンドラ->結果 を返す １コネクション１スレッ
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
kikuzone on Twitter: "「同じ著者の小説をつなげてzip圧縮したら、複数の著者の小説をつなげて圧縮するよりも圧縮率がいいから著者推定に使える！」って論文が見つかった。キワモノかと思ったら精度いいし。論文探してるとしばしば「その発想はなかったわ」な物が見つかって面白いが俺は数日前にこれをやっとくべきだ。"
加藤 和彦 Kazuhiko KATO, Dr. Prof.
