What Are Phantom Dots?
Before my level generator draws a line, it goes through each empty cell and calculates the minimum distance in each direction from that cell to either the edge of the board or a non-empty cell. This has a major impact in how the program draws the next line.
A phantom dot is a dot that exists during that calculation, but does not exist when my program actually draws the line (unlike other filled cells – it is still possible for the program to draw a line through a phantom dot).
How much difference can that make? Here’s an example from a 25×25 grid:
The first grid shows how a fairly typical line drawing algorithm used by my program would draw a line connecting the two purple dots. The second grid shows how the line is drawn with the two red dots.
How Do They Happen?
Initially: by accident due to a bug in my program.
The bug occurred whenever my program failed to draw a line connecting a pair of randomly selected dots according to it’s own rules. In this scenario, the program would recalculate each cells distance to the edge before removing the dots and drawing the next line.
I caught this during what appeared to be an extremely basic code optimization while looking through my code:
canComplete = CanCompleteIt(fg, block) && line != null;
canComplete = line != null && CanCompleteIt(fg, block);
Anyone with a basic knowledge of the C# language should be able to spot why the first line is less efficient than the 2nd: if the statement to the left of an && operator is false, the statement on the right isn’t executed. Thus, the computationally less expensive operation should almost always be on the left-side – and comparing an object to null is almost always going to be computationally less expensive than calling a separate function – even without knowing what function does.
The “bug” wasn’t really in this line of code though – it was in the CanCompleteIt function. This is where the program does the recalculation that can influence the next line it draws – and it does so before the dots are removed from the grid.
The single code change made level generation about three times faster at a board size of 100×100. Initially – I assumed it was because the CanComplete function took a lot of unnecessary time saved by performing the null reference check first. Sadly, it was mostly due to the impact it had on the levels it generated.
The Effects on the Levels
I introduced this code change for the last 1800/12000 (15%) of levels generated for the 101×99 gallery.before I knew it had any effect on the levels. When I saw that these levels averaged about 10% fewer lines and 10% fewer line direction changes than the rest, I realized that the CanCompleteIt function was doing more than I thought and eventually figured out why.
Similarity Filtering picked just 3 of these levels of the 60 it chose for the set (1/3rd of the amount it should have) – additionally, the 1800 levels scored on average much worse than the rest in the earlier stages of filtering.
In terms of evaluating levels – I frequently disagree with my program; and in this case, 1 of the 3 levels it picked was among my favorites in the set. So I let the program generate the entire 111×99 set with the code change.
111×99 and Why I Bash It
My program hated the 12,000 levels generated for the set and scored them far worse than any set before or after it for each of the 9 iterations – and while this undoubtedly influences my opinion, it isn’t the reason I don’t like it.
In a vacuum, there is nothing wrong with the set. The problem is that most the patterns are either repeats or small variations of previous patterns – though in many cases, more “perfect” variations of the pattern than see before. Here is an example:
While the first time I saw this pattern I thought it was great (at around 50×50), I have seen it many other times, though never so big and perfect and subsequently boring as this version.
Additionally – even if a saw a pattern that wasn’t a repeat, I expect that it would become one very shortly if I continued to generate levels with these settings. This even happened within the set itself:
I certainly didn’t help the cause by picking nearly identical colors for each. I used to think the 1st level was “better” due to it being more complicated, but the 2nd image is now my favorite from the whole set due to it’s perfectness.
I haven’t seen a level either before or after this set as close to either of these levels as they are to each other – but that isn’t because they don’t exist. I only look at about 1 out of 200 levels that my program generates and I am virtually certain there are many versions of this pattern in the levels that I don’t look at.
A Level Impacted By Phantom Dots
There are 8 versions of this level in the original 80×80 gallery and another 3 versions in the 80×80 remake.
Phantom dots likely caused most of the unusual but natural bends (almost certainly the large bends on the left side). Admittedly, the level had even more appeal when I didn’t know how it happened.
The 2nd (or 3rd) Unintentional Bug that Made My Program an Art Generator
Similarity filtering was developed as an alternative method of finding “better” levels for my games. After I found that this method worked really well compared to my previous formulaic approach, I developed Similarity Maps to visually illustrate how it works on this website. The shading from the maps remains a crucial component of the artwork.
The largest board size in my games is 18 rows by 13 columns (238 cells) – about as big as they can get and still be playable on a smartphone. When I saw the similarity maps and thought they looked cool, I decided to see what it could do at larger board sizes and the rest is history. The program still draws the lines using exactly the same algorithms as it did for the levels in my games.
The Bugs
- The “step” bug isn’t really a bug, but a modification I made to my line drawing algorithms to make it handle what I call steps: the zig-zagging diagonal lines that you see in many of the images which look kind of like a staircase at much smaller board sizes (see: Stepping Up). The modification effected all line drawing algorithms – and turned out to be inefficient with standard rectangular boards without walls. When I switched the code back to save some time generating levels, I discovered that the modification also was essential to the artwork.
- Another bug limited the length of any individual line to a hard-coded 500 cells and made the level generator extremely slow beyond 60×60 as a result (the 60×60 and 70×56 highlights set is the last one generated before I discovered/fixed this bug). However, when I removed the bug entirely and let the program draw lines filling up to 50% of the entire board – the resulting levels were practically worthless. The compromise was to set the maximum line length to a percentage of the boards total cells – which is set at 24.9% and hasn’t been changed since.
- The phantom dots bug. The last bug also causes a condition that results in phantom dots as early as the first line – the program sometimes fails to draw a line connecting two dots in an empty board because the line exceeds the maximum length – which creates phantom dots for the next pair of dots that it tries to connect.
Purposely Adding Phantom Dots – And Rectangles
If the bug improves the levels, why not purposely induce it?
Over time I added have several options that purposely introduce phantom dots and rectangles:
- Add X phantom dots before drawing the first line (remove for the next line)
- Keep the phantom dots for X number of lines (the dots are in the same place).
- Add X phantom rectangles with random dimensions between Y and Z.
Before the 90s, the first option was the only one that I added and I used it relatively sparingly mostly because it makes the program slower and it already takes a long time to generate levels at 111×109 and larger.
Half of the 91×91 levels generated for the 90+91 set had the option to add 2 phantom dots before drawing the 1st line. The problem with this option is that the dots are only there for the 1st attempt at drawing the 1st line – if it fails, the original bug will add a different pair of phantom dots, but the original dots won’t exist. Thus, the setting didn’t really add anything to the levels that didn’t already happen frequently before. My similarity filtering agreed: the setting had a much greater impact on the bottom half of levels than it did on the top half and practically no effect on the 0.5% of levels that actually made it into the set.
The 2nd setting attempted to fix this by keeping the phantom dots added before drawing the first line for X lines. A setting of 1 line meant that in the case described above, the phantom dots would exist alongside the two dots the bug created.
The 3rd setting will draw phantom rectangles of random dimensions between a specified range. So far the largest range of dimensions I’ve tried is 2 to 25 cells with as many as 5 of these added before the first line. If the program somehow picked 25×25 all 5 rectangles and they somehow didn’t intersect, a full 3,125 of the 8,100 cells could be “covered” by these phantom rectangles – though the program could still draw lines through these rectangles.