Loading ...
Sorry, an error occurred while loading the content.

[XP] Re: The ant algorithm

Expand Messages
  • William Tozier
    ... Langton s. Chris Langton, coiner of the term artificial life , editor of the first Artificial Life workshop proceedings, and researcher at the Swarm
    Message 1 of 22 , Aug 1, 2001
    • 0 Attachment
      >Search the Internet for "Langston's Ant". You'll find lots.

      Langton's. Chris Langton, coiner of the term "artificial life",
      editor of the first Artificial Life workshop proceedings, and
      researcher at the Swarm Corporation and the Sante Fe Institute. That
      particular ant algorithm is a simple example of a two-dimensional
      Turing Machine, and has been written up in Scientific American (as I
      recall).

      (mine that paragraph for more keywords)

      ((I used to be the principal editor at Artificial Life Online))
      --
      William Tozier
      bill@...

      "The only normal people are the ones you don't know very well."
      -- Joe Ancis
    • C. Keith Ray
      ... Do y all have unit tests for it? ... C. Keith Ray
      Message 2 of 22 , Aug 3, 2001
      • 0 Attachment
        > From: grenning@...
        >
        >I just uploaded the ant program done by Bob Martin and I in the
        >Raleigh Airport bar while waiting for our plane.
        >
        >The GUI is slow and flickers, but the ant is doing his thing. You
        >have to let it run for a few minutes until something interesting
        >happens.

        > From: wecaputo@...
        >
        > Eric Meade:
        >>Sorry I don't have the code, I just did some consultation on getting
        >>the Java UI stuff to work. The others folks are on this list,
        >>perhaps one of them will comply with your request.
        >
        > I have the C++ version. If I get a chance I will upload it.

        Do y'all have unit tests for it?

        ----

        C. Keith Ray
        <http://homepage.mac.com/keithray/resume.html>
      • William Tozier
        ... Not to put too fine a point on it, but determining whether the ant algorithm will reach a particular configuration is provably NP-hard. Thus this thread
        Message 3 of 22 , Aug 3, 2001
        • 0 Attachment
          > >>Sorry I don't have the code, I just did some consultation on getting
          >>>the Java UI stuff to work. The others folks are on this list,
          >>>perhaps one of them will comply with your request.
          >>
          >> I have the C++ version. If I get a chance I will upload it.
          >
          >Do y'all have unit tests for it?

          Not to put too fine a point on it, but determining whether the ant
          algorithm will reach a particular configuration is provably NP-hard.

          Thus this thread may yet be transformed into something useful:
          (a) the 2-d Turing algorithm is deterministic
          (b) and is very simple
          (c) the patterns generated by the algorithm are extremely complex and
          show (on average) exponential divergence from slightly different
          initial conditions
          (d) at the same time, it's quite possible to generate identical
          patterns, and even identical patterns+ant states, from entirely
          different starting conditions.

          Therefore,
          To write an AT for Langton's Ant algorithm, would you test the
          patterns generated from known starting points and "hope" that you
          haven't seen a false positive by reaching the "passing" state through
          a different trajectory?

          The question of testing research-level (read "complex") systems is
          still an open question on this list, as I recall. Might not be a bad
          time to re-instatiate it.
          --
          William Tozier
          bill@...

          "The only normal people are the ones you don't know very well."
          -- Joe Ancis
        • Ron Jeffries
          It seems to me that for the ant, whose rules are trivial, a very simple acceptance test will clearly suffice. Why might it not? R ... Ron Jeffries
          Message 4 of 22 , Aug 3, 2001
          • 0 Attachment
            It seems to me that for the ant, whose rules are trivial, a very simple
            acceptance test will clearly suffice. Why might it not?

            R

            Responding to William Tozier (12:06 PM 8/3/2001 -0400):
            > > >>Sorry I don't have the code, I just did some consultation on getting
            > >>>the Java UI stuff to work. The others folks are on this list,
            > >>>perhaps one of them will comply with your request.
            > >>
            > >> I have the C++ version. If I get a chance I will upload it.
            > >
            > >Do y'all have unit tests for it?
            >
            >Not to put too fine a point on it, but determining whether the ant
            >algorithm will reach a particular configuration is provably NP-hard.
            >
            >Thus this thread may yet be transformed into something useful:
            >(a) the 2-d Turing algorithm is deterministic
            >(b) and is very simple
            >(c) the patterns generated by the algorithm are extremely complex and
            >show (on average) exponential divergence from slightly different
            >initial conditions
            >(d) at the same time, it's quite possible to generate identical
            >patterns, and even identical patterns+ant states, from entirely
            >different starting conditions.
            >
            >Therefore,
            >To write an AT for Langton's Ant algorithm, would you test the
            >patterns generated from known starting points and "hope" that you
            >haven't seen a false positive by reaching the "passing" state through
            >a different trajectory?
            >
            >The question of testing research-level (read "complex") systems is
            >still an open question on this list, as I recall. Might not be a bad
            >time to re-instatiate it.
            >--
            >William Tozier
            >bill@...
            >
            >"The only normal people are the ones you don't know very well."
            > -- Joe Ancis
            >
            >To Post a message, send it to: extremeprogramming@...
            >
            >To Unsubscribe, send a blank message to:
            >extremeprogramming-unsubscribe@...
            >
            >Don't miss XP UNIVERSE, the first US conference on XP and Agile
            >Methods. see www.xpuniverse.com for details and registration.
            >
            >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
            >


            Ron Jeffries
            www.XProgramming.com
            The practices are not the knowing. They are a path to the knowing.
          • Ron Jeffries
            Here is the ant program in StarLogo. (Probably would be much the same in Logo, but I don t remember Logo that well.) `turtle` to setup setcolor red setxy 0 0
            Message 5 of 22 , Aug 3, 2001
            • 0 Attachment
              Here is the ant program in StarLogo. (Probably would be much the same in
              Logo, but I don't remember Logo that well.)

              `turtle`
              to setup
              setcolor red
              setxy 0 0
              end

              to go
              forward 1
              ifelse patchcolor = black
              [stamp color
              right 90]
              [stamp black
              left 90]
              end


              `observer`
              to setup
              clear-all
              create-turtles 1
              ask-turtles [setup]
              end

              Howzat?

              Ron Jeffries
              www.XProgramming.com
              The practices are not the knowing. They are a path to the knowing.
            • Robert Sartin
              ... Those don t sound like unit tests. I would write unit tests that were much smaller in scale. Test that the ant does the right thing to one pixel and moves
              Message 6 of 22 , Aug 3, 2001
              • 0 Attachment
                --- William Tozier <bill@...> wrote:
                > Not to put too fine a point on it, but determining whether the ant
                > algorithm will reach a particular configuration is provably NP-hard.

                Those don't sound like unit tests.

                I would write unit tests that were much smaller in scale. Test that the
                ant does the right thing to one pixel and moves to the correct next
                pixel. Test that the object storing pixel values stores them correctly.
                For both kinds of test, define behavior for going off the edge. Seems
                pretty straightforward.

                Testing that the ant works using the implied suggested unit test would
                be like unit testing a bookkeeping system by giving it 10 years of data
                and making sure the ending account balances were correct.

                Regards,

                Rob


                __________________________________________________
                Do You Yahoo!?
                Make international calls for as low as $.04/minute with Yahoo! Messenger
                http://phonecard.yahoo.com/
              • wecaputo@thoughtworks.com
                ... Of course :-) The whole point of the exercise was: a)To practice test-first and pair programming b)To kill the many hours of United flight delays. It
                Message 7 of 22 , Aug 3, 2001
                • 0 Attachment
                  >> I have the C++ version. If I get a chance I will upload it.

                  >Do y'all have unit tests for it?

                  Of course :-)

                  The whole point of the exercise was:
                  a)To practice test-first and pair programming
                  b)To kill the many hours of United flight delays.

                  It worked on both counts.
                • Matthew Davis
                  ... NP-hard. ... I think Mr. Tozier is talking about Acceptance Tests. Here are some ideas: Write ATs with simple setups that you can figure by hand. Log the
                  Message 8 of 22 , Aug 3, 2001
                  • 0 Attachment
                    --- In extremeprogramming@y..., Robert Sartin <sartin@a...> wrote:
                    > --- William Tozier <bill@w...> wrote:
                    > > Not to put too fine a point on it, but determining whether the ant
                    > > algorithm will reach a particular configuration is provably
                    NP-hard.
                    >
                    > Those don't sound like unit tests.

                    I think Mr. Tozier is talking about Acceptance Tests.

                    Here are some ideas:

                    Write ATs with simple setups that you can figure by hand. Log the
                    ant's progress, and compare that log to a hand-generated log.
                    Considering there are really only two things the ant can do, ten or
                    twenty steps should suffice.

                    For large tests, you might trust that the answer is correct and just
                    want to verify performance and resource use.

                    Also, run 2 or 3 longer tests from known starting positions, and
                    record the ending position. Write ATs that verify this, not because
                    it necessarily demonsrates "correctness", but because it will catch
                    any accidental change in behavior later.

                    -Matthew
                    azami@...
                  • wecaputo@thoughtworks.com
                    ... In true XP fashion we did not do this. (note too that the question was about unit tests) We wrote test first to get the three rule implemented. We looked
                    Message 9 of 22 , Aug 3, 2001
                    • 0 Attachment
                      Bill Tozier:
                      >Therefore,
                      >To write an AT for Langton's Ant algorithm, would you test the
                      >patterns generated from known starting points and "hope" that you
                      >haven't seen a false positive by reaching the "passing" state through
                      >a different trajectory?

                      In true XP fashion we did not do this. (note too that the question was
                      about unit tests)

                      We wrote test first to get the three rule implemented. We looked at the
                      screen and said "yup that looks good -- its running too fast to be sure
                      though." Test-firsted in a delay loop, slowed it down, watched it for a
                      while, and could verify that it was doing what the rules said it should.

                      Not proven correct in any theoretical sense, but worked the same way that
                      Kent's did, and that is all we were after.

                      And then we moved on to something else. In fact, I am playing with sockets
                      right now, and we were talking about rolling the two together -- place worm
                      holes on the screen, and if the ant hits one, send its state through a
                      socket connection to another console, and have it start there until it hits
                      another one. Might work on that this weekend.

                      Best,
                      Bill
                    • Ron Jeffries
                      I need a really easy way to write graphics to a Windows screen from Ruby. Anyone got one of those? R ... Ron Jeffries www.XProgramming.com The practices are
                      Message 10 of 22 , Aug 3, 2001
                      • 0 Attachment
                        I need a really easy way to write graphics to a Windows screen from Ruby.
                        Anyone got one of those?

                        R

                        Responding to wecaputo@... (01:34 PM 8/3/2001 -0500):

                        >Bill Tozier:
                        > >Therefore,
                        > >To write an AT for Langton's Ant algorithm, would you test the
                        > >patterns generated from known starting points and "hope" that you
                        > >haven't seen a false positive by reaching the "passing" state through
                        > >a different trajectory?
                        >
                        >In true XP fashion we did not do this. (note too that the question was
                        >about unit tests)
                        >
                        >We wrote test first to get the three rule implemented. We looked at the
                        >screen and said "yup that looks good -- its running too fast to be sure
                        >though." Test-firsted in a delay loop, slowed it down, watched it for a
                        >while, and could verify that it was doing what the rules said it should.
                        >
                        >Not proven correct in any theoretical sense, but worked the same way that
                        >Kent's did, and that is all we were after.
                        >
                        >And then we moved on to something else. In fact, I am playing with sockets
                        >right now, and we were talking about rolling the two together -- place worm
                        >holes on the screen, and if the ant hits one, send its state through a
                        >socket connection to another console, and have it start there until it hits
                        >another one. Might work on that this weekend.
                        >
                        >Best,
                        >Bill
                        >
                        >
                        >
                        >
                        >
                        >
                        >To Post a message, send it to: extremeprogramming@...
                        >
                        >To Unsubscribe, send a blank message to:
                        >extremeprogramming-unsubscribe@...
                        >
                        >Don't miss XP UNIVERSE, the first US conference on XP and Agile
                        >Methods. see www.xpuniverse.com for details and registration.
                        >
                        >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
                        >


                        Ron Jeffries
                        www.XProgramming.com
                        The practices are not the knowing. They are a path to the knowing.
                      • bill@williamtozier.com
                        ... Sorry -- I shifted the thread somewhat, and was in fact speaking of Acceptance Tests. Best, Bill Tozier
                        Message 11 of 22 , Aug 3, 2001
                        • 0 Attachment
                          --- In extremeprogramming@y..., Robert Sartin <sartin@a...> wrote:
                          >
                          > --- William Tozier <bill@w...> wrote:
                          > > Not to put too fine a point on it, but determining whether the ant
                          > > algorithm will reach a particular configuration is provably NP-hard.
                          >
                          > Those don't sound like unit tests.

                          Sorry -- I shifted the thread somewhat, and was in fact speaking of Acceptance
                          Tests.

                          Best,
                          Bill Tozier
                        • bill@williamtozier.com
                          ... website for this posting]Perhaps you re right -- since there are only two colors of block, four dire= ctions it can be facing, and one deterministic
                          Message 12 of 22 , Aug 3, 2001
                          • 0 Attachment
                            --- In extremeprogramming@y..., Ron Jeffries <ronjeffries@a...> wrote:
                            > It seems to me that for the ant, whose rules are trivial, a very simple
                            > acceptance test will clearly suffice. Why might it not?

                            [forgive any errors or out-of-thread reasoning, since I'm forced to use the=
                            website
                            for this posting]

                            Perhaps you're right -- since there are only two colors of block, four dire=
                            ctions it
                            can be facing, and one deterministic output of color change and movement fo=
                            r
                            each of these 8 (actually two, given rotational symmetry) input combination=
                            s. I
                            stand corrected.

                            But as I recall you and I were in a situation not too many months ago where=
                            the
                            subject at hand was probabilistic, not deterministic, and the idea of writi=
                            ng
                            acceptance and even unit tests was discussed at length. I'm not sure a cons=
                            ensus
                            was ever reached.

                            Suppose we change the problem just a tad, and make the behavior of the ant =

                            probabilistic. (If one were to do this -- and afterwards go through the rig=
                            ht
                            nomenclatural and analytical gyrations -- it would be reasonable to expect =
                            that the
                            result could be published in the physics literature in an instant, adding a=
                            n
                            interesting line one's resumé). Say it has a probability p of doing what th=
                            e
                            deterministic ant would have done, and a probability (1-p) of moving forwar=
                            d one
                            block with no change to the lattice colors. Or maybe it will do the opposit=
                            e of
                            what the deterministic ant would have done with probability (1-p). Or it mo=
                            ves
                            forward a number of steps decided according to a Bernoulli distribution. &c=
                            &c. All
                            viable publications that somebody with too many United miles might want to =

                            undertake.

                            What do we do to write the acceptance test for any of these untrustworthy a=
                            nts?

                            Best,
                            Bill
                          • David Stagner
                            bill@williamtozier.com wrote: [random stuff snipped] ... Pull the probability-generating algorithm out to be tested separately. Hopefully, it can run quickly.
                            Message 13 of 22 , Aug 3, 2001
                            • 0 Attachment
                              bill@... wrote:
                              [random stuff snipped]
                              >
                              > What do we do to write the acceptance test for any of these untrustworthy a=
                              > nts?

                              Pull the probability-generating algorithm out to be tested separately.
                              Hopefully, it can run quickly. Determine the level of statistical
                              accuracy required, and write a unit test that runs the method some
                              sufficiently large n times, and analyzes the results to +/- required
                              accuracy. If the accuracy is up in the 3 or 4 9's range, it is unlikely
                              to accidentally fail a unit test, right?

                              Now write a mock object to replace the probability engine, and plug that
                              into the ant movement. Ant movement is then deterministic, and can be
                              unit tested using ordinary means.

                              In other words, refactor to make sure the ant's legs aren't too tightly
                              coupled to its brain.
                              --

                              David Stagner

                              National Marrow Donor Program
                              3001 Broadway Street NE
                              Broadway Ridge Suite 500
                              Minneapolis, MN 55413

                              Email: dstagner@...
                            • Robert Sartin
                              ... Got it. Same comments apply in variation: NP-hard doesn t mean unsolveable. For a given small instance of the problem, the end state may be known. For any
                              Message 14 of 22 , Aug 3, 2001
                              • 0 Attachment
                                --- bill@... wrote:
                                > --- In extremeprogramming@y..., Robert Sartin <sartin@a...> wrote:
                                > >
                                > > --- William Tozier <bill@w...> wrote:
                                > > > Not to put too fine a point on it, but determining whether the
                                > ant
                                > > > algorithm will reach a particular configuration is provably
                                > NP-hard.
                                > >
                                > > Those don't sound like unit tests.
                                >
                                > Sorry -- I shifted the thread somewhat, and was in fact speaking of
                                > Acceptance Tests.

                                Got it.

                                Same comments apply in variation:

                                NP-hard doesn't mean unsolveable. For a given small instance of the
                                problem, the end state may be known. For any reasonable-sized instance
                                of the problem it is polynomial order to figure out the expected state
                                after N iterations.

                                Is this problem really NP-hard or is it a variation of the halting
                                problem? Although the halting problem is, in general, unsolvable, many
                                instances of the problem have defined solutions. Again, some versions
                                of the problem will have known end states that aren't too bad to
                                calculate, and all versions of the problem have known state after N
                                steps.

                                The ATs for the bookkeeping system would be made of a number of small
                                sets of entries with known end results, and possibly intermediate
                                states or actions. The ATs for LA should include some initial states
                                that have a known end state (if any such exist and are known) and some
                                initial states for which intermediate states at various number of steps
                                are known. Of course, you'll want to check the GUI, too; see all of the
                                threads here on GUI ATs.

                                Regards,

                                Rob


                                __________________________________________________
                                Do You Yahoo!?
                                Make international calls for as low as $.04/minute with Yahoo! Messenger
                                http://phonecard.yahoo.com/
                              • Ron Jeffries
                                ... Well, let s see. I m designing ahead here, in a speculative way, just so as to be able to talk about the future. The ants might be written with an embedded
                                Message 15 of 22 , Aug 3, 2001
                                • 0 Attachment
                                  Responding to bill@... (08:47 PM 8/3/2001 +0000):
                                  >What do we do to write the acceptance test for any of these untrustworthy
                                  >ants?

                                  Well, let's see. I'm designing ahead here, in a speculative way, just so as
                                  to be able to talk about the future.

                                  The ants might be written with an embedded Strategy object, each of which
                                  implemented exactly one of the behaviors you mentioned (going straight,
                                  reversing the behavior of another strategy, and so on).

                                  Those objects are all easy to UNIT test, in the standard and obvious way.
                                  Similarly, it is easy to test the plugability of the Strategy based on the
                                  random dice roll. It is hard, however, to test the random number generator.
                                  Fortunately, you didn't ask about that.

                                  Now then, to acceptance test a particular ant, is it sufficient to prepare
                                  a sequence of "random" numbers for him, hand-calculate what he should do,
                                  then create an ant with that sequence in his random number generator, and
                                  see that he does it?

                                  What concerns might we be left with?

                                  Ron Jeffries
                                  www.XProgramming.com
                                  The practices are not the knowing. They are a path to the knowing.
                                • Ron Jeffries
                                  You expressed this much more clearly than I did. Thanks! ... Ron Jeffries www.XProgramming.com The practices are not the knowing. They are a path to the
                                  Message 16 of 22 , Aug 3, 2001
                                  • 0 Attachment
                                    You expressed this much more clearly than I did. Thanks!

                                    Responding to David Stagner (03:54 PM 8/3/2001 -0500):
                                    >bill@... wrote:
                                    >[random stuff snipped]
                                    > >
                                    > > What do we do to write the acceptance test for any of these
                                    > untrustworthy a=
                                    > > nts?
                                    >
                                    >Pull the probability-generating algorithm out to be tested separately.
                                    >Hopefully, it can run quickly. Determine the level of statistical
                                    >accuracy required, and write a unit test that runs the method some
                                    >sufficiently large n times, and analyzes the results to +/- required
                                    >accuracy. If the accuracy is up in the 3 or 4 9's range, it is unlikely
                                    >to accidentally fail a unit test, right?
                                    >
                                    >Now write a mock object to replace the probability engine, and plug that
                                    >into the ant movement. Ant movement is then deterministic, and can be
                                    >unit tested using ordinary means.
                                    >
                                    >In other words, refactor to make sure the ant's legs aren't too tightly
                                    >coupled to its brain.
                                    >--
                                    >
                                    >David Stagner
                                    >
                                    >National Marrow Donor Program
                                    >3001 Broadway Street NE
                                    >Broadway Ridge Suite 500
                                    >Minneapolis, MN 55413
                                    >
                                    >Email: dstagner@...
                                    >
                                    >To Post a message, send it to: extremeprogramming@...
                                    >
                                    >To Unsubscribe, send a blank message to:
                                    >extremeprogramming-unsubscribe@...
                                    >
                                    >Don't miss XP UNIVERSE, the first US conference on XP and Agile
                                    >Methods. see www.xpuniverse.com for details and registration.
                                    >
                                    >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
                                    >


                                    Ron Jeffries
                                    www.XProgramming.com
                                    The practices are not the knowing. They are a path to the knowing.
                                  • William Tozier
                                    ... Excellent -- a tidy explanation. Thanks much. -- William Tozier bill@williamtozier.com The only normal people are the ones you don t know very well. --
                                    Message 17 of 22 , Aug 3, 2001
                                    • 0 Attachment
                                      >bill@... wrote:
                                      >[random stuff snipped]
                                      >>
                                      >> What do we do to write the acceptance test for any of these untrustworthy a=
                                      > > nts?
                                      >
                                      >In other words, refactor to make sure the ant's legs aren't too tightly
                                      >coupled to its brain.

                                      Excellent -- a tidy explanation. Thanks much.
                                      --
                                      William Tozier
                                      bill@...

                                      "The only normal people are the ones you don't know very well."
                                      -- Joe Ancis
                                    • William Tozier
                                      ... A funny pain I get when I drink cold stuff. Otherwise, no concerns whatsoever. Thanks! -- William Tozier bill@williamtozier.com The only normal people are
                                      Message 18 of 22 , Aug 3, 2001
                                      • 0 Attachment
                                        >Now then, to acceptance test a particular ant, is it sufficient to prepare
                                        >a sequence of "random" numbers for him, hand-calculate what he should do,
                                        >then create an ant with that sequence in his random number generator, and
                                        >see that he does it?
                                        >
                                        >What concerns might we be left with?

                                        A funny pain I get when I drink cold stuff. Otherwise, no concerns
                                        whatsoever. Thanks!
                                        --
                                        William Tozier
                                        bill@...

                                        "The only normal people are the ones you don't know very well."
                                        -- Joe Ancis
                                      • Robert C. Martin
                                        ... This code (created after several G&Ts) needs some work. It redraws the entire map after ever move. This makes it slow, and it also makes it flicker. One
                                        Message 19 of 22 , Aug 11, 2001
                                        • 0 Attachment
                                          > -----Original Message-----
                                          > From: C. Keith Ray [mailto:ckeithray@...]
                                          > Sent: Friday, August 03, 2001 9:19 AM
                                          > To: extremeprogramming@yahoogroups.com
                                          > Subject: [XP] Re: The ant algorithm
                                          >
                                          >
                                          > > From: grenning@...
                                          > >
                                          > >I just uploaded the ant program done by Bob Martin and I in the
                                          > >Raleigh Airport bar while waiting for our plane.
                                          > >
                                          > >The GUI is slow and flickers, but the ant is doing his thing. You
                                          > >have to let it run for a few minutes until something interesting
                                          > >happens.

                                          This code (created after several G&Ts) needs some work. It redraws the
                                          entire map after ever move. This makes it slow, and it also makes it
                                          flicker. One of our next test cases was going to be to update only those
                                          areas of the screen that changed after each move. This would speed things
                                          up dramatically, and would also probably eliminate the flickering.

                                          Alas, our plane took off before we could add this feature. James and I will
                                          have to wait for another airport delay to finish it.

                                          Robert C. Martin | "Uncle Bob" | Software Consultants
                                          Object Mentor Inc. | rmartin@... | We'll help you get
                                          PO Box 5757 | Tel: (800) 338-6716 | your projects done.
                                          565 Lakeview Pkwy | Fax: (847) 573-1658 | www.objectmentor.com
                                          Suite 135 | | www.XProgramming.com
                                          Vernon Hills, IL, | Training and Mentoring | www.junit.org
                                          60061 | OO, XP, Java, C++, Python|

                                          "One of the great commandments of science is:
                                          'Mistrust arguments from authority.'" -- Carl Sagan
                                        • C. Keith Ray
                                          ... Not really, Java has more horsepower than you might think, try my modified version... ... The flicker is caused because Canvas or one of its parent classes
                                          Message 20 of 22 , Aug 12, 2001
                                          • 0 Attachment
                                            > This code (created after several G&Ts) needs some work. It redraws the
                                            > entire map after ever move. This makes it slow,

                                            Not really, Java has more horsepower than you might think, try my modified
                                            version...

                                            > and it also makes it
                                            > flicker. One of our next test cases was going to be to update only those
                                            > areas of the screen that changed after each move. This would speed things
                                            > up dramatically, and would also probably eliminate the flickering.

                                            The flicker is caused because Canvas or one of its parent classes erases its
                                            part of the window; I modified the code that was uploaded to the egroups
                                            archive to remove the flicker. I'm pretty sure this is mentioned somewhere
                                            in the book "Java FAQs".

                                            I also modified the drawing code to draw the ant(s) in red, and played with
                                            having 10 ants at once.

                                            Changing the value for sleeping speeds up or slows down the animation
                                            nicely...
                                            use Thread.sleep( 10 ); for ants moving too fast to follow
                                            use Thread.sleep( 100 ); for ants moving /almost/ too fast to follow
                                            use Threed.speep( 1000 ); to be able to see exactly what is going on...

                                            Sorry, but I didn't make my modifications test-first....


                                            package ants;

                                            import java.awt.Canvas;
                                            import java.awt.Graphics;
                                            import java.awt.Color;

                                            public class AntCanvas extends Canvas
                                            {
                                            Board board;

                                            public AntCanvas( Board b )
                                            {
                                            board = b;
                                            }

                                            public void update( Graphics g )
                                            {
                                            paint( g ); // see Java FAQs about flicker
                                            }

                                            public void paint( Graphics g )
                                            { // see Java FAQs about flicker
                                            // to avoid flicker, don't call parent class's paint method.
                                            for ( int row = 0; row < board.mRows; row++ )
                                            {
                                            for ( int column = 0; column < board.mColumns; column++ )
                                            {
                                            Color color = Color.white;
                                            if ( board.getColor( row, column ) )
                                            {
                                            color = color.black;
                                            }
                                            if ( board.getAnt( row, column ) != null )
                                            {
                                            color = color.red;
                                            }
                                            g.setColor( color );
                                            g.fillRect( column * 5, row * 5, 4, 4 );
                                            }
                                            }
                                            }
                                            }

                                            package ants;

                                            import javax.swing.*;
                                            import java.awt.*;

                                            public class Application1
                                            {
                                            public Application1()
                                            {
                                            try
                                            {
                                            try
                                            {
                                            UIManager.setLookAndFeel(
                                            UIManager.getSystemLookAndFeelClassName() );
                                            }
                                            catch (Exception e)
                                            {
                                            }

                                            Board board = new Board( 100, 100 );
                                            Frame frame = new Frame()
                                            {
                                            public void update( Graphics g )
                                            {
                                            paint( g );
                                            }
                                            };

                                            Ant ant[] = new Ant[ 10 ];

                                            for ( int i = 0; i < ant.length; i++ )
                                            {
                                            ant[i] = new Ant( board );
                                            ant[i].setPosition( i * 5 + 10, i * 5 + 10 );

                                            switch ( i % 4 )
                                            {
                                            case 0:
                                            ant[i].setHeading( 0 );
                                            break;

                                            case 1:
                                            ant[i].setHeading( 90 );
                                            break;

                                            case 2:
                                            ant[i].setHeading( 180 );
                                            break;

                                            case 3:
                                            ant[i].setHeading( 270 );
                                            break;
                                            }
                                            }
                                            AntCanvas canvas = new AntCanvas( board );
                                            canvas.setSize( 500, 500 );
                                            frame.add( canvas );
                                            frame.pack();
                                            frame.show();

                                            while( true )
                                            {
                                            for ( int i = 0; i < ant.length; i++ )
                                            {
                                            ant[i].flip();
                                            ant[i].turn();
                                            ant[i].move();
                                            }//for
                                            canvas.repaint();

                                            try
                                            {
                                            Thread.sleep(100);
                                            }
                                            catch( Exception e)
                                            {
                                            }
                                            }//while
                                            }
                                            catch (Exception e)
                                            {
                                            e.printStackTrace();
                                            }
                                            }

                                            // Main entry point
                                            static public void main(String[] args)
                                            {
                                            new Application1();
                                            }
                                            }

                                            package ants;

                                            public class Board
                                            {
                                            int mRows;
                                            int mColumns;

                                            private Ant cellAnts[][];
                                            private boolean cellColors[][];

                                            public Board( int rows, int columns )
                                            {
                                            mRows = rows;
                                            mColumns = columns;

                                            cellAnts = new Ant[rows][columns];
                                            cellColors = new boolean[rows][columns];
                                            }

                                            // the original code threw an exception when
                                            // an ant tried to 'wander' off the edge of the
                                            // board...

                                            public boolean inBounds( int row, int column )
                                            {
                                            return ( row >= 0 && row < mRows
                                            && column >= 0 && column < mColumns );
                                            }

                                            public boolean getColor( int row, int column )
                                            {
                                            if ( inBounds( row, column ) )
                                            {
                                            return cellColors[row][column];
                                            }
                                            else
                                            {
                                            return false;
                                            }
                                            }

                                            public Ant getAnt( int row, int column )
                                            {
                                            if ( inBounds( row, column ) )
                                            {
                                            return cellAnts[row][column];
                                            }
                                            else
                                            {
                                            return null;
                                            }
                                            }

                                            public void setColor( int row, int column, boolean value )
                                            {
                                            if ( inBounds( row, column ) )
                                            {
                                            cellColors[row][column] = value;
                                            }
                                            }

                                            public void setAnt( int row, int column, Ant value )
                                            {
                                            if ( inBounds( row, column ) )
                                            {
                                            cellAnts[row][column] = value;
                                            }
                                            }
                                            }

                                            package ants;

                                            public class Ant
                                            {
                                            Board itsBoard;

                                            int itsRow = 0;
                                            int itsColumn = 0;

                                            int oldRow = 0;
                                            int oldColumn = 0;

                                            int itsHeading = 0;

                                            public Ant(Board b)
                                            {
                                            itsBoard = b;
                                            }

                                            public void setPosition(int row, int column)
                                            {
                                            itsRow = row;
                                            itsColumn = column;
                                            }

                                            public boolean isOnBlack()
                                            {
                                            return ! itsBoard.getColor( itsRow, itsColumn );
                                            }

                                            public void flip()
                                            {
                                            itsBoard.setColor( itsRow, itsColumn,
                                            ! itsBoard.getColor( itsRow, itsColumn ) );

                                            itsBoard.setAnt( oldRow, oldColumn, null );
                                            itsBoard.setAnt( itsRow, itsColumn, this );
                                            }

                                            public void setHeading(int heading)
                                            {
                                            itsHeading = heading;
                                            }

                                            public void move()
                                            {
                                            oldRow = itsRow;
                                            oldColumn = itsColumn;

                                            if (itsHeading == 0)
                                            {
                                            itsColumn++;
                                            }
                                            else if (itsHeading == 90)
                                            {
                                            itsRow++;
                                            }
                                            else if (itsHeading == 180)
                                            {
                                            itsColumn--;
                                            }
                                            else if (itsHeading == 270)
                                            {
                                            itsRow--;
                                            }
                                            }

                                            public boolean areYouAt( int row, int column )
                                            {
                                            return itsRow == row && itsColumn == column;
                                            }

                                            public void turn()
                                            {
                                            if ( isOnBlack() )
                                            {
                                            itsHeading = (itsHeading + 270) % 360;
                                            }
                                            else
                                            {
                                            itsHeading = (itsHeading + 90) % 360;
                                            }
                                            }

                                            public int getHeading()
                                            {
                                            return itsHeading;
                                            }

                                            public int getRow()
                                            {
                                            return itsRow;
                                            }

                                            public int getColumn()
                                            {
                                            return itsColumn;
                                            }
                                            }

                                            Possible enchancements: draw each Ant in its own color, pattern, or
                                            with little numbers... draw the ant as an arrow-head pointing in its
                                            current direction...

                                            Make the board values grayscale (0-255) instead of black and white (0,1),
                                            and have black squares "fade away" little by little. Have ant treat
                                            a gray value >= 128 as white, gray value < 127 as black.

                                            Change the movement pattern of the ants... Make movement choices
                                            more random.

                                            Customize the movement pattern of _each_ ant.

                                            Turn this into the Game of Life.

                                            Turn this into a simulation of plants (non-moving food sources) and
                                            grazers (moving food-eaters). Add predators who eat the grazers. Combine
                                            this with the Game of Life so that plants use the Life rules for
                                            growth/death.

                                            ----

                                            C. Keith Ray
                                            <http://homepage.mac.com/keithray/resume.html>
                                          Your message has been successfully submitted and would be delivered to recipients shortly.