## Hit Detection Experiments

I decided I wanted to write an environment hit detection system the other day. My intention was to make a collidable image, by which I mean particles/circles could collide with arbitrary shapes based on the pixels of the image. Decided I could check if a line formed by the last position of the particle and the new position intersects any pixels in my image. To do this I started of trying to do something similar to a binary search since I was assuming that when it collided, the image would most often intersect near the center of my motion line. Here's what I came up with:

Algorithm A1:1 2 3 4 5 6 7 8 9 10 11 12 //maxTries is set to p1.distanceTo(p2)/2 at first public boolean hitTest(Point2D p1, Point2D p2, int maxTries) { Point2D mid = getMidpoint(p1, p2);   if (map.getRGB((int) mid.getX(), (int) mid.getY()) == 0xFF000000) { return true; } else if (maxTries < 0) { return false; } else { return hitTest(p1, mid, maxTries - 1) || hitTest(mid, p2, maxTries - 1); } }

It works but after some analysis I realized it was very slow. In an attempt to determine exactly how slow, I determined that if there's no collision it runs $\sum\limits_{n=0}^{N} 2^{n+1}$ times where $N$ is the length of the line. Simplifying, I get $2(2^{n+1} - 1)$ so it's complexity is $O(2^N)$. Exponential time, not great. I also graphed the performance to see if it mattered for the line lengths I would be using (remember, it runs in exponential time and this graph is on a logarithmic scale).

While I was doing these checks I thought of a better way to do it. I would use the Bresenham Line algorithm to find the points I should check on the image. There were almost no modifications to the algorithm necessary just that instead of setting a pixel, I check the color of my collision image and return true if it's black.

Algorithm A2 (basically just the Bresenham Line algorithm):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 public boolean hitTest(Point2D p1, Point2D p2) { double dx = Math.abs(p2.getX() - p1.getX()); double dy = Math.abs(p2.getY() - p1.getY()); double x = p1.getX(); double y = p1.getY();   int sx1,sx2,sy1,sy2; if (p1.getX() < p2.getX()) { sx1 = sx2 = 1; } else { sx1 = sx2 = -1; } if (p1.getY() < p2.getY()) { sy1 = sy2 = 1; } else { sy1 = sy2 = -1; }   double den, num, numadd, numpixels; if(dy < dx){ sx1 = 0; sy2 = 0;   den = dx; num = dx/2.0; numadd = dy; numpixels = dx; }else{ sx2 = 0; sy1 = 0;   den = dy; num = dy/2.0; numadd = dx; numpixels = dy; }   for(int i = 0; i <= numpixels; i++){ if(map.getRGB((int)x, (int)y) == 0xff000000){ return true; }   num += numadd; if(den < num){ num -= den; x += sx1; y += sy1; }   x += sx2; y += sy2; }   return false; }

I also graphed this one's performance, obviously it's much better since Bresenham's Line algorithm is $O(N)$. Also his $N$ is smaller than my $N$ because his is the length of the longest component (x or y) of the line while mine is the length of the line. This one didn't need to be on a logarithmic scale.

Obviously it's much faster but it's not actually accurate enough; sometimes particles can still pass through my image and sometimes they will stick to the edge when they're supposed to be bouncing off. I might end up using a collider that checks with the intersection method of java's GeneralPath class. I also thinking it could be fast doing a somewhat more accurate check after the initial check with my current algorithm to be certain whether I've hit or not. There's more testing preform.

## LSP v0.8 Released

I finally made the first build of Livestream Processor! And it has a logo made by my friend Antonio Lassandro. The code snapshot is on Github here and the downloads are hosted on Google Code hopefully that will always show the v0.8 downloads, I had to link to a search result.

Anyway, right now it's pretty good at concatenating and speeding up videos. I tried it with full livestream recordings from my latest ludum dare attempt and it actually sorta worked. The audio went out of sync on the concatenating part then in the timelapsing part the audio ended up like twice as long as the video but I ended up with a 60 times speed video of the livestream. It isn't quite ready for the intended use case though.

Since releasing v0.8 I have already fixed some bugs and added the ability to build exe files for Windows. I plan on realeasing that and a few more changes I intend to make after I have fixed the bugs with large files but before I implement the downloader. Hopefully that comes sooner rather than later and LSP will be ready for real users.

## Livestream Processor

For the last two months I have been spending a lot of time working on a new program called, for lack of a better name, Livestream Processor. The plan is to be able to process video, mostly from livestreams, in a few specific ways. The inspiration comes from my Ludum Dare livestreams, I want to to make a timelapse out of them so I can upload them on youtube.

Doing that requires three steps:

2. Concatenate all the video parts together (twitch.tv splits videos up into two hour segments)
3. Speed up the video by quite a bit to condense 48 hours into ~15mins

