Blog 418: Mazing Woes Y4

So in the previous entry, I talked about making a procedural maze generator for Project Y4. This was fraught with danger and frustration, but ultimately successful.

The plan was simple.

• Observe example code.
• Translate to WC3’s scripting language, Jass
• Profit

The place I was expecting the most trouble to come from was handling lists and even 2D arrays in Jass, which can only sustain arrays. But no, harking back to the array-implementation-of-a-list lectures of yesteryear, I did actually manage it.

And then I found the mathemagical hax that allows you to turn a 2D array into a 1D array and vice versa (okay, that was after I decided using the hash table was a bad idea), so actual storage of the maze grid was simple and effective.

But after clearing up all the general coding mistakes that caused infinite loops to abound (Jass only has while loops; I’m extremely partial to C-likes’ for loops that increment the iterator for you) along with a few logical errors (thanks Owenalacastery of #WC3C), the generator continued to fail.

But it wasn’t failing anywhere consistent. It was dropping all over the place, and after I disconnected the printing mechanism (that slapped tiles down on the ground in the right places) I discovered it was working… partially. Little segments of maze were being pooped out before it died.

I was pretty convinced I had a logical error somewhere, some missing piece of the algorithm causing it to crash out under certain circumstances. Maybe it was a hole in my array implementation of the list, or my 1D-to-2D mathemagic.

I reimplemented the entire thing in Java to try and narrow down the problem, hoping that translating the logic again would highlight the missing pieces — first with an actual 2D array and an actual dynamic list, then with an array implementation of a list, then with a 1D-2D array.

You know the worst thing? All three times, absolutely perfect. The thing ran first time, and again and again, pumping out perfect mazes of the correct size. How infuriating — my implementation of the algorithm was, in fact, completely correct. I checked my translations against each other and they were the same.

And then Anitarf piped up. “The op limit.” What is the op limit? As far as I’m aware, it’s a seemingly benevolent limit on the number of functions you can call when running a trigger, to stop infinite loops powering away into the distance and killing everything else. The problem is that a maze generator, even running on a small grid, needs to churn through a lot of mathemagic to get itself done — we’re talking a few thousand operations. Not anything to worry about in real terms, but for WC3 apparently just a bit too much.

With some coaching by Griffen on how to get around this problem, mazes of a thoroughly reasonable 16×32 (the size of the map area I’ve cordoned off for this, though the absolute max is about 22×46) were produced.