Computer Science Canada

Mass 2D hit detection
Author:  keyboardwalker [ Sun Jan 27, 2013 6:53 pm ]
Post subject:  Mass 2D hit detection
Okay so I am trying to find the best way to do 2D hit detection very quickly. I currently have two methods one is with the the array of dots and checks to see if the movement location is okay by checking to see if any of the dots are in the array are in that X and Y location The other with colour. The issue with using the array locations is that you are doing a check for every single dot to see if any of the other dots are in that location. So far the best method I have found for hit detection with dots is actually colour which can be unreliable in some cases but it works. So what I was wondering is there a faster way or a just as fast way but more reliable?

This is what I have done for colour hit detection:

Turing:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Click on the screen to move the dots to the mouse
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
const SCREENH := 400
const SCREENW := 400
%SCREENW * SCREENH
%This is the number of dots
%Shoud really be called NUMDOTS :)
%If it is really slow change it to a lower number
const NUMBOXS := 2000
%The array of boxes
var BoxX : array 1 .. NUMBOXS of int
var BoxY : array 1 .. NUMBOXS of int
%Their colours
var BoxColour : int
setscreen ("graphics:400;400,nobuttonbar,offscreenonly")
procedure Grid_Dots
    var Counter : nat
    var XCur : int
    var YCur : int
    XCur := 1
    YCur := SCREENH
    Counter := 1
    randint (BoxColour, 1, 255)
    loop
        BoxX (Counter) := XCur
        BoxY (Counter) := YCur
        XCur := XCur + 1
        Counter := Counter + 1
        if XCur > SCREENW then
            XCur := 1            YCur := YCur - 1
        end if
        exit when Counter > NUMBOXS
    end loop
end Grid_Dots
procedure Draw_Dots
    %It goes through the array of created dots and draws a dot there
    var Counter : nat
    Counter := 1
    cls
    loop
       drawdot (BoxX (Counter), BoxY (Counter), BoxColour)
        Counter := Counter + 1
        exit when Counter = NUMBOXS
    end loop
end Draw_Dots
procedure Follow_Mouse
    %Variables for mousewhere
    var MouseX : int
    var MouseY : int
    var MouseButton : int
    %The movement that the dots will try to move.
    const SPEED := 2
    loop
        mousewhere (MouseX, MouseY, MouseButton)
        if MouseX > 0 and MouseX < SCREENW and MouseY > 0 and MouseY < SCREENH and MouseButton = 1 then
            %This goes through each individual dot to see if
            %It makes any contact.
            %
            for Indy : 1 .. NUMBOXS
                %This draws a white dot in the dot's location
                %This is used to prevent having to clear the screen every
                % movement.
                drawdot (BoxX (Indy), BoxY (Indy), 0)
                if MouseY > BoxY (Indy) then
                    %This checks to see if where it wants to go is dot coloured.
                    if not whatdotcolour (BoxX (Indy), BoxY (Indy) + SPEED) = BoxColour then
                        BoxY (Indy) := BoxY (Indy) + SPEED
                        %This checks to see if where it wants to go is dot coloured but it goes 1 dot closer
                        %Consider this take 2
                    elsif whatdotcolour (BoxX (Indy), BoxY (Indy) + SPEED - 1) = 0 then
                        BoxY (Indy) := BoxY (Indy) + SPEED - 1
                    end if
                elsif MouseY < BoxY (Indy) then
                    if not whatdotcolour (BoxX (Indy), BoxY (Indy) - SPEED) = BoxColour then
                        BoxY (Indy) := BoxY (Indy) - SPEED
                    elsif not whatdotcolour (BoxX (Indy), BoxY (Indy) - SPEED + 1) = BoxColour then
                        BoxY (Indy) := BoxY (Indy) - SPEED + 1
                    end if
                end if
                if MouseX > BoxX (Indy) then
                    if not whatdotcolour (BoxX (Indy) + SPEED, BoxY (Indy)) = BoxColour then
                        BoxX (Indy) := BoxX (Indy) + SPEED
                    elsif not whatdotcolour (BoxX (Indy) + SPEED - 1, BoxY (Indy)) = BoxColour then
                        BoxX (Indy) := BoxX (Indy) + SPEED - 1
                    end if
                elsif MouseX < BoxX (Indy) then
                    if not whatdotcolour (BoxX (Indy) - SPEED, BoxY (Indy)) = BoxColour then
                        BoxX (Indy) := BoxX (Indy) - SPEED
                    elsif not whatdotcolour (BoxX (Indy) - SPEED + 1, BoxY (Indy)) = BoxColour then
                        BoxX (Indy) := BoxX (Indy) - SPEED + 1
                    end if
                end if
                drawdot (BoxX (Indy), BoxY (Indy), BoxColour)
            end for
        else
            delay (100)
        end if
        View.Update
        %It will exit when you press a key
        exit when hasch
    end loop
