# 导航网格插件

一个功能完整的3D导航网格系统插件，为EG引擎提供基于导航网格的寻路和路径规划功能。

## 功能特性

### 核心功能
- **导航网格生成**: 支持从3D场景自动生成导航网格
- **路径查找**: 基于A*算法的高效寻路
- **可视化编辑**: 直观的导航网格编辑界面
- **多边形管理**: 导航网格多边形的增删改查
- **路径可视化**: 实时显示寻路结果

### 寻路算法
- **A*算法**: 经典的启发式搜索算法
- **Dijkstra算法**: 保证最短路径的搜索算法
- **多种启发式函数**: 欀曼哈顿距离、欧几里得距离等
- **路径平滑**: 漏斗算法和简单平滑算法
- **多路点路径**: 支持经过多个路点的复杂路径规划
- **动态障碍物**: 运行时添加和移除障碍物
- **路径缓存**: 提高重复路径查找性能

### 编辑功能
- **可视化编辑**: 图形化界面编辑导航网格
- **多种工具**: 选择、添加、删除、绘制工具
- **属性调节**: 网格大小、代理尺寸等参数调节
- **撤销重做**: 编辑历史管理和操作回退
- **网格对齐**: 网格对齐功能提高编辑精度
- **自动连接**: 自动计算多边形连接关系

### 性能优化
- **空间哈希**: 加速多边形查找
- **对象复用**: 减少内存分配
- **批量处理**: 提高大量数据处理效率
- **LOD支持**: 多层次细节支持

### 高级特性
- **分层寻路**: 大场景高效寻路
- **路径复杂度分析**: 路径质量评估
- **备选路径**: 多条路径选择
- **路径验证**: 路径有效性检查
- **统计信息**: 详细的性能和使用统计
- **网格分析**: 质量分析和优化建议
- **网格优化**: 自动优化和简化功能
- **格式支持**: 多种文件格式导入导出

## 使用方法

### 快捷键操作
- **F1**: 切换导航网格编辑器显示
- **F2**: 切换导航网格可见性
- **F3**: 查找随机路径进行测试
- **F4**: 清除所有路径可视化
- **F5**: 从场景生成导航网格
- **F6**: 验证导航网格完整性
- **F7**: 优化导航网格
- **F8**: 显示统计信息
- **F9**: 分析导航网格质量
- **F10**: 导出分析报告
- **F11**: 简化导航网格
- **F12**: 检测瓶颈区域

### GUI界面操作
插件会在屏幕左上角创建控制面板，可以通过按钮直接操作导航网格功能。

