generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Challenge: Most Efficient Way to do part-in-part check

Previous Thread :: Next Thread 
blocco is not online. blocco
Joined: 14 Aug 2008
Total Posts: 29474
04 Sep 2013 02:43 PM
I love challenges. I know you do too. I have gathered you all here today to ask you to find the most efficient way to check whether a part is within another part.

**Two half-challenges:**

* Find the most efficient algorithm to check whether two parts are **PARTIALLY** within each other.
* Find the most efficient algorithm to check whether two parts are **WHOLLY** within each other.

**Drawbacks:**

* Region3 cannot be rotated, so using that alone will not work (the algorithm should work on parts of any orientation)
* Magnitude alone will not work, as parts are not spheres.

Any questions? Feel free to ask.

~ blocco
Report Abuse
digpoe is not online. digpoe
Joined: 02 Nov 2008
Total Posts: 9092
04 Sep 2013 02:52 PM
part.Shape = "Ball"


the part is now a sphere


can I use magnitude now?
Report Abuse
BenBonez is not online. BenBonez
Joined: 29 Aug 2008
Total Posts: 19362
04 Sep 2013 02:52 PM
digpoe wins
Report Abuse
blocco is not online. blocco
Joined: 14 Aug 2008
Total Posts: 29474
04 Sep 2013 02:53 PM
**NOTE:** This challenge only requires that the ClassName be "Part". If you wish to make an algorithm for all derived classes of "BasePart", feel free, but this challenge only requires cuboids to be checked.
Report Abuse
digpoe is not online. digpoe
Joined: 02 Nov 2008
Total Posts: 9092
04 Sep 2013 02:54 PM
local part = Instance.new("Part", workspace)
part.Shape = "Ball"

--code to check some magnitude hacks
Report Abuse
leates is not online. leates
Joined: 16 Jan 2009
Total Posts: 5650
04 Sep 2013 03:08 PM
Have a look manually.

rofl
Report Abuse
crazywaffleman1 is not online. crazywaffleman1
Joined: 05 Dec 2009
Total Posts: 781
04 Sep 2013 03:41 PM
part:dostuff('omgifoundit') the end

>best skrept evr
Report Abuse
booing is not online. booing
Joined: 04 May 2009
Total Posts: 6594
04 Sep 2013 03:44 PM
I've not tested this, but wouldn't this work?

local p = [part]
local c = p.CFrame
p:MoveTo(p.Position)
if (p.CFrame ~= c) then
is in part
end
p.CFrame = c
Report Abuse
booing is not online. booing
Joined: 04 May 2009
Total Posts: 6594
04 Sep 2013 03:44 PM
ops im an idot, that wouldn't work for angles but is easy to adapt
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 04:24 PM
local part1, part2 = lol, whatever
for i, v in next, {
Vector3.new(part1.Size.X/2, part1.Size.Y/2, part1.Size.Z),
Vector3.new(part1.Size.X/2, part1.Size.Y/2, -part1.Size.Z),
Vector3.new(part1.Size.X/2, -part1.Size.Y/2, part1.Size.Z),
Vector3.new(part1.Size.X/2, -part1.Size.Y/2, -part1.Size.Z),
Vector3.new(-part1.Size.X/2, part1.Size.Y/2, part1.Size.Z),
Vector3.new(-part1.Size.X/2, part1.Size.Y/2, -part1.Size.Z),
Vector3.new(-part1.Size.X/2, -part1.Size.Y/2, part1.Size.Z),
Vector3.new(-part1.Size.X/2, -part1.Size.Y/2, -part1.Size.Z)} do
local relpos = part2.CFrame:pointToObjectSpace(part1.Position + v)
if math.abs(relpos.X) <= part1.Size.X/2 or math.abs(relpos.Y) <= part1.Size.Y/2 or math.abs(relpos.Z) <= part1.Size.Z/2 then
return true
end
end
return false

--h4x, I think (untested)
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 04:29 PM
local intersect = function(part1, part2)
for i, v in next, {
Vector3.new(part1.Size.X/2, part1.Size.Y/2, part1.Size.Z/2),
Vector3.new(part1.Size.X/2, part1.Size.Y/2, -part1.Size.Z/2),
Vector3.new(part1.Size.X/2, -part1.Size.Y/2, part1.Size.Z/2),
Vector3.new(part1.Size.X/2, -part1.Size.Y/2, -part1.Size.Z/2),
Vector3.new(-part1.Size.X/2, part1.Size.Y/2, part1.Size.Z/2),
Vector3.new(-part1.Size.X/2, part1.Size.Y/2, -part1.Size.Z/2),
Vector3.new(-part1.Size.X/2, -part1.Size.Y/2, part1.Size.Z/2),
Vector3.new(-part1.Size.X/2, -part1.Size.Y/2, -part1.Size.Z/2)} do
local relpos = part2.CFrame:pointToObjectSpace(part1.CFrame * v)
print(relpos)
if math.abs(relpos.X) <= part1.Size.X/2 and math.abs(relpos.Y) <= part1.Size.Y/2 and math.abs(relpos.Z) <= part1.Size.Z/2 then
return true
end
end
return false
end

while wait() do
print(intersect(workspace.Part1, workspace.Part2))
end


