Dijktra算法可视化器

Question

几个月前，我制作了一个交互式dijktra可视化工具，允许用户设置地图节点并运行算法。我认为这是巩固我的算法和html/css知识的好方法。我希望你们能对我的申请进行测试，并给出任何我能做得更好的建议。

我想要改进的一个特定元素是地图呈现，我通过创建一个表并更新它的行和列来实现它。这个解决方案效果很好，但我发现，对于尺寸更大的地图，它的速度很慢。

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 
}

希望大家喜欢它，欢迎大家提出批评，玩得开心！

我的页面：https://github.com/Tlomoloko/Dijkstra_目视器

Answer 1

使用DOM而不是标记

代码通过构建包含标记的字符串来构建DOM。标记作为传输格式(如服务器和客户端之间的传输格式)，当您访问DOM时，您应该避免使用标记来构建页面内容。

构建一个表.

通常，构建页面内容最好使用DOM接口，而不是创建包含标记的字符串。

例如，要创建一个表并插入行，然后插入单元格，则需要

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

对使用的调用和接口的引用包括

• Node.appendChild
• Document.createElement
• HTMLTableElement
• HTMLTableElement.insertRow
• HTMLTableRowElement
• HTMLTableRowElement.insertCell
• HTMLTableCellElement继承自HTMLElement

这将提高性能，因为不需要解析标记。

然而，随着表越来越大，它们变得越来越慢。现在，基于网格的路径查找解决方案可以包含100,000+单元，这远远超出了表的实际限制。

--一个更好的方法

当您只显示颜色信息时，表是复杂的实体。显示像素网格的最佳方法是使用位图。在这种情况下，HTMLCanvasElement提供像素存储和接口CanvasRenderingContext2D，以根据需要更改像素内容。

创建画布

创建画布并准备画布

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

为了实用，画布像素需要有一个可辨别的大小。我们可以通过使用CSS规则调整画布的大小来做到这一点。由于图像是插值的(平滑的)，我们也需要确保像素使用正确的渲染规则。

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

单元和像素

现在的问题是像素颜色。数组nodeColors (未传递给您提供的函数)包含表示CSS颜色的字符串。不幸的是，这不是一个RGBA8像素值。理想情况下，nodeColors应该是一个由32位无符号int组成的数组，每个int表示一个像素。

将CSS #颜色(形式为#RRGGBBAA)转换为RGBA8像素

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

理想情况下，您应该使用原始通道值并构建RGBA8像素。

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

然后使用Uint32Array创建保存每个像素的nodeColors。

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

渲染

一旦设置了画布和像素颜色数组，就很容易将像素从颜色数组传输到画布显示缓冲区。

为了..。

• 使用ctx.getImageData获取画布像素
• 或创建缓冲区ctx.createImageData
• 获取8位缓冲区的32位视图，从图像数据Uint8ClampedArray.buffer创建数组
• 使用Uint32Array.set设置像素
• 将像素移动到画布存储区，使用ctx.putImageData发送图像数据

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

示例

下面的示例只说明如何使用上述方法以较低的呈现开销来动画基于网格的复杂数据。

它没有实现Dijkstra的算法，而是一个派生的路径查找解决方案。

它将路径查找函数转换为生成器函数，以便在定义的步骤上暂停解决方案，从而显示部分解决方案。

在我的答案中的描述和下面的实现之间还有其他一些细微的区别。

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;
            minDist = dMap[u] & 0xFFFF;
            idx = u;
            idx = checkHomeStep(idx, d);
            idx = checkHomeStep(idx, l);
            idx = checkHomeStep(idx, r);
            dMap[idx] = 0xFFFFFFFF;
            yield idx;
        }
    }
}

canvas {
    position: absolute;
    top: 0px;
    left: 0px; 
    background: #036;
    image-rendering: pixelated; 
}

<canvas id="canvas"></canvas>

Answer 2

我不知道在这种情况下是否存在避免嵌套循环的方法，因为您需要执行一个calc，它涉及每个内循环索引和每个外部循环索引。

但是，我认为在内部循环中的每一次迭代中计算row * mapWidth都是不必要的，前提是这两个变量都在内部循环之外可用。

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;

        //...
    }
//...
}