ostatní [Otazka] Ako generovat spawn poziciu hraca

[Jiu 299]

Ahoj,

Potreboval by som vymysliet algoritmus, ktory by vedel na zaklade seedu (ID [long]) generovat cca rovnomerne rozlozene unikatne pozicie v 2D priestore.

Mam priestor 100x100 v roomke (https://cord.dj/r/0wui9jo4cgr), ked sa pripoji hrac, tak by som ho potreboval spawnut tak, aby rovnomerne vyplnal volny priestor. tj. nespawne sa nahodne hrac na hraca, ale spawne sa do cca najviac volneho priestoru.

 

Niekto nejake napady?
 

[Quiter 99]

Neviem či úplne chápem čo chceš, ale čo keby si každému bodu priradil "prioritu" a následne túto prioritu znižoval ak v jej okolí pribudol nový hráč?

 

Príklad: 5 x 5

001 001 001 001 001			003 003 003 002 001			003 003 003 002 001
001 001 001 001 001			003 100 003 002 001			003 100 003 002 001
001 001 001 001 001			003 003 003 002 001			004 004 004 002 001
001 001 001 001 001			002 002 002 002 001			003 004 004 004 002
001 001 001 001 001			001 001 001 001 001			002 003 100 003 002

Najprv majú všetky maximálnu prioritu

Potom vygenerujem pozíciu 1, 1 (začínam 0, 0) a všetkym okolo znížim prioritu o 2 a tým vedľa nich o 1.

Potom vygenerujem pozíciu 4, 2 a opäť znížim prioritu. Prvku ktorý vygenerujem nastavím úplne najnižšiu prioritu aby mal prakticky 0 šancu že sa opäť vyskytne.

 

Vo výsledku to pre teba znamená, že pred generovaním náhodnej pozície si musíš vypočítať súčet priorít (ideálne ako "1 / priorita"), vygenerovať číslo z tohto rozsahu a potom nájsť ktorá pozícia patrí vygenerovanej hodnote.

 

Takže vo výsledku by to mohlo robiť to čo chceš, ale je za tým dosť réžie.

[DuFF 86]

Zdravím,

vyzerá to ako zaujímavý problém a pokúsim sa niečo vymyslieť... Zatiaľ zdieľam aspoň hračku, ktorá sa môže hodiť na vizualizáciu pri návrhu generátora:
 

Spoiler

class DumbGeneratorStrategy {
    constructor() {
        this.lastPoint = [0, 0]
    }
    
    generatePoint() {
        const [lastX, lastY] = this.lastPoint;
        const newPoint = [lastX + 1, lastY + 1];
        this.lastPoint = newPoint; 
        return newPoint;
    }
}

// TODO: seed
function random(min, max) {
    var range = max - min;
    return min + range * Math.random();
}

class FullyRandomGeneratorStrategy {
    constructor() {
    }
    
    generatePoint() {
        const x = random(0, 100);
        const y = random(0, 100);
        return [x, y];
    }
}

// https://stackoverflow.com/questions/951021/what-is-the-javascript-version-of-sleep
// sleep time expects milliseconds
function sleep (time) {
  return new Promise((resolve) => setTimeout(resolve, time));
}

const CANVAS_ID = 'drawingSpace';

function getCanvas() {
    return document.getElementById(CANVAS_ID);
}

function addCanvas() {
    const canvas = document.createElement('canvas');
    canvas.setAttribute('id', CANVAS_ID);
    canvas.setAttribute('width', 500);
    canvas.setAttribute('height', 500);
    canvas.setAttribute('style', 'border:1px solid #000000;');
    document.body.append(canvas);
    const ctx = canvas.getContext('2d');
    ctx.scale(5, 5); // show 100x100 space on a 500x500 canvas
}

function clearCanvas() {
    const canvas = getCanvas();
    const ctx = canvas.getContext('2d');
    ctx.clearRect(0, 0, canvas.width, canvas.height);
}

async function drawPoints(numberOfPoints, millisecondsPerPoint, strategy,) {
    const canvas = getCanvas();
    const ctx = canvas.getContext('2d');
    for (var i = 1; i < numberOfPoints; ++i) {
        var [x, y] = strategy.generatePoint();
        ctx.fillRect(x, y, 1, 1);
        await sleep(millisecondsPerPoint);
    }
}

addCanvas();
while (true) {
    await drawPoints(100, 10, new FullyRandomGeneratorStrategy());
    clearCanvas();
}

 

Viete si napísať vlastnú stratégiu generovania bodov - stačí vytvoriť triedu, ktorá obsahuje metódu generatePoint, ktorá vracia súradnice nového bodu. Táto metóda môže tiež ako side-effect napríklad updatovať nejaký váš stav (v prípade DumbGeneratorStategy je to iba posledný bod, ale môže to byť kľudne nejaká kolekcia všetkých bodov atď.), ktorý sa dá použiť na maximalizáciu vzdialenosti medzi generovanými bodmi.

// Edit:
Napísal som SquareSectorGeneratorStrategy, ktorá by možno mohla stačiť:
 

Spoiler

class SquareSector {
    constructor(bottomLeft, topRight) {
        [this.bottomLeftX, this.bottomLeftY] = bottomLeft;
        [this.topRightX, this.topRightY] = topRight;
        this.innerSectors = [];
        this.point = null;
        this.cumulativeNumberOfPoints = 0;
    }
    
    addPoint() {
        ++this.cumulativeNumberOfPoints;
        
        // sector does not contain any points yet
        if (!this.point) {
            const randomX = random(this.bottomLeftX, this.topRightX);
            const randomY = random(this.bottomLeftY, this.topRightY);
            this.point = [randomX, randomY];
            return this.point;
        }
        
        // sector contains only a single point - it is needed to create inner sectors
        if (this.innerSectors.length === 0) {
            this.split();
        }
        
        // pick one inner sector based on their cumulativeNumberOfPoints
        const priorities = this.innerSectors.map(sector => 1 - sector.cumulativeNumberOfPoints / this.cumulativeNumberOfPoints);
        const prioritiesSum = priorities.reduce((a, b) => a + b);
        const probabilities = priorities.map(priority => priority / prioritiesSum);
        const probabilityTable = probabilities.reduce((a, b) => {
            const lastElement = a[a.length - 1];
            const newElement = lastElement + b;
            a.push(newElement);
            return a;
        }, [0]);
        const randomNumber = Math.random();
        for (let i = 0; i < probabilityTable.length; ++i) {
            if (randomNumber < probabilityTable[i]) {
                return this.innerSectors[i - 1].addPoint();
            }
        }
    }
    
    split() {
        // create inner sectors
        const midPointX = (this.bottomLeftX + this.topRightX) / 2;
        const midPointY = (this.bottomLeftY + this.topRightY) / 2;
        this.innerSectors.push(new SquareSector([this.bottomLeftX, this.bottomLeftY], [midPointX, midPointY])); // bottomLeft
        this.innerSectors.push(new SquareSector([midPointX, this.bottomLeftY], [this.topRightX, midPointY])); // bottomRight
        this.innerSectors.push(new SquareSector([this.bottomLeftX, midPointY], [midPointX, this.topRightY])); // topLeft
        this.innerSectors.push(new SquareSector([midPointX, midPointY], [this.topRightX, this.topRightY])); // topRight
        
        // move the existing point to one of the new inner sectors
        for (const sector of this.innerSectors) {
            if (sector.containsPoint(this.point)) {
                sector.point = this.point;
                this.point = null;
                break;
            }
        };
    }
    
    containsPoint(point) {
        const [x, y] = point;
        return this.bottomLeftX <= x && x <= this.topRightX
            && this.bottomLeftY <= y && y <= this.topRightY;
    }
}

class SquareSectorGeneratorStrategy {
    constructor() {
        this.rootSector = new SquareSector([0, 0], [100, 100]);
    }
    
    generatePoint() {
        return this.rootSector.addPoint();
    }
}

 

Funguje tak, že sa kresliaca plocha rozdeľuje na sektory. Začína sa hlavným sektorom, ktorý pokrýva celú plochu. V prípade, že sa do sektoru vkladá 2. bod, sektor sa rozdelí na 4 štvorcové podsektory (ľavý dolný roh, pravý dolný roh, ľavý horný roh, pravý horný roh). Každý (pod)sektor si drží celkový počet bodov, ktoré sa nachádzajú v jeho všetkých podsektoroch (vrátane ich vnorených podsektorov). Tento počet potom zohráva úlohu pri voľbe, do ktorého zo 4 podsektorov sa má bod vložiť. Voľba sa opakuje postupne na nižších a nižších úrovniach, až kým sa nenájde sektor, ktorý neobsahuje žiadny bod. Vtedy sa vygeneruje náhodná pozícia v rámci daného sektoru... 

Všimol som si, že je trochu problém s tým, keď máš smolu a bod sa vygeneruje presne na hranici sektorov. Susediace sektory o sebe nič nevedia a je možné, že tak skončia 2 body nalepené na sebe. Ak chceš tomuto javu predísť, možno by sa dal upraviť spôsob, akým sa generujú body v najnižšom podsektore, t.j. zmeniť to z úplne náhodnej voľby na nejakú prioritizáciu stredu sektora.

Vizualizácia: https://www.youtube.com/watch?v=Y2ehPGPD1ZI&ab_channel=HFCDuFF

Edited 12. Březen, 2023 by DuFF