Revisiting Lights Out

A long time ago I made a simulation of a well known game Lights Out. I made this a while ago and wasn't the best programmer at the time. Sure I could code but didn't really understand being efficient. I recently took some time to revisit my old project and I wanted to document the problems I ran into and the most impactful changes I made and why.

Here is the embedded video if you want

Part 1: The Problems I Had

Most minor issues first

UI and buttons

1. Too many buttons There were a lot of buttons. Firstly 4x4 and 5x5 game sizes are not always solvable. I removed those as a default option and only kept the grid sizes which solve. Next I cleaned up some of the buttons. There used to be warnings like (large grids laggy) and "Auto Solve (buggy)". It looked bad. While the warning was valid, I now have the skills to fix lag to an extent.
2. Unclear what the game was and how to play or win This was another fundamental change. There used to be a button which would set up the game state labeled randomized. The user would need to load the page, select the grid size, and click randomize. Simple right? Apparently not. Now when the user loads the page it starts as a randomized 6x6 grid. It used to be a 3x3. That option still exists, but I like the 6x6 because it is harder.

Small polishing steps

These are some smaller things that felt wrong.

1. Browser alerts Winning used to just trigger alert("You Won"). It worked but felt cheap and the user had to click to close it. I replaced this with an animation.
2. Win animation I added a cascading waterfall animation across the grid when you win. It randomly picks from 12 patterns. After the animation the grid auto randomizes so you can play again immediately. This seems small but it really helps people understand what is going on.
3. Hint button The solver always started from the top left which helped reveal a pattern or at least a strategy. If you know the math behind this game and some linear algebra you know the order does not matter. So I made the order random.

The largest problem: Large grids were laggy

The game uses linear algebra to solve the puzzle using Gaussian elimination with the three elementary row operations. That part was not very efficient but fine for now. The real problem was the buttons. I originally forked this from another project as a quick tool for my Math 221 class and while it worked it did not scale.

A 100x100 grid which I hard coded as the max size can have 10,000 button elements. Each one had event listeners, CSS transitions, and class toggles. Even 50x50 made the browser sluggish. This killed performance. We needed a different approach.

Part 2: The Changes

Fixing buttons

Using canvas elements

Instead of thousands of DOM buttons, large grids over 20x20 are now rendered using a single HTML5 canvas element. One element and one click handler. Only the cells that change are redrawn.

Canvas rendering is fast even for 10,000 cells. This fixed the lag from DOM creation. Auto solve on large grids was still freezing the browser though.

Faster solver

The bottleneck was now the solver. For an nxn grid the coefficient matrix is n squared by n squared. Gaussian elimination here is roughly O(n to the 6). That is bad.

Roughly speaking a 50x50 grid needs about 15.6 billion operations. A 100x100 grid is around one trillion operations.

The fix

Instead of storing each matrix entry separately we pack 32 columns into a single Uint32. One XOR now processes 32 columns at once. That gives roughly a 32x speedup. For a 100x100 grid the inner loop runs about 313 times instead of 10,000.

bit 0:  rowA[0]  ^ rowB[0]
bit 1:  rowA[1]  ^ rowB[1]
...
bit 31: rowA[31] ^ rowB[31]

This is exactly the same as doing 32 separate XOR operations. The CPU just does them all at once. The math does not change.

This works because the CPU treats a 32 bit register as one unit. When the XOR instruction runs all bits are updated in parallel.

Summary

The math is the same. We did not change the algorithm, only how the data is represented. Small grids still use the DOM version because it is more intuitive. Large grids use canvas and the bitwise solver.

Performance changes

1. Canvas for large grids instead of thousands of buttons
2. Bitwise solver packing 32 columns per Uint32

Everything else like animations and UI changes were quality of life improvements. Now 100x100 grids are actually playable.

You can try it here: https://blake1332.github.io/Lights-Out-Game/