If you were to check the repository, you would notice that my commits aren't very frequent and if you were to compile and run the program you would notice that it doesn't do very much yet; even though I said I've been spending a lot of time. So far it only concatenates videos.

This is because a lot of my time was spent, not coding, but setting up a few build tools so I can do it 'right.' Essentially, when large projects are put together, they have fancy scripts put together to download all the dependencies and compile then package the finished product for all of the supported platforms with no intervention. I decided that I wanted to learn how to set up something like this and ended up re-working my build system several times before finally getting one working correctly. I didn't know what I was doing and now I do.

## Ludum Dare 24

Original Post

This time I'll be doing the jam though with a friend and fellow computer science major Brandon. I'll be streaming again and I'll do the live builds as well.

Oh and here's what I'll be using to actually make the game:

## Matrices

Today I was reading Twitter and ran out of posts to view so I noticed my background. For more than a year my background has been a screenshot of this code:

MatrixMult.java1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class MatrixMult { static int[][] mult(int[][] a, int[][] b){ int product[][] = new int[a.length][b[0].length]; int temp = 0;   for(int row = 0; row &lt; product.length; row++){ for(int col = 0; col &lt; product[row].length; col++){ for(int i = 0; i &lt; a[0].length; i++){ temp += a[row][i] * b[i][col]; } product[row][col] = temp; temp = 0; } } return product; } }

You might be able to tell from the name that it multiplies matrices together. Even though I wrote this quite a while ago I still remember how much fun it was to write. It was an assignment near the end of my AP Computer Science class during my Junior year of High School. I remember getting a working method withing a few minutes like any other assignment but it was ugly and I saw opportunity for improvement.

I went through several revisions making my code faster and more concise each time until I ended up with something I could be proud of. It turns out what I enjoy most about programming is not creating applications or games but solving difficult problems with good code.

Seeing my old code reminds of the time I solved the first programming mission on hackthissite.org. I spent some time working on it and a few months later while learning about popular algorithms in AP Computer Science I realized that I had independently derived the bubble sort algorithm. I also remember a challenge from cplusplus.com that intentionally led the ‘player’ to the binary search algorithm but I didn’t know it at the time and had a lot of fun making it on my own.

What I’m saying is the three times I remember having the most fun writing code were all optimizing an algorithm. Its just not something I expected when I first learned of programming during a game of Interactive Buddy nearly four years ago.

## On Building a Clock

People take clocks for granted. In fact, no one really looks at them, a clock simply displays time. I doubt many people have wondered about the inner workings of a digital clock, it is just a bunch of wires, right? I decided to make one because I needed a simple, easy to complete project.

There are several types of clocks and multiple ways to build each type. Some clocks keep time by tracking a swinging pendulum or by using clockwork. Others keep track of time with specific electrical circuits. Electrical clocks then have two subgroups, micro-controller based and a cheaper type normally found on store shelves. I weighed my options and chose to build the simpler but more expensive kind. The electronics I put together just displayed the time. The micro-controller, basically a simple computer, kept track of time.

At the time I had built a few quick circuits involving simple displays, such as a single LED or a seven-segment display, a set of seven LEDs meant to display a number. I wanted to use a more complicated display, one with more lights than output pins on my micro-controller. A programmer can control an output pin (an electronic switch) with code. They can decide when it will send power and when it will not. The micro-controller I used has only twelve output pins, which causes an interesting problem: how do I independently control thirty lights with only twelve switches?

An integrated circuit, or computer chip, can provide the answer. After searching the Internet for awhile, I finally remembered about the shift register. I first learned about this chip in a tutorial about making a bar graph out of LEDs. Shift registers, or small integrated circuits designed to take pulses of electricity and then split up the stream and send each value to a separate pin, effectively allow me to use one output pin on my micro-controller to control the eight output pins on the shift-register. At this point I had enough output pins to properly control my display. However, the problems do not end there.

The makers of the display did not want to waste space by providing upwards of sixty input pins (each light needs two pins, one for positive one for negative) so I could control each light individually. Instead the display has only twelve pins broken down as follows: seven pins, one for each segment, four more pins for choosing which number to light up, and one negative pin shared between all of the lights. The segment pins, when powered, turn on a specific light. These lights are seven bars arranged in the shape of the number eight, just like a commercial digital clock. When I power the pins in the correct configuration, I can display a limited set of letters or any number. Together these seven lights make a digit; there are four of them on my display. The four digit choosing pins then decide which of the digits to turn on. All of the lights channel the electricity back through the single ground pin.

