JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums News, Programs & Events Discussions Algorithm Games (Article) Pegs and Rubber Band Game
 Pegs and Rubber Band Game | Reply Hello, I have to make a flash game like this: There is a board with holes in it (more than 1000). Initially, there are 3 pegs placed on the board and a rubber band around them. We have 3 possible operations: 1. Add peg - adds a peg on the board 2. Remove peg - removes a peg ( if there are more than 3 pegs) - the rubber band must take the shape of the remaining pegs. 3. Move peg - rubber band must be updated with current positions of the pegs.How would you solve the problem of finding the rubber band's shape optimally?I have 2 ideeas, but I have to work on them a little bit. The main ideea is that we have to change the rubber band's shape only at "Move" operation, and we use the same number of pegs, only one is changing position: 1.A derivation from convex hull algorithm. We have to know wich pegs are inside the rubber band and wich are outside. It might get a little complicated. 2.We work with only 3 pegs: 2 anchors and 1 middle. The 2 anchors form a boundary line for the interaction of the 1 middle peg. On the active side of the line the rubber band functions as 2 segments between the 2 anchor pegs and the middle peg. On the inactive side the 1 middle peg is free to move while the rubber band functions as a straight line between the 2 anchor pegs. The caveat to the above is that there are cases in which movement of the 1 middle peg in the active side of the boundary line can can cause one of the 2 segments to contact a 4th peg. The program must detect this occurrence and update the new anchor pegs accordingly.Do you have any other ideeas, or suggestions?
 Re: Pegs and Rubber Band Game (response to post by gabitzish0) | Reply The convex hull looks like the way to go here. The convex hull needs to be updated (recomputed) only in the following cases:* A peg is added to the outside of the current hull* A peg is removed from the boundary of the current hull* A peg is moved from the inside of the current hull to its outsideYou can check whether a point is inside/outside/boundary of the hull by using the solution to PointInPolygon: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry3
 Re: Pegs and Rubber Band Game (response to post by dimkadimon) | Reply No, I think you didn't understood the problem. The rubber band's shape changes when a peg is moved from outside to inside. So we don't actually need the convex hull, but something derivated from it. The band can have the shape of a star (for example), where 5 pegs are stretching the band from inside to outside, and 5 pegs from outside to inside.I think the second approach that i've posted in the thread it's better.
 Forums News, Programs & Events Discussions Algorithm Games (Article) Pegs and Rubber Band Game Previous Thread  |  Next Thread