--Tested and working
Report Abuse
blocco is not online. blocco
Joined: 14 Aug 2008
Total Posts: 29474
04 Sep 2013 04:31 PM
@Notunknown99: That's the same thing I did, and unfortunately it doesn't work in all cases. Imagine two skinny boxes whose vertices don't intersect each other, yet they are within each other.
Report Abuse
MrNicNac is not online. MrNicNac
Joined: 29 Aug 2008
Total Posts: 26567
04 Sep 2013 04:31 PM
1)

function partInPart(p1, p2)
return math.abs(p2.CFrame:pointToObjectSpace(p1.CFrame.p).x) <= p2.Size.x/2 and math.abs(p2.CFrame:pointToObjectSpace(p1.CFrame.p).y) <= p2.Size.y/2 and math.abs(p2.CFrame:pointToObjectSpace(p1.CFrame.p).z) <= p2.Size.z/2
end

2)

Who cares
Report Abuse
booing is not online. booing
Joined: 04 May 2009
Total Posts: 6594
04 Sep 2013 04:33 PM
oooooooo
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 04:33 PM
@MrNicNac: That only checks if a point is within a part...
Report Abuse
MrNicNac is not online. MrNicNac
Joined: 29 Aug 2008
Total Posts: 26567
04 Sep 2013 04:35 PM
"@MrNicNac: That only checks if a point is within a part..."

True, but it's an algorithm which can be easily altered. The best way to continue is not to do all the vertices - because some don't need to be checked (since there are "part rules" where if 1 vertex is colliding then another must be.
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 04:43 PM
@blocco: < instead of <=..?

Although you might have to do a check for if one parts position is identical to the second parts.
Report Abuse
blocco is not online. blocco
Joined: 14 Aug 2008
Total Posts: 29474
04 Sep 2013 04:43 PM
You can't simply check all 8 vertices; there are edge cases and corner cases that fail if you check vertices only
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 04:45 PM
local intersect = function(part1, part2)
for x = -1, 1, 2 do
for y = -1, 1, 2 do
for z = -1, 1, 2 do
local relpos = part2.CFrame:pointToObjectSpace(part1.CFrame * Vector3.new(x*part1.Size.X/2, y*part1.Size.Y/2, z*part1.Size.Z/2))
if math.abs(relpos.X) < part1.Size.X/2 and math.abs(relpos.Y) < part1.Size.Y/2 and math.abs(relpos.Z) < part1.Size.Z/2 then
return true
end
local relpos2 = part1.CFrame:pointToObjectSpace(part2.CFrame * Vector3.new(x*part2.Size.X/2, y*part2.Size.Y/2, z*part2.Size.Z/2))
if math.abs(relpos2.X) < part2.Size.X/2 and math.abs(relpos2.Y) < part2.Size.Y/2 and math.abs(relpos2.Z) < part2.Size.Z/2 then
return true
end
end
end
end
return false
end

while wait() do
print(intersect(workspace.Part1, workspace.Part2))
end

--h4x?
Report Abuse
MrNicNac is not online. MrNicNac
Joined: 29 Aug 2008
Total Posts: 26567
04 Sep 2013 04:47 PM
"You can't simply check all 8 vertices; there are edge cases and corner cases that fail if you check vertices only"

I'm not sure what you mean, and it'd be great to have an example, because I almost thought you had a good point (as in, something I never realized). But the corner checks suffice in that they check if the edge regions intersect as well.
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 04:49 PM
@MrNicNac: It only checks the vertices of a single part for within another part. If the second parts vertices are within the first part, but not within the first parts vertices, it will still return false when it should not.
Report Abuse
MrNicNac is not online. MrNicNac
Joined: 29 Aug 2008
Total Posts: 26567
04 Sep 2013 04:51 PM
Right, I've realized that my code from a few years back is not up-to-par with the point of this thread, but I was asking what he means when the edge detection would work if you simply checked 8 vertices of a part.

The inequality equations allow for complete regions of a box-bound to work.

Now odd shapes would be fun because of how calculus can be applied to making them into smaller shapes.
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 04:51 PM
--[[Made it a bit neater and added a check for if one parts position is identical to the other parts (Likely have horrible efficiency, though D:)]]

local abs = math.abs

local intersect = function(part1, part2)
if part1.Position == part2.Position then
return true
end
for x = -1, 1, 2 do
for y = -1, 1, 2 do
for z = -1, 1, 2 do
local relpos = part2.CFrame:pointToObjectSpace(part1.CFrame * Vector3.new(x, y, z) * part1.Size/2)
if abs(relpos.X) < part1.Size.X/2 and abs(relpos.Y) < part1.Size.Y/2 and abs(relpos.Z) < part1.Size.Z/2 then
return true
end
local relpos2 = part1.CFrame:pointToObjectSpace(part2.CFrame * Vector3.new(x, y, z) * part2.Size/2)
if abs(relpos2.X) < part2.Size.X/2 and abs(relpos2.Y) < part2.Size.Y/2 and abs(relpos2.Z) < part2.Size.Z/2 then
return true
end
end
end
end
return false
end

while wait() do
print(intersect(workspace.Part1, workspace.Part2))
end
Report Abuse
Oysi is not online. Oysi
Joined: 06 Jul 2009
Total Posts: 9058
04 Sep 2013 05:19 PM
[ Content Deleted ]
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
04 Sep 2013 05:22 PM
Soooo.... I take it we COULD get if the edges are intersecting, in oppose to the vertices for a faster script?
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image