It is currently Tue May 23, 2017 9:41 am



Welcome
Welcome to rfobasic

You are currently viewing our boards as a guest, which gives you limited access to view most discussions and access our other features. By joining our free community, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content, and access many other special features. In addition, registered members also see less advertisements. Registration is fast, simple, and absolutely free, so please, join our community today. **You are not required to provide truthful information to any registration questions. Be whomever you wish to be.!


Post new topic Reply to topic  [ 27 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: A simulator of the Algorithm of Ants colony...
Unread postPosted: Tue May 16, 2017 1:47 am 
Offline

Joined: Sat Mar 02, 2013 11:04 am
Posts: 836
Location: France
Hello,

some of you know the Algorithm of Ants colony or Ants System or ACO. It used generally to find an optimal path... (ex: Traveling Salesman Problem)

You can see a version working here.

My question is first for the latest experts of the capabilities (graphics in particular) of RFO that are still on this forum even if I am not exactly a newbie myself ;)

Even with less functionnalities than that on youtube I'm not sure it's doable with RFO ?

- Ants quantity must be variable (just black points that move on segments)
- the rate of evaporation of pheromones on the segments must also be able to be modified
- and obviously the graph also.

The interface to make the graph is already done but to move as many ants on segments at the same time with so many simultaneous controls seems to me very very difficult ...
Attachment:
Screenshot_2017-05-16.png
Screenshot_2017-05-16.png [ 67 KiB | Viewed 369 times ]


Your opinion interests me very much. (Not about the screenshot, but about the feasibility of the simulator in RFO Basic! :) )

Cheers

Gilles

_________________
"It is better to mobilize intelligence for stupid things, rather than mobilizing stupidity for intelligent things."
Galaxy TAB S 8.4, 2560x1600, Marshmallow 6.0.1
Galaxy Note II, 1280x720, JB4.1.2
Galaxy A3, 1280x720, Android 6.0.1


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Wed May 17, 2017 3:45 am 
Offline
User avatar

Joined: Wed Jul 10, 2013 8:11 am
Posts: 325
Hi Gilles,

I have changed the main loop of
http://rfobasic.freeforums.org/hot-summer-of-code-t4408-10.html
DASHPATHEFFECT
to
Code:
i=0
speed = 3
DO
i= i + speed
GR.SET.DASHPATHEFFECT pathPatternType1, i*sx
Gr.paint.get thePaint
GR.MODIFY gfirst,"paint",thePaint
GR.MODIFY g,"paint",thePaint
if i >27 then i = 0
gr.render
! GR.TOUCH touched,x,y
UNTIL touched


So you get running dots along lines and curves.
Maybe about 5 DASHPATHEFFECTHs do the job.

I would also play with the alpha parameter on the background lines.

Happy coding
Gregor


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Wed May 17, 2017 4:57 am 
Offline

Joined: Sat Mar 02, 2013 11:04 am
Posts: 836
Location: France
Hi gregor,

I'm so sorry but I did not watch very much your OliBasic.apk surely because I did not see my need of commands added !? :oops:

To modify the color of segments to show pheromones on it : a simple gr.modify ptr, "alpha", newValue should do the trick ! ;)

My doubts relate mainly to the amount of graphic information and calculations to be processed simultaneously by RFO !!!
- we can say may be: 100 ants maxi on around 80 segments maxi !?

Cheers

Gilles

_________________
"It is better to mobilize intelligence for stupid things, rather than mobilizing stupidity for intelligent things."
Galaxy TAB S 8.4, 2560x1600, Marshmallow 6.0.1
Galaxy Note II, 1280x720, JB4.1.2
Galaxy A3, 1280x720, Android 6.0.1


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Wed May 17, 2017 6:52 am 
Offline
User avatar

Joined: Wed Jul 10, 2013 8:11 am
Posts: 325
Hi Gilles,

I believe, there is no limit in quantities of graphic objects.
But the refresh rate with gr.render decrease.
A good game cheats the eyes.

Gregor


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Wed May 17, 2017 10:34 am 
Offline

Joined: Sat Mar 02, 2013 11:04 am
Posts: 836
Location: France
Hi gregor,

it's not a game just a simulator of the algorithm of the Ants Colony generaly used to find a shortest path...

Do you think is feasible with RFO ?

Bundles, Lists or Stacks are slow and heavy to manage instead of arrays... but many things have to be done between each GR.RENDER !!!

Cheers

Gilles

