Jas

1. 動線シミュレーションに基づくドア配置最適化 | | ハイライト Python を用いて，間取り設計の最適化のためのドア配置最適化プログラムを開発 大規模な人の流れシミュレーションのために，2D ナビゲーションメッシュ（半エッジメッシュ，A*経路探索，ファンネルアルゴリズム） をゼロから実装 動的メッシュの切断/統合操作 と 履歴追跡 を活用したランタイム最適化システムを設計 高速処理のためにデータ指向設計(DOD)を適用 Demo 結果 苦労した部分 ▶ 動的なメッシュ処理 関連コード： u_geometry.py, g_mesh.py, s_door_system.py Half–edge 構造に対して，基本的な操作を2種類実装した： Edge を切断する操作と，Edge を統合する操作． メッシュを更新する際に構造を壊さず，元のメッシュ情報を保持することが重要だった． Half–edge 構造の活用： 各 Edge に探索を効率化する情報（例：面，対角の頂点など）を組み込む． ジオメトリーの管理やデバッグを容易にするため，ジオメトリーに ID を付与し，デバッグ描画で確認できるようにした． 履歴機能の実装： 一連の更新を行っても，元の Edge を保存できるようにする． ジオメトリーの変更を追跡するために，履歴機能を導入． 履歴機能では，初期の Edge と Edge 上の位置（0–1）を記録することで，変更を管理できる． 🔼 デバッグ描画では，ドアコンポーネントを Edge 上で時計回りに移動させながら， 動的にメッシュを切断/統合しているが，初期に作成したジオメトリーの情報が保持されている． 注目すべき部分 ▶ ナビゲーションメッシュの実装 関連コード： u_cdt.py, u_path_finding.py, g_navmesh.py カスタマイズ性を重視し，ゼロからナビゲーションメッシュを実装することにした． ナビゲーションメッシュの実装には，メッシュの構築，A*経路探索，ファンネルアルゴリズムの実装など，多くの技術的課題があった． 特に,ファンネルアルゴリズムの実装では，複雑なエッジケースが多く，デバッグが困難だった． 実装の流れ： 2Dメッシュの構築 CDT（Constrained Delaunay Triangulation）ライブラリのPython Bindingを使用して実装した． 生成したメッシュを前処理として Half-edge 構造に変換し，各 Edge に種類情報やフラグを記録することで， その後の最適化処理をスムーズかつ高効率に実行できるようにする． A*経路探索の実装 メッシュの面（三角形）上で最短の三角形ルートを探索する． ファンネルアルゴリズムの適用 A*で求めた三角形ルートに基づき，ファンネルアルゴリズムを使用して最適な移動経路を計算する． ▶ ランタイム最適化アルゴリズム 関連コード： u*loader.py, s*\*\*\*.py, o_optimizer.py, f_layout.py 本プログラムは，動線を考慮した間取り最適化を目的とし，サンプリング点を設定して人の動線をシミュレーションする． 平均移動距離をロス関数とし，ドアの配置を最適化することを主眼としている． 最適化の手順： 初期設定の読み込み ドアの初期設定,部屋の接続要件，および最適化パラメータをTOMLファイルに記述し，プログラムに読み込む． Flood Algorithm を用いてメッシュ上の閉領域を検出し，部屋の接続要件を自動生成する． 最適化処理 接続条件を基にドアの初期配置を自動生成する． その後，MCMC（Markov Chain Monte Carlo）アルゴリズムを適用し，ドアの位置を動的に変更しながら最適な配置を探索する． 最適配置の確定と履歴管理 最適なドア配置が決定した後，メッシュデータを更新し，最適化結果を反映する． さらに，履歴管理機能を活用して変更を追跡し，最適な配置を維持できるようにする． プレゼンテーションスライド 修士論文発表用スライド（修正版） ...