HyperRogue的SAG图嵌入算法用模拟退火实现优雅的非欧几何可视化【免费下载链接】hyperrogueA SDL roguelike in a non-euclidean world项目地址: https://gitcode.com/gh_mirrors/hy/hyperrogueHyperRogue 是一款运行在非欧几何世界中的 SDL roguelike 游戏而其 RogueViz 演示模块里藏着一项非常有趣的算法SAGSimulated Annealing Graph embedding模拟退火图嵌入。它能把任意一张抽象的节点-边关系图优雅地铺到双曲平面的密铺tessellation或蜂巢honeycomb格子上并借助模拟退火Simulated Annealing自动寻优得到直观、紧凑、几乎不交叉的可视化布局。本文将带你从零理解这套算法的原理与用法 。为什么要在双曲几何里摆放图普通软件里画关系图我们习惯把节点丢进欧氏平面的 xy 坐标里。但双曲平面有着指数级膨胀的空间离中心越远可用格子越多这正好天然适合摆放规模很大的图——外围节点有足够空间散开而中心区域留给枢纽节点。SAG 的做法非常直接不再计算坐标而是为每个图节点分配密铺中的一个格子cell让相连的节点彼此靠近。由于可用的格子数量有限可以预先划定一块固定区域问题转化为一个组合优化问题——这正是退火算法的主场。核心代码位于 rogueviz/sag/ 目录详细说明见 rogueviz/sag/README.md。三种代价函数如何定义摆得好最优的定义因人而异SAG 内置了三种方法实现于 rogueviz/sag/functions.cpp方法优化目标适合场景closestNEAREST最小化所有边上权重 × 端点距离的总和让权重大的边尽量短节点抱团紧凑match最小化 (距离 − 1/权重) 的平方和让边长在图中精确代表权重倒数logisticLIKELIHOOD基于双曲随机图模型最大化似然有边想靠近无边想远离整体结构最清晰其中 logistic 方法最有物理味道根据双曲随机图模型距离为 d 的一对节点以概率1 / (1 exp((d − R) / T))相连。算法最大化实际边落在高概率区、非边落在低概率区的整体似然参数 R中心距离和 T平滑度还能在退火过程中自动重新拟合。这就是为什么它能画出类似脑区连接组brain connectomes那样的漂亮结构。模拟退火是如何运转的退火循环的核心实现见 rogueviz/sag/annealing.cpp思路可以用三步说清随机扰动每一轮随机挑一个节点把它挪到附近的某个格子或与另一个节点交换位置并快速增量计算代价变化 change无需全图重算接受准则若 change 0变差了则以概率 exp(−change × exp(−temperature)) 接受这次劣化——高温时大方探索低温时只走下坡路降温温度从 hightemp默认 10线性降到 lowtemp默认 −15探索逐渐收敛为精炼。整个退火既可以在后台持续运行边优化边渲染实时观察布局慢慢结晶成型也可以用-sagfull 秒数或-sagfulli 迭代次数一次性跑完。除了模拟退火SASAG 还支持纯爬山模式HC和关闭off通过-sagmode切换。快速上手命令行关键参数一览用项目自带的 mymake 加上-rv选项即可编译 RogueViz 版 HyperRogue见 Makefile.rv 与 mymake.cpp./mymake -rv运行后常用参数大致如下完整列表见各 .cpp 文件-sag-creq x— 只取离中心最近的 x 个格子作为嵌入区域-sag_gdist x— 使用几何距离而非格子步数作为距离度量-sag_gdist_dijkstra m— 远距离时用 Dijkstra 精确计算格子间距离-sag-weighted/-sag-unweighted— 分别读取带权node1;node2;weight与不带权node1 node2的图-sagtemp 高 低— 设定退火温度区间如-sagtemp 10 -15-sagfull 60— 全速退火 60 秒后出图。 小技巧先用小格子区域 closest 方法快速看整体聚簇再换 logistic 方法跑长时间退火能得到结构最清晰的最终版图。模块结构速览SAG 模块小而自洽适合阅读学习rogueviz/sag/sag.cpp— 主入口交互菜单、后台迭代调度iterate()、turn()rogueviz/sag/cells.cpp— 格子集合构建与 N×N 距离表含内存映射大表rogueviz/sag/data.cpp— 图数据管理、节点-格子映射sagid/sagnode、结果保存rogueviz/sag/functions.cpp— 三种代价函数与 R/T 参数自动优化rogueviz/sag/annealing.cpp— 模拟退火与爬山核心循环及命令行参数。写在最后SAG 用不到几百行核心代码就展示了模拟退火 双曲几何的组合威力把抽象关系图变成一张张紧凑而优雅的超曲面地图。如果你既好奇优化算法又想看非欧几何的实际应用不妨编译 RogueViz 版本亲手跑一次-sagfull亲眼看着节点在高温下乱跳、随温度降低逐渐各就各位——这本身就是一幅动态的数学景观 ✨。【免费下载链接】hyperrogueA SDL roguelike in a non-euclidean world项目地址: https://gitcode.com/gh_mirrors/hy/hyperrogue创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 HyperRogue的SAG图嵌入算法：用模拟退火实现优雅的非欧几何可视化
HyperRogue的SAG图嵌入算法用模拟退火实现优雅的非欧几何可视化【免费下载链接】hyperrogueA SDL roguelike in a non-euclidean world项目地址: https://gitcode.com/gh_mirrors/hy/hyperrogueHyperRogue 是一款运行在非欧几何世界中的 SDL roguelike 游戏而其 RogueViz 演示模块里藏着一项非常有趣的算法SAGSimulated Annealing Graph embedding模拟退火图嵌入。它能把任意一张抽象的节点-边关系图优雅地铺到双曲平面的密铺tessellation或蜂巢honeycomb格子上并借助模拟退火Simulated Annealing自动寻优得到直观、紧凑、几乎不交叉的可视化布局。本文将带你从零理解这套算法的原理与用法 。为什么要在双曲几何里摆放图普通软件里画关系图我们习惯把节点丢进欧氏平面的 xy 坐标里。但双曲平面有着指数级膨胀的空间离中心越远可用格子越多这正好天然适合摆放规模很大的图——外围节点有足够空间散开而中心区域留给枢纽节点。SAG 的做法非常直接不再计算坐标而是为每个图节点分配密铺中的一个格子cell让相连的节点彼此靠近。由于可用的格子数量有限可以预先划定一块固定区域问题转化为一个组合优化问题——这正是退火算法的主场。核心代码位于 rogueviz/sag/ 目录详细说明见 rogueviz/sag/README.md。三种代价函数如何定义摆得好最优的定义因人而异SAG 内置了三种方法实现于 rogueviz/sag/functions.cpp方法优化目标适合场景closestNEAREST最小化所有边上权重 × 端点距离的总和让权重大的边尽量短节点抱团紧凑match最小化 (距离 − 1/权重) 的平方和让边长在图中精确代表权重倒数logisticLIKELIHOOD基于双曲随机图模型最大化似然有边想靠近无边想远离整体结构最清晰其中 logistic 方法最有物理味道根据双曲随机图模型距离为 d 的一对节点以概率1 / (1 exp((d − R) / T))相连。算法最大化实际边落在高概率区、非边落在低概率区的整体似然参数 R中心距离和 T平滑度还能在退火过程中自动重新拟合。这就是为什么它能画出类似脑区连接组brain connectomes那样的漂亮结构。模拟退火是如何运转的退火循环的核心实现见 rogueviz/sag/annealing.cpp思路可以用三步说清随机扰动每一轮随机挑一个节点把它挪到附近的某个格子或与另一个节点交换位置并快速增量计算代价变化 change无需全图重算接受准则若 change 0变差了则以概率 exp(−change × exp(−temperature)) 接受这次劣化——高温时大方探索低温时只走下坡路降温温度从 hightemp默认 10线性降到 lowtemp默认 −15探索逐渐收敛为精炼。整个退火既可以在后台持续运行边优化边渲染实时观察布局慢慢结晶成型也可以用-sagfull 秒数或-sagfulli 迭代次数一次性跑完。除了模拟退火SASAG 还支持纯爬山模式HC和关闭off通过-sagmode切换。快速上手命令行关键参数一览用项目自带的 mymake 加上-rv选项即可编译 RogueViz 版 HyperRogue见 Makefile.rv 与 mymake.cpp./mymake -rv运行后常用参数大致如下完整列表见各 .cpp 文件-sag-creq x— 只取离中心最近的 x 个格子作为嵌入区域-sag_gdist x— 使用几何距离而非格子步数作为距离度量-sag_gdist_dijkstra m— 远距离时用 Dijkstra 精确计算格子间距离-sag-weighted/-sag-unweighted— 分别读取带权node1;node2;weight与不带权node1 node2的图-sagtemp 高 低— 设定退火温度区间如-sagtemp 10 -15-sagfull 60— 全速退火 60 秒后出图。 小技巧先用小格子区域 closest 方法快速看整体聚簇再换 logistic 方法跑长时间退火能得到结构最清晰的最终版图。模块结构速览SAG 模块小而自洽适合阅读学习rogueviz/sag/sag.cpp— 主入口交互菜单、后台迭代调度iterate()、turn()rogueviz/sag/cells.cpp— 格子集合构建与 N×N 距离表含内存映射大表rogueviz/sag/data.cpp— 图数据管理、节点-格子映射sagid/sagnode、结果保存rogueviz/sag/functions.cpp— 三种代价函数与 R/T 参数自动优化rogueviz/sag/annealing.cpp— 模拟退火与爬山核心循环及命令行参数。写在最后SAG 用不到几百行核心代码就展示了模拟退火 双曲几何的组合威力把抽象关系图变成一张张紧凑而优雅的超曲面地图。如果你既好奇优化算法又想看非欧几何的实际应用不妨编译 RogueViz 版本亲手跑一次-sagfull亲眼看着节点在高温下乱跳、随温度降低逐渐各就各位——这本身就是一幅动态的数学景观 ✨。【免费下载链接】hyperrogueA SDL roguelike in a non-euclidean world项目地址: https://gitcode.com/gh_mirrors/hy/hyperrogue创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考