2
\$\begingroup\$

A couple months ago I made an interactive dijktra visualizer that allowed the user to setup the map nodes and run the algorithm. I thought it was a good way to solidify my algorithm and html/css knowledge. I'd like for you guys to test my application out and give any advice in any way I could make it better.

One particular element that i'd like to improve is the map rendering, which I did by making a table and updating it's rows and columns. This solution worked out good but I found it to be slow with maps with larger dimensions.

function render () {
    let html = ''

    for (let row = 0; row < mapHeight; row++) {
        html += '<tr>'

        for (let column = 0; column < mapWidth; column++) {
            // Ignore "nodeIndex", "colorIndex" and such
            nodeIndex = column + ( row * mapWidth )
            let colorIndex = myNodes[nodeIndex].colorIndex

            html += `<td style="background-color:${nodeColors[colorIndex]};"></td>`
        }

        html += '</tr>'
    }

    //"mapTable" being the element in which this table is rendered
    mapTable.innerHTML = html 
}

Hope you guys like it and please feel welcome to give any criticism, have fun!

My page: https://github.com/Tlomoloko/Dijkstra_Visualizer

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Use DOM not markup

Your code builds DOM by building a string containing markup. Markup is intended as a transport format eg between server and client and you should avoid using markup to build page content when you have access to the DOM.

Building a table.

Generally building page content is best done using the DOM interface rather than creating a string containing the markup.

For example to create a table and insert row then cells you would

function createTable(width, height, colors) {
    var r = , c; // row column
    const table = document.createElement("table");
    while (r < height) {
        const row = table.insertRow();
        c = 0;
        while (c < width) {
             cell = row.insertCell();
             cell.style.background = colors[c + r * width];
             c ++;
        }
        r ++;
    }
    document.appendChild(table);
}

The references for calls and interfaces used are

This will improve performance as there is no need to parse the markup.

However as tables get larger them become slower and slower. A grid based path finding solution these days can contains 100,000+ cells which is well beyond the practical limit of a table.

A better way

Tables are complicated entities when all you display is color information. The optimal method to show a grid of pixels is to use a bitmap. In this case a HTMLCanvasElement provides both a pixel store and an interface CanvasRenderingContext2D to change pixel content as needed.

Create Canvas

To create a canvas and prepare a canvas

function createCanvas(container, width, height) {
    const canvas = Object.assign(document.createElement("canvas"), {width, height});
    container.appendChild(canvas);
    return canvas;
}

To be practical the canvas pixels need to be of a discernible size. We can do this by sizing the canvas using a CSS rule. Because images are interpolated (smoothed) we also need to ensure pixels use the correct rendering rule.

canvas {
    width: 100%;
    height: 100%;
    image-rendering: pixelated;    
}

Cells and pixels

The issue now is the pixel colors. The array nodeColors (not passed to the function you provide) contains strings representing a CSS color. This is unfortunately not a RGBA8 pixel value. nodeColors ideally should be an array of 32bit Unsigned ints each int representing a pixel.

To convert from a CSS # color (in the form #RRGGBBAA) to a RGBA8 pixel

