Field assign function

[trsh]

Hi! I could not make sense of some of function you wrote, so i did my version. What it does, is, for example takes mountain 1 and assign distances on its neighbors, than for next mountain etc. When all mountains are iterated, it goes trough again, but assigns neighbor neighbors, etc., until all is assigned. In simple words it kind of radiates the fields out for the seed 1 by 1. What do you think? Seems to work, but results are different.

/* Distance from any point in seeds_r to all other points, but 
 * don't go past any point in stop_r */
function assignDistanceField(mesh, seeds_r, stop_r) {
    const randInt = makeRandInt(SEED);
    let {numRegions} = mesh;
    let r_distance = new Float32Array(numRegions);
    r_distance.fill(Infinity);

    let queue = [];
    for (let r of seeds_r) {
        queue.push(r);
        r_distance[r] = 0;
    }

    let r_field = [];
    var i = 0;

    while(queue.length > 0){

        if(r_field[i] === undefined){
            r_field[i] = [queue[i]];
        }

        let new_r_field = [];

        for (let n = 0; n < r_field[i].length; n++) {
            let current_r = r_field[i][n];
            let neighbor_rs = mesh.r_circulate_r([], current_r);            

            for (let neighbor_r of neighbor_rs) {
                if (!stop_r.has(neighbor_r)){
                    let new_r_distance = r_distance[current_r] + 1;

                    if (r_distance[neighbor_r] === Infinity) {
                        r_distance[neighbor_r] = new_r_distance;  
                        new_r_field.push(neighbor_r);
                    }else if(new_r_distance < r_distance[neighbor_r]){
                        r_distance[neighbor_r] = new_r_distance;
                    }
                }                
            }
        }        

        r_field[i] = new_r_field;

        if(r_field[i].length === 0){
            queue.splice(i, 1);
            r_field.splice(i, 1);
        }

        i++;

        if(i >= queue.length){ // shuffle
            i = 0;
        }
    }

    /*let out_r = [];
    for (let queue_out = 0; queue_out < mesh.numRegions; queue_out++) {
        let pos = queue_out + randInt(queue.length - queue_out);
        let current_r = queue[pos];
        queue[pos] = queue[queue_out];
        mesh.r_circulate_r(out_r, current_r);
        for (let neighbor_r of out_r) {
            if (r_distance[neighbor_r] === Infinity && !stop_r.has(neighbor_r)) {
                r_distance[neighbor_r] = r_distance[current_r] + 1;
                queue.push(neighbor_r);
            }
        }
    }*/

    return r_distance;
    // TODO: possible enhancement: keep track of which seed is closest
    // to this point, so that we can assign variable mountain/ocean
    // elevation to each seed instead of them always being +1/-1
}

[trsh]

P.S. in your code I got lot's of undefined for let current_r = queue[pos];. Have no idea how that effects stuff when going down the pipe :)

[redblobgames]

Ah, sorry about that! As a "game jam" type project, some of my code here is messy and undocumented. It works similarly to your function, but it does it by trying to minimize allocations. Here's the explanation of how that function works:

This is adapted from a breadth first search (BFS). With BFS, the queue will be all elements in queue[queue_out ... queue.length-1]. Pushing onto the queue adds an element to the end, increasing queue.length. Popping from the queue removes an element from the beginning by increasing queue_out.

To add variety, I do a random search instead of a breadth first search. I continue to queue[queue_out ... queue.length-1] as the frontier elements to be searched, but at each step I pick a random element to pop instead of the earliest one. I do this by swapping queue[pos] and queue[queue_out].

Yes, you are correct, there is a bug in the code. Instead of the for loop having queue_out < mesh.numRegions it should be queue_out < queue.length.

[trsh]

Ok. Will try to get my head around it. Thanks for the explanation :)