#44748 - rize - Sat Jun 04, 2005 11:58 pm
I'm working on this little game and it occured to me that I have no idea how I should go about coding the collision for a 2D platformer. Well, no I do have an idea, but I don't have any reference point.
So I have a character who is ultimately a box as far as the "physics" is concerned.
My current plan is to have the lines that deliniate where the character cannot go sorted into four groups. horizontal lines that block downward movement, horizontal lines that block upward movement, vertical lines that block leftware movement and vertical lines that block rightward movement. Each set of lines would be compiled into a sorted array that could be binary searched at ease during gameplay (to see if the character can move in the direction that the player or gravity intends). So a square shaped block would need 1 line in each of the four groups to be defined properly. The level editor I intend to make would compile the lines for me.
A potential problem with this is that it might be slower than it could be. If the player is moving right, I'd have to check for collisions with any right blocking line within the movement range that the player is attempting (including lines far above and below the player). Then again, this will probably run fine.
Diagonal lines would have to be taken care of separately. I'm thinking about surrounding each diagonal surface with a hit detection box and ignoring such surfaces until the player enters that box. I'd also ensure that the player can't be in two such boxes at once. If the player is in the "on the ground state" while in this box, then the player's height would be some function of the diagonal line's slope and the player's X position within the box. If the player is in the air inside of the box surrounding this diagonal line. Then I use some function of the line's slope and the players X location within the box to determine if the player is trying to pass through the diagonal line and should be moved from the jumping state to the ground state. Possible problems with this are that making diagonal surfaces meet up with horizontal ones well could be difficult. Then again, I think this will work too. But is there a better way?
Moving platforms would be handled individually/separately from fixed lines since they wouldn't remain sorted properly. Or maybe I won't use moving platforms. Platforms that merely appear and disappear could be easily done by having a flag associated with each line marking whether it is present or not.
So, does this sound like a good way to do such a game, or is there a better way? Is there some good example documented somewhere in some book, or does everyone have to guess how such games are done the first time they make one?
#44773 - dagamer34 - Sun Jun 05, 2005 4:18 am
Stick to tile based collision and then move to objects with bounding boxes.
Look into finite state machines too. Basically what it is is that you have an object, and it has several states. Based on these states, different actions will happen. Search FSM on these boards and you'll get more info, but in general, you need some way to organize your collision code or it will become a real mess. That is why 99% of problems occur: poor planning. Seperate stuff into classes and you should be good to go.
_________________
Little kids and Playstation 2's don't mix. :(
#44774 - DekuTree64 - Sun Jun 05, 2005 4:55 am
I think it would be easier to just store a byte for each tile of the map, with 4 bits representing wether each edge of that tile is blocked. You don't need to do any complicated binary searching, just an array lookup into the tile map based on the character's x/y position.
Slanted tiles will be more difficult, but it sounds like you know how to handle them. Probably easiest to define just a few slope types that you can hardcode equations for, instead of trying to do some general system. It will also make it easier to fit all the info for it in a single byte in your collision map.
Moving platforms would probably work better as sprites that clamp the player to the top of them if there's a collision.
What I would actually suggest doing for your first attempt is just a tilemap where the tiles are either solid or non-solid, and the characters are the size of a single tile. Keep it super-simple so you can focus on learning instead of fiddling with bugs. Once that works, throw it away :)
Some of the knowledge you gain might not carry over exactly to a more complicated system, but it will give you a starting point to build off of.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#44783 - rize - Sun Jun 05, 2005 7:23 am
dagamer34, thanks for the advice
Yeah, I know what FSM's are. I'm definitely going to devise a state machine to represent the characters movement abilities in relation to the world. And I'll be using objects of course.
My current plan is to have a level object consiting of some description of how the player can interact with the current tilemap. Then my character object and also enemy objects would query the level object with the direction of its movement (two bits) and its new location (two uint16s). Then the level object would respond by either returning the location or returning a slightly truncated location due to some collision with an obstacle. The question is how will I determine collisions.
What's this about sticking with tile based collision and then moving to bounding boxes though? Should I use one or the other? I don't need to practice first. I can start out with whatever is most appropriate. The tilemap method appears to require less CPU power than the one I thought of, but more memory. Requiring a 512x512 one byte per tile map (at most; unless the DS can have bigger maps than the GBA) is 256 KB though. Is the DS's main memory heirarchy efficient enough to work effectively with such a large chunk of data at once? (I hope so since I'm using an arccos lookup table elsewhere).
dekutree64, thanks for providing details about using a tile based method. I'm new at this type of game. In fact, I've never done any GBA programming, only DirectDraw and Direct3D programming which doesn't use tiling of course.
If I use tiles as you suggest, then I have to check a number of separate tiles (any tiles my characters are trying to enter). Tiles with slopes would be enterable from the appropriate sides, but I'd need to keep an eye on the center point at the bottom and top of each character to make sure they don't pass through a sloped line.
That could work.
Draw backs are that I would need 1 byte per tile. 256 KB for a 512x512 map. 64 KB for a 256x256 map etc. Of course, a 512x512 map is huge. 16 DS screens horizontally by 21 and a third vertically. Still, that's not an insignificant amount of data. I'd also have to read individual bits of that byte (requiring one bitwise op and a shift before a comparison can be done). For every tile that any character tries to enter. I guess that's not too bad. The upper 4 bits could represent whether or not a diagonal is present, whether it blocks from the top or bottom, whether the slope is neg or positive and whether the slope is 30 or 45 degrees. I could also make slopes block both directions and use an extra bit to describe two more slopes, say 60 and 75 degrees.
Using my lines method I could have obstructions that aren't on tile boundaries, and possibly diagonals of any slope. The level object may be much smaller as well. A single line requiring 6 bytes (one x or y value and two y or x values) could potentially cover the entire horizontal range of a tile map. 512 bytes in the optimal case. Naturally most lines would be shorter, but overall it would probably take up much less space.
However, it would be more difficult to read the structure quickly. Then again, with a 256 KB tilemap matrix in use at one time, how efficient will reading such a tilemap be? Cache can't fit all of that at one time.
I need to think about this more. If anyone else wants to weigh in, please do so.
#44808 - dagamer34 - Sun Jun 05, 2005 6:39 pm
| rize wrote: |
dagamer34, thanks for the advice
Yeah, I know what FSM's are. I'm definitely going to devise a state machine to represent the characters movement abilities in relation to the world. And I'll be using objects of course.
My current plan is to have a level object consiting of some description of how the player can interact with the current tilemap. Then my character object and also enemy objects would query the level object with the direction of its movement (two bits) and its new location (two uint16s). Then the level object would respond by either returning the location or returning a slightly truncated location due to some collision with an obstacle. The question is how will I determine collisions.
What's this about sticking with tile based collision and then moving to bounding boxes though? Should I use one or the other? I don't need to practice first. I can start out with whatever is most appropriate. The tilemap method appears to require less CPU power than the one I thought of, but more memory. Requiring a 512x512 one byte per tile map (at most; unless the DS can have bigger maps than the GBA) is 256 KB though. Is the DS's main memory heirarchy efficient enough to work effectively with such a large chunk of data at once? (I hope so since I'm using an arccos lookup table elsewhere).
dekutree64, thanks for providing details about using a tile based method. I'm new at this type of game. In fact, I've never done any GBA programming, only DirectDraw and Direct3D programming which doesn't use tiling of course.
If I use tiles as you suggest, then I have to check a number of separate tiles (any tiles my characters are trying to enter). Tiles with slopes would be enterable from the appropriate sides, but I'd need to keep an eye on the center point at the bottom and top of each character to make sure they don't pass through a sloped line.
That could work.
Draw backs are that I would need 1 byte per tile. 256 KB for a 512x512 map. 64 KB for a 256x256 map etc. Of course, a 512x512 map is huge. 16 DS screens horizontally by 21 and a third vertically. Still, that's not an insignificant amount of data. I'd also have to read individual bits of that byte (requiring one bitwise op and a shift before a comparison can be done). For every tile that any character tries to enter. I guess that's not too bad. The upper 4 bits could represent whether or not a diagonal is present, whether it blocks from the top or bottom, whether the slope is neg or positive and whether the slope is 30 or 45 degrees. I could also make slopes block both directions and use an extra bit to describe two more slopes, say 60 and 75 degrees.
Using my lines method I could have obstructions that aren't on tile boundaries, and possibly diagonals of any slope. The level object may be much smaller as well. A single line requiring 6 bytes (one x or y value and two y or x values) could potentially cover the entire horizontal range of a tile map. 512 bytes in the optimal case. Naturally most lines would be shorter, but overall it would probably take up much less space.
However, it would be more difficult to read the structure quickly. Then again, with a 256 KB tilemap matrix in use at one time, how efficient will reading such a tilemap be? Cache can't fit all of that at one time.
I need to think about this more. If anyone else wants to weigh in, please do so. |
Well, what I really meant was for tile based collision to be used for background objects, pretty much anything that doesn't move. They are also simpler to deal with because you don't have to worry about the coordinates of other objects.
_________________
Little kids and Playstation 2's don't mix. :(
#44812 - abigsmurf - Sun Jun 05, 2005 7:17 pm
There's a number of things you can do to improve the speed of the code. One of the biggest performance gains is to eliminate as much collision detection as possible, one of the simplest ways of doing this is to divide the play area up into tiles (which you'll have already done using a tile based engine). In each of these tiles you store details of whats contained in the tile.
As ideally the player's sprite can only be in a maximum of four tiles at the same time, you greatly reduce the number of checks you need to do. You look at each of the tiles the player is in and if another object is also in you do a collision detection test with it, if the player is the only thing in a tile, you do nothing and test the next tile.
Also per pixel collision detection is pretty over rated for most types of simple gamesm you're best off using a bounding box which has limits inside the sprite itself. It's far more enojyable playing a game where it doesn't matter if something brushes the player without him dying than a player getting killed when something hits 5 pixels to the right of his head
#44818 - rize - Sun Jun 05, 2005 7:54 pm
So using 512x512 byte array (256 KB) doesn't strike anyone as wasteful?
#44829 - DekuTree64 - Sun Jun 05, 2005 9:30 pm
It is wasteful, but you can split the world up into blocks about the size of the screen that can be compressed individually, and only load the 4 or 9 blocks nearest to the player.
The problem with doing that is that if an enemy is far from the player, the part of the collision map it's on won't be loaded so it won't have anything to keep it from falling to its doom. Only way around that is to stop updating the sprite's movement if it's off the loaded area.
That would be where loading the 9 nearest blocks is good, because it makes sure there's quite a bit of space loaded, so sprites can be moving offscreen for a while before you get too far away. That makes it harder to realize they ever get stopped.
Another trick, which I actually used on my old RPG engine, is to have no seperate collision map at all. Instead, tag each tile in your tileset with collision info.
Like, set a platform tile to be collidable from the top, so a falling player will land on it, but you can jump through from below. Then everywhere you use that tile, the collision is already done for you. Then you can use the block loading system I described on the graphical tiles (which you'd probably want to do anyway), and magically you have collision with no extra memory.
It's also a heck of a lot easier to create maps that way. The only reason I actually did it was out of laziness over drawing the collision layer :)
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#44849 - sajiimori - Sun Jun 05, 2005 11:56 pm
It sounds like you're a fairly experienced programmer, so here's a very fast run-down of some collision schemes. I'm not putting much detail here, so feel free to ask about the ones you're most interested in.
The two main approaches have been covered: Representing the collision shape on a per-spatial-unit basis (where the units are fixed size), and representing it on a per-feature basis.
With a piece of data per fixed-size spatial unit (i.e. a tile map), there can be a lot of redundant data for large empty or solid regions, but collision checks are constant time.
Using a hierarchal map can help reduce waste, where the map is first divided into large chunks that might be reused, and then further divided into smaller tiles that make up the meta-tiles. This technique has diminishing returns if the collision shape isn't very repetitive.
Having a piece of data per feature is very space efficient for most data sets, but it can be slow to traverse all the features if they are not organized in a way that allows sub-linear access times. That is, it's slow to iterate through all the features every time an object moves.
Sorting the objects along some axis can help, but it may not be enough for maps that extend very far on multiple axes (i.e. anything besides a side-scroller).
Shape partitioning is more scalable than linear sorting. You make a bounding volume that encloses all of your objects, and then select two or more subsets of your objects and make smaller bounding volumes for those, and so on until you reach a point where it's not desirable to subdivide further. Then you traverse the tree by going down all the branches whose bounding volumes you're intersecting.
An alternative to shape partitioning is space partitioning. That is, rather than choosing subsets of your shape and then making the volumes for them, you choose the volumes and then add the features that overlap them.
Space partitioning can be done in many ways. Perhaps the simplest is to overlay a regular grid on top of your set of collision features, and add each feature to the cells that it overlaps. This involves some of the waste of tile maps and it's not very friendly to features that vary widely in size.
Both of those problems can be fixed by using a hierarchy of grids, and one of the best ways to do that is by using a quadtree, which repeatedly divides the map into four quadrants. You add each object to the level in the tree that's appropriate for its size -- higher up for larger objects.
More general than quadtrees is binary space partitioning (BSP). You pick a plane and divide your features by which side of the plane they lie on, and then repeat on each side until it's no longer desirable to subdivide.
My favorite scheme so far is a type of BSP where the dividing plane is chosen from the set of surfaces in the world, and you continue partitioning until there are no planes left. Rather than using the tree to determine which objects to check against, traversing the tree is the collision test.
Last edited by sajiimori on Mon Jun 06, 2005 3:40 am; edited 2 times in total
#44859 - rize - Mon Jun 06, 2005 3:03 am
Thanks for the info. I'll investigate BSP in particular.
However, as DekuTree suggested, I had already been thinking that with the tilemap loaded into video memory already, I can just read the tile numbers out of that and use them to look up the proper collision info for that tile (which would be the same for every tile of that type). That'll probably be the best method as far as run-time verses programming time goes.
#44929 - blt - Mon Jun 06, 2005 9:31 pm