Because the display only has one set of segment pins, only one digit may be displayed at a time. For example, if I were to send data to the display that would create the number two and I powered all four of the digit choosing pins, all of the digits would display the ‘two’ character. This happens because the digits share segment, or data, pins. They cannot all display a different character at the same time. This design saves space so nearly every type of display uses it. The ubiquity of this problem made the solution easy to find.

The answer, called multiplexing, involves consecutively flashing each digit on and off then changing the display data before lighting up the next digit. A computer can perform this task so quickly that all of the digits appear lit at the same time; they can even have different numbers on them. Theoretically, this works; however, real life electronic components require a specific amount of power to work as intended.

The micro-controller, to accommodate a wide range of devices, puts out more power than my display could receive. So I needed another part to lower the power. A resistor can make this happen. I can only explain resistors by using water as a metaphor for electricity. I like to think of them as a thin section of pipe. So when the water gets to the thin pipe, the water slows down just like the current of the electricity. Each light pin needs a resistor between it and the shift register so it stays cool and does not prematurely break. With the hardware completed, only the software remains.

The micro-controller requires some code to complete tasks. Basically it needs to keep track of time, then from that value determine each digit to display and finally invoke the multiplexing strategy to display the numbers. It only needs a programmer to provide the necessary code.

Buttons to set the time make a useful addition to any clock. I imagine the insides of a button looks like a removable section of wire. When pressed, the wire drops down and a connection occurs; when not pressed, the wire lifts up with the button and the connection stops. In reality buttons lift and place a metal ball onto a set of four pins. To use a button, I only had to provide power to the input pin then connect the button’s output pin to an input pin on my micro-controller. The micro-controller can then check the button’s state by checking if the input pin has power. Next I added code to increment the stored time value when the micro-controller detects that the button is down.

I finished the clock so I decided to plug it in and set the time. There it lived on my desk for a few days, until I got tired of the cluster of wires and random components. After clearing the table, I looked at the clock and decided I do not need it. I pushed it into a box and moved on to the next project.

## More Ideas - Math!

I recently discovered a book called Secrets of Mental Math: The Mathemagician’s Guide to Lightning Calculation and Amazing Math Tricks by Arthur Benjamin and Michael Shermer. Obviously I need a way to practice these techniques so I don’t forget them. This led me to an idea for a new android app that I will be working on this weekend. Here’s the design document (So the form isn’t very rigorous, I just want to remember my plans):

Quick Math; Android
- Configurable math tester/timer
- Any of the 4 basic functions + power function can be tested (power function allows for radicals by using < 0 exponents)

Not really in the book but might get into the app:
- Systems of equations? (You sort of need paper for this)
- Trig?

The main purpose is to practice techniques for fast calculations in your head
- It will keep track of stats like time by test type
- The arguments to the functions are configurable.
- Ability to choose only n-digit numbers
- Ability to choose only < n numbers
- Option to type in the answer or stop the time then type it in
- Possibly able to write a function for arguments (a*b) / c where (a*b) is an argument and / is the function making c the second argument

I’m learning these techniques from a book so I’m not sure it’d be legal to put them in the app. However, it’s not like the author independently thought of all of them.

There’s also an awesome layout and input design I have but that would be difficult to include in a text file.

As for my other ideas, I still want to make them but I’ve found myself spending a lot of time on extra-curricular activities and homework. When I do find some free time it is usually spent playing games on steam or writing code for Ep1c G4m3 (Which btw, compiles now).

This weekend my plan is to get something working on Quick Math so I can begin to learn the techniques. As I get farther in the book I’ll add features that allow me to practice the new techniques. Quick Math will be open source (GPL?), on github and the Android Market for free.

## Github, Ep1c G4m3 and ideas

I’ve started to rewrite Ep1c G4m3 because last time I changed the code to comply with a better rendering system I broke everything. I’ve already made a lot of improvements to the current code revision. I’ll do one huge commit once I’ve re-written everything. I wonder if I can import an SVN database into Github.

EDIT: You can! All it takes is "git svn clone" thanks again Stack Overflow!

As for Github, I’m no longer going to use Google Code. The git system seems so much better than SVN. It’s more simple and it’s just better in every way. Also I like the design of Github’s site more.

My first idea is for a comprehensive Minecraft mod to better accommodate adventure maps. I’ve never written a Minecraft mod before but it’s Java so I should be fine. This will defiantly be open source and on Github. Anyway, here’s the design document I have so far.

- Maps will be distributed as zip files containing notes, NPC files, the map file and the texture pack.
- Tracks objectives using the achievement pop-ups
- Adds an objective dialog box
- Uses World edit region selections to display notes or complete/add objectives in game
- Saves the world in the distributed form so it can be redone.
- Useful NPCs

