数学吧 关注:931,817贴子:8,928,079
  • 9回复贴,共1

分享一下打游戏遇到的规划问题

只看楼主收藏回复

原型是最近玩《滞困:异星黎明》遇到的,游戏是类环世界那样的风格,设定中,一个区域(每个区域都是正方形)的四条边都至少有一条相邻边是空着的才能运行,于是在建仓库的时候经常遇到规划一个大区域,同时要在其中留好空隙让每个区域都能运作的问题。
转化为数学问题,可以想作,在一个大棋盘中填入0和1,其中,每个1至少有一个边上是0,那么怎么规划填入更多的1?

比如一个3x3的空,虽然第一想法肯定是所有的1和0错开放,至少不会出错,但是这样摆不一定是最优的。
我初步的想法是,这个问题反过来想,一个0可以提供4个1的位置,角上的0可以提供2个1,边上的0可以提供3个1,那么把各种0和他们提供的1组成一个图形,可以转变成在区域里填入特定图形的模式:

用黄色代表边上的0组成的T字形,绿色代表角上的0组成的三角形,多余的两块空白则2选1。
这样的好处是,组合好的图形会进一步把棋盘封闭,减少一个1被多个0反复占用的情况。

如果用填色法来给我的仓库规划,就会长成这个样子。
感觉这个规划问题还挺有意思的,有点像围棋里的气反过来的解法,不知道8u有没有过类似的经历


IP属地:重庆1楼2025-05-09 11:52回复
    确实很有意思


    IP属地:北京来自Android客户端2楼2025-05-14 22:12
    回复
      2025-12-25 00:42:31
      广告
      不感兴趣
      开通SVIP免广告
      很好的思路,我只能提供一个比较弱的想法。三种颜色可以等价地看作假设了一个0的各邻居都是1,或者说0不能挨着0。如果证明了这种做法总是会带来更优的结果,那就可以认为剩下的工作就只是拼拼图了


      IP属地:北京来自Android客户端3楼2025-05-14 22:16
      回复
        其实是用十字图形(5个正方形组成)去完全覆盖m*n的方形网格,求十字图形最小数,想了一下不是很好讨论。。。
        定义:覆盖效率:K = m*n/(5*十字图形个数)
        有没有谁感兴趣去求一下K的上界,我构造了一下,至少是大于0.827的


        IP属地:四川4楼2025-05-16 11:32
        回复