Визуализатор алгоритмов Дейктры

Пару месяцев назад я сделал интерактивный визуализатор 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_Visualizer

Используйте 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-битных беззнаковых целых чисел, каждое целое число, представляющее пиксель.

Для преобразования из цвета 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
• получить 32-битное представление 8-битного буфера создать массив из данных изображения 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);
}

Пример

Приведенный ниже пример предназначен только для того, чтобы показать, как вышеперечисленные методы можно использовать для анимации сложных данных на основе сетки с небольшими накладными расходами на рендеринг.

Он не реализует алгоритм Дейкстры, а скорее является производным решением для поиска пути.

Он преобразует функцию поиска пути в функцию генератора, чтобы решение можно было приостановить на определенных шагах, чтобы можно было отобразить частичное решение.

Существуют различные другие незначительные различия между описанием в моем ответе и приведенными ниже реализациями.

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>

Я не знаю, есть ли способ избежать вложенного цикла в этом случае, потому что вам нужно выполнить вычисление, которое включает каждый индекс внутреннего цикла с каждым индексом внешнего цикла.

Но я думаю, что не нужно рассчитывать 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;

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