- World Edit only used for creating maps
- Allow selecting types of mob spawners in game
- Locked doors/chests and keys
- NPC control
- Can choose type (Testificate or human)
- Can choose NPC skins
- Create patrol paths
- Set as hostile or pasive
- Set name
- Players can speak to npcs by right clicking.
- Dialog paths defined in a text file (includes objective and item checking)
- Dialog options can give or take items and create or complete objectives.

Client Mod:
- New dialog boxes for objective notifications and for notes
- New key to open the objectives list
- NPC Dialog
- Locked chests/doors keys (New blocks (Just data value changes?) and item)
- Store objectives
- Show distributed zip on the maps list with a new game type “Adventure”
- Add a restart button to the maps list which will be grayed out for everything but adventure maps

Server Mod:
- Players share objectives and both will see and can choose options in dialog with NPCs
- NPCs do not respod to player-typed messages
- Warns on wrong number of players but will allow it
- Restarting map is a server command
- Uses the same load procedure as the client mod
- Warns if clients don’t have the mod
- Same NPC controls

- In the server config file specify adventure map loading with “a:filename” no .zip (Hopefully bukkit will allow me to do this)

The second is a data collection app for Android. I don’t know about the price of this one. If it’s free it’ll be open source though. Maybe a free version without line of best fit, calculated columns or graph display widget? How do you feel about optional ads? Anyway here’s my design document.

Data; Android App

- Price: TBD

- Displays an axis
- Displays a table
- Uses sql lite
- db import and export for backup
- Several different data sets can be saved and loaded under different names (Either dropdown box or in menu)
- Tables:
- Set title and units
- Allows multiple columns of data
- Allow calculated colums (Data derived for a forumla using data from other columns)
- Quick entry (A seperate screen to enter another point)
- Can be configured to allow y-value setting or to just increment y
- Can be accessed by the widget
- Can be accessed by tapping the column title
- Data entry can also be done by scrolling the appropreate cell and tapping it (Cell is a text box)
- Graph:
- Displays axis lables and autoscales
- Axes displayed can be chosen from a list of data columns
- Can plot a function
- Can calculate and plot line of best fit
- Can use the line of best fit to predict a point of future data
- Widget:
- Graph display (4x4)
- Tap to bring up quick column entry
- Column type entry is configurable at widget addition
- Long press to re-config
- Displays a graph of the user’s choosing
- Quick entry button (1x1)
- Tap to bring up quick column entry
- Column type entry is configurable at widget addition
- Long press to re-config

- Possable features:
- PDF export? (I doubt anyone would want this)
- Sensor data collection
- Can be done with a background service
- Collects for a specified amount of time
- Multiple sensors at once? (ex: gps+wifi)
- gps
- Displacement on one axis
- Velocity?
- acceleromiter
- microphone
- Frequency
- Loudness
- Battery temp?
- Wifi signal strength?
- Antenna signal strength?
- Battery percentage?
- Web server interface?
- Text message data entry?

I’m super excited about both of these but I have no idea when I’ll have time to get started on either of them. For now, I have to write essays for Miami University’s application; the deadline is Thursday (Nov. 3, 2011)

It’s been a while since I’ve posted anything here. So here’s how life has been going.

The first quarter of school is almost over now and my prediction was incorrect. I haven’t done any more programming than I did during the summer. I’ll attribute this to homework.

I decided to prove to myself that I’m capable of a 4.0 gpa and it’s working out so far. In years past I haven’t been doing all of my work on time or really trying very hard; school isn’t about grades, it’s about learning.

Speaking of school, I’m in a new class in which the students are required to complete a capstone project. My project is starting a team and competing in the First Robotics Competition. I’m extremely exited to start designing and building but for now we have to apply for grants and learn how to use some software.

Recently I acquired an old computer and I’ve been setting it up as a server. So far it runs a web server and a minecraft server. Its URL is mc.fsmv.co.cc. When installing the OS I ran into some problems, this was fun to fix. In the process I learned a lot about GRUB and the process Linux goes through when it boots.

Tonight is homework amnesty night so I’m going to use my extra time to write some essays for my college applications. Hopefully I’ll have time to re-configure the plugins and permissions for the minecraft server (last time I restarted the entire directory was deleted because for some reason the wrong user owned it). There’s so much to do and so little time to do it.

P.S. - I’m not sure I’m going to continue development on Ep1c G4m3. When I started writing it, I wasn’t aware of the proper way to do 2D graphics. This means the code is organized weirdly and it all extends the wrong class. To fix this I would have to re-write nearly the entire thing, just to get the same effect with better performance. To be honest, the game isn’t that important to me and I’ve already learned a lot about graphics in Java. I mean look at DON’T_DIE, I created that out of things I learned from Ep1c G4m3. What I’m trying to say is: Ep1c G4m3 has served its purpose. It could be time to move it over to the project graveyard.