Browser-Based 2D Platformer Game Engine (SMB)

[Charles Stover]

Decided to turn my Pokemon engine into a general game engine. Going to have, at least, two sub-engines: platformers and RPGs.

This is a tech demo of the uber-alpha platformer engine in development.

[ⓦ৹₪deⓡ]

Neat, how are you currently handling collision detection? I've toyed with doing something like this but could never find the time.

ETA: Oh, and I hate hate hate IE6. I only code for it if I absolutely have to.

[Jordan]

I love it, very nice job.

I had some problems with my collision detection algorithms as well when I was working on a small project, but I just took an algorithms class at University which covered the algorithms you'd want to use for collision detection. If you want them I can dig them out and send them to you. The basic idea is to look ahead in time by drawing a line and seeing if any two lines intersect (although you don't want to compare all the lines with each other, just those near to each other). This solves the problems of two particles which are moving at high velocities from moving through each other (since the easiest way for collision detection is to just compare all points against each other after they move, but this is slow and doesn't work for fast moving objects).

[Charles Stover]

May 11, 2011 19:04:17 GMT -8 ⓦ৹₪deⓡ said:

Neat, how are you currently handling collision detection? I've toyed with doing something like this but could never find the time.

Comparing four coordinates (top left of Object 1, bottom right of Object 1, top left of Object 2, bottom right of Object 2), then determining if any one is inside the other object's coordinates.

Took me a while to iron out. The biggest problem was that I forgot programs consider 0 to be a pixel, so I'd have the width as 0 to 16 for a 16px width, which ended up being 17px, and I couldn't for so long figure out why the Hell there was an extra pixel between the collisions. Bleh.

ETA: Oh, and I hate hate hate IE6. I only code for it if I absolutely have to.

I hear a lot of people have problems with it. But, really, once you determine how to separate margins->border->width->padding, as annoying as it is to do, it becomes very simple.

It's built into EditPlus, so I've always used it for convenience sake. I just have to press Ctrl-B to test code, instead of Alt-Tab, F5 (assuming I'm on the correct page, even).

[Charles Stover]

May 11, 2011 20:37:28 GMT -8 Jordan said:

I love it, very nice job.

I had some problems with my collision detection algorithms as well when I was working on a small project, but I just took an algorithms class at University which covered the algorithms you'd want to use for collision detection. If you want them I can dig them out and send them to you. The basic idea is to look ahead in time by drawing a line and seeing if any two lines intersect (although you don't want to compare all the lines with each other, just those near to each other). This solves the problems of two particles which are moving at high velocities from moving through each other (since the easiest way for collision detection is to just compare all points against each other after they move, but this is slow and doesn't work for fast moving objects).

Yeah, it currently doesn't support high velocity collisions (e.g. two 16px-width objects moving towards each other at 32px/iteration).

I originally didn't do this out of fear that it would take too long to process each point in the line, but on second thought, it may work out perfectly.

At current, if it collides at the new position, it subtracts a pixel until it no longer is colliding (so if you move at 2px/iteration, and you are 1px away from something, you can move that 1px, whereas 2px is a collision).

So instead of starting at 2px away and counting down, start at 1px and count up.

But, dear lord, that has got to take a _long_ time to calculate, since most movements will succeed for the full length.

I wish I had an old, crap computer to test it on. I fear it is only going so fast because I'm on a gaming computer.

Maybe I'm lucky and basic calculations (if x1 <= x2) take almost no time at all to finish, so doing 50 of them a second isn't noticeable on any computer...

Anyway, yeah, if you want to send the algorithms, I'll look them over. I've been hoping to optimize the current one, but I can't think of any other way to do it.

[Peter]

May 12, 2011 12:38:46 GMT -8 Charles Stover said:

Maybe I'm lucky and basic calculations (if x1 <= x2) take almost no time at all to finish, so doing 50 of them a second isn't noticeable on any computer.

This would be a perfect example of when to use a QuadTree to improve the efficiency of your collision detection engine, that way you aren't checking every object to see if there is possibility of a collision.

[Jordan]

May 12, 2011 12:38:46 GMT -8 Charles Stover said:

May 11, 2011 20:37:28 GMT -8 Jordan said:

I love it, very nice job.

I had some problems with my collision detection algorithms as well when I was working on a small project, but I just took an algorithms class at University which covered the algorithms you'd want to use for collision detection. If you want them I can dig them out and send them to you. The basic idea is to look ahead in time by drawing a line and seeing if any two lines intersect (although you don't want to compare all the lines with each other, just those near to each other). This solves the problems of two particles which are moving at high velocities from moving through each other (since the easiest way for collision detection is to just compare all points against each other after they move, but this is slow and doesn't work for fast moving objects).

Yeah, it currently doesn't support high velocity collisions (e.g. two 16px-width objects moving towards each other at 32px/iteration).

I originally didn't do this out of fear that it would take too long to process each point in the line, but on second thought, it may work out perfectly.

At current, if it collides at the new position, it subtracts a pixel until it no longer is colliding (so if you move at 2px/iteration, and you are 1px away from something, you can move that 1px, whereas 2px is a collision).

So instead of starting at 2px away and counting down, start at 1px and count up.

But, dear lord, that has got to take a _long_ time to calculate, since most movements will succeed for the full length.

I wish I had an old, crap computer to test it on. I fear it is only going so fast because I'm on a gaming computer.

Maybe I'm lucky and basic calculations (if x1 <= x2) take almost no time at all to finish, so doing 50 of them a second isn't noticeable on any computer...

Anyway, yeah, if you want to send the algorithms, I'll look them over. I've been hoping to optimize the current one, but I can't think of any other way to do it.

I'm in the process of moving out of my apartment at Uni which is why I'm replying late, and I can't seem to find my notebook, but the idea is to not try each point on a line, but to just get the end point of the line and then check to see if the line intersects with another line by using the cross product.

Here are some links that cover what I'm referring to, and it seems to be the standard for collision detection. Whenever someone writes "x", they are referring to the cross product and not multiplication. Also, some of the material at the beginning of the posts are about solving how to get the equations you need which is some Calculus III stuff. You may want to briefly read about vectors and parametrization (this is probably not necessary, though).

1. stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
2. bloggingmath.wordpress.com/2009/05/29/line-segment-intersection/
3. www.saipanyam.net/2010/04/computational-geometry-part-1.html
    www.saipanyam.net/2010/04/computational-geometry-part-2.html

[Charles Stover]

May 15, 2011 3:35:51 GMT -8 Peter said:

May 12, 2011 12:38:46 GMT -8 Charles Stover said:

Maybe I'm lucky and basic calculations (if x1 <= x2) take almost no time at all to finish, so doing 50 of them a second isn't noticeable on any computer.

This would be a perfect example of when to use a QuadTree to improve the efficiency of your collision detection engine, that way you aren't checking every object to see if there is possibility of a collision.

More info?

[Jordan]

The quadtree looks like it would work well, but it may be easier for you to just split your screen in to two halves or four pieces and then just check the objects in each piece against each other. That's what I did in my basic engine and it worked fairly well. After reading about the quadtree, it appears to have a running time of O(nlogn) if your objects are spread out across the screen, but it can be worse than just checking all the items against each other ( O(n²) ) if they are cluttered together on your screen.

www.codeproject.com/KB/recipes/QuadTree.aspx
en.wikipedia.org/wiki/Quadtree

[Charles Stover]

I saw the Wiki, but I'm no professional in algorithms. I've only had up to Calculus, but I've taken 0 programming and algorithm classes, and the article doesn't seem to explain to people in my position - only people familiar with programming algorithms.

[Jordan]

Sorry, I'll try and give a clear example.

The quadtree is made up of a tree of Nodes, each with four child nodes. A Node is simply an object which contains a value or a set of values, and also has child nodes (four in this case). A very basic example in Javascript of a node:

function Node(_value) {

    // The value the node contains. The quadtree would contain several
    // values, each for an object in its area on the game screen.
    this.value = _value;

    // References to child Nodes.
    this.children = [];
}

var n = new Node(12);
n.children[0] = new Node(10);
n.children[1] = new Node(25);
...

This would create a tree where the node containing the value 12 is the parent, and it points to two children containing the values 10 and 25. The amount of children a node should have depends on what you are doing, but in the case of a quadtree it would have four children. You usually don't want too many child nodes. These trees made of nodes are used extensively in computer science since they are great for storing and searching for data quickly because you can search for something much faster than if you just searched an array of items which is in linear time (n). Searching a tree of nodes is in logarithmic time (logn).

By the way, whenever you see someone write O(something here), this is called "Big-O", and it represents the worst cast running time of an algorithm. For example, if you have n items in an array, and you want to search that array for a value, the worst cast would be that the item is at the very end of the array and so you will have to search through n items thus giving you O(n). If you store all those items in a binary search tree (a tree where each node has left and right child nodes, and the left child is less than the node and the right child is greater than the node), you can search the tree in O(logn) which is much faster since every time you step down the tree you are removing half of the items left to search from your search (assuming the tree is balanced).

This is the idea behind the quadtree, except you have four child nodes. Every time you move your objects in your game, you want to re-insert them all into this quadtree which will organize them based on their coordinates and dimensions, and then when you need to detect collisions, you simply loop through each object, query the current object from the quadtree, receive a few items that are in the vicinity of that object from the quadtree, and then only compare those objects against each other. In Big-O terms, you can now do collision detection in O(nlogn) time rather than O(n²) assuming the items in your game are relatively spread out across the screen.

I found an implementation in Javascript which should be helpful: www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/

Check the box that says "Show QuadTree Boundaries" on the first example. Notice when there are too many items in a quadrant of the screen or a sub quadrant that an additional four quads/nodes are added to the quadtree in that quadrant and the items are stored in those four nodes (which are now child nodes of the previous one) rather than just one. It keeps dividing up the space so only a few items are associated with each other to allow for quick collision detection.

See "function tick_quad()" in collision.js to see how the collision detection works. He just grabs an item, asks for it in the quadtree, gets back a list of items that are in the same vicinity, and then checks them against each other.

If you don't feel like using a quadtree, I'd recommend just splitting the screen into halves or four quadrants one time, and then just push each object in your game into one of the halves or four quadrants and only compare those items. If an item overlaps, put it in all the quadrants it overlaps (which could be all four if the item is in the middle of the screen). Something like...

var quadrants = [
    [],[],[],[]
];

// loop through items that have moved
    // push item into one of the four quadrants
// loop through four quadrants
        // loop through items in current quadrant
            // do collision detection in current quadrant

By the way, I'm open to criticism because I'm not a pro at this.

[Chris]

courses.csail.mit.edu/6.006/spring11/lectures/lec24.pdf

Depending how you have data set up, if a quad-tree approach is too slow, you might try a line-sweep method. Slide 15 contains some pseudo-code. I'm not 100% sure how the speed will compare, but algorithmically they're about the same.

[Charles Stover]

I don't think line-sweep is valid for HTML-based objects, since there is no "get objects that are positioned inside line X," without having to loop through each object and calculating its position for every position of the line. And if you're going to loop through each object and calculate its position in the first place, there is no reason to do the sweep. It would be much better for something like C++, or whatever language involves just checking the colors currently displayed on screen instead of values stored in memory.

Beyond that, I think it would be pretty slow for box-shaped objects (like HTML elements), since they're comprised of four lines instead of just one. Each object would take roughly 4x as long to check.

Quad tree appears a bit complicated, but I'm liking how fast it runs on that page. Why re-invent the wheel? If it's free and open-source, I might just port that exact version, but it's hard to say how well it will work. He is using <canvas> where I'm using actual elements. The majority of the time processing may not be comparing the coordinates, but retrieving the coordinates (element.style.top, element.style.left, element.style.top + element.style.height, element.style.left + element.style.width). If that is the part that is causing the most lag, a different algorithm won't help as much as hoped.

I was also considering just not checking against objects previously checked that haven't been moved. If Object A and B haven't collided and neither object have moved, they still haven't collided, so don't bother checking (probably something like if (hasMoved[objectID])). I'm wondering how well that would work compared to how it currently runs. Guess I could try both.