Как можно более эффективно кодировать этот проект Cellular Automata? - PullRequest
Новая
       9

Как можно более эффективно кодировать этот проект Cellular Automata?

0 голосов
/ 30 ноября 2018

Я новичок в программировании и меня интересуют сотовые автоматы, поэтому я решил попробовать написать скрипт с использованием JavaScript как для практики кодирования, так и для того, чтобы я мог сделать персонализированный.Созданный мною проект клеточных автоматов предназначен для простой двоичной (черно-белой) 2D-таблицы CA, которая просматривает цвета 8 ближайших соседей ячейки и цвет самой ячейки и обновляет ее цвет в зависимости от правил, приведенных втаблица 'ruleset' под таблицей CA.Единственная проблема заключается в том, что написанный мной код обрабатывает каждую итерацию вечно, очевидно из-за всех больших циклов, в которых он нуждается.На самом деле, когда я пишу это, я понимаю, что могу уменьшить вычислительную мощность, необходимую, прекратив поиск сравнения между текущей конфигурацией цвета соседа и набором всех возможных конфигураций, когда оператор if находит правильную конфигурацию, но это, вероятно, не уменьшитвычислительная мощность нужна на количество, которое я бы предпочел, и я уверен, что есть больше способов сделать это быстрее.Если бы кто-нибудь мог дать мне несколько советов о том, как уменьшить вычислительную мощность еще больше, я был бы очень признателен.Также, пожалуйста, объясните свои ответы в терминах непрофессионалов.Спасибо!Вот код: 

<!DOCTYPE html>
<html>
<head>
<title></title>


<style>
table {border-collapse: collapse;}
table, td, th {border: 1px solid black;}
td {width:1px; height:1px;}
</style>

</head>
<body>

<button onclick="Toggle()">Toggle</button>  

<!-- Toggle runs the Iterate function with a setInterval -->

<button onclick="Iterate()">Iterate</button>
<br>


<script>


document.write("<table>")
for (row=0; row<100; row++) {
document.write("<tr>")
for (col=0; col<100; col++) 
{document.write("<td id = 'R" + row + "C" + col + "'  style='background-color: white' ondblclick='MouseDown(this)' onmousedown='MouseDown(this)' onmouseover='MouseUp(this)'>" + "</td>")}
document.write("</tr>")}
document.write("</table>")

// This is the cellular automata table

document.write("<br>")

document.write("<table>")
for (row=0; row<16; row++) {
document.write("<tr>")
for (col=0; col<32; col++) 
{document.write("<td id = 'id" + (col+32*row) + "'  style='background-color: white' ondblclick='MouseDown(this)' onmousedown='MouseDown(this)' onmouseover='MouseUp(this)'>" + "</td>")}
document.write("</tr>")}
document.write("</table>")

// This is the 'ruleset' table


let determiner = 0
function MouseDown(cell) {determiner = 1
if (cell.style.backgroundColor == "white") {cell.style.backgroundColor = "black"}
else {cell.style.backgroundColor = "white"}}
window.addEventListener('mouseup', function(event){determiner = 0})
function MouseUp(cell) {if (determiner == 1) {
if (cell.style.backgroundColor == "white") {cell.style.backgroundColor = "black"}
else {cell.style.backgroundColor = "white"}}}

// This section provides the click & drag cell colour changing functions



for (i=0; i<512; i++) {
if (i % 512 < 256){this["j1"] = "white"} else {this["j1"] = "black"}
if (i % 256 < 128){this["j2"] = "white"} else {this["j2"] = "black"}
if (i % 128 < 64){this["j3"] = "white"} else {this["j3"] = "black"}
if (i % 64 < 32){this["j4"] = "white"} else {this["j4"] = "black"}
if (i % 32 < 16){this["j5"] = "white"} else {this["j5"] = "black"}
if (i % 16 < 8){this["j6"] = "white"} else {this["j6"] = "black"}
if (i % 8 < 4){this["j7"] = "white"} else {this["j7"] = "black"}
if (i % 4 < 2){this["j8"] = "white"} else {this["j8"] = "black"}
if (i % 2 < 1){this["j9"] = "white"} else {this["j9"] = "black"}
this["compare"+i] = {unit00: j1,unit01: j2,unit02: j3,unit10: j4,unit11: j5,unit12: j6,unit20: j7,unit21: j8,unit22: j9}
}

// This creates an object for each possible block of 9 cells to compare with the actual blocks of cells around each cell in the Iterate() function


