将地图约束表示为ADT

Question

这是一个玩具问题:

(roguelike)2D地图由方形单元组成,每个单元都有一种材料(岩石或空气).

每个单元具有四个边界(N,S,E和W).每个边界由两个单元共享.

只有当一侧是岩石而另一侧是空气时,边界可以选择性地包含"墙特征".

(墙壁功能可以是杠杆,图片,按钮等)

只有当一边是岩石而另一边是空气时,代数数据类型设计才能有一个存储墙特征的地方？即,数据结构不能代表两个气囊或两个岩石细胞之间的边界上的壁特征.

我尝试过的一种方法是对单元格值进行XORing棋盘图案,反转变化并且不变.

我不断得知自己在细胞之间存在多条等效路线的事实 - SSW与SWS相同(这个问题的1D版本是微不足道的).

(我认识到ADT表示不会特别'可查询'.)

---

更新失败的尝试:

称东边界E和南边界S.让每个边界为Same或者Diff Feature.这种方法的问题在于它允许存在不一致的路由,例如:

E<0,0> Same
S<1,0> Same
S<0,0> Same
E<0,1> Diff

是否有一个数学名称,说不同的路线必须汇总到相同的总数？

您可以说Same为1且Diff为-1,并且任何两个单元格之间的每条路径上的乘积必须相等(1或-1).

Answer 1

我不知道传统的ADT是否可行,但你可以用GADT做到这一点.这在一个维度上有一个无限的地图,在另一个维度中是有限的:

{-# LANGUAGE GADTs #-}


data Nil
type AirEnd = AirCell Nil
type RockEnd = RockCell Nil

data AirCell next
data RockCell next

data WallFeature = Lever | Picture | Buttons | Etc ()
type Wall = Maybe WallFeature


data RogueStrip contents neighbour where

  AirEnd_ngbAir :: RogueStrip AirEnd AirEnd
  AirEnd_ngbRock :: Wall -> RogueStrip AirEnd RockEnd
  RockEnd_ngbAir :: Wall -> RogueStrip RockEnd AirEnd
  RockEnd_ngbRock :: RogueStrip RockEnd RockEnd

  AirCons_nextAir_ngbAir ::
          RogueStrip          (AirCell next')           neighbourNext
       -> RogueStrip (AirCell (AirCell next')) (AirCell neighbourNext)
  AirCons_nextAir_ngbRock :: Wall ->
          RogueStrip          (AirCell next')            neighbourNext
       -> RogueStrip (AirCell (AirCell next')) (RockCell neighbourNext)
  AirCons_nextRock_ngbAir :: Wall ->
          RogueStrip          (RockCell next')           neighbourNext
       -> RogueStrip (AirCell (RockCell next')) (AirCell neighbourNext)
  AirCons_nextRock_ngbRock :: Wall -> Wall ->
          RogueStrip          (RockCell next')            neighbourNext
       -> RogueStrip (AirCell (RockCell next')) (RockCell neighbourNext)
  RockCons_nextAir_ngbAir :: Wall -> Wall ->
          RogueStrip           (AirCell next')           neighbourNext
       -> RogueStrip (RockCell (AirCell next')) (AirCell neighbourNext)
  RockCons_nextAir_ngbRock :: Wall ->
          RogueStrip           (AirCell next')            neighbourNext
       -> RogueStrip (RockCell (AirCell next')) (RockCell neighbourNext)
  RockCons_nextRock_ngbAir :: Wall ->
          RogueStrip           (RockCell next')           neighbourNext
       -> RogueStrip (RockCell (RockCell next')) (AirCell neighbourNext)
  RockCons_nextRock_ngbRock ::
          RogueStrip           (RockCell next')            neighbourNext
       -> RogueStrip (RockCell (RockCell next')) (RockCell neighbourNext)


data RogueSList topStrip where
  StripCons :: RogueStrip topStrip nextStrip -> RogueSList nextStrip
                                             -> RogueSList topStrip

data RogueMap where
  RogueMap :: RogueSList top -> RogueMap