Collision Detection

[prolemur]

So far in my little program there's a red and blue box which can move around on the screen and can go through each other. It does show a notification telling the user they have collided with the other box, but instead I want it to actually stop the character as if it had walked into a box

 

Thanks, here's my turing code so far, I'm sure it could be easily interpretted by others though and that was the reason I didn't put turing in the title.

View.Set ("graphics:640;480,nobuttonbar")var x1 : int := 100var y1 : int := 100var x2 : int := 150var y2 : int := 150var h1 : int := 300var v1 : int := 100var h2 : int := 350var v2 : int := 150var speed : int := 1var ypath : booleanvar xpath : booleanvar collision : booleanvar control : array char of booleanloop    %%%   INPUT   %%%    Input.KeyDown (control)    if control ('w') and y2 < maxy then        y1 += speed        y2 += speed    end if    if control ('s') and y1 > 0 then        y1 -= speed        y2 -= speed    end if    if control ('d') and x2 < maxx then        x1 += speed        x2 += speed    end if    if control ('a') and x1 > 0 then        x1 -= speed        x2 -= speed    end if    if control (KEY_UP_ARROW) and v2 < maxy then        v1 += speed        v2 += speed    end if    if control (KEY_DOWN_ARROW) and v1 > 0 then        v1 -= speed        v2 -= speed    end if    if control (KEY_RIGHT_ARROW) and h2 < maxx then        h1 += speed        h2 += speed    end if    if control (KEY_LEFT_ARROW) and h1 > 0 then        h1 -= speed        h2 -= speed    end if    %%%   COLLISION   %%%    if x1 > h2 or x2 < h1 then        ypath := false    else        ypath := true    end if    if y1 > v2 or y2 < v1 then        xpath := false    else        xpath := true    end if    if xpath = true and ypath = true then        collision := true    else        collision := false    end if    if xpath = true then        put "on course to collide on x-axis"    end if    if ypath = true then        put "on course to collide on y-axis"    end if    if collision = true then        put "They have collided!"    end if    %%%   GRAPHICS   %%%    Draw.Box (x1, y1, x2, y2, red)    Draw.Box (h1, v1, h2, v2, blue)    delay (10)    clsend loop

[DoubleY]

 I request a Steam key

[prolemur]

I don't know if I needed to or not but I made 3 booleans, on path to collide along x-axis, y-axis and collision is true if xpath and ypath are true.

 

So i need to find out which one of these requirements to a collision were met first x or y to be able to prevent the boxes moving in that direction, some kind of or gate, I didn't pay to much attention in class to that lesson (eg. xpath= true, then they collide. I don't want the boxes to be able to move in the xpath)

 

I'll find out which one can't go the other way with greater and less than...

[fletch to 99]

Oh God... Turing..

 

I did this 2 years ago in class. Give me a few minutes and I'll take a look.

[prolemur]

Oh God... Turing..

 

I did this 2 years ago in class. Give me a few minutes and I'll take a look.

Thanks, Ya I did this last year and I'm trying c++ at the moment and thought it would be easier to do it with the syntax I know than the completely new one and sdl api.

[fletch to 99]

Thanks, Ya I did this last year and I'm trying c++ at the moment and thought it would be easier to do it with the syntax I know than the completely new one and sdl api.

Oh well in that case: http://gamedev.stackexchange.com/questions/33530/simple-2d-collision-detection-algorithm-library

[prolemur]

Oh well in that case: http://gamedev.stackexchange.com/questions/33530/simple-2d-collision-detection-algorithm-library

I just realized it would be much easier to do with circles as they have a single side.

[WanderingFool]

Well just quickly googling Turing programming I must say it probably would make your life easier if you had put the collision detection in a function....anyways my quick thought about this project (loosely basing this off of what I have done in the past).

 

This approach would require you creating variables for velocity though

Detect inputs

Set "velocities"

"Move" object temporary

Detect collision

If no collision just repeat above

if collision remove your last move

 

The other way, would be to make your collision detection a function and then you could just check for a collision before setting the new position...I posted a quick one...excuse any syntax errors, I don't have a turing compiler....I would stress not to do it this way (as it is a bit convoluted, but it should work)