_________________
"It is better to mobilize intelligence for stupid things, rather than mobilizing stupidity for intelligent things."
Galaxy TAB S 8.4, 2560x1600, Marshmallow 6.0.1
Galaxy Note II, 1280x720, JB4.1.2
Galaxy A3, 1280x720, Android 6.0.1


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Thu May 18, 2017 12:13 pm 
Offline
User avatar

Joined: Wed Jul 10, 2013 8:11 am
Posts: 325
Cassiope34 wrote:
Hi gregor,

it's not a game just a simulator of the algorithm of the Ants Colony generaly used to find a shortest path...
I know ;)
Quote:
Do you think is feasible with RFO ?
Yes but with mind :?
Quote:

Bundles, Lists or Stacks are slow
I think in some cases they are faster if your algorithm is clever :)
Quote:
and heavy to manage instead of arrays... but many things have to be done between each GR.RENDER !!!

Most of the things should be done before the graphic is involved.
If you use DASHPATHEFFECT not more than 10 GR.RENDER should be used after a parameter change.

500 iterations are normally enough.
https://github.com/lukedodd/ant-tsp/blob/master/AntTsp.java

Also interesting: (Google search) Implementation and Applications of Ant Colony Algorithms Denis Darquennes

But in any case a challenging task.

Happy coding
Gregor


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Sat May 20, 2017 2:05 am 
Offline

Joined: Sat Mar 02, 2013 11:04 am
Posts: 836
Location: France
Hi greg & all,

is there somebody to help me to obtain more precision ?

Code:
REM test_angle @Cassiope34 0517

gr.open 255,90,140,80,0,0    % green & landscape
gr.screen w,h
scx =1280
scy =800
sx =w/scx : sy =h/scy
gr.scale sx, sy

pas =8   % step

DO
  gr.cls
  gr.color 255,255,255,0,0
  gr.line trait, 400, scy/2, 880, scy/2

  gr.color 255,255,0,0,1
  gr.circle curs, scx/2, scy/2, 8

  gr.color 255,0,0,255,2
  gr.text.size 26
  gr.text.draw mess, 10, 30, "message"
  new =0

  Do

    do
      gr.touch touched, x, y
      if !background() then gr.render
    until touched | new | quit
    if new | quit then D_U.break
    x/=sx : y/=sy

    gr.modify curs, "x", x, "y", y
    do
      gr.touch touched, tx, ty
      tx/=sx : ty/=sy
      gr.modify trait, "x1", x, "y1", y, "x2", tx, "y2", ty : gr.render
    until !touched

    d  =HYPOT((tx-x),(ty-y))    % segment length
    an =acos((tx-x)/d)
    gr.modify mess, "text", "Distance ="+int$(d)+" ,  angle ="+int$(todegrees(an))+"°"
    dp =d/pas
    ix =pas*cos(an)
    iy =pas*sin(an)
    if y>ty then iy=-iy
    for p=1 to dp+1
      gr.move curs, ix, iy : gr.render
    next

  Until new
UNTIL quit
END "Bye...!"

OnBackKey:
  Dialog.message win$,"       What do you want ?", ok, " Exit ", " New ? ", " Cancel "
  new  =(ok=2) : quit =(ok=1)
back.resume


Because of this lack of precision in the calculations I fail to advance on the simulator :oops: :oops:

Cheers

Gilles

_________________
"It is better to mobilize intelligence for stupid things, rather than mobilizing stupidity for intelligent things."
Galaxy TAB S 8.4, 2560x1600, Marshmallow 6.0.1
Galaxy Note II, 1280x720, JB4.1.2
Galaxy A3, 1280x720, Android 6.0.1


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Sat May 20, 2017 8:11 am 
Offline
User avatar

Joined: Sat Oct 04, 2014 5:45 am
Posts: 639
Hi Gilles,

I suggest you use Bresenham's Theorem : https://en.wikipedia.org/wiki/Bresenham ... _algorithm
It always checks the error and is quicker than trigonometry to travel along a line.
Browsing the net you will find many code that is very efficient for this algorithm. 8-)

