Bloodman 290 Odesláno: 10. Březen Share Odesláno: 10. Březen 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? Link to comment Share on other sites More sharing options...
Quiter 96 Odesláno: 11. Březen Share Odesláno: 11. Březen 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. Link to comment Share on other sites More sharing options...
DuFF 78 Odesláno: 11. Březen Share Odesláno: 11. Březen (upraveno) 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 by DuFF 1 Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now