end Follow_Mouse

Grid_Dots
Draw_Dots
Follow_Mouse

Author:  Insectoid [ Sun Jan 27, 2013 8:44 pm ]
Post subject:  RE:Mass 2D hit detection
Using an array is your best bet. You don't have to check everything though. If your character is all the way on the left, he can't possibly hit anything on the right, so why bother checking against objects on the right?
Author:  keyboardwalker [ Sun Jan 27, 2013 9:47 pm ]
Post subject:  Re: RE:Mass 2D hit detection
Insectoid @ Sun Jan 27, 2013 8:44 pm wrote:
Using an array is your best bet. You don't have to check everything though. If your character is all the way on the left, he can't possibly hit anything on the right, so why bother checking against objects on the right?

Here is my hit detection with arrays but it can't compare to hit detection with colour. How can I optimize it so that it is faster? I don't know how to apply what you just said.
Try running the two and see the difference I really want the fastest way.
const NUMDOT := 200
var DotX : array 1 .. NUMDOT of nat
var DotY : array 1 .. NUMDOT of nat
var MouseX, MouseY, MouseButton : int
var Count : nat
var Hit : boolean
var Temp : int
for I : 1 .. NUMDOT
randint (Temp, 1, 400)
DotY (I) := Temp
randint (Temp, 1, 400)
DotX (I) := Temp
end for
setscreen ("offscreenonly")
loop
mousewhere (MouseX, MouseY, MouseButton)
if MouseButton = 1 then
for i : 1 .. NUMDOT
if DotX (i) > MouseX then
Count := 1
Hit := false
loop
if DotX (i) - 1 = DotX (Count) and DotY (i) = DotY (Count) then
Hit := true
end if
Count := Count + 1
exit when Count = NUMDOT or Hit
end loop
if not Hit then
DotX (i) := DotX (i) - 1
end if
elsif DotX (i) < MouseX then
Count := 1
Hit := false
loop
if DotX (i) + 1 = DotX (Count) and DotY (i) = DotY (Count) then
Hit := true
end if
Count := Count + 1
exit when Count = NUMDOT or Hit
end loop
if not Hit then
DotX (i) := DotX (i) + 1
end if
end if
if DotY (i) > MouseY then
Count := 1
Hit := false
loop
if DotY (i) - 1 = DotY (Count) and DotX (i) = DotX (Count) then
Hit := true
end if
Count := Count + 1
exit when Count = NUMDOT or Hit
end loop
if not Hit then
DotY (i) := DotY (i) - 1
end if
elsif DotY (i) < MouseY then
Count := 1
Hit := false
loop
if DotY (i) + 1 = DotY (Count) and DotX (i) = DotX (Count) then
Hit := true
end if
Count := Count + 1
exit when Count = NUMDOT or Hit
end loop
if not Hit then
DotY (i) := DotY (i) + 1
end if
end if
end for
end if
cls
for I : 1 .. NUMDOT
drawdot (DotX (I), DotY (I), black)
end for
View.Update
exit when hasch
end loop
Author:  Insectoid [ Mon Jan 28, 2013 1:27 pm ]
Post subject:  RE:Mass 2D hit detection
You could try breaking the screen up into a grid of smaller squares. Figure out what squares your objects are in, then figure out which square(s) your character is in, and only check for collisions with objects in the same square(s) as your character.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy