我正在使用程序生成构建 3d 游戏。我试图以这样一种方式连接一些预先生成的房间，无论如何，玩家总是可以到达 map 上的任何其他房间。房间有“可能的入口点”，连接走廊必须连接到这些入口点。但是，并非所有入口点都可以从房间内的所有其他入口点到达。例如，可能存在陷阱，因此位于底部的玩家将无法穿过房间到达顶部，而必须另寻出路。
给定一组嵌入 3d 空间中的预先存在的有向图，添加一组总长度最小的(双向)路径，将子图连接成更大的图。否则(因为 some research 表明这是 NP-Hard)使路径尽可能短以便在短时间内计算。
我最好的解决方案是基于 this procedural generation post ，他在其中创建了所有节点的德莱尼三角剖分。我将房间的每个强连接组件(例如陷阱的顶层和底层)视为单独的节点，并以此为基础构建 MST，但这限制了一些更有趣的可能性(例如，必须通过两条单向路径返回起点)。
有谁知道解决这个问题的更好方法吗？
最佳答案
也许您可以更好地利用您正在为 3d 空间建模这一事实。这意味着您可以将问题划分为一组平面图，每个平面图代表不同的楼层。您可以从构建每一层楼开始，使其紧密相连。然后，当您加入楼层(可能只有几个楼梯和陷阱)时，通过删除一些边来扰乱解决方案，同时仍保持整体强连通图。移除边缘的有趣选择是那些会导致地板本身失去强连接性但在考虑其他地板时保持属性的边缘。这些被称为桥梁，并且有一个 linear algorithm for finding them .
如果您只计算边而不是它们的长度，单独求解平面图(楼层)会将其转换为多个 Euclidean Steiner tree problems ，虽然仍然是 NP-hard，但可以使用 near-optimal polynomial-time approximation scheme 来解决.但是，您提到要最小化路径的总长度，这使得它成为 rectilinear Steiner tree problem。 .很多research由于它在电路设计中的适用性，已经对这个问题进行了研究。现有的近似值可以达到最佳值的 1.5 倍以内，这可能更适合您正在做的事情:略长的走廊而不是所有入口都集中在一个地方。
关于c# - 确保部分连接的有向图是强连接的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22314164/
我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以
我使用的是Firefox版本36.0.1和Selenium-Webdrivergem版本2.45.0。我能够创建Firefox实例，但无法使用脚本继续进行进一步的操作无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)错误。有人能帮帮我吗？ 最佳答案 我遇到了同样的问题。降级到firefoxv33后一切正常。您可以找到旧版本here 关于ruby-无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)，我们在StackOverflow上找到一个类
我需要在RubyonRails中实现无向图G=(V,E)并考虑构建一个Vertex和一个Edge模型，其中Vertex有_多条边。由于边恰好连接两个顶点，您将如何在Rails中执行此操作？您是否知道任何有助于实现此类图表的gem或库(对重新发明轮子不感兴趣;-))？ 最佳答案 不知道有任何现有库在ActiveRecord之上提供图形逻辑。您可能必须实现自己的Vertex、EdgeActiveRecord支持的模型(请参阅Rails安装的rails/activerecord中的vertex.rb和edge.rb/test/fixtur
如何在ruby中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL
我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha
C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.
require"socket"server="irc.rizon.net"port="6667"nick="RubyIRCBot"channel="#0x40"s=TCPSocket.open(server,port)s.print("USERTesting",0)s.print("NICK#{nick}",0)s.print("JOIN#{channel}",0)这个IRC机器人没有连接到IRC服务器，我做错了什么？ 最佳答案 失败并显示此消息::irc.shakeababy.net461*USER:Notenoughparame
考虑一下:现在这些情况:#output:http://domain.com/?foo=1&bar=2#output:http://domain.com/?foo=1&bar=2#output:http://domain.com/?foo=1&bar=2#output:http://domain.com/?foo=1&bar=2我需要用其他字符串输出URL。我如何保证＆符号不会被转义？由于我无法控制的原因，我无法发送&。求助!把我的头发拉到这里:\编辑:为了澄清，我实际上有一个像这样的数组:@images=[{:id=>"fooid",:url=>"http://
我有一个super简单的脚本，它几乎包含了FayeWebSocketGitHub页面上用于处理关闭连接的内容:ws=Faye::WebSocket::Client.new(url,nil,:headers=>headers)ws.on:opendo|event|p[:open]#sendpingcommand#sendtestcommand#ws.send({command:'test'}.to_json)endws.on:messagedo|event|#hereistheentrypointfordatacomingfromtheserver.pJSON.parse(event.d
我有一个ruby脚本可以打开与Apple推送服务器的连接并发送所有待处理的通知。我看不出任何原因，但当Apple断开我的脚本时，我遇到了管道损坏错误。我已经编写了我的脚本来适应这种情况，但我宁愿只是找出它发生的原因，这样我就可以在第一时间避免它。它不会始终根据特定通知断开连接。它不会以特定的字节传输大小断开连接。一切似乎都是零星的。您可以在单个连接上发送的数据传输或有效负载计数是否有某些限制？看到人们的解决方案始终保持一个连接打开，我认为这不是问题所在。我看到连接在3次通知后断开，我看到它在14次通知后断开。我从未见过它能超过14点。有没有人遇到过这种类型的问题？如何处理？