function Iterate() {
this["groupvec"] = []
for (i=0; i<100; i++) {
for (j=0; j<100; j++) {
if (i !== 0 && i !== 99) {rownum = [i-1, i, i+1]}
else if (i == 0) {rownum = [99, 0, 1]}
else if (i == 99) {rownum = [98, 99, 0]}
if (j !== 0 && j !== 99) {colnum = [j-1, j, j+1]}
else if (j == 0) {colnum = [99, 0, 1]}
else if (j == 99) {colnum = [98, 99, 0]}
this["group"+"R"+i+"C"+j] = {}
for (r in rownum) {
for (c in colnum) {
this["group"+"R"+i+"C"+j]['unit'+r.toString()+c.toString()] = document.getElementById("R" + rownum[r] + "C" + colnum[c]).style.backgroundColor
}}
this["groupvec"].push( JSON.stringify(this["group"+"R"+i+"C"+j]) )
}}
for (i=0; i<100; i++) {
for (j=0; j<100; j++) {
for (k=0; k<512; k++) {
if (groupvec[j+(100*i)] == JSON.stringify(window["compare"+k.toString()])) {
document.getElementById("R"+i+"C"+j).style.backgroundColor = document.getElementById("id"+k).style.backgroundColor
}}}}}

// This function finds the colours of the cells in a block of 9 cells around each cell, compares them with the 'compare' objects and then changes their colour to the colour of the 'ruleset' table with the same index as the 'compare' object.

let toggler = null
function Toggle() {
if (toggler == null) {toggler = setInterval(Iterate.bind(null), 1000)}
else {clearInterval(toggler); toggler = null}
}

// This provides an automated run function for the CA

</script>


</body>
</html>

1 Ответ

0 голосов
/ 30 ноября 2018

Ваш код повторяется 5 210 000 раз за каждую итерацию (100 строк * 100 столбцов * 3 ячейки * 3 ячейки + 100 строк * 100 столбцов * 512 ячеек набора правил).Это довольно большая работа для каждой итерации, и она усугубляется использованием HTML <table>, с которого вы постоянно читаете и пишете стили.

Если вы хотите более надежное решение,попробуйте использовать Canvas для отображения состояния вашего ЦС и массивы JavaScript для обработки этого состояния.Возможно, вы все еще можете использовать таблицу для установки набора правил в начале, а затем сохранить его в массиве, чтобы при проверке вы проверяли массив данных в памяти.

Тогда ваш код можетвыглядеть примерно так, что повторяется 80 000 раз (хотя может быть и больше, если вы включите свои наборы правил): 

const canvas = document.getElementById('canvas');
const context = canvas.getContext('2d');
const width = 100;
const height = 100;
const cellWidth = 4;
const cellHeight = 4;

// Access cells with automaton[row][column]
let automaton = Array(height).fill(Array(width).fill(0)));

// Initialise your automaton somehow
// ...

function iterate() {
    // Create the next automaton state to write updates to
    let nextAutomaton = Array(height).fill(Array(width).fill(0)));
    for (let y = 0; y < height; ++y) {
        for (let x = 0; x < width; ++x) {
            // Get the surrounding 8 cells
            // (n + MAX + 1) % MAX will wrap around
            // (n + MAX - 1) % MAX will wrap around
            const surroundingIndices = [
                { x: x, y: (y + height - 1) % height },                       // above
                { x: (x + width + 1) % width, y: (y + height - 1) % height }, // above right
                { x: (x + width + 1) % width, y: y },                         // right
                { x: (x + width + 1) % width, y: (y + height + 1) % height }, // below right
                { x: x, y: (y + height + 1) % height },                       // below
                { x: (x + width - 1) % width, y: (y + height + 1) % height }, // below left
                { x: (x + width - 1) % width, y: y },                         // left
                { x: (x + width - 1) % width, y: (y + height - 1) % height }  // above left
            ];
            for (int i = 0; i < 8; ++i) {
               const cell = automaton[surroundingIndices.y][surroundingIndices.x];
               // Do something based on the value of this surrounding cell
               // This could depend on your ruleset
               // ...
            }
            // Set this cell's value in the next state
            nextAutomaton[y][x] = 1;
            // Render the cell
            context.fillStyle = 'red';
            context.fillRect(x, y, cellWidth, cellHeight);
        }
    }
    // Overwrite the old automaton state
    automaton = nextAutomaton;
}

Для анимации вашего автомата вам понадобится window.requestAnimationFrame, который должен вызывать себя рекурсивно с помощью функции iterate, и который вы можете запускать или останавливать с помощью переключателя (см. window.cancelAnimationFrame).

...