Mass 2D hit detection

[keyboardwalker]

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

[Insectoid]

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?

[keyboardwalker]

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

[Insectoid]

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.