### 编程接口
```python
# 获取插件实例
navmesh_plugin = world.plugin_manager.get_plugin("navigation_mesh")

# 生成导航网格
navmesh_plugin.generate_navmesh_from_scene()

# 从文件加载导航网格
navmesh_plugin.load_navmesh_from_file("path/to/navmesh.json")

# 保存导航网格到文件
navmesh_plugin.save_navmesh_to_file("path/to/navmesh.json")

# 查找路径
start_point = Point3(0, 0, 0)
end_point = Point3(10, 0, 10)
path = navmesh_plugin.find_path(start_point, end_point)

# 检查点是否可行走
is_walkable = navmesh_plugin.is_point_walkable(Point3(5, 0, 5))

# 获取最近的可行走点
closest_point = navmesh_plugin.get_closest_point(Point3(3, 2, 4))

# 添加动态障碍物
obstacle_id = navmesh_plugin.add_dynamic_obstacle(Point3(5, 0, 5), 1.0, 2.0)

# 移除动态障碍物
navmesh_plugin.remove_dynamic_obstacle(obstacle_id)

# 设置导航网格参数
navmesh_plugin.set_navmesh_settings({
    'cell_size': 0.3,
    'agent_height': 1.8,
    'agent_radius': 0.4
})

# 设置寻路算法
navmesh_plugin.set_pathfinder_algorithm('astar')  # 或 'dijkstra'

# 查找多路点路径
waypoints = [Point3(0, 0, 0), Point3(5, 0, 5), Point3(10, 0, 10)]
path = navmesh_plugin.find_path_with_waypoints(waypoints)

# 估算路径代价
cost = navmesh_plugin.estimate_path_cost(Point3(0, 0, 0), Point3(10, 0, 10))

# 验证路径有效性
is_valid = navmesh_plugin.validate_path(path)

# 分析路径复杂度
complexity = navmesh_plugin.get_path_complexity(path)

# 查找备选路径
alternative_paths = navmesh_plugin.find_alternative_paths(Point3(0, 0, 0), Point3(10, 0, 10), 3)

# 清空路径缓存
navmesh_plugin.clear_path_cache()

# 重新构建导航网格
navmesh_plugin.rebuild_navmesh()

# 启用空间哈希优化
navmesh_plugin.enable_spatial_hashing(True)

# 设置空间哈希网格大小
navmesh_plugin.set_spatial_hash_cell_size(5.0)

# 导出统计信息
navmesh_plugin.export_statistics("stats.json")

# 导入/导出设置
navmesh_plugin.import_settings("settings.json")
navmesh_plugin.export_settings("settings.json")

# 高级功能
# 分析网格质量
quality_report = navmesh_plugin.analyze_mesh_quality()

# 获取优化建议
suggestions = navmesh_plugin.suggest_optimizations()

# 检测瓶颈区域
bottlenecks = navmesh_plugin.detect_navigation_bottlenecks()

# 生成完整分析报告
report = navmesh_plugin.generate_analysis_report()

# 导出分析报告
navmesh_plugin.export_analysis_report("analysis_report.json")

# 获取网格复杂度评分
complexity_score = navmesh_plugin.get_mesh_complexity_score()

# 推荐网格简化策略
simplification_recommendation = navmesh_plugin.recommend_mesh_simplification()

# 合并相邻多边形
merged_count = navmesh_plugin.merge_adjacent_polygons()

# 简化多边形
simplified_count = navmesh_plugin.simplify_mesh_polygons()

# 移除小多边形
removed_count = navmesh_plugin.remove_small_mesh_polygons()

# 执行完整网格优化
optimization_result = navmesh_plugin.optimize_navigation_mesh('medium')

# 设置优化参数
navmesh_plugin.set_optimization_settings({
    'merge_threshold': 0.5,
    'simplify_threshold': 0.1,
    'min_polygon_area': 0.01
})

# 获取优化参数
optimization_settings = navmesh_plugin.get_optimization_settings()

# 填补网格空隙
filled_gaps = navmesh_plugin.fill_mesh_gaps()

# 平滑边界
smoothed_edges = navmesh_plugin.smooth_mesh_boundaries()

# 平衡多边形大小
balanced_polygons = navmesh_plugin.balance_polygon_sizes()

# 序列化导航网格
serialized_data = navmesh_plugin.serialize_navigation_mesh()

# 反序列化导航网格
success = navmesh_plugin.deserialize_navigation_mesh(serialized_data)

# 保存导航网格（高级选项）
navmesh_plugin.save_navmesh_to_file_advanced("navmesh.json", compress=True, pretty_print=True)

# 加载导航网格（高级选项）
navmesh_plugin.load_navmesh_from_file_advanced("navmesh.json")

# 导出为标准格式
navmesh_plugin.export_to_standard_format("navmesh.obj", "obj")

# 从标准格式导入
navmesh_plugin.import_from_standard_format("navmesh.obj", "obj")

# 获取文件信息
file_info = navmesh_plugin.get_navmesh_file_info("navmesh.json")

# 批量分析多个网格文件
analysis_results = navmesh_plugin.batch_analyze_navmeshes(["navmesh1.json", "navmesh2.json"])

# 比较两个导航网格
comparison_result = navmesh_plugin.compare_navigation_meshes("navmesh1.json", "navmesh2.json")

# 验证网格文件
validation_result = navmesh_plugin.validate_navmesh_file("navmesh.json")

# 优化并保存网格
optimization_result = navmesh_plugin.optimize_and_save_navmesh("input.json", "output.json", "medium")

# 创建优化流水线
pipeline_result = navmesh_plugin.create_optimization_pipeline(['merge', 'simplify', 'remove_small'])
```

## 核心组件

### 导航网格管理器
负责导航网格的加载、生成、管理和查询。

主要功能：
- 多边形数据管理（添加、删除、修改）
- 点位置查询（最近点、可行走性检查）
- 空间查询优化（空间哈希）
- 可视化显示控制
- 动态障碍物管理
- 网格验证和优化

### 路径查找器
实现基于导航网格的多种寻路算法。

主要功能：
- A*、Dijkstra等多种寻路算法
- 路径平滑和优化
- 动态障碍物避让
- 路径缓存机制
- 性能统计和分析
- 备选路径生成

### 导航网格编辑器
提供可视化编辑导航网格的功能。

