Javascript: optimiser la structure de données pour le jeu d'échecs

Question

Essayer de comprendre comment stocker des données utiles pour la programmation des parties d'échecs. J'ai décidé de stocker les rayons émis par les pièces d'échecs embarquées dans un Raycaster; Cette question concerne la mise en œuvre de cette structure.

TL; DR (pour les joueurs d'échecs seulement ...)

tout d'abord, j'ai identifié trois types de rayons:

• Ray.NORMAL ou Ray.FULL: ils sont émis par tous chessmen mais pas des pions, d'une manière itérative (freux, évêque, reine) ou non (chevalier et roi)
• Ray.CAPTURE: émis que par des pions, avant gauche et/ou capture avant droit
• Ray.OFFSET : émis par les pions en allant de l'avant, et les rois/les corbeaux par les rongeurs

Ainsi, un rayon est défini comme suit:

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

rayons ont également deux propriétés de composés spéciaux:

• ombrage {ray: null, idx: -1}
• passage {ray: null, idx: -1}

qui indique où cette instance de rayon peut être assombrie par une autre chessman, et où un autre rayon est traversant, pour détecter praticabilité et interférences (pour roque)

PROBLÈME:

Comment stocker efficacement rays dans le raycaster?

D'une certaine manière qui optimise les opérations telles que:

• 1. ajoutant un rayon nouvellement calculé, calcul interactions avec ceux précédemment stockées, à un mois, le coût opmal?
• 2. détermination d'un ref départ donné, toutes les tuiles ciblées/ref?
• 3. déterminer facilement les rayons cible un arbitre donné, pour calculer l'équilibre de pression sur ce carreau?

SOLUTIONS proposées/alternatives

• seul réseau de rayons: le pire cas 64 * 63 éléments, costful de rechercher une interaction de rayons et de calcul
• Carte des tableaux: Map.set (startingRef, [list_of_emtted_rays_from_startingRef])
• Carte des tableaux: Carte.set (endingRef, [list_of_targetinhg_rays_to_endingRef])

et peut-être un bon candidat:

maintenir 2 cartes de tableaux, un pour émis, et un pour le ciblage

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

Alors, quels sont vos sentiments à propos de cette structure de données (le RayCaster)?

Answer 1

enfin depuis cartes sont temps accès constant, je l'ai considéré comme une mise en œuvre à double cartes:

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

Chaque carte est calée par refs de société, de "A1" à "H8"

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

Ajout

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

Et aa simple rayon:

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

informatique interactions de rayons (de passage et d'ombrage) est plus complexe:

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 
} 

Le reste du produit est simplement de déterminer la classe de rayons comment deux rayons peuvent interagir (croisement ou ombrage)

Merci pour vos conseils, meilleures salutations!