A Simple HTML & JavaScript Maze

So, a few weekends ago I put together a quicky maze generation web page for Jenna (my daughter) as she is into mazes right now and wanted to play with the computer.

It was a quicky thing and we were all happy with it. I made it show her how the maze is generated and let her print out nice looking mazes from her computer.

But then something very unexpected happened. When I tried it on IE it was over 1000 times slower than Firefox on the same machine when the window was full screen!

I thought it might be a fluke of my setup - but even my Palm Pre cell phone was significantly faster than IE8 on Windows 7, so I figured that there must be some strange interaction on the way the maze is rendered.

The maze is a simple table of styled TDs that have a width and height of the cell size and a background color of either a floor (walkable area) or wall. The whole rendering was done in some simple JavaScript that updated the styles of the cells.

The end result is that a 2-way 2.4GHz PC running IE8 and Win7 could not match the performance of a 500MHz ARM cell phone. (My Palm Pre) and using Chrome, Safari, or Firefox produced results that were around 500 to 2000 times faster.

Before anyone thinks this was a JavaScript problem, I did some extra instrumentation and while IE8 is slow in JavaScript, the actual performance problem was not in JavaScript but somewhere in the DOM layout and rendering layer. So, while the JavaScript that I quickly wrote may not be optimal, the it was also not the reason for the extreme slow performance.

So, upon seeing this, I went on to try to find other ways to render the maze in standard DOM (HTML) layout that may speed things up for IE8. I have tried now a total of 4 different layout mechansms. This has produced a number of interesting results and I have found something that significantly improves IE8 results but overall has had no significant impact on the other browsers. However, the best I was able to get with the same visual results was to get IE8 to be less than 10% of the performance of Chrome. That is, Chrome was, at its slowest, more than 10 times faster.

So, to try out these different layouts, here are the links and the details as to how they work. Warning, in a full-screen IE8 browser window, these will take some time to run, especially the first and third versions. The "JS Only" links show the same exact JavaScript but with no rendering of the progress. The maze is generated in a single go.

Link Description
The original table layout - the way I originally designed it
My first non-table try using <div> rows and in-line block <div> cells
Non-table with <div> rows and floating <div> cells
Non-table with <div> rows and floating <div> cells and overflow hidden
A zip file containing all files for these pages

Valid XHTML 1.0 Strict Valid CSS 2.1 PS - I do have some performance numbers but don't have the time to do the multiple runs needed (especially on IE8) so have not posted those numbers. However, on a full-screen browser using the default link and step size, the difference in performance is rather dramatic. Measure for yourself using the above links.

Keyboard actions after maze has rendered
Key Action
O Ok
S Show statistics display
R Re-run maze generation
H Hint - flood-fill solution finding trick
U Un-hint - remove the flood-fill solution rendering
T Toggle - an interesting effect

Note that the solution finding trick is based on the fact that the maze is fully connected and thus there are exactly two walls in the maze. By coloring one of the walls we can then find the path through the maze by staying between the two different colors. The flood-fill mechanism also is an interesting way to show off some continuation programming for JavaScript.