主要功能：
- 多种编辑工具（选择、添加、删除、绘制）
- 实时可视化反馈
- 编辑历史管理（撤销/重做）
- 参数调节界面
- 快捷键支持
- 网格对齐和辅助功能

### 导航网格工具集
提供导航网格的高级分析和优化功能。

主要功能：
- 网格质量分析
- 性能评估
- 优化建议
- 自动优化
- 格式转换
- 批量处理

## 数据结构

### 导航网格多边形
表示导航网格中的一个可行走区域，包含：
- 多边形顶点（任意数量）
- 相邻多边形信息
- 门户点（与邻居的连接点）
- 中心点计算
- 面积和边界框计算
- 点在多边形内判断
- 最近点计算

### 导航网格节点
用于寻路算法中的节点表示，包含：
- 多边形ID
- 位置信息
- 代价信息（g_cost, h_cost, f_cost）
- 父节点引用
- 门户点入口信息

### 寻路路径
表示计算出的路径，包含：
- 路径点列表
- 路径长度和复杂度
- 路径有效性验证

## 性能优化

### 算法优化
- **高效数据结构**: 使用优先队列优化寻路算法
- **启发式函数**: 智能的启发式代价计算
- **节点剪枝**: 避免重复节点计算
- **路径缓存**: 缓存常用路径提高查找速度
- **空间哈希**: 加速多边形空间查询

### 内存管理
- **对象池**: 减少对象创建和销毁开销
- **数据压缩**: 优化导航网格数据存储
- **批量处理**: 提高大量数据处理效率

### 渲染优化
- **LOD支持**: 根据距离调整显示细节
- **视锥剔除**: 只渲染可见区域
- **批处理**: 合并相似的渲染调用

## 扩展开发