I quickly found this for 2D in RapidQ Basic :
Code:
SUB draw_line(x1, y1, x2, y2, colour)
    x_dist = abs(x2-x1)
    y_dist = abs(y2-y1)
    IF y2-y1 < -x_dist OR x2-x1 <= -y_dist THEN
        SWAP x1, x2       ' Swap start and end points
  SWAP y1, y2
    END IF
    IF x1 < x2 THEN x_step = 1 ELSE x_step = -1
    IF y1 < y2 THEN y_step = 1 ELSE y_step = -1

    IF y_dist > x_dist THEN     ' steep angle, step by y
  error = y_dist/2
  x = x1
  FOR y = y1 TO y2
      canvas.Pset(x, y, colour)
      error = error - x_dist
      IF error < 0 THEN
          x = x + x_step
    error = error + y_dist
      END IF
  NEXT y
    ELSE          ' not steep, step by x
        error = x_dist/2
  y = y1
  FOR x = x1 TO x2
      canvas.Pset(x, y, colour)
      error = error - y_dist
      IF error < 0 THEN
          y = y + y_step
    error = error + x_dist
      END IF
  NEXT y
    END IF

END SUB


If you want to plot 3D then I could give you a snippet from my CNC software also in RapidQ

Regards
Emile

_________________
Download and tutorial for RFODESIGNER
https://sites.google.com/site/rfodesigner/


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Sat May 20, 2017 8:49 am 
Offline

Joined: Sat Dec 22, 2012 2:32 pm
Posts: 830
Hi Gilles!

...cool project! I think it will be much much slower then we see in your given link....but that doesn't
matter, because it hasn't to compete against smth. ... it's all about having fun to realize it and maybe
to show the pricinple of the algorithm to other interested people!!

Related ro your problem: i think it's because GR.MOVE command has an implicit integer-character because you can only move in steps of full pixel. I didn't figure out whether it does an ROUND or an INT/FLOOR operation internaly, but all of them are leading to quit big errors in comparison to the original desired angle (compare PRINT .....)

Solution could be to use GR.MODIFY, see below. But it isn't worked out/optimised in all details, just a quick sketch....

Hope you will go on!

best regards, brochi


P.S.: Emile was faster (crosspost)

Code:
DO
  DO
   GR.TOUCH touched, x, y
   IF !BACKGROUND() THEN GR.RENDER
  UNTIL touched | new | quit
  IF new | quit THEN D_U.BREAK
  x/=sx : y/=sy

  GR.MODIFY curs, "x", x, "y", y
  DO
   GR.TOUCH touched, tx, ty
   tx/=sx : ty/=sy
   GR.MODIFY trait, "x1", x, "y1", y, "x2", tx, "y2", ty : GR.RENDER
  UNTIL !touched

  d  =HYPOT((tx-x),(ty-y))    % segment length
  an =ACOS((tx-x)/d)
  !GR.MODIFY mess, "text", "Distance ="+INT$(d)+" ,  angle ="+INT$(TODEGREES(an))+"°"
  dp =d/pas
  ix =  pas*COS(an)
  iy =  pas*SIN(an)


  IF y>ty THEN iy=-iy

%-----------------------
% just to show the problem:
  ixr = round (ix) : iyr = round (iy)
  ixi = int (ix)   : iyi = int (iy)
  PRINT TODEGREES(an), TODEGREES(ATAN2(iy,ix)), TODEGREES(ATAN2(iyr,ixr)), TODEGREES(ATAN2(iyi,ixi))
%-----------------------

%-------------------------
%workaround:
  GR.GET.VALUE curs, "x", ixs, "y", iys
  dx = tx-x 
  IF y>ty THEN facy=1 else facy=-1

  FOR xx=ixs TO ixs+dx STEP dx/50
   !GR.MOVE curs, ixi, iyi
   GR.MODIFY curs, "x", xx , "y", iys- (xx-ixs)*TAN(an)*facy
   GR.RENDER
  NEXT
%-----------------------


UNTIL new

UNTIL quit


Report this post
Top
 Profile  
 
 Post subject: Re: A simulator of the Algorithm of Ants colony...
Unread postPosted: Sat May 20, 2017 9:07 am 
Offline
User avatar

Joined: Sat Oct 04, 2014 5:45 am
Posts: 639
Hi Brochi,

Brochi wrote:
i think it's because GR.MOVE command has an implicit integer-character because you can only move in steps of full pixel

Yes this is Gilles's obstacle. The "inacuracy" is now also helped along with the trigonometry (sin,cos,tan,etc) as in Gilles's version.
Therefore I put forward the famous Bresenham's Theorem. It will only move to a full integer and add the error values and when the sum of errors equals a full integer (1) then the plot gets compensated. Brochi I know you know this stuff but only for the readers' sake.
Gilles I like what you want to achieve. Watching you ;)

Regards
Emile

_________________
Download and tutorial for RFODESIGNER
https://sites.google.com/site/rfodesigner/


Report this post
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 27 posts ]  Go to page 1, 2, 3  Next


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
suspicion-preferred