View.Set ("graphics:640;480,nobuttonbar")var x1 : int := 100var y1 : int := 100var x2 : int := 150var y2 : int := 150var h1 : int := 300var v1 : int := 100var h2 : int := 350var v2 : int := 150var speed : int := 1var ypath : booleanvar xpath : booleanvar collision : booleanvar control : array char of booleanfunction detectSquareCollision (x1,x2,y1,y2,h1,h2,v1,v2 : int) : int    if x1 > h2 or x2 < h1 then        ypath := false    else        ypath := true    end if    if y1 > v2 or y2 < v1 then        xpath := false    else        xpath := true    end if    if xpath = true and ypath = true then        result 0    else        collision := false    end if    if xpath = true and collision = false then        result 1    end if    if ypath = true and collision = false then        result 2    end if    result 3end detectSquareCollisionloop    %%%   INPUT   %%%    Input.KeyDown (control)    if control ('w') and y2 < maxy and detectSquareCollision (x1,x2,y1,y2+1,h1,h2,v1,v2) > 0 then        y1 += speed        y2 += speed    end if    if control ('s') and y1 > 0 and detectSquareCollision (x1,x2,y1-1,y2,h1,h2,v1,v2) > 0 then        y1 -= speed        y2 -= speed    end if    if control ('d') and x2 < maxx and detectSquareCollision (x1,x2+1,y1,y2,h1,h2,v1,v2) > 0 then        x1 += speed        x2 += speed    end if    if control ('a') and x1 > 0 and detectSquareCollision (x1-1,x2,y1,y2,h1,h2,v1,v2) > 0 then        x1 -= speed        x2 -= speed    end if    if control (KEY_UP_ARROW) and v2 < maxy and detectSquareCollision (x1,x2,y1,y2,h1,h2,v1,v2+1) > 0 then        v1 += speed        v2 += speed    end if    if control (KEY_DOWN_ARROW) and v1 > 0 and detectSquareCollision (x1,x2,y1,y2,h1,h2,v1-1,v2) > 0 then        v1 -= speed        v2 -= speed    end if    if control (KEY_RIGHT_ARROW) and h2 < maxx and detectSquareCollision (x1,x2,y1,y2,h1,h2+1,v1,v2) > 0 then        h1 += speed        h2 += speed    end if    if control (KEY_LEFT_ARROW) and h1 > 0 and detectSquareCollision (x1,x2,y1,y2,h1-1,h2,v1,v2) > 0 then        h1 -= speed        h2 -= speed    end if    %%%   COLLISION   %%%    if x1 > h2 or x2 < h1 then        ypath := false    else        ypath := true    end if    if y1 > v2 or y2 < v1 then        xpath := false    else        xpath := true    end if    if xpath = true and ypath = true then        collision := true    else        collision := false    end if    if detectSquareCollision (x1,x2,y1,y2,h1,h2,v1,v2) = 1 then        put "on course to collide on x-axis"    end if    if detectSquareCollision (x1,x2,y1,y2,h1,h2,v1,v2) = 2 then        put "on course to collide on y-axis"    end if    if detectSquareCollision (x1,x2,y1,y2,h1,h2,v1,v2) = 0 then        put "They have collided!"    end if    %%%   GRAPHICS   %%%    Draw.Box (x1, y1, x2, y2, red)    Draw.Box (h1, v1, h2, v2, blue)    delay (10)    clsend loop

[prolemur]

 

Well just quickly googling Turing programming I must say it probably would make your life easier if you had put the collision detection in a function....anyways my quick thought about this project (loosely basing this off of what I have done in the past).

 

This approach would require you creating variables for velocity though

Detect inputs

Set "velocities"

"Move" object temporary

Detect collision

If no collision just repeat above

if collision remove your last move

 

The other way, would be to make your collision detection a function and then you could just check for a collision before setting the new position...I posted a quick one...excuse any syntax errors, I don't have a turing compiler....I would stress not to do it this way (as it is a bit convoluted, but it should work)

*snip*

Thanks works like a charm

I've been pulling my hair out over this, or at least missing south park

[prolemur]

Thanks again for the help, I have to do the same type of thing now with an array of items.

 

I only need the collision to work on one side of each of the rectangles though so it should be easier for the computer. Basically I am remaking space invaders and want to make the aliens die when they get shot (right now it just goes straight through them). I tried using the old code here and changing it to apply correctly to a 2d array but I can't seem to do it.

 

Here is what I was trying to do with your code (all the stuff in the line of comment %%%%%)

