Do geometry calculations #51

Closed
nwinter opened this Issue Jan 3, 2014 · 41 comments

Projects

None yet

8 participants

@nwinter
Contributor
nwinter commented Jan 3, 2014

Various parts of the game engine "rely" on being able to tell whether Thangs contain or intersect each other, or how far away their nearest edges are. Thangs are either ellipses or rectangles, and may be rotated.

I haven't actually finished the geometry calculations to determine most of the rectangle-rectangle, rectangle-ellipse, or ellipse-ellipse distances, intersections, or containment, especially with rotation.

So currently most of the calculations which would depend on those are hacked around--instead of Thangs being able to collect or melee attack each other if they're touching, instead they can do so if their center points are closer than their attackRange or collectRange or whatever silly nonsense property I have. This is fiddly and not good.

Since this is so CodeCombat-agnostic as to not require figuring out good test cases within the game engine itself, I've pulled out the relevant code into a Codepen so it'll be easy to play with:

screenshot 2014-01-02 16 34 41

http://codepen.io/nwinter/pen/itsgx

Update--Julia has made some progress here: http://codepen.io/julenka/pen/DkEtb

Fork that, have fun, and do however much you want to do toward:

  1. Getting my simple tests at the bottom to work by calculating distances from edges instead of centers
  2. Adding more tests to make sure
  3. Making it work with rotation
  4. Filling in methods like Thang.intersects and Thang.contains in addition to Thang.distance.

It might be helpful to also add a simple graphics layer that draws the shapes you're working with in Thang's toString() method (before it returns the string).

Or if one prefers, they can hack on the Vector and Rectangle code in the repo itself, with some of it being in the physics.Physical Component in the level editor. Adding tests to our testing system would be pretty sweet, too.

@zachster01
Contributor

Just a heads-up that I'm working on this problem if anyone wants to collaborate. I'm looking to incorporate SAT ( Separating Axis Theorem ) for the Thang.intersects method and maybe Voronoi Regions for the Thang.distance method. I'm open to suggestions though!

@twoducky

@zachster01 I'd like to work with you on this. I'm new to github and to programming for video games, but I'm a quick study. Let me know how I can help. :)

@zachster01
Contributor

@twoducky That sounds terrific! I'm finishing up some school work over the weekend, but I'll try to be free in a few hours if you want to coordinate. I'll message you so we can work on what our plan of attack will be. Welcome to the team!

@zachster01
Contributor