### 添加新的寻路算法
1. 在[pathfinder.py](file:///home/hello/EG/plugins/user/navigation_mesh/tools/pathfinder.py)中实现新的算法类
2. 继承现有寻路器或创建新的寻路器类
3. 在插件主文件中集成新的算法

### 添加新的网格生成方法
1. 在[navmesh_manager.py](file:///home/hello/EG/plugins/user/navigation_mesh/core/navmesh_manager.py)中实现新的生成方法
2. 添加对应的GUI控制元素
3. 在编辑器中添加对应的生成选项

### 添加新的编辑工具
1. 在[navmesh_editor.py](file:///home/hello/EG/plugins/user/navigation_mesh/editor/navmesh_editor.py)中创建新的工具类
2. 继承NavMeshEditorTool基类
3. 实现工具的交互逻辑
4. 在编辑器中注册新工具

### 添加新的分析工具
1. 在[navmesh_analyzer.py](file:///home/hello/EG/plugins/user/navigation_mesh/tools/navmesh_analyzer.py)中实现新的分析功能
2. 在[navmesh_tools.py](file:///home/hello/EG/plugins/user/navigation_mesh/tools/navmesh_tools.py)中集成新工具
3. 在插件主文件中暴露新功能接口

## 故障排除

### 路径查找失败
1. 检查导航网格是否正确生成和加载
2. 确认起点和终点在可行走区域内
3. 检查多边形连接是否正确
4. 验证导航网格完整性（使用F6快捷键）

### 性能问题
1. 使用寻路统计功能分析性能瓶颈
2. 调整启发式权重优化搜索效率
3. 简化导航网格结构
4. 启用空间哈希优化
5. 调整最大搜索节点数限制

### 编辑器无法使用
1. 确认GUI系统是否正常工作
2. 检查快捷键是否被其他系统占用
3. 重新启用插件尝试
4. 检查是否有Python异常（查看控制台输出）

### 网格生成问题
1. 检查场景中是否有合适的几何体用于生成
2. 调整网格生成参数（网格大小、代理尺寸等）
3. 使用测试网格功能验证基本功能

### 文件操作问题
1. 检查文件路径是否正确
2. 确认文件权限是否足够
3. 验证文件格式是否支持
4. 检查磁盘空间是否充足

## API参考

### Plugin类主要方法

#### 初始化和控制
- `initialize()` - 初始化插件
- `enable()` - 启用插件
- `disable()` - 禁用插件
- `finalize()` - 清理插件资源

#### 导航网格操作
- `load_navmesh_from_file(filepath)` - 从文件加载导航网格
- `save_navmesh_to_file(filepath)` - 保存导航网格到文件
- `generate_navmesh_from_scene()` - 从场景生成导航网格
- `rebuild_navmesh()` - 重新构建导航网格

#### 路径查找
- `find_path(start_point, end_point)` - 查找两点间路径
- `find_path_with_waypoints(waypoints)` - 查找经过多个路点的路径
- `find_alternative_paths(start_point, end_point, count)` - 查找备选路径

#### 点查询
- `is_point_walkable(point)` - 检查点是否可行走
- `get_closest_point(point)` - 获取最近的可行走点

#### 动态障碍物
- `add_dynamic_obstacle(position, radius, height)` - 添加动态障碍物
- `remove_dynamic_obstacle(obstacle_id)` - 移除动态障碍物

#### 设置和配置
- `set_navmesh_settings(settings)` - 设置导航网格参数
- `get_navmesh_settings()` - 获取导航网格参数
- `set_pathfinder_algorithm(algorithm)` - 设置寻路算法
- `get_available_algorithms()` - 获取可用算法列表
- `set_pathfinder_settings(settings)` - 设置寻路参数
- `get_pathfinder_settings()` - 获取寻路参数

#### 性能和统计
- `show_stats()` - 显示统计信息
- `export_statistics(filepath)` - 导出统计信息
- `clear_path_cache()` - 清空路径缓存

#### 优化和验证
- `validate_navmesh()` - 验证导航网格
- `optimize_navmesh()` - 优化导航网格
- `enable_spatial_hashing(enabled)` - 启用/禁用空间哈希
- `set_spatial_hash_cell_size(size)` - 设置空间哈希网格大小

#### 高级分析功能
- `analyze_mesh_quality()` - 分析网格质量
- `suggest_optimizations()` - 提供优化建议
- `analyze_pathfinding_performance(sample_count)` - 分析寻路性能
- `detect_navigation_bottlenecks()` - 检测瓶颈区域
- `analyze_coverage()` - 分析覆盖情况
- `generate_analysis_report()` - 生成分析报告
- `export_analysis_report(filepath)` - 导出分析报告
- `get_mesh_complexity_score()` - 获取网格复杂度评分
- `recommend_mesh_simplification()` - 推荐网格简化策略

#### 网格优化功能
- `merge_adjacent_polygons()` - 合并相邻多边形
- `simplify_mesh_polygons()` - 简化多边形
- `remove_small_mesh_polygons()` - 移除小多边形
- `optimize_navigation_mesh(optimization_level)` - 优化导航网格
- `set_optimization_settings(settings)` - 设置优化参数
- `get_optimization_settings()` - 获取优化参数
- `fill_mesh_gaps()` - 填补网格空隙
- `smooth_mesh_boundaries()` - 平滑边界
- `balance_polygon_sizes()` - 平衡多边形大小

#### 序列化和文件操作
- `serialize_navigation_mesh()` - 序列化导航网格
- `deserialize_navigation_mesh(data_str)` - 反序列化导航网格
- `save_navmesh_to_file_advanced(filepath, compress, pretty_print)` - 保存网格（高级选项）
- `load_navmesh_from_file_advanced(filepath)` - 加载网格（高级选项）
- `export_to_standard_format(filepath, format_type)` - 导出为标准格式
- `import_from_standard_format(filepath, format_type)` - 从标准格式导入
- `get_navmesh_file_info(filepath)` - 获取文件信息
- `batch_analyze_navmeshes(filepaths)` - 批量分析网格
- `compare_navigation_meshes(navmesh1_path, navmesh2_path)` - 比较网格
- `validate_navmesh_file(filepath)` - 验证网格文件
- `optimize_and_save_navmesh(input_filepath, output_filepath, optimization_level)` - 优化并保存
- `create_optimization_pipeline(steps)` - 创建优化流水线

## 性能调优建议

### 寻路性能
1. 合理设置启发式权重（通常1.0为最佳）
2. 限制最大搜索节点数避免长时间搜索
3. 启用路径缓存减少重复计算
4. 使用适当的空间查询优化

### 内存使用
1. 及时清理不用的路径缓存
2. 控制导航网格复杂度
3. 合理设置空间哈希网格大小

### 渲染性能
1. 只在需要时显示导航网格
2. 使用LOD减少远处细节
3. 批量处理渲染调用

### 网格优化
1. 定期分析网格质量
2. 根据建议进行优化
3. 平衡网格精度和性能
4. 移除不必要的细节

## 版本信息

- 版本: 1.0.0
- 作者: EG Team
- 发布日期: 2024年

## 许可证

本插件遵循EG引擎许可证协议。