View.Set ("graphics:640;360,offscreenonly,nobuttonbar,title:Space Invasion")var lag : int := 10var pad : int := 10var midx : int := maxx div 2var ship : boolean := truevar x : int := midxvar y : int := padvar xsize : int := 20var ysize : int := 10var speed : int := 1var lives : int := 3var shot : boolean := falsevar xshot : int := midxvar yshot : int := pad + ysizevar xshotsize : int := 2var yshotsize : int := 6var shotspeed : int := 2var shotsfired : int := 0var alienx : int := 210var alieny : int := 200var xaliensize : int := 20var yaliensize : int := 10var aliensx : int := 8var aliensy : int := 5var alienspeed : int := 10var aliendelay : int := 80var aliencount : int := 0var alien : array 1 .. aliensx, 1 .. aliensy of booleanvar control : array char of booleanfor i : 1 .. aliensx    for j : 1 .. aliensy        alien (i, j) := true    end forend for%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function attempt%%%%%%%%%%%%%%%%%%%%%%%%%%%%%var ypath : array 1 .. aliensx, 1 .. aliensy of booleanvar xpath : array 1 .. aliensx, 1 .. aliensy of booleanvar collision : array 1 .. aliensx, 1 .. aliensy of booleanfunction detectmurder (alienx, alieny, xaliensize, yaliensize, aliensx, aliensy, xshot, yshot : int) : int    for i : 1 .. aliensx        for j : 1 .. aliensy            if xshot > alienx + i * xaliensize + (i - 1) * pad and xshot + xshotsize < alienx + (i - 1) * (xaliensize + pad) then                xpath (i, j) := false            else                xpath (i, j) := true            end if            if yshot > alieny + j * yaliensize + (j - 1) * pad and yshot + yshotsize < alieny + (j - 1) * (yaliensize + pad) then                ypath (i, j) := false            else                ypath (i, j) := true            end if            if xpath (i, j) = true and ypath (i, j) = true then                result 0            else                collision (i, j) := false            end if            if xpath (i, j) = true and collision (i, j) = false then                result 1            end if            if ypath (i, j) = true and collision (i, j) = false then                result 2            end if            result 3        end for    end forend detectmurderprocedure danger    if shot = true then        if detectmurder (alienx, alieny, xaliensize, yaliensize, aliensx, aliensy, xshot, yshot) > 0 then            for i : 1 .. aliensx                for j : 1 .. aliensy                    if xpath (i, j) = true and ypath (i, j) = true then                        alien (i, j) := false                    end if                end for            end for        end if    end ifend danger%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function attempt%%%%%%%%%%%%%%%%%%%%%%%%%%%%%procedure input    Input.KeyDown (control)    if control (KEY_LEFT_ARROW) and x > pad then        x -= speed    elsif control (KEY_RIGHT_ARROW) and x + xsize < maxx - pad then        x += speed    end ifend inputprocedure alienai    if aliencount mod aliendelay = 0 then        alienx += alienspeed        if alienx + aliensx * xaliensize + (aliensx - 1) * pad >= maxx - pad or alienx <= pad then            alienspeed *= -1            alieny -= yaliensize + pad        end if    end if    aliencount += 1end alienaiprocedure shooting    if shot = true then        yshot += shotspeed        shotsfired += 1        Draw.FillBox (xshot, yshot, xshot + xshotsize, yshot + yshotsize, white)        if yshot >= maxy then            shot := false            yshot := pad + ysize        end if    elsif shot = false then        if control (chr (32)) then            shot := true            xshot := x + xsize div 2 - xshotsize div 2        end if    end ifend shootingprocedure graphics    if ship = true then        Draw.Box (x, y, x + xsize, y + ysize, 11)    end if    for i : 1 .. aliensx        for j : 1 .. aliensy            if alien (i, j) = true then                Draw.Box (alienx + (i - 1) * (xaliensize + pad), alieny + (j - 1) * (yaliensize + pad), alienx + i * xaliensize + (i - 1) * pad, alieny + j * yaliensize + (j - 1) * pad, 10)            end if        end for    end for    if shot = true then        Draw.Box (xshot, yshot, xshot + xshotsize, yshot + yshotsize, 42)    end if    colorback (black)    View.Update    delay (lag)    clsend graphicsloop    input    alienai    shooting    graphics    dangerend loop