@twoducky My apologies. It looks like there isn't a private messaging system for github. If you'd like to coordinate via email, feel free to message me at zachster01(at)gmail.com. Just replace the (at) with the @ symbol (I'm not sure if there are any bots that crawl these message boards looking for email addresses).

@yangshun
Contributor

@zachster01 what's your progress on this? I have actually implemented a physics engine before and my experience can come in useful here. Seems like a collision module of the physics engine is required.

@nwinter
Contributor
nwinter commented Feb 26, 2014

@bnosrat is also working on this now. How's it going?

@bahador
bahador commented Feb 26, 2014

@nwinter I've finished contains() and am a case and a half away from finishing intersects(). I'll be moving on to distance() soon, but it'll have to wait until next week because I had to make last minute plans to go out of town from Thursday until Sunday. This issue is more hand written math to figure out all of the necessary quadratics than it is actual coding, but it's necessary to make sure the equations are right.

@nwinter
Contributor
nwinter commented Feb 26, 2014

@bnosrat could you post your code somewhere, maybe on a Codepen? Might be interesting to split this up and let some others collaborate / look at some parts of it.

@zachster01
Contributor

@yangshun Sorry for the lack of updates, I was promoted at work for the new systems migration that's going underway and have been working 50-60 hour weeks on top of going to school full-time. I hope that things will die down soon, but if you want to work with @bnosrat and @twoducky, it looks like they'll be able to help more. For now I'm probably going to bow out until things die down. I look forward to coming back in the near future!

@yangshun
Contributor

@bnosrat could you show us what you have so far? If you don't mind I would like to work with you on it.

@bahador
bahador commented Feb 28, 2014

I have limited computer/internet access until next week, but here's the working code for ellipse.contains(thang): http://codepen.io/anon/pen/fAxuH
If I manage to finish thang.intersects(thang) by Sunday, I'll post it up asap.
If not, both intersects and distance will have to wait until next week.

@bahador
bahador commented Mar 1, 2014

I've added intersects. Distance is next, but it'll have to wait until next week. Please play around with what I've got and let me know if you notice any errors.

Post Script: I wrote the code differently (ie more clearly and cleanly) locally, but just did a messy copy/pasta to put it into the pen. In the pen's current form, it could and should be refactored. But I'll worry about all that at the end...

Post Script v2: I just realized I only did the ellipse vs rectangle case for intersects. I still have to do rectangle vs rectangle and ellipse vs ellipse.

@bahador
bahador commented Mar 4, 2014

@nwinter @yangshun either of you had time to look at my code? im just looking for a little input. im aiming to have rectangle-rectangle intersection done today and ellipse-ellipse intersection done by tomorrow, and then i can move to distance. fyi all of these include rotation and off-origin centers. and just as before, ill refactor when its all done.

questions: the previous contains code returned false for points that fall on vertices. is this right? my code does this as well, but i can change it if falling on vertices should return true when calling the contains method. id also like to know the same for intersects as well. all things being equal, i think both should return true if a point falls on a vertex, although more so for intersects than contains.

@nwinter
Contributor
nwinter commented Mar 4, 2014

I checked out the posted Codepen and it seems like it's the earlier version where Ellipse contains is done, but I don't see intersects. Is there a new pen link?

@Snipx
Snipx commented Mar 5, 2014

@nwinter Hey Nick, I was checking upon this issue and it seems to me pretty messy for now. I can see at least 4 links to CodePen with different states of work done and I can't see any commits related to this issue. Maybe it makes sense to introduce a little bit of structure to this topic?

Anyway, I feel confident about the subject of the issue, so I gues I would be able to help out. Please, hint me with something to start from not to inrersect with other guys.

@bahador
bahador commented Mar 5, 2014

@Snipx I did contains with rotation for all cases and I'm almost done doing intersects with rotation for all cases. You can try distance if you like?

@Snipx
Snipx commented Mar 5, 2014

@bnosrat All right, to split this up, I will start from rectangle-rectangle distance.

@nwinter
Contributor
nwinter commented Mar 5, 2014

The reason that there aren't commits related to this, and that the code is worked on on Codepen, is because the code really lives inside the physics.Physical Components, and we don't yet have more than very basic version control and permissions on those. #264 would help there.

@bahador
bahador commented Mar 6, 2014

@nwinter @yangshun I updated my codepen (http://codepen.io/anon/pen/fAxuH) and now it includes contains with rotation for all cases, and intersects with rotation for rectangle-rectangle and ellipse-rectangle. I'm working on intersects with rotation for ellipse-ellipse now.

@Snipx How is distance going?

edit: My codepen needs refactoring and comments. I'll do that at the end.

@bahador
bahador commented Mar 7, 2014

@nwinter I'm having trouble with ellipse-ellipse intersection. It's been too long since linear algebra and differential equations, so I don't remember enough of it. This link was helping me out, but I'm not sure what to do (http://yehar.com/blog/?p=2926).

edit: The source code is at the bottom. I'll port it over from processing to CoffeeScript tomorrow.

@Snipx
Snipx commented Mar 7, 2014

@bnosrat I'm still in process of implementing rectangle-rectangle distance. Hope to finish soon :)

@nwinter
Contributor
nwinter commented Mar 7, 2014

@bnosrat Wow, no wonder I wasn't able to just figure out ellipse-ellipse intersection when I was doing the first pass here–that's looking kind of hairy. Is there a simpler method that we could use that would be imperfect but close enough?

@bahador
bahador commented Mar 7, 2014

@nwinter Here are two options I can think of:

Option 1: Break the ellipses down into a polygon using some sort of predetermined scheme (eg calculate one hundred steps from min x to max x, then calculate the y values for each step, and connect the points to make a polygon) and then do line-line intersection. Although it will be many operations, each operation is quick. Regardless, this may not be the smartest way. I'm just giving an example.

Option 2: Port the Processing code that guy used in the link I provided into CoffeeScript. This is what I'm most likely going to try first.

@Snipx
Snipx commented Mar 8, 2014

So, I have some results in implementing rectangle-rectangle distance, please, check it out:
http://codepen.io/Snipx/pen/renHw

I have added Line and Segment helper "classes", in order for these symbols to at least resemble programming code :)

@nwinter
Contributor
nwinter commented Mar 8, 2014

@bnosrat Speed is pretty important here, so that first option doesn't sound totally amazing, but maybe if we used something coarse like 8 steps, it would be close enough. Is that second hairy example going to be faster?

@Snipx Looking good! Want to add some more test cases? If we get a good number of tests, it will be a lot easier for me to integrate everything and be sure I haven't broken it, and then we can optimize performance with confidence, too.

@Snipx
Snipx commented Mar 8, 2014

@nwinter I have reforked the last @bnosrat's pen in order to use the latest intersects and contains function(if one rectangle contains other or intersects with it then I think the distance is zero).
I also added some new tests to cover almost all cases, I suppose. Feel free to ask me for some more if necessary.
So the current link is http://codepen.io/Snipx/pen/BuLzw
However, I came across a strange thing during debugging and testing my implementation.

See the following lines in the link above:

rect1 = new Thang({x: 0, y: 0}, 8, 2, 0, "box", Math.PI / 100);
log(rect1.rectangle().vertices())
rect2 = new Thang({x: 0, y: 8}, 8, 2, 0, "box", Math.PI / 100);
log(rect2.rectangle().vertices())
log(rect1.intersects(rect2))

.intersects returns true, which is a surprising fact for me and therefore my distance function returns 0, of course.
@bnosrat could you look at that piece of code?
Sorry if I am wrong, it's too late in my place, but I guess these rectangles are at too different heights from each other and cannot intersect

@bahador
bahador commented Mar 11, 2014

@nwinter Sorry, I mentioned it previously but probably forgot to notify you. Intersects returns true if it falls on a vertex. I can change it to return false in these cases. I believe contains already returns false in these cases. Also worth mentioning, I've been busy moving motorcycles and equipment for the past several days. The motorcycle shop I do coding work for, and where I work on my bikes and store my projects, lost their lease this month, so I have to move a lot of things. I hope to be done moving by the end of the week so that I can get back to programming.

@bahador
bahador commented Mar 17, 2014

@nwinter I believe I fixed it. It was a case that one of my if statements was not conditional enough to catch, but I believe I catch all cases now.

http://codepen.io/anon/pen/fAxuH

I still have not made any progress on ellipse-ellipse intersection. Life is just a mile a minute...

@nwinter
Contributor
nwinter commented Mar 17, 2014

Ah, great! So correct me if I'm wrong, but is the only case remaining to be handled just this thorny ellipse-ellipse intersection?

@bahador
bahador commented Mar 17, 2014

@nwinter Yes. I did all cases for contains, and this wraps up all cases intersection except for ellipse-ellipse. I think somebody else was working on distance. I'm going to refactor and comment my pen right now.

@bahador
bahador commented Mar 17, 2014

@nwinter Ok I refactored it a bit and added comments. I hope it all makes sense now to anybody that reads it. Here is a brief rundown:

  • [Class: LineSegment] Convenience class for line and line segment geometry
  • [Class: Ellipse] Ellipse equivalent of Rectangle
  • [Method: Rectangle.lineSegments()] Returns an array of 4 LineSegments
  • Rectangle contains point with and without rotation
  • Ellipse contains point with and without rotation
  • Rectangle-Rectangle intersection with and without rotation
  • Ellipse-Rectangle intersection with and without rotation
  • A bunch of tests in the form of log statements (I have the Mocha equivalents)
@nwinter
Contributor
nwinter commented Mar 28, 2014

Sorry @bnosrat, it's proving to be a bit tricky to find a big batch of time to get this integrated into the system, since the major version change to the Physical Component needs to be very well tested, it being the first major version change that we have done so far–not all the versioning system is built for it. I'm on the lookout for a long block of time where I can really focus on merging and testing it.

@bahador
bahador commented Mar 29, 2014

no worries. i've sort of been exploring new technologies on my own. i just
bought a domain and started development on my own site/app in node with
express and angular that i deployed on heroku, just because i wanted to
expose myself to new [to me] technologies. i just finished making all of
the front end technologies i want to work with work well together. i'll be
spending the rest of the weekend making a landing page, and then i'll be
moving on to back end technologies like passport, mongoose, and connect.
afterwards i plan on playing with scala/akka and/or shark/spark on aws ec2.

You can't teach a hammer to love nails.

On 27 March 2014 17:23, Nick Winter notifications@github.com wrote:

Sorry @bnosrat https://github.com/bnosrat, it's proving to be a bit
tricky to find a big batch of time to get this integrated into the system,
since the major version change to the Physical Component needs to be very
well tested, it being the first major version change that we have done so
far-not all the versioning system is built for it. I'm on the lookout for a
long block of time where I can really focus on merging and testing it.

Reply to this email directly or view it on GitHubhttps://github.com/codecombat/codecombat/issues/51#issuecomment-38877204
.

@GlenDC
Contributor
GlenDC commented Apr 4, 2014

Hi Bnosrat. How is the progress going on this issue? Did you manage to find some time to work on some of your ideas?

@bahador
bahador commented Apr 7, 2014

I've effectively stopped working on this issue. I got it as far as I could
with tests covering most cases I could think of proving my code works (as
far as I can tell). I finished all cases for contains and all cases for
intersects except for ellipse-ellipse. Somebody else was working on
distance.

You can't teach a hammer to love nails.

On 4 April 2014 13:36, Glen De Cauwsemaecker notifications@github.comwrote:

Hi Bnosrat. How is the progress going on this issue? Did you manage to
find some time to work on some of your ideas?


Reply to this email directly or view it on GitHubhttps://github.com/codecombat/codecombat/issues/51#issuecomment-39608571
.

@nwinter nwinter added a commit that referenced this issue Jul 16, 2014
@nwinter nwinter Merged in geometry work from #51. 42af807
@nwinter
Contributor
nwinter commented Jul 16, 2014

Thanks for everyone's work on this, especially Julia, @bnosrat, and @Snipx. I've finally had a day to merge everything together, complete the refactoring, add tests, and migrate all the levels to take the new distance calculation methods into account. Everything can happen in the main repo now instead of Codepen.

There are a few TODOs left in ellipse.coffee and rectangle.coffee where ellipse-related distance and ellipse-ellipse intersection methods haven't been implemented yet. If anyone wants to take a crack at those, that's the last thing we need before we can close this. Probably translating the code from this blog post for the ellipse-ellipse intersection case would be the way to go there. @schmatz expressed interest today, but it's up for grabs.

To work on it, just add test cases to ellipse.spec.coffee, then open /test/lib/world and try to make them pass.

@coder0xff
Contributor

After doing quite a bit of digging and maths, the few remaining methods might not be worth it to implement if the current approximations are "good enough." In specific, there's no practical analytic solution to those problems, so root finding or some other iterative approximation is necessary. While certainly doable, the cost of computation is high (at least in comparison to the other geometry tests). If there's enough desire for them still, I'll implement them and you can decide if/when to use them.

@nwinter
Contributor
nwinter commented Feb 24, 2015

Let's call it done, then! Nice work, everyone.

@nwinter nwinter closed this Feb 24, 2015
@bahador
bahador commented Feb 24, 2015

huzzah!

@coder0xff
Contributor

Seems I spoke to soon. I believe I've found an analytic solution.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment