Javascript：优化国际象棋游戏的数据结构

Question

试图找出如何为国际象棋游戏编程存储一些有用的数据。

我决定将由机载西洋棋棋子发出的光线存储在Raycaster中;这个问题是关于这个结构的实现。

TL; DR（仅用于国际象棋游戏玩家...）

首先，我已确定了三个各种射线：

• Ray.NORMAL或Ray.FULL：它们是由发射所有的棋子，但不是棋子，在一个迭代的方式（车，象，后）否（骑士和国王）
• Ray.CAPTURE：只能通过典当发出，左前方和/或右前方捕捉
• Ray.OFFSET ：向前移动时由兵发出，以及为铸造而成的国王/白嘴鸦

因此光线的定义如下：

class Ray { 

    constructor (owner, kind) { 
    this.owner = owner // chessman which emits ray 
    this.kind = kind 
    this.ref = null 
    this.sequence = [] 
    } 

    // is computed afetr construction 
    expand (ref, sequence) { 
    this.ref = ref // starting ref (origin of the ray) 
    this.sequence = sequence // array of refs 
    } 

    // is called when ray is inserted into raycaster 
    interact (otherRay) { 
    // to be implemented 
    } 
} 

光线也有两个特殊化合物性质：

• 遮蔽{射线：空，IDX：-1}
• 交叉{ray：null，idx：-1}

它表示这个光线实例在哪里可以由另一棋子被隐藏，并且其中另一个射线横穿它，以检测通过性和干扰（对于易位）

该问题：

如何存储有效光线在RayCaster？

在优化诸如操作的方式：

• 1. 添加新计算的射线，计算与先前存储的人的相互作用，在MO，opmal成本？
• 从一个给定的起始REF确定，所有目标砖/ REF？
• 确定哪个容易射线靶向给定的参考，来计算在此瓦PRESSION平衡？

提出的解决方案/ ALTERNATIVES

• 射线的单一阵列：最坏的情况下64层* 63层的元件，珍贵寻求的光线和计算相互作用
• 地图阵列：Map.set（ startingRef，[list_of_emtted_rays_from_startingRef]）
• 数组映射：映射。集（endingRef，[list_of_targetinhg_rays_to_endingRef]）

，也许一个很好的候选人：

保持2个地图阵列，一个用于发射，一个用于靶向

class RayCaster { 
    constructor() { 
    this.startings = new Map() 
    this.endings = new Map() 
    } 

    cast(board) { ...iterate through board and casts individual rays } 

    add(ray) { ... } 

    getRefsAttackedBy(ref) { ... } 

    getRefsAttacking(ref) { ... } 
} 

那么，什么是你的感情关于这个数据结构（RayCaster）？

Answer 1

终于因为地图是时间常数的访问，我也考虑过双地图实现：

constructor() { 
    this.startings = new Map() 
    this.endings = new Map() 
    this.counters = { rays: 0, interactions: 0 } 
} 

每个地图由董事会裁判键，从“A1”到“H8”

casts(board) { 
    this.counters = { 
    rays: this.raysFrom(board), 
    interactions: this.computeInteractions() 
    } 
} 

添加射线是简单明了：

raysFrom(board) { 
    let counter = 0; 

    board.traverse((ref, chessman) => { 
    let rays = chessman.cast(ref) 

    for(let ray of rays) { 
     this.add(ray) 
    } 

    counter += rays.length 
    }) 

    return counter 
} 

和AA简单射线：

add (ray) { 
    let skey = ray.ref 
    let sRays = this.startings.get(sKey) 

    if(sRays.indexOf(ray) === -1) { 
    sRays.push(ray) 
    } 

    ray.traverse((seqIdx, seqRef) => { 
    let seqKey = seqRef.key 
    let eRays = this.endings.get(seqKey) 

    if (eRays.indexOf(ray) === -1) { 
     eRays.push(ray) 
    } 
    }) 
} 

计算射线相互作用（交叉和阴影）是更复杂：

computeInteractions() { 
    let counter = 0 

    // consider all starting rays 
    for (let {sRef, sRays} of this.startings) { 
    for (let sRay of sRays) { 
     sRay.traverse((seqIdx, seqRef) => { 

     // consider all possible intersections 
     // into the endings map 
     let eRays = this.endings.get(seqRef.ref) 

     for(let eRay of eRays) { 
      // ensure that rays are different 
      if (sRay !== eRay) { 
      sRay.interact(eRay) 
      eRay.interact(sRay) 
      } 
     } 
     }) 
    } 
    } 

    return counter 
} 

工作的其余部分只是在射线类别确定如何两条射线能相互作用（交叉或阴影）

感谢您的咨询，最好的问候！