Thanks getting this part done of the game is pretty much the most important, also when the aliens reach an end of the screen they do 2 steps and i only want them to do 1 (ex get to right side, move down, move left. right now it goes get to right side, move down and move left at the same time.)

 

[Nuluvius]

You might want to take a look at the Quadtree data structure and the like.

 

http://en.wikipedia.org/wiki/Quadtree

[Ciccioo]

You might want to take a look at the Quadtree data structure and the like.

http://en.wikipedia.org/wiki/Quadtree

you really like quadtrees, don't you

[Nuluvius]

you really like quadtrees, don't you

I love them Made an animated 2D word cloud with one a while ago.

[prolemur]

You might want to take a look at the Quadtree data structure and the like.

 

http://en.wikipedia.org/wiki/Quadtree

Can you give me an example of how I would use that in my program?

 

This seems like an optimization things, but I'm not done the program yet, if it is.

[Nuluvius]

Can you give me an example of how I would use that in my program?

 

This seems like an optimization things, but I'm not done the program yet, if it is.

 

Google for: Quadtree collision detection

 

There is some rich information to be had there. Sorry I don't have time right now (vary busy week days).

[Nuluvius]

Only skim read:

http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374

Plus CD algorithm:

http://gamedevelopment.tutsplus.com/tutorials/collision-detection-with-the-separating-axis-theorem--gamedev-169

[Ciccioo]

You might want to take a look at the Quadtree data structure and the like.

This seems like an optimization things, but I'm not done the program yet, if it is.

it could even be a good thing, but i don't think that implementing such a data structure is worth it with this amount of objects, since iterating through all the aliens is perfectly doable

also, since the alien's movements is so regular, i believe that you can just find a pretty much straightforward formula to check for the collision

[prolemur]

it could even be a good thing, but i don't think that implementing such a data structure is worth it with this amount of objects, since iterating through all the aliens is perfectly doable

also, since the alien's movements is so regular, i believe that you can just find a pretty much straightforward formula to check for the collision

Ya it's pretty much checking if two lines collide, only in the one direction. The array part and the function is what I'm having problems with.

[prolemur]

I did the collsion detection and just threw it inside another method and it runs whenever a shot is in play. A problem that came up with this detection is that it will kill an alien when it goes through the cracks and the aliens change position right into the shot and die. I don't want this to happen because that's not present in the real game. Most of the functionality is done though it just needs to feel more like a game.

 

Also I tried there being 100x100 aliens and it was really laggy so maybe further on down the line i can add quadtree collision detection to make it smoother.

 

Also this game runs faster or slower depending on your computer at the moment, not sure how to fix this in turing, but as long as your not using a TI-83 it should be roughly the same cross platform.

 

Turing download for windows

View.Set ("graphics:640;360,offscreenonly,nobuttonbar,title:Space Invasion")var lag : int := 10var pad : int := 10var midx : int := maxx div 2var ship : boolean := truevar x : int := midxvar y : int := padvar xsize : int := 20var ysize : int := 10var speed : int := 2var lives : int := 3var shot : boolean := falsevar xshot : int := midxvar yshot : int := pad + ysizevar xshotsize : int := 2var yshotsize : int := 6var shotspeed : int := 3var shotsfired : int := 0var alienx : int := 170var alieny : int := 200var xaliensize : int := 20var yaliensize : int := 10var aliensx : int := 10var aliensy : int := 6var alienspeed : int := 10var aliendelay : int := 100var aliencount : int := 0var alien : array 1 .. aliensx, 1 .. aliensy of booleanvar control : array char of booleanfor i : 1 .. aliensx    for j : 1 .. aliensy        alien (i, j) := true    end forend forprocedure input    Input.KeyDown (control)    if control (KEY_LEFT_ARROW) and x > pad then        x -= speed    elsif control (KEY_RIGHT_ARROW) and x + xsize < maxx - pad then        x += speed    end ifend inputprocedure alienai    if aliencount mod aliendelay = 0 then        alienx += alienspeed        if alienx + aliensx * xaliensize + (aliensx - 1) * pad >= maxx - pad or alienx <= pad then            alienspeed *= -1            alieny -= yaliensize + pad        end if    end if    aliencount += 1end alienaiprocedure shooting    if shot = true then        yshot += shotspeed        Draw.FillBox (xshot, yshot, xshot + xshotsize, yshot + yshotsize, white)        for k : 1 .. aliensx            for m : 1 .. aliensy                if alien (k, m) = true then                    if xshot <= alienx + k * xaliensize + (k - 1) * pad then                        if xshot + xshotsize >= alienx + (k - 1) * (xaliensize + pad) then                            if yshot + yshotsize >= alieny + (m - 1) * (yaliensize + pad) then                                if yshot <= alieny + m * yaliensize + (m - 1) * pad then                                    alien (k, m) := false                                    shot := false                                    yshot := pad + ysize                                    xshot := x + xsize div 2 - xshotsize div 2                                end if                            end if                        end if                    end if                end if            end for        end for        if yshot >= maxy then            shot := false            yshot := pad + ysize        end if    elsif shot = false then        if control (chr (32)) then            shot := true            xshot := x + xsize div 2 - xshotsize div 2        end if    end ifend shootingprocedure graphics    if ship = true then        Draw.Box (x, y, x + xsize, y + ysize, 11)    end if    for i : 1 .. aliensx        for j : 1 .. aliensy            if alien (i, j) = true then                Draw.Box (alienx + (i - 1) * (xaliensize + pad), alieny + (j - 1) * (yaliensize + pad), alienx + i * xaliensize + (i - 1) * pad, alieny + j * yaliensize + (j - 1) * pad, 10)            end if        end for    end for    if shot = true then        Draw.Box (xshot, yshot, xshot + xshotsize, yshot + yshotsize, 42)    end if    colorback (black)    View.Update    delay (lag)    clsend graphicsloop    input    alienai    shooting    graphicsend loop% Make it use the last and first aliens x + xsize and x to choose when to change direction% for i : 1..aliensx%   if aliens(aliensxmin,i) = false then%       aliensxmin += 1%   elsif aliens (aliensxmax,i) = false then%       aliensxmax -=1%   end if% end for

