Raycasting in 2D

Newbie & Debugging Questions
#1

Hey everyone, I am creating a 2D top down shooter but am having trouble with collision detection.

I am at the point in the game where the player can shoot but bullet to environment collision isnt going so well. So far I have it so that the parts of the tilemap that entities can collide with are stored in an arraylist of Rectangles representing those cells, and am seeing if the bullet rectangles intersect with them, and if they do, i remove the bullet.

However the problem comes in when the bullets move really fast like they should, even when they move fairly slow actually, but basically what happens is the bullets go through the walls, so if an enemy is on the other side of the wall, it still has a chance of being hit.

I heard from others that for things like this I should use raycasting, however I am not really sure where to start with that. I know that the point of raycasting is to draw a line going from the tip of the gun, toward the direction its facing, and seeing if it every collides with any of Rectangles, or “forbidden” tiles. However I am not sure about how to go about implementing this.

Also, if i do implement this, I wouldnt need bullets right? Just a flash at the muzzle and maybe a collision drawing, but nothing in between since the bullets would be moving so fast, im sure thats just prefrence though…

Links, help, or anything is appreciated :slight_smile:

#2

The easiest way out is to interpolate your bullet’s positions between the updates, to such a small interval that it gets in the sub-pixel accuracy. At every interval you check whether it is inside those rectangles.

The other way is to do true physics… which will be a lot of work, yet faster to calculate.

#3

Yea I think i will have to pass on the physics, but am not sure if I understand what you mean. Are you saying, instead of doing raycasting, just update the bullets position by an extremely small amount so that it checks almost every position and wont be able to move 5-10 pixels through the wall?

But wouldnt that effect bullet speed? like wouldnt the bullet move extremely slow?

#4

Check this out:

http://www.java-gaming.org/index.php/topic,19328.0.html

#5

If you want fast moving bullets then you just need to do “swept” collision detection each frame rather than just testing the new position. For bullets that means taking the last frame’s position and the new position and creating some sort of collision geoemtry out of that - line segments work well, or capsules (line segments with a radius) are nice too. Much more efficient and less hacky than doing a fixed number of intermediate steps.

#6

Yeah line-line intersection is one of the best ways, where the line goes from the back of bullet’s last position, to the front of its new position. After finding all bodies that intersect with the line, you then test which entity is the closest to the start of the line, and collide the bullet with that entity.

#7

Wow, thanks guys for all the replies, im gonna look into them. Also, when you guys say I should do some type of “swept” collision by using a line from the last position of the bullet to the front, are you saying I should have something like… A function that will contain a last position and new position of the bullet, which will be used to create that line, then it will check and see if that line intersects with anything, and if it does, check to see what it hit, and based on that do what it needs to?

#8

Yep, that’s what I do. Each bullet has an oldBackX and Y.

#9

Nice, thanks man! Ill give it a shot, especially since its what you do and I really enjoyed playing your 2D multiplayer shooter lol, really is kind of fun, although couldnt figure out how to get the sniper,but yea its an awesome display of what your engine can do!

#10

oh cheers! well if you think that’s good, you should see what others here can do.

good luck with your 2d shooter, let us know how your progress is going on the forums 8)

#11

My solution regarding reducing the interval is the most simple to implement, that’s why I suggested it. It is hardly performant. Anyway, it’s amazing how poorly performing code is ‘forgiven’ by todays incredible CPU speeds.

To answer your question: no, the bullets would not have to move incredibly slow, you just need to do the check N times per frame, instead of 1 time per frame.

Anyway, since a rectangle is composed of 4 lines, and the moving bullet is 1 line, a line vs line collision check is rather simple to implement, and will make your engine more scalable, because performance will be much better.

#12

Well the question is how do you do line vs line collision testing if you don’t know the level’s geometry? If your game is like Worms (the level is a bitmap, not a bunch of geometry) then your only option is to do the pixel-by-pixel method. And yeah, if the rest of your game isn’t incredibly complicated this collision method works absolutely fine, basically because processor speeds are so incredibly high now.

#13

You might want to read the first post.

#14

Hey everyone, sorry I dont have much progress to tell about with my collision detection, but of course I have another question :stuck_out_tongue:

How can we use a directional vector in Java? Is there anything built right in? I remember using something a while back but am not 100% sure what it was and how.

Also, should i store all collidable rectangles in one arraylist? because right now, i have an arraylist of Rectangles representing the tiles on the map that can be collided into, but for the entities, i loop through the ArrayList of entities and then use a getRect method to get theirs…because otherwise, i have to have like 2 or 3 nested for loops, looping through every bullet, then every entity, then ever collidable rectangle…

#15

You can make an interface:


public interface BoundingBox
{
   public Rectangle getBoundingBox();
}



public Wall implements BoundingBox
{
   private final Rectangle bounds;

   public Wall(Rectangle bounds)
   {
      this.bounds = bounds;
   }

   public Rectangle getBoundingBox()
   {
       return bounds;
   }
}



public Player implements BoundingBox
{
   private int x, y;
   private boolean dirty;
   private final Rectangle bounds;

   public Player(Dimension dim)
   {
      this.bounds = new Rectangle(dim);

      this.setPosition(0, 0);
   }



   public void setPosition(int x, int y)
   {
      this.dirty= (this.x != x) || (this.y != y);
      this.x = x;
      this.y = y;
   }

   public Rectangle getBoundingBox()
   {
       if(this.dirty)
       {
            this.bounds.x = this.x - this.bounds.width/2;
            this.bounds.y = this.y - this.bounds.height/2; // either this for vertically centered box
            this.bounds.y = this.y - this.bounds.height; // ...or this, which is what you probably need

            this.dirty= false;
       }
       return bounds;
   }
}

Then add all your Walls AND Players (and many more types) in the same List. Now you can iterate over that list, regardless of the types.

#16

Yeah I know he doesn’t need to, I was saying in general. If you don’t know geometry that’s one reason to use pixel-by-pixel collision.

#17

Whoo! Thanks for that Riven! much more efficient then what im doing :persecutioncomplex:

Although not sure what the “dirty” boolean is used for, and I think i am just going to have to use a list of rectangles (list) because my tilemap is stored in a map that my engine calls up, and then i use a method the gives the game an ArrayList of all the rectangles that are collidable on that certain map…

Also, when i find out if the bullet did collide with something, then i can just use instanceof, to find out with what and what to do right?

but once again thanks!

#18

Ok, A lot of progress has been made, Bullet collison is pretty good at the moment, I used the method of just checking the bullets position more than once per update, and I used the BoundingBox method for item collision.

So thank you all for those suggestions and advice!!

Also, I have implemented a Weapon class, and LUA scripting so i can easily create many different types of weapons with lua files, rather than hard coding them all in, which was actually fairly simple to implement and very helpful!

However I have another question, for enemy AI (similar to how ComanderKeith did it in his multiplayer shooter “demo” of his engine) should that be included in LUA files or should I just hard code that in? I appreciate any answers like to my previous questions because it really helps me get a view of all the different ways to implement things!

#19

You can also really easy use Java’s JIT to add in Java code as external scripts for weapons. I’ve done that and it works well, plus it’s more powerful than something like LUA.

#20

Do you mean by using Janino?

http://www.janino.net/

I was thinking of using this in my next game, it looks really really good.

Enemy AI need not be that complicated by the way. Like the bots can just do laps of way points until they see an enemy that is unobstructed, then they stop and shoot. That seems to work well and is pretty fun, I’ve seen other people use it too.