The reqiurement is that the software be able to play the game, so I need a data structure to store the game position for analysis. The intersection check is moot until I can store the current state of the game, update it, and analyze the potential moves. If moves are made that create a cycle, then the possibility of a vertex, or even a subgraph, being contained by that cycle exists, which removes the possibility of edges to a vertex outside the cycle, but not to the vertexes in the cycle. That would have to be incorperated into the data structure. I think the adjacency list might store the position, but then the AI for the game will be very tough to do. As for the intersection check this will work to prevent an illegal move, but the tougher part will be making the computer move if the best move is a line that loops around other vertices. Or maybe I should forget programming and try my hand at cartooning!
On 5/12/06, Bernard Poulin <[EMAIL PROTECTED]> wrote:
(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 > > _______________________________________________ > > [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 > _______________________________________________ [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