function CSStoPixel(cssHashColor) {
     return parseInt(cssHashColor.slice(1,3), 16) + 
            ((parseInt(cssHashColor.slice(3,5), 16) << 8) +  
            ((parseInt(cssHashColor.slice(5,7), 16) << 16) +  
            ((parseInt(cssHashColor.slice(5,7), 16) << 24);
}

Ideally you would use the raw channel values and build the RGBA8 pixels

function RGBAtoPixel(r, g, b, a) { // each 8 bit in range 0 - 255
     return (a << 24) + (b << 16) + (g << 8) + r;
}

Then use a Uint32Array to create the nodeColors to hold each pixel

const nodeColors = new Uint32Array(width * height); // colors are defaulted to transparent black

Rendering

Once you have setup the canvas and the pixel color array it then is trivial to transfer the pixels from the color array to the canvas display buffer.

To...

// Assumes pixel array size matches canvas pixel count
function displayPixelArray(pixels, canvas) {
    const ctx = canvas.getContext("2d");
    const imgBuf = ctx.getImageData(0, 0, canvas.width, canvas.height);
    new Uint32Array(imgBuf.data.buffer).set(pixels);
    ctx.putImageData(imgBuf, 0, 0);
}

Example

The example below intends to only show how the methods above can be used to animate complex grid based data with a low rendering overhead.

It does not implement Dijkstra's algorithm but rather a derived path finding solution.

It converts a path finding function into a generator function so that the solution can be paused at defined steps so that the partial solution can be displayed

There are various other minor differences between the description in my answer and the implementations below.

const ctx = canvas.getContext("2d");
function resized() {
    canvas.width = innerWidth;
    canvas.height = innerHeight;
}
resized();
addEventListener("resize", resized);
const MAP_WIDTH = 128;      // in pixels
const MAP_HEIGHT = 128;     // in pixels
const DEMO_STEP_TIME = 34; // in ms
const DEMO_RESTART_TIME = 1000; // in ms
const DENO_PX_PER_STEP = 96;
const DEMO_WALL_COUNT = 160;
const randUint = (m, M) => Math.random() * (M - m) + m | 0;
const randOdds = (odds) => Math.random() < 1 / odds;
const P2 = (x, y) => ({x, y});
const pathCols = new Uint32Array(MAP_WIDTH * MAP_HEIGHT);
const worldMap = new Uint32Array(MAP_WIDTH * MAP_HEIGHT);
const worldMapImg = createCanvas(MAP_WIDTH, MAP_HEIGHT);
const pathColImg = createCanvas(MAP_WIDTH, MAP_HEIGHT);
const start = P2(10, 10);
const end = P2(MAP_WIDTH - 10, MAP_HEIGHT - 10);
var demoQuickRestart = false;

demo();
function stepPathFinding(pathSolver) {
    if (pathSolver.next().value !== undefined) {
        setTimeout(stepPathFinding, DEMO_STEP_TIME, pathSolver);
    } else {
        setTimeout(demo, demoQuickRestart ? 18 :  DEMO_RESTART_TIME)   
    }
    displayPathing(ctx, pathCols, pathColImg, worldMapImg);
}
function demo() {
    createRandomMap(worldMapImg, worldMap, pathColImg);
    const pathSolver = findShortest(pathCols, worldMap, start, end, MAP_WIDTH, MAP_HEIGHT);
    stepPathFinding(pathSolver); 
}
function createRandomMap(mapImg, map) {
    const w = mapImg.width, h = mapImg.height;
    mapImg.ctx.clearRect(0, 0, w, h);
    mapImg.ctx.fillStyle = "#0C0";
    mapImg.ctx.fillRect(0, 0, w, h);
    mapImg.ctx.clearRect(2, 2, w-4, h-4);
    mapImg.ctx.beginPath();
    var c = DEMO_WALL_COUNT, wW, wH; // w for wall
    while (c--) {
        if (randOdds(2)) {
            wW = 1;
            wH = randUint(9, 26);
        } else {
            wH = 1;
            wW = randUint(9, 26);
        }
        mapImg.ctx.rect(randUint(0, w - wW), randUint(0, h - wH), wW, wH);
    }
    mapImg.ctx.fill();
    map.set(new Uint32Array(mapImg.ctx.getImageData(0, 0, w, h).data.buffer));
}
function createCanvas(width, height) {
    const canvas = Object.assign(document.createElement("canvas"), {width, height});
    canvas.ctx = canvas.getContext("2d");
    return canvas;
}
function displayPathing(ctx, cols, colsImg, wMapImg) {
    ctx.imageSmoothingEnabled = false;
    const w = ctx.canvas.width, h = ctx.canvas.height;
    ctx.clearRect(0, 0, w, h);
    ctx.drawImage(wMapImg, 0, 0, w, h);
    const imgBuf = colsImg.ctx.getImageData(0, 0, colsImg.width, colsImg.height);
    new Uint32Array(imgBuf.data.buffer).set(cols);
    colsImg.ctx.putImageData(imgBuf, 0, 0);
    ctx.drawImage(colsImg, 0, 0, w, h)
}


function *findShortest(dMap, wMap, start, end, w, h) {
    // name rules use in this function are u,l,r,d for up, left, right, down
    var pxCount = 0, idx, minDist;
    dMap.fill(0); 
    const worldSize = w * h;
    const markWalls = () => {
        var idx = worldSize;
        while (idx--) { dMap[idx] = wMap[idx] !== 0 ? 0x1FFFFFF : 0 }
    }
    markWalls();
    const endIdx = end.x + end.y * w;
    const startIdx = start.x + start.y * w;
    const stack = [startIdx];
    if (dMap[startIdx] !== 0 || dMap[endIdx] !== 0) { demoQuickRestart = true; return; } // no solution.
    demoQuickRestart = false;
    dMap[startIdx] = 0xFF000000;
    const nextNode = (idx, dist) => {
        if (!dMap[idx] && !wMap[idx]) {
            dMap[idx] = 0xFF000000 + dist + 32;
            stack.push(idx);
            return 1;
        }
        return 0;
    }
    const checkHomeStep = (currentIdx, nextIdx) => {
        const dist = dMap[nextIdx] & 0xFFFF;
        if (dist <= minDist) {
            if (dist < minDist || randOdds(2)) {
                minDist = dist;
                return nextIdx;
            }
        }   
        return currentIdx;
    }
    while (stack.length) {
        const pxIdx = stack.shift();
        const dist = dMap[pxIdx] & 0xFFFF;
        const u = pxIdx - w, d = pxIdx + w, l = pxIdx - 1, r = pxIdx + 1;
        u >= 0 && nextNode(u, dist);
        d < worldSize && nextNode(d, dist);
        l % w > 0 && nextNode(l, dist);
        r % w < w - 1 && nextNode(r, dist);   
        (pxCount++ % DENO_PX_PER_STEP) === 0 && (yield pxIdx);
    }
    
    // find path home
    idx = endIdx;
    if (dMap[idx] > 0) {  // only if a clear path found;
        while (idx !== startIdx) {
            const u = idx - w, d = idx + w, l = idx - 1, r = idx + 1;
            const ul = idx - w - 1, ur = idx - w + 1 , dl = idx + w - 1, dr = idx + w + 1;
            minDist = dMap[u] & 0xFFFF;
            idx = u;
            idx = checkHomeStep(idx, d);
            idx = checkHomeStep(idx, l);
            idx = checkHomeStep(idx, r);
            
            if (randOdds(2)) {
                idx = checkHomeStep(idx, ul);            
                idx = checkHomeStep(idx, ur);
                idx = checkHomeStep(idx, dl);
                idx = checkHomeStep(idx, dr);
            }
            
            dMap[idx] = 0xFFFFFFFF;
            yield idx;
        }
    }
}
canvas {
    position: absolute;
    top: 0px;
    left: 0px; 
    background: #036;
    image-rendering: pixelated; 
}
<canvas id="canvas"></canvas>

\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much for taking your time to answer my question so thoroughly! I really had no idea how to make this faster. I'll take a look at these elements that you mentioned, I'm sure they will be of great help \$\endgroup\$
    – Tlomoloko
    Mar 26, 2021 at 0:27
2
\$\begingroup\$

I don't know if there is a way to avoid the nested loop in this case because you need to do a calc that involves every inner loop index with every outer loop index.

But I think that is not necessary to calculate row * mapWidth in every iteration in the inner loop, once that both variables are available outside it

for (let row = 0; row < mapHeight; row++) {
    //...
    let cached = row * mapWidth;

    for (let column = 0; column < mapWidth; column++) {
        nodeIndex = column + cached;
        let colorIndex = myNodes[nodeIndex].colorIndex;

        //...
    }
//...
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.