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).

Graph of algorithm A1's runtime

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.

Graph of algorithm A2's runtime

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.

Categories: Articles | Tags: , , | Leave a comment

LSP v0.8 Released

Livestream Processor Logo

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.

Categories: Project Updates | Tags: , , , | Leave a comment

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:

  1. Download the videos from twitch.tv
  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.

Continue reading “Livestream Processor” »

Categories: Project Updates | Tags: , , , | Leave a comment

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.

Follow my progress:

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

Categories: Project Updates | Tags: , , | Leave a comment

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.java
1
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.

Categories: Uncategorized | Tags: , , | Leave a comment

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. 

Categories: Ideas | Tags: , , | Leave a comment

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.

Adventure; Minecraft Mod

    - 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
    - Adds an adventure world type.
    - 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
       - Load from distributed zip
       - 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)

Categories: Ideas, Project Updates | Tags: , , , , , , , , | Leave a comment

Updates

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.

Categories: Project Updates | Tags: , , , , , , , | Leave a comment

DON'T DIE

Link: DON'T DIE

Ok, so the name isn’t very imaginative. It’s not like the game is very polished or anything though.

I made this because I started to write a test case for Ep1c G4m3 (I couldn’t get the rotating gun-arm to rotate) and I ended up making it into a simple little game. The source can be found here.

The next release of Ep1c G4m3 should come as soon as I have some art for it. I’ll probably be able to add this rotation code and create an enemy before the art thing happens. I’ll go ahead and say version 0.5a will be out by October.

Categories: Project Updates | Tags: , , , | Leave a comment

Ep1c G4m3 - Version 0.1a

Link: Ep1c G4m3 - Version 0.1a

This is the first executable release for Ep1c G4m3. The player doesn’t actually have any graphics, just filler colors. But the main engine works, it probably needs some optimization though.

Categories: Project Updates | Tags: , , | Leave a comment