JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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 outside

You 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.
RSS