Javascript : optimize data structure for chess game

Trying to figure out how to store some useful data for chess games programming.

I decided to store rays emitted by on-board chessmen in a Raycaster; This question is about the implementation of this structure.

TL;DR (for chess gamers only...)

first of all, I have identified three kinds of rays :

Ray.NORMAL or Ray.FULL: they are emitted by all chessmen but not pawns, in an iterative way (rook, bishop, queen) or not (knight and king)

Ray.CAPTURE: emitted only by pawns, ahead left and /or ahead right captures

Ray.OFFSET: emitted by pawns when moving forward, and kings/rooks for castling

Thus a ray is defined like this :

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
  }
}

Rays also have two special compound properties :

shadowing { ray: null, idx: -1 }

crossing { ray: null, idx: -1 }

which denote where this ray instance may be shadowed by another chessman, and where another ray is crossing it, to detect passability and interference (for castling)

THE PROBLEM:

How to store efficiently rays in the RayCaster?

In a way that optimizes operations such as:

adding a newly computed ray, computing interactions with previously stored ones, at a mo,opmal cost?

determining from a given starting ref, all targeted tiles/ref?

determining easily which rays target a given ref, to compute pression balance on this tile?

PROPOSED SOLUTIONS / ALTERNATIVES

single array of rays : worst case 64 * 63 elements, costful for seeking a ray and compute interactions

Map of arrays : Map.set(startingRef, [list_of_emtted_rays_from_startingRef])

Map of arrays : Map.set(endingRef, [list_of_targetinhg_rays_to_endingRef])

and maybe a good candidate :

maintain 2 maps of arrays, one for emitted, and one for targeting

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) { ... }
}

So what are your feelings about this data structure (the RayCaster)?

---

finally since Maps are time constant access, I have considered a double-maps implementation :

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

Each map is keyed by board refs, from "a1" to "h8"

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

Adding rays is straighforward :

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
}

And aa simple ray :

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)
    }
  })
}

Computing ray interactions (crossing and shading) is more complicated :

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
}

The rest of the work is just determining in the ray class how two rays could interact (crossing or shading)

Thanks for advice, best regards !

链接地址: http://www.djcxy.com/p/84634.html

上一篇: oledb异常未处理

下一篇: Javascript：优化国际象棋游戏的数据结构