We are more than happy to announce the winners of Cemetech Contest #19: Pathfinding from Hell.



Participants had to make a pathfinding algorithm in pure BASIC, which finds its way through some 10x10 mazes. To make it more challenging, some tokens were forbidden, which made it harder but funnier. Entries were required to fulfill this task, and output a correct path.

Judging was a puzzle, and that was due to a mistake on our behalf. Only 2 participants submitted an entry, so one might assume it would be pretty easy to judge. However, we didn't make the inputs before looking at both entries. While testing an example, we noticed that both participants used a different way to find a path, one of which heavily depended on the input. But, we had no inputs yet, and we knew what kind of inputs (lots of walls, or more open areas) were required for one entry to find a path very quickly. Thus, we were all biased for making inputs, so that is why we decided to do it a little bit differently. Instead of making all the inputs ourselves, I've asked a friend to generate some inputs (who was totally independant). Because there were only 2 entries, we decided that 9 inputs in total would be enough, especially since the timings of both entries were quite different. So, we all tested 3 inputs each, and this was enough to declare a winner.

And now it's finally time to announce the winners!

• The second place goes to commandblockguy. He wrote a very nice program which works perfectly, but sadly it wasn't the fastest, and because his program was bigger as well, he only got 8 points for elegance. If only the speed was a bit faster, he would surely have a chance to win this contest. Nevertheless, congratulations on actually finishing an algorithm and being second!
  
• The first place goes to jacobly. He wrote a very small and fast program, which did a recursive search in the maze, finding it's way through the maze, resulting in a very nice score of 97 points. The only problem with jacobly's entry was that it sometimes results in an error, although it found a path. However, we did not disallow resulting in an error, so we want to congratulate him with his well-earned first place!

As mentioned in the original news article, the winners will receive a Steam giftcard of $30 and $15 respectively. Outside of that, jonbush is willing to create plaques for both winners. Congratulations again to both winners, and hope to see you all next time at Cemetech Contest 20!

Well done.

Congratulations to both commandblockguy and jacobly!

I am excited to see the algorithms, and if the respective programmers would post them, that would be awesome!

Congratulations Jacobly for submitting a very small and fast valid entry! Also, congrats to commandblock for submitting a good entry.
As for the algorithms, we will leave it up to the individual users to decide if they would like to post their solutions or not.

Here is my code:

Code:


Here is an explanation:
Basically, a position in the matrix, starting at the start point, is stored in A using the integer and decimal parts
A direction is also stored in C.
Code:
holds an X component between -1 and 1 while
Code:
holds a Y component.
Later on, terms "left", "right", and "straight" are relative to to this rotation value and not the matrix.
A wall-following approach is taken, marking each coordinate traversed with a 3 in the matrix.
It first tries to turn right, then straight, then left by adjusting the value in C, which is formatted in this odd fashion to allow easy turning.
When it comes to a dead end, a 0 is stored in Xmax and begins overwriting 3s with 0s until the path is found, and a 3 is written back into Xmax
Obviously, a 2-wide corridor leading to a dead end would give problems, as the solution has to be singular, so a special case exists if there is a 3 to the left of the position.
This leads to some issues with turns in 2-wide corridors, so 3s are used instead of 2s.
Afterwards, all connected 3s are converted to 2s, leaving the 3s not connected to the path which are ignored.
B is used as a temporary variable throughout the process. Don't ask why B was used and not C, I have no idea myself.

I hope I explained everything here...

Well my program errors on purpose to save on size. I did this knowing I would lose points for elegance, to give everyone else a chance.

This would have been my entry if I had been restricted to only using one program. It would have gotten the same size score, but would have been slightly slower:
Code:


If I had not been allowed to error to end the program, I would have done this, at the cost of 6 bytes of code:
Code:


Here's the final program I submitted:
Code:


Edit: Here's a less optimized but readable version of the same algorithm:
Code:

How will the Steam gift card be sent?
Will you PM me the code on the back of the card, or do you need to know my Steam account to transfer funds?

We will fix that as soon as possible, you will receive soon a PM from one of us with some more information and details