• Content count

  • Joined

  • Last visited

Community Reputation

230 Neutral

About EqualityAssignment

  • Rank
  1. Efficient representation of twists

    I may have sent you on a wild goose chase with braid theory. Sorry about that :(. It sounds like you are saying that that bottom set of lines there--where blue/green twist in steps 3, 4, 7, and 8--that those strings will all slip free in your simulation, so that configuration is basically no tangle at all? If that's what's happening, then your algorithm seems correct to me. I must be misunderstanding something. Actual, physical, strings in that configuration don't slip free: I just took three very thin wires and twisted them together like the green blue and red lines in that bottom plot, then I taped the ends down, and I found that I could not separate the wires without removing the tape. Are the top ends basically free in your simulation, since they are connected to kites, not the ground? Like you can pull the kite through the knot to get it and its string free? I guess then every knot would slip free though ... It's not important that I understand what you are doing though, only that it works for your purposes. So if you are convinced then don't worry about it, the fault is mine and no harm is done :).
  2. Efficient representation of twists

    First, in your blog post, "Multiple twists: {0, 0, 0, -2, 0, 0}" should be "Multiple twists: {0, 0, 0, -3, 0, 0}" shouldn't it? More importantly, I think your normal form isn't right. Let there be three cables, red, green, and blue. Then we have an a length three twist array: {green-red, blue-red, blue-green}. I can make two different braids that both have twist array {2, 0, 2}, but they are not the same. In particular, if you add the same sequence of extra twists to the end, one of them untwists all the way and the other gets twistier. I think that is gonna be a problem for you? Images here: http://imgur.com/a/IDcls x1+x1+x2+x2 and x2+x2+x1+x1. If I understand your idea right, you would call them both {2,0,2}. If you add (-x2-x2-x1-x1) to the end, then only one of them becomes the trivial braid, both you would call both {0,0,0}. I think that will cause problems for you? The normal form defined in that paper doesn't look too much like yours to me. As exhibited above, even the positive word component can't be reduced to {*, *, *} form. That's equivalent to assuming commutativity for twist-addition I think, and commutativity fails. I agree that your twist-array is a braid-invariant, but not a complete one. If the braids are the same they have the same twist-array, but if the twist-arrays are the same that doesn't mean the braids are. You basically proved that in your blog post. The set of twist-arrays has group structure with elementwise addition. The mapping from braid to twist-array is a group homomorphism. You proved this yourself, by showing that the sum of the twist-arrays of two braids is the twist-array of their concatenation, and by showing that the relations xi+xj=xj+xi (if not adjacent) and xi+x(i+1)+xi=x(i+1)+xi+x(i+1) hold for the twist-arrays too. In the paper they use a braid invariant called exp which just counts twists (-1 for one way, +1 for the other), the twist-array is a stronger version of that invariant that counts twists for each pair of cables individually. The normal form they define in the paper expresses every braid as the concatenation of a power of one of the "Garside braids" and a "positive braid", in which every crossing goes in the same direction (CW or CCW). If I am reading the paper right, the Garside braids themselves are positive braids, and in the normal form, the Garside braid always has power <= 0. Basically if you have B = delta^k * T with B a braid, delta a Garside braid, and T a positive word, you can always do B = delta^k * delta^(-1) * delta * T = delta^(k-1) * T' with T' = delta * T a new (larger) positive word. So you can always make the power on delta smaller, but it is bounded above. (Sorry, I just switched from additive to multiplicative notation.) (Finally, The Sage mathematics package can draw braids nicely ... so no more gimp for me :). It's a pain to install though so that doesn't help you.) I guess this still doesn't help you solve your problem. Good discussion though, thanks for bringing this up.
  3. Efficient representation of twists

    I agree. It doesn't help you answer those queries afaik.   But clumping cables by twist shouldn't be on the order of #cables*#twists should it? Assign every cable a color, then for each twist, if the cables have different colors (red, blue), pick one (red), then for every cable if its color is red make it blue. Iterate until no more twists. Each time you replace a color like that, the number of colors falls by 1. When it hits 1, you know every cable is together and you early-out. At the end you arrange the cables into lists by color.   So you can never iterate all the cables more than (#cables - 1) times. Because for each twist, either the cables are the same color and you don't iterate all the cables, or they are different colors and that can only happen (#cables - 1) times.   That's #twists + #cables^2 + some #cables terms for set-up and tear-down right? If #twists is the problem that should be fine?
  4. Efficient representation of twists

    You're talking about braid groups right? Doesn't the standard presentation basically do what you want? For n cables: https://en.wikipedia.org/wiki/Braid_group G = <x1, ..., x(n-1) | xi+xj = xj+xi (|i - j| > 1 or i = j), xi+x(i+1)+xi = x(i+1)+xi+x(i+1) (0 < i < n-1)> x2 means cable 2 goes under cable 3. x2 + x3 means cable 2 goes under cable 3 then cable 3 (which used to be cable 2) goes under cable 4. -x2 means cable 2 goes OVER cable 3. So x2 - x2 = 0. See below: http://imgur.com/a/ix6YP   This numbering is different than yours, watch out for that. Below I encode your examples:   No twists: 0   Simple twist: x1 - x3 = -x3 + x1   Multiple twist: -x2 - x2 - x2   Arbitrary twists: x1 + x2 - x3 + x2 + x1 + x3 = x1 + x2 - x3 + x2 + x3 + x1   Note: x2 - x3 + x2 != -x3 + x2 - x3.   Store the list of numbers (1, 2, -3, 2, 1, -3). It is exactly addition (in a group), when you see the same number and its inverse you just delete both. You can use the relations to rearrange and try to simplify the equation. E.g. ... -x2 + x1 + x2 + x1 - x2 - x1 = -x2 + x2 + x1 + x2 - x2 - x1 = 0   See the other image in that imgur   To query how many twists a particular cable is involved in, you read the string from left to right, keeping track of which position the cable is in, and incrementing by 1 every time it is involved in a twist.   Or, since you always add twists at one end, do the computations to update the twists-per-cable counts every time you add a twist, and never recompute from the beginning.   To group the cables into components, where everything in a component is twisted together (transitively), read from left to right and keep track. Again, you can probably update this computation in real time if you prefer.   It's probably not very satisfying that you can get multiple representations for the same braid, even for the trivial braid, but that's fundamental to the problem. Maybe look into computations with the braid group?
  5. Creating an isometric camera system

    I'm a newbie, but I had a thought: enlarge your viewing frustrum by one tile in every direction, that is, shift the left, right, top, and bottom clipping planes out by one tile's width; then represent a tile by a point at its center; do culling; depth sort; and draw the tiles' sprites with billboarding. Best of luck, will be lurking in thread :).
  6. Puzzle I came up with

    I guess the solution was the culmination of three lines of thought:   [spoiler] "base five is a red-herring"; "maybe I'm supposed to read this symbol in a non-obvious direction"; and "base two makes a lot of sense here".   Lots of trail and error was involved in getting there. At one point, I was even trying to read the thing in a spiral pattern. [/spoiler]
  7. Puzzle I came up with

    slicer4ever solved A, so here's B.   [spoiler] B: Each ring is a five digit number in binary, with each of the five bars in the ring being one digit: the ones place at the 12 o'clock position, counting up clockwise (1s, 2s, 4s, 8s, 16s). The entire symbol is a five digit number in base 32, with each of the five rings being one digit: the ones place in the center, counting up outwards (1s, 32s, 1024s, 32768s, 1048576s). B1: (1 + 2 + 8)*1 + (2 + 4 + 16)*32 + (1 + 2 + 4 + 8)*1024 = 16075 B2: (4 + 8 + 16)*1 + (1 + 2 + 4 + 8 + 16)*32 + (4 + 8)*1024 + (1)*32768 = 47076 B3: (1 + 2 + 4 + 8 + 16)*1 + (1 + 2 + 4 + 8 + 16)*32 + (1 + 2 + 4 + 8 + 16)*1024 + (1 + 2 + 4 + 8 + 16)*32768 = 1048575 B4: (2 + 4 + 8 + 16)*1 + (2 + 4 + 8 + 16)*32 + (2 + 4 + 8 + 16)*1024 + (2 + 4 + 8 + 16)*32768 + (2 + 4 + 8 + 16)*1048576 = 32472030 [/spoiler]   edit: fixed mistype in B4 answer. (Yes, both of us apparently.)
  8. How did 2D games handle this collision in antiquity?

    http://www.gamedev.net/page/resources/_/technical/game-programming/the-guide-to-implementing-2d-platformers-r2936 The links must flow.
  9. In regards to a protagonist's weapon

    Bayonet. You've already got a rifle after all. [url]http://en.wikipedia.org/wiki/File:Combat_knife_attached_to_gun.jpg[/url]
  10. Good online resources to learn C++?

    I've seen "Thinking in C++" recommended in situations like this before. It's a book, but one that has been made available for free by the author. Download available: http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html Probably you can find more lists of resources with an appropriate google search, maybe "site:www.gamedev.net c++ learning online", something like that. I think this is a fairly common question. Best of luck to you! EDIT: Something / some software interaction mangles all my posts, deleting newlines, escaping characters incorrectly, etc.
  11. Might just be my way of seeing things, but........

    As a player, if game programmers can have half the work done for them and put the effort into more and better games, then hell yeah. As a programmer, I don't like implementing stuff repeatedly, and love to have a library take care of that so I can move onto new things. I do tend to do everything on my own the first time through, (partially because I don't know enough about the problem to look for a pre-packaged solution until I start writing code). I'm not entirely sure that's a good thing. If you want to write a game, then as nice as learning about collision detection by implementing it is, it's even nicer to have the game at the end. Plus the collision detection will probably work better that way.
  12. Need some advice on a algorithm building a lookup list

    I did a little reasoning and came up with this formula: distance from tile 1 at (x1, y1) to tile 2 at (x2, y2) assuming all directions have the same movement cost is abs(x2 - x1) + ceiling(abs(y2 - y1) / 2) It worked with the coordinates I tested based on your map. Derived from finding out that: 1. if y1 = y2 then d = abs(x2 - x1) 2. if x1 = x2 then d = ceil(abs(x2 - x1) / 2) and then just guessing that since 2 included one as a subcase, that it might just work for everything. Turned out it seems to have done so. Not sure how that corresponds to clb's post. I suspect if you plug his formula's into the cartesian distance formula you will get my result. I started but got somewhere messy. Might try some more.
  13. How many games are possible in Tictactoe?

    Also the board is symmetric along 4 axii: horizontal, vertical, and 2 diagonals. So you can pick one, flip/mirror the board across it, and thus show half the possible sequences of moves to be duplicates of the other half.
  14. Why Did All My Programs Minimize At Once?

    *blink* ... [I]wut???[/I] I can't find the hard cats OR the long dogs. Google is not the space pipe. I found this: http://www.gamedev.net/topic/546210-it-is-possible-to-write-wow-in-machine-language/ which has this:[url="../../user/62708-mike.popoloski/"][color=#B57438][/color][/url] Mike.Popoloski: Or, as one might ask, how long is a long dog? How hard is a hard cat? These are questions of the universe that may remain a mystery for all time.
  15. [Solved] Vector extrusion

    You just need to displace c1 by w1 in a direction perpendicular to A, then by w2 perpendicular to B. To get a perpendicular vector, swap the components and negate one. There are two perpendiculars, and two components to negate. The combination I used below will shift the point down and right when the distances are positive. Perpendicular vector to A = (-A.y, A.x) to B = (B.y, -B.x) You want to use a perpendicular direction, not a perpendicular vector here, because the length of A and B are inconsequential, its the distances who supply the magnitude of the shift. So normalize those perpendicular vectors. direction perpendicular to A = Vector2(-A.y, A.x).normalized() direction perpendicular to B = Vector2(B.y, -B.x).normalized() Then multiply those unit vectors times the distances, equivalent to creating a new vector with the distance as its magnitude and the direction as its theta. displacement 1 = w1 * Vector2(-A.y, A.x).normalized() displacement 2 = w2 * Vector2(B.y, -B.x).normalized() Then just apply the displacements to c1. c2 = c1 + w1 * Vector2(-A.y, A.x).normalized() + w2 * Vector2(B.y, -B.x).normalized(). The rays emitting from c2 in the way the vectors/rays A and B emit from c1 are just c2 + A and c2 + B. (When a vector is emitting from somewhere, its being rayish.)