(I am re-sending this message - somehow, I got a "disk full error" message from the flashcoders server) --------------
Not sure what you mean by: "How do you tell when a dot has been encircled by a line?" I do not understand why we need to keep track of cycles? What is the relation with your game constraints? I am assuming these are "straight lines", right? ...or can they be of any shape? Essentially what you (seem to) want is simply checking if any line crosses when the user interacts with a dot or a line. In other words, block the user from drawing a line that will cross another one. Just for that, you do not need to keep track of "all the possibilities" in advance... A straight array of dots and lines should be enough for this. ...or I must be missing something. I know that doing an intersection check on a complete graph can be a lengthy task but: Since this an interactive, human-driven game - you can reduce the verification processing by just checking one move at a time. The processing time will be at least linear (e.g. not exponential). So it should not be too too bad - especially if the number of segments should fit on a screen in a human-readable form (< 200 ?). my 0,02$ B. 2006/5/12, Weldon MacDonald <[EMAIL PROTECTED]>:
My first thought was an adjacency list with something to indicate forbidden edges (for a dot inside a cycle), so it might help. The problem isn't that simple though, as more and more moves are made whose in what cycle and can make waht move is a good deal less than clear. On 5/12/06, André Goliath <[EMAIL PROTECTED]> wrote: > FWIW if have written some AS2 classes some time ago that implement a graph > by using adjacenty lists. > If it would help you let me know > > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Weldon > MacDonald > Sent: Thursday, May 11, 2006 2:49 PM > To: Flashcoders mailing list > 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 > _______________________________________________ > Flashcoders@chattyfig.figleaf.com > 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 > > _______________________________________________ > Flashcoders@chattyfig.figleaf.com > 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 _______________________________________________ Flashcoders@chattyfig.figleaf.com 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
_______________________________________________ Flashcoders@chattyfig.figleaf.com 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
