Implementing per-pixel collision detection in a 2D game can be accomplished using a variety of methods:
- Sprite image rotation, bounds intersection
- Sprite translation, per-pixel comparison of of non-alpha-transparent pixels
- Sprite translation, maintaining a bounding box, per-pixel comparison of of non-alpha-transparent pixels
The first method assumes that you are rendering your image verbatim, and the image is actually what you are manipulating. This is typically the way you’d be doing things in a Java Swing game. The bounding box of your sprite is effectively the bounding box of your image.
Here’s what that might look like:
if (sprite.boundingBox.intersects(otherSprite.boundingBox)) {
//collision!
}The second method utilizes matrix transforms (location, rotation, scaling) to figure out where and how to render pixels. This transformation is the most common scenario in C# XNA game development. Since you are essentially plotting pixels right to the screen, no bounding box exists. Each time your game loop runs, it’s necessary to ask the sprite where its pixels currently are and compare them with collidable pixels in the scene. This is VERY expensive, since you have to ask all your sprites on the screen for their current pixel information, ask your player sprite for its pixel information, and then do combinatorial math to determine if any non-alpha-transparent pixels are true for both sets of pixels.
Here’s what that might look like:
public bool CollidesWith(Sprite entitySprite)
{
Matrix myMatrix = this.Sprite.GetMatrixTransform();
Matrix theirMatrix = entitySprite.GetMatrixTransform();
Color[,] myColorArray = this.Sprite.ColorArray;
Color[,] theirColorArray = entitySprite.ColorArray;
Matrix myMatrixToTheirs = myMatrix * Matrix.Invert(theirMatrix);
int myWidth = myColorArray.GetLength(0);
int myHeight = myColorArray.GetLength(1);
int theirWidth = theirColorArray.GetLength(0);
int theirHeight = theirColorArray.GetLength(1);
for (int x1 = 0; x1 < myWidth; x1++)
{
for (int y1 = 0; y1 < myHeight; y1++)
{
Vector2 pos1 = new Vector2(x1, y1);
Vector2 pos2 = Vector2.Transform(pos1, myMatrixToTheirs);
int x2 = (int)pos2.X;
int y2 = (int)pos2.Y;
if ((x2 >= 0) && (x2 < theirWidth) &&
(y2 >= 0) && (y2 < theirHeight) &&
(myColorArray[x1, y1].A > 0) &&
(theirColorArray[x2, y2].A > 0))
{
return true;
}
}
}
return false;
}The third method is essentially the previous method, with the optimization of a bounding box being maintained around your drawn pixels. Checking for a collision has an early-exit optimization, in that you first check which sprites bounding boxes intersect with eachother, and then only do the per-pixel collision detection on those sprites. This is a much better way to do things, and many orders of magnitude faster.
Here’s what that might look like:
public bool CollidesWith(Sprite entitySprite)
{
if (!entitySprite.BoundingBox.Intersects(this.Sprite.BoundingBox))
{
return false;
}
...
//rest of above method here
...
}
A coworker and I were recently discussing SDE interview questions, and I proposed that one of them could relate to memoization, which stored calculated values with the intent of not needing to recalculate them later. He had never heard of memoization, so I wrote up two little sampler programs to demonstrate the value that memoization can add. These programs calculate the Nth Fibonacci number, in the typical lazy recursive way (iterative could be better, but this is just to prove a point).
First, here is the non-memoized form:
#include <iostream>
class Fibber
{
private:
std::map<unsigned int, double> _fibs;
public:
double fib_of(unsigned int idx)
{
if(idx <= 2)
{
return 1;
}
else
{
return fib_of(idx - 1) + fib_of(idx - 2);
}
}
};
int main()
{
Fibber x;
for(int i = 1; i <= 100; i++)
{
std::cout << x.fib_of(i) << std::endl;
}
}Now, if we take that same program but add memoization:
#include <iostream>
#include <map>
class Fibber
{
private:
std::map<unsigned int, double> _fibs;
public:
double fib_of(unsigned int idx)
{
if(idx <= 2)
{
return 1;
}
else
{
double ret = 0;
std::map<unsigned int, double>::iterator loc_iter = _fibs.find(idx);
if(loc_iter != _fibs.end())
{
ret = loc_iter->second;
}
else
{
double calculated = fib_of(idx - 1) + fib_of(idx - 2);
_fibs.insert(std::pair<unsigned int, double>(idx, calculated));
ret = calculated;
}
return ret;
}
}
};
int main()
{
Fibber x;
for(int i = 1; i <= 100; i++)
{
std::cout << x.fib_of(i) << std::endl;
}
}The difference in performance between the two is night-and-day. Try it out!
Posted: January 6th, 2011 | Author: benlakey | Filed under: benlakey.com | Tags: algorithms, C++, memoization | No Comments »
I’m doing some simplistic string exercises using some of the programming competition problems from years past at EWU. This one is called ‘Zorro’. It takes in an integer representing the width of a ‘Z’ which will be represented on the screen using the letters of the alphabet in sequence (circularly).
Example input:
4
Example output:
abcd
e
f
ghij
This is the main body of the code to perform:
private static void OutputZ(int widthX)
{
Console.WriteLine();
char c = 'z';
int posX = 0;
for (posX = 0; posX < widthX; posX++)
Console.Write(c = NextChar(c));
Console.WriteLine();
for (posX = widthX - 2; posX > 0; posX--)
{
for (int i = 0; i < posX; i++)
Console.Write(" ");
Console.WriteLine(c = NextChar(c));
}
for (posX = 0; posX < widthX; posX++)
Console.Write(c = NextChar(c));
Console.WriteLine();
}I posted the full code on my projects page.
Posted: May 22nd, 2010 | Author: benlakey | Filed under: benlakey.com | Tags: algorithms, C# | No Comments »
In my spare time this weekend, I wrote a maze solving algorithm, which is reminiscent of a program I wrote as homework over a year ago, but slightly better. Its still wasteful in terms of efficient moves, but the improvements can come later. It does not utilize backtracking at all, which it needs to at some point when I find time. Here’s a snippet of some methods from it, for the curious:
private Point findStart()
{
for(int y = 0; y < m_mazeNodes.length; y++)
{
for(int x = 0; x < m_mazeNodes[y].length; x++)
{
if(m_mazeNodes[y][x].getState() == MazeNode.SlotValue.start)
return new Point(x, y);
}
}
return null;
}
public void solve()
{
Point start = findStart();
solveRecursive(start.x, start.y);
}
private void solveRecursive(int currentX, int currentY)
{
if(m_solved == true)
return;
if(isValidLocation(currentX, currentY) == false)
return;
if(m_mazeNodes[currentY][currentX].getState() == MazeNode.SlotValue.end)
{
m_solved = true;
return;
}
if(m_mazeNodes[currentY][currentX].getState() == MazeNode.SlotValue.visited)
return;
if(m_mazeNodes[currentY][currentX].getState() == MazeNode.SlotValue.wall)
return;
if (m_mazeNodes[currentY][currentX].getState() != MazeNode.SlotValue.start)
m_mazeNodes[currentY][currentX].setState(MazeNode.SlotValue.visited);
solveRecursive(currentX+1, currentY);
solveRecursive(currentX, currentY+1);
solveRecursive(currentX-1, currentY);
solveRecursive(currentX, currentY-1);
}
private boolean isValidLocation(int x, int y)
{
if(x < 0)
return false;
if(y < 0)
return false;
if(y > m_mazeNodes.length-1)
return false;
if(x > m_mazeNodes[y].length-1)
return false;
return true;
}
The code below is from an interesting problem I was solving as part of practice for an upcoming programming competition. It’s purpose is to read in a series of strings from an input file (the number of which is defined on the first line of that file), and discover the various permutations of the letters in the given string. This code is not intended to be elegant; It’s only an algorithm test drive. The code here is in Java.
import java.io.*;
import java.util.*;
public class Anagrams
{
public static void main(String[] args) throws Exception
{
ArrayList answers = null;
Scanner fin = new Scanner(new File("src/input.txt"));
int numberOfWords = fin.nextInt();
fin.nextLine();
for(int i = 0; i < numberOfWords; i++)
{
String toPass = fin.nextLine();
answers = findAnagrams(toPass);
}
for(int p = 0; p < answers.size(); p++)
System.out.println(answers.get(p));
}
public static ArrayList findAnagrams(String inputString)
{
ArrayList answers = new ArrayList();
char[] inputStringCharArray = inputString.toCharArray();
int len = inputStringCharArray.length;
for(int shift = 0; shift < inputString.length(); shift++)
{
answers.add(new String(inputStringCharArray));
for(int swapPos = 1; swapPos < inputString.length(); swapPos++)
{
String potentialAnswer = stringFromSwap(inputStringCharArray, len-swapPos, len-swapPos-1);
if(answers.contains(potentialAnswer) == false)
answers.add(potentialAnswer);
}
//shift inputStringCharArray around left by 1 char
char startChar = inputStringCharArray[0];
for(int curPos = 0; curPos < len-1; curPos++)
{
inputStringCharArray[curPos] = inputStringCharArray[curPos+1];
}
inputStringCharArray[len-1] = startChar;
}
return answers;
}
public static String stringFromSwap(char[] inputStringCharArray, int lSpot, int rSpot)
{
char[] passedByValue = inputStringCharArray.clone();
char temp = passedByValue[rSpot];
passedByValue[rSpot] = passedByValue[lSpot];
passedByValue[lSpot] = temp;
String toReturn = new String(passedByValue);
return toReturn;
}
}
