2D Collision detection help

Accname

2D-Graphics enthusiast
Reaction score
1,462
Hi guys.
I was thinking alot about collision detection in a 2D game recently. More specifically the collision with a static terrain which doesnt change anymore after creation.

Lets say our game object has a position, defined by its X and Y coordinate, and it wants to travel to another position, also defined by X and Y, and we wanna know if this movement is possible or if it collides with the terrain.
OriginalProblem.png


I am basically looking at 2 different ways of implementing it. The first way is to have a big two dimensional array for the map. I can specify a cell size for flexible accuracy and i just check all points between the original position and the final destination.
Problem is, the faster the object is moving, that is, the further away the target location is from the original location, the more calculations need to be done.
But its very simple calculations. Just find the next point, check with the array, if there was a collision then stop, if not, continue until the target is reached.
SolutionA.png


The other way i was thinking about was to define all collision with the terrain by points in a coordinate system which represent line segments. Then, i could check if the line segment formed by the objects original position and target location intesects with any collision line segments in the map.
The calculation to determine whether two line segments collide is a little bit more complex, but its indepent on the length of the lines.
Now the performance would depend on the number of collision lines within the proximity of the object.
SolutionB.png


So the first solution will probably need more RAM in a conventional scenario whereas the second solution might need more processing power for slow moving objects and less processing power for very fast objects.

Any suggestions?
 

camelCase

The Case of the Mysterious Camel.
Reaction score
362
Quad-tree + Line segment test?
I mean, each partition of your quad-tree can be a rect (which is made of four line segments, obviously) and, deciding which partition of the quad-tree each line segment collider belongs in is easy, just check if the line segment collides with any of the four line segments that make up the rect..

To figure out which lines to test against, just create a line segment and get all the partitions that it would collide with; all line segments in those partitions need to be tested against.

All this is only necessary if your map's huge, though..

Line segment + 2D array might work if you use some 2D line rasterizing algorithm but I'm not sure how accurate it'd be.. Also, some spaces in your 2D array will not even have any line segments in them, wasting memory =x
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
Imo: Do the first one. A lot less trouble in the long run.

If you have only two dozen or so collidible objects at once on your screen (or only short walking distances):
Do exactly as you described it.

If you have a lot more than that:
Draw an axis-aligned hitbox around each objects and do line-box intersection tests instead. If the test passes, then do a normal test with that object.

Just don't burden yourself with too much technical trouble. Your CPU can solve that stuff brute-force :p
 

Accname

2D-Graphics enthusiast
Reaction score
1,462
Thanks for the answers so far.
I am currently going with the first solution. Problem is, its a very huge map (2048 * 2048 cells) and alot of memory is just used for this data. My idea was that usually its not like the map is dotted randomly with impassable terrain. There is a certain structure behind it.
For example a house usually makes up a big rectangular shape of impassable terrain. I thought i could use this information to save memory if i just define polygons for the passability tests.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top