GigglingCorpse

So there’s this website that let’s you convert regular image files into icons. You’ve probably seen it before, maybe used it once or twice. It has a donate button, which allows donations by way of Paypal. That button is there for one reason, and one reason only: to prove Karl wrong.

You see, he once posited that no one ever donates. And now, finally, after all six of these months and 100978 icon conversions, someone has. An entire American(USD) cent, and all the way from Italy. I mean sure, it may have been a mistake. I might even concede that it probably was a mistake. Either way, it’s a counter example!

Theory disproven.

One day for fun, Karl and I thought up few different ways to accomplish the same thing. That sort of thing is fun. No, it’s fun.

I decided to compare two of them for speed. The range and domain of both functions are {1,2,3}.

Method A
Based on a table.
function( a:int, b:int ) : int {
   var c:int = a^b;
   return c ? c : a;
};

Mathod B
Based on the same table, but karnaugh-mapped, circuit-design style.
function( a:int, b:int ) : int {
   var a0:int = a&1;
   var a1:int = (a&2)>>1;
   var b0:int = b&1;
   var b1:int = (b&2)>>1;
   return ((( a0&~b0 | (~a0)&b0 | a1&b1&b0 )<<1 ) | ( b1&~a1 | a1&~b1 | a1&a0&b0 | (~b0)&~a0 ))&3;
};

Method A is always faster than Method B (except sometimes in firefox for some reason) on my computer, but the difference is minimal (like .5%). There are obviously little ways in which we can tweak the algorithms. For example: we could not declare a0, a1, b0, and b1 every single time.

Function Racer
Click on it to start the race. Click off of it to stop the race.
The number below each method is the number of milliseconds consumed for the total operations performed (above the methods).
The operation size (at the top) is scaled to keep the framerate between 29 and 32.

At first I was all how am i going to deal with the order of operations? and I thought about maybe creating a parse tree. That seemed excessive, especially when I thought about how simple calculators usually work (from a usage standpoint). Which was okay, even good, but how to account for brackets. Or better, nested brackets?

There’s probably a real name for this method, but I don’t know it. Karl will definitely know? And if he doesn’t he’s lying.

So we have the screen, which I will call B and a stack of registers which I will call A_n. Each register has a value and an operator.

What happens usually is you type a bunch of literals, and then an operator. When you type an operator it checks if there is data in the nearest register, and if so combines the two values using the operator stored in the register and moves the new value and operator into the register. There are only binary operators at the moment, but unary operators would be easy to implement.

When you open a bracket, a new register is pushed onto the stack and the system makes use of that one from now on. When you close a bracket, the operation of the last register is performed with B, and the last register is popped off the stack – its value stored in B.
In this way the calculator supports nested brackets.

12 + 5 =

12
A₀ = null
B = 12

+
A₀ = {12,+}
B = <empty>

5
A₀ = {12,+}
B = 5

=
A₀ = null
B = 17

5 * ( 1 + 1 ) =

5
A₀ = null
B = 5

*
A₀ = {5, *}
B = <empty>

(
A₀ = {5, *}
A₁ = null
B = <empty>

1
A₀ = {5, *}
A₁ = null
B = 1;

+
A₀ = {5, *}
A₁ = {1, +}
B = <empty>

1
A₀ = {5, *}
A₁ = {1, +}
B = 1;

)
A₀ = {5, *}
B = 2;

=
A₀ = null
B = 10;

Thoughts? Potential bugs?

So you have these two shapes, right? One of them is the guy who can see, and the other a bitter enemy who blocks his line of sight.
Stretched between their centres, where their souls live, is an imaginary line:

The red blob is our protagonist, and the blue hexapod an enemy of his sight.
Perpendicular to that line, is another imaginary line:

For each point of the hexepod, we want to find where it falls on that line. Or, to calculate the distance from the point to another point on the original line. Also the line made by those two points should be perpendicular to that original line:

The point at the greatest distance, on each side of the line, is the point we will use when drawing the occlusion shadow. Here, Karl pointed out a problem: Our algorithm assumes parallel vision lines, and so the approach will break down as a shape nears a source, especially if that shape is much larger and irregularly shaped. In many cases, this shouldn’t pose too much of a problem. Well. In some cases. In the case blogged earlier, at least.

The min and max points are the ones we use to calculate the blocked area. We can draw the lines from the centre of the guy to the points in question, and all we have to do now is extend those lines from the points until they are off the screen:

That is all. Also there are probably some neat optimizations we could implement, especially if the world is based on tiles. Any objects contained within tiles in darkness could easily be excluded from calculations – which would work even better if we first sorted the list of objects by proximity to the character. We could discard any points that lie on tiles which couldn’t possibly hold the most distal points. And if we have control over objects, we could return only points that could possibly block sight.

Your friend,
Brad