[Ciccioo]

alright, let's see if we can come up with something more adequate for this specific situation

copypasting from your code, the left offset of the k-th column of aliens is determined as

leftOffset = alienx + (k - 1) * (xaliensize + pad)

now, from that equation we can work out that

k = (xaliensize + pad + leftOffset - alienx) / (xaliensize + pad)

so, substituting "leftOffset" with a certain coordinate you can instantaneously get the column index of the aliens who sit on that line

in your case, you will substitute "leftOffset" with xshot

then you can do the same for the top offset, so that you find the row index of the alien that is being shot

now you combine the row and column index, validate them, check if that alien is still alive and boom

in this example i didn't take into account the size of both the alien and the shot, but once you see how this thing works that should be fairly simple to implement

@prolemur i see only now that you didn't follow the topic

[prolemur]

alright, let's see if we can come up with something more adequate for this specific situation

copypasting from your code, the left offset of the k-th column of aliens is determined as

leftOffset = alienx + (k - 1) * (xaliensize + pad)

now, from that equation we can work out that

k = (xaliensize + pad + leftOffset - alienx) / (xaliensize + pad)

so, substituting "leftOffset" with a certain coordinate you can instantaneously get the column index of the aliens who sit on that line

in your case, you will substitute "leftOffset" with xshot

then you can do the same for the top offset, so that you find the row index of the alien that is being shot

now you combine the row and column index, validate them, check if that alien is still alive and boom

in this example i didn't take into account the size of both the alien and the shot, but once you see how this thing works that should be fairly simple to implement

@prolemur i see only now that you didn't follow the topic

 

I follow the topic by checking my content i just don't know how to put that into my code.

[Nuluvius]

Just a question; are these things abstracted out into their own classes? i.e. ship, aliens, bullets and so fourth...

[Ciccioo]

Just a question; are these things abstracted out into their own classes? i.e. ship, aliens, bullets and so fourth...

his whole code is posted in the first page, so we can see that nope, that's not the case

[Nuluvius]

his whole code is posted in the first page, so we can see that nope, that's not the case

 

Yes but how many iterations has it undertaken since? Plus you missed the point a little bit, I'm trying to hint... 

 

 

*cough* Single responsibility principle *cough*

[Ciccioo]

Yes but how many iterations has it undertaken since? Plus you missed the point a little bit, I'm trying to hint... 

*cough* Single responsibility principle *cough*

normal turing is not object oriented, and that wouldn't solve the problem anyway

the point of the thread is to come up with an algorithm that can detect shot-hits, thing that can be worked out either with the method that the OP used in his last version of the code, or with the method i proposed a couple posts ago