Archived

This topic is now archived and is closed to further replies.

FiveFootFreak

Colission detection... yes, again

Recommended Posts

Greetings, imagine I have a 2D level map with the usual things on it, like walls, objects, etc. Now, I can think of two ways to do some accurate colission detection. Way 1 would be to define bounding lines for every object that can be added to a map. I would then have to implement an algorithm that checks if lines overlap to check if objects collide. Way 2 would be to create a 1 bit overlay map. Objects that are placed on the map would then turn the bits corresponding to their "blocked" parts from 0 to 1. An algorithm for this solution would eat up a lot less CPU cicles (I assume) because I would only have to check if a bit that is trying to be set to 1 is already 1. Problem with this is, that on large maps, it would eat up memory. Is the extra memory worth saving CPU cycles? Has anyone tried this out successfully? What do you think?

Share this post


Link to post
Share on other sites
depends on what you are actually trying to collide with..

if you are talking about player interaction with the background then you need to define a set of hotspots on the character and test the type of tile under those spots (providing your tiles are resonably small).

in Jumpman I have ladders, ropes, girders, chains, lifts etc.. all sorts of things he can climb/run on. as there can be more than one type of object in the same place (ie a ladder that goes over a girder) then I build up a bit test map for each cell in the game.. as the game is run, each object populates the bit map (I use different bits per object but you don''t have to). the player code then checks for what objects types are underhim (I have hot spots at his feet, belt and head) and a lot of rules which define what he can do depending on the combinations of bit patterns underhim.. (if you look at my jumpman site (dev-dairy) then I have some explanation and screen shots of how I did it (you will have to go back a month or so though)...

objects in a game like that are more dynamic (ie.. they can be collected).. its best to use bounding box detection for that as generally you don''t have many objects (even if you do.. a bounding box check is very quick)

hope that helps..

Jumpman - Under Construction

Share this post


Link to post
Share on other sites
Polygon division
I solved it this way

use function equations y = kx+m

Calculate the y = kx+m using the player pos and the destination.
k= y2-y1/x2-x1 or something like that
m = ?
This is what I have in my head right now, you have to look in a book on how to solve m.


If we now look at a wall, se the wall like four lines
(3,3) (5,3)
*---*
| |
| |
*---*
(3,9) (5,9)

Lines between
(5,9)<->(5,3)
(3,9)<->(3,3)
(3,3)<->(5,3)
(3,9)<->(5,9)

If we are walking Northwest the collision will occur on lines A(5,9)<->(5,3) and B (3,9)<->(5,9)

If we want too decide if we collide with A we need to solve y where x = 5.
y= kx+m


If we want too decide if we collide with B we need to solve x where y = 9
x = (y-m)/k

When this is done we have to decide if the y pos in A is within top and bottom or the solved x position is within left and right of the wall.

example
if(y >= 3 && y <= 9)
if this is true we have a collision at
x = 5
y = kx+m

if(x >= 3 && x <= 5)
if this is true we have a collision at
x = (y-m)/k
y = 9


I use this in my game, I calculate the collision and sets (at the moment) the destination to the solved x and y. I only do this collision detecting once when the player requests movement. There will be another ice cream to break when we have one more dimension the time. Cause it would be good if I had collision with the players not only the static objects in the map.

I have to say this is very hard to get working correctly, you will discover some problems on the way. I still have some problems but it is working better now than before. Using this you eliminate the problem with players have too much speed and walks through walls.

Share this post


Link to post
Share on other sites
I think the one bit depth mask can be a decent solution to detect the collisions of your "sprites" with the static elements of decor. Specially if the details are small and you need accuracy (à la Worms) the geometric solutions will be less efficient and memory wasting.

2 ideas :

1) I suppose your 2D data is somewhere in system memory. You could hide a collision bit in the color data lower blue bit for instance. This would accelerate the per pixel test by avoiding bit indexing issues. If you repeat (instantiate) graphic elements you will need a kind of quadtree to quickly access the right graphic source.

Memory should not be a real problem on PCs. So the following would be more appropriate for small machines like GameBoy.

2) With a separate collision mask you could compress/decompress you can still use idea 1) in real time and copy the blocks dynamically to a 1bit offscreen in your main memory. Thus you will save space due to repetitions. 1 extra bit per pixel for each element adds just 1/16th or 1/32th of the memory you already use, same thing for the 1bit buffer which is of the size of your rgb screen memory : that is not much.

3) You can also use simple compression schemes and stream/decrompress. For instance RLE encoding or packing lines of consecutive full or empty bytes. For terrain/tunnel like environments you could use the same trick as ID used in Doom to render vertical 3D walls. Think vertically, compress columns instead of rows !

Share this post


Link to post
Share on other sites