HTe guy who asked me for this is a mathematician and his speacilty is graph theory, but he doesn't have a clue. It's looking like keeping track of the cycles will be the problem.
On 5/11/06, Scott Hyndman <[EMAIL PROTECTED]> wrote:
Wow, great question. Needless to say, you can't figure these things out with vertices and edges alone, you're going to have to assign location to each vertex and use that to calculate the intersection...but that's where things get hazy. You probably don't want to brute force it, because your worst case gets bad. I'm sure there is some sort of clever math solution, but I've never been much of a mathematician. So maybe you could do something visual. If your edges are drawn in one color, maybe you could check all the pixels in a line between the desired end points, and see if any of the pixels contain the edge color, in which case, don't allow the connection to be made. I'll keep thinking about it though. Scott -----Original Message----- From: [EMAIL PROTECTED] on behalf of Weldon MacDonald Sent: Thu 5/11/2006 8:48 AM To: Flashcoders mailing list Cc: Subject: [Flashcoders] sprouts data structure I have a request for a game called sprouts. The game starts with a few randomly distributed dots. There is one move and 2 restrictions. Move: draw a line for a dot to itself (a loop) or to another dot. Any line drawn has a new dot on it. Restriction 1: no more than 3 lines from any dot. Restriction 2: no lines can cross. Simple game, but the data structure to keep track of the game and in particular to handle restriction 2 is a bear. How do you tell when a dot has been encircled by a line? The game is, of course based on graph theory, and you can represent a graph in several ways, but how to determine that it remains planar? I haen't begun to think about the visual part of this, if I don't have a reasonable data structure I can't teach a computer to play the game. Any ideas? Hints? Wildly improbable ideas? -- Weldon MacDonald _______________________________________________ [email protected] To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com _______________________________________________ [email protected] To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
-- Weldon MacDonald _______________________________________________ [email protected] To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
