Author 
Message 

DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 11 Dec 2004 09:44:43 pm Post subject: 


here's my code, this seems to not work as well as what did before, I must've missed some optimization. If anyone finds it please say so.
Code: Plot1(Scatter,X,Y,.
L_X>P
L_Y>Q
Repeat getKey or S<2
L_P>X
L_Q>Y
DispGraph
min(L_X)1>M
min(L_Y)1>N
max(L_X)+1>O
max(L_Y)+1>P
DelVar L_PDelVarL_Q
1>S
For(I,M,O
For(J,N,P
sum(1=max(abs(L_XI),abs(L_YJ
3=Ans or 3=Ansmax(L_X=I and L_Y=J
If Ans:Then
I>L_P(S
J>L_Q(S
S+1>S
End
End
End
End
PlotsOff
ClrHome:"
Last edited by Guest on 14 Dec 2004 08:06:58 am; edited 1 time in total 

Back to top 


alexrudd pm me if you read this
Bandwidth Hog
Joined: 06 Oct 2004 Posts: 2335

Posted: 12 Dec 2004 02:51:59 pm Post subject: 


Sir Robin wrote: here's my code, this seems to not work as well as what did before, I must've missed some optimization. If anyone finds it please say so.
Code: min(L_X)1>M
min(L_Y)1>N
max(L_X)+1>O
max(L_Y)+1>P
Code: sum(1=max(abs(L_XI),abs(L_YJ
3=Ans or 3=Ans+max(L_X=I and L_Y=J
If Ans:Then
For the first one, I doubt it makes a difference, but I think you can put the 1+ before the max( and take off the parenthesis.(sp?)
And I don't know if it applies in this case, but putting the conditional with the If statement instead of using <conditional> If Ans is sometimes faster. 

Back to top 


Jutt
Advanced Newbie
Joined: 27 Jun 2004 Posts: 94

Posted: 13 Dec 2004 08:31:29 am Post subject: 


Wouldn't it be smaller and faster to do this?
For(I,min(L_X)1,1+max(L_X
For(J,min(L_Y)1,1+max(L_Y
Also, I tested your program and it doesn't seem to simulate the real game of life.
did you use other rules? 

Back to top 


axcho
Active Member
Joined: 09 Nov 2004 Posts: 555

Posted: 13 Dec 2004 01:57:10 pm Post subject: 


Here's the life program I made. I know it is not extremely efficient. That's what lead to this topic in the first place. I doubt that any smallscale optimization could dramatically improve the speed, which is why I've been trying to come up with better ways of doing it. It simulates a 7x7 life grid bounded by OFF cells.
Code: DelVar [A]{9,9\>\dim([A]
[A]\>\[B]
ClrHome
For(A,1,8
Output(A,8,"LLLLLLLLL
End
Output(8,1,"LLLLLLL
DelVar C2\>\A
2\>\B
Repeat Ans=105
Output(A1,B1,sub(" O",[A](A,B)+1,1
A+(Ans=34 and A<8)(Ans=25 and A>2\>\A
B+(C=26 and B<8)(C=24 and B>2\>\B
Output(A1,B1,"+
(C=21)+[A](A,B
Ans2(Ans=2\>\[A](A,B
getKey\>\C
End
If [A]=\()\[A]
Then
For(A,2,8
For(B,2,8
randInt(0,1\>\[A](A,B
Output(A1,B1,sub(" O",Ans+1,1
End
End
End
While 1
For(A,2,8
[A](A1,2)+[A](A1,3)+[A](A,3)+[A](A+1,2)+[A](A+1,3\>\C
[A](A,2)(Ans\!=\2 and [A](A,2
Ans+(C=3 and not(Ans\>\[B](A,2
Output(A1,1,sub(" O",Ans+1,1
[A](A1,2)+[A](A1,3)+[A](A1,4)+[A](A,2)+[A](A,4)+[A](A+1,2)+[A](A+1,3)+[A](A+1,4\>\C
[A](A,3)(Ans\!=\2 and [A](A,3
Ans+(C=3 and not(Ans\>\[B](A,3
Output(A1,2,sub(" O",Ans+1,1
[A](A1,3)+[A](A1,4)+[A](A1,5)+[A](A,3)+[A](A,5)+[A](A+1,3)+[A](A+1,4)+[A](A+1,5\>\C
[A](A,4)(Ans\!=\2 and [A](A,4
Ans+(C=3 and not(Ans\>\[B](A,4
Output(A1,3,sub(" O",Ans+1,1
[A](A1,4)+[A](A1,5)+[A](A1,6)+[A](A,4)+[A](A,6)+[A](A+1,4)+[A](A+1,5)+[A](A+1,6\>\C
[A](A,5)(Ans\!=\2 and [A](A,5
Ans+(C=3 and not(Ans\>\[B](A,5
Output(A1,4,sub(" O",Ans+1,1
[A](A1,5)+[A](A1,6)+[A](A1,7)+[A](A,5)+[A](A,7)+[A](A+1,5)+[A](A+1,6)+[A](A+1,7\>\C
[A](A,6)(Ans\!=\2 and [A](A,6
Ans+(C=3 and not(Ans\>\[B](A,6
Output(A1,5,sub(" O",Ans+1,1
[A](A1,6)+[A](A1,7)+[A](A1,8)+[A](A,6)+[A](A,8)+[A](A+1,6)+[A](A+1,7)+[A](A+1,8\>\C
[A](A,7)(Ans\!=\2 and [A](A,7
Ans+(C=3 and not(Ans\>\[B](A,7
Output(A1,6,sub(" O",Ans+1,1
[A](A1,7)+[A](A1,8)+[A](A,7)+[A](A+1,7)+[A](A+1,8\>\C
[A](A,8)(Ans\!=\2 and [A](A,8
Ans+(C=3 and not(Ans\>\[B](A,8
Output(A1,7,sub(" O",Ans+1,1
End
[B]\>\[A]
End


Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 14 Dec 2004 08:06:36 am Post subject: 


Quote: For(I,min(L_X)1,1+max(L_X
For(J,min(L_Y)1,1+max(L_Y This way, it calculates max(L_X and max(L_Y every loop.
Quote: Also, I tested your program and it doesn't seem to simulate the real game of life.
did you use other rules?
3=Ans or 3=Ans+max(LX=I and LY=J
I typed that in wrong, it should be
3=Ans or 3=Ansmax(LX=I and LY=J
(fixed in my post)
That fixes the problem.
Edit: about axcho's post.
I'm not sure that storing the grid in a matrix that way can get terribly efficient no matter how you optimize.
If you want to optimize that though, here's a way:
1. DelVar L181>dim(L1
then you go through the list in the following way:
For(I,11,71
I+2not(fPart(I/9>I //skips the border cells
then the neighbor cells are given by
L1(I10), L1(I9), L1(I, L1(I1), L1(I+1), L1(I+, L1(I+9), and L1(I+10).
You add these up; the cell is ON next generation if the sum is 3, or if the sum is 2 but the cell is already ON.
Last edited by Guest on 14 Dec 2004 08:15:56 am; edited 1 time in total 

Back to top 


Jutt
Advanced Newbie
Joined: 27 Jun 2004 Posts: 94

Posted: 14 Dec 2004 09:00:00 am Post subject: 


Sir Robin wrote: Quote: For(I,min(L_X)1,1+max(L_X
For(J,min(L_Y)1,1+max(L_Y This way, it calculates max(L_X and max(L_Y every loop.
The fun is that it doesn't.
I tested this program:
Code: 1>A
20>B
For(X,A,B
A+1>A
B1>B
End
Disp X You'll see that X=21 after the for loop in spite of B changing during the loop.
A is only needed at the start, so why would the calc check it every loop? 

Back to top 


Ray Kremer
Member
Joined: 16 Feb 2004 Posts: 237

Posted: 14 Dec 2004 05:10:57 pm Post subject: 


Jutt wrote: You'll see that X=21 after the for loop in spite of B changing during the loop.
Apparently that depends on whether you are using an 8X or an 89 family calculator. 

Back to top 


axcho
Active Member
Joined: 09 Nov 2004 Posts: 555

Posted: 14 Dec 2004 11:02:49 pm Post subject: 


Quote: I'm not sure that storing the grid in a matrix that way can get terribly efficient no matter how you optimize.
Yep. That's why I've been trying to come up with better ways of doing it. Maybe I could use a string for the map, and create a blank temporary list every frame. Then I would use inString to find the ON cells, and add 1 to all their neighbors in the list. After that, go through the list, apply the generation rules and convert it to a string. That sounds kind of inefficient. But who knows, it might be a little faster.
I haven't tried your program yet, Sir Robin. But if it's all fixed I will soon.
About the For loops, I think that it takes the values of the variables when it starts the loop, and doesn't update them. I've used For loops where I use a variable for something, and put as both the counter and end point of the For loop. In that case it takes the value from the variable and stores it away somewhere, then it uses the same variable as the counter for the loop.
Last edited by Guest on 14 Dec 2004 11:09:41 pm; edited 1 time in total 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 15 Dec 2004 07:57:57 am Post subject: 


Yes, I've realized that. I think I tested it on my 89 and thought that if the 89 has such a flaw the 83+ would too.
Updated:
Code: Plot1(Scatter,X,Y,.
L_X>P
L_Y>Q
Repeat getKey or S<2
L_P>X
L_Q>Y
DispGraph
DelVar L_PDelVarL_Q
1>S
For(X,min(L_X)1,1+max(L_X
For(Y,min(L_Y)1,1+max(L_Y
sum(1=max(abs(L_XX),abs(L_YY
3=Ans or 3=Ansmax(L_X=X and L_Y=Y
If Ans:Then
X>L_P(S
Y>L_Q(S
S+1>S
End
End
End
End
PlotsOff
ClrHome:"
I have tried writing a different program, this time calculating the maximum and minimum for Y separately in each Xloop. This is faster when, for example, there are two shapes far away from each other. However, I have not been able to optimize this enough to make this noticeably faster in general, sometimes it's even slower. 

Back to top 


smileyguy597
Newbie
Joined: 12 Dec 2004 Posts: 12

Posted: 15 Dec 2004 09:57:05 pm Post subject: 


what do the underscors mean 

Back to top 


alexrudd pm me if you read this
Bandwidth Hog
Joined: 06 Oct 2004 Posts: 2335

Posted: 15 Dec 2004 10:41:50 pm Post subject: 


We use them in conjunction with an L to stand for the little L thingy for lists.
L_1 = list one (small font is not working for me, don't ask.) 

Back to top 


Arcane Wizard `semihippie`
Super Elite (Last Title)
Joined: 02 Jun 2003 Posts: 8993

Posted: 16 Dec 2004 03:11:11 am Post subject: 


[size=14] capital l works too. 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 16 Dec 2004 05:35:37 pm Post subject: 


not in code blocks it doesn't.
Anyway, back on topic about programming the game of life. I think that all of us can program in the simple rules; the real question is how to store the data.
I. something fixed, like a matrix.
the easiest way to do this is to use the graph screen and pxlTest. You will die of boredom if you check each of the 63*95 pixels each loop, so you should maybe keep track of the minimum and maximum X and Y of the shape. Something nice about this way is: pxlTest(Y,X is a very fast way (comparatively) of checking if (X,Y) is filled.
But, you will need to store the next generation separate. To do this, you can use a matrix, NOT recommended, you can use two lists like in method II below, or use Pic variables to keep 2 copies of the graph screen.
If you do the last, it would be something like this:
StorePic 1 //before loop
ClrDraw
StorePic 2
RecallPic 1
//inside loop
If <the pixel should be on next generation>
Then
ClrDraw
RecallPic 2
pxlOn(Y,X
StorePic 2
ClrDraw
RecallPic 1
End
This is hard work, takes a lot of your time drawing, and is not recommended.
II. Keep track only of the coordinates of the ON cells.
The simplest way to do this is storing the xcoordinates to LX and the ycoordinates to LY. That way, you can draw the whole thing with Plot1(Scatter,X,Y,. and DispGraph (like my program).
Now is the question, how to choose which cells to check for being ON in the next generation. This method has to be both fast (so we don't waste too much time choosing) and effective (so we don't choose many cells we know are going to be OFF)
First of all, you can just check all the cells from min(LX)1 to max(LX)+1 and min(LY)1 to max(LY)+1. Good for compact shapes, not so good for something sparse that has a few cells over a large area.
You can do the same thing, but skip values of X such that min(LXX)>1 (I am assuming you check cells first by X and then by Y). This solves the problem of a sparce shape with many gaps along the Xaxis. If you want to do the same thing for the Yaxis, you should do it outside the loop.
min(L_X)1>M
min(L_Y)1>N
max(L_X)+1>O
max(L_Y)+1>P
seq(min(LXX)<2),X,M,O>U
seq(min(LYY)<2),Y,N,P>V
For(X,M,O
If LU(XM+1
Then
For(Y,N,P
If LV(YN+1
Then
<check (X,Y)>
End
End
End
End
Finally, you could go through the list itself and only check neighbors.
For(I,1,dim(LX
For(X,1,1
For(Y,1,1
<check (X+LX(I), Y+LY(I))>
End
End
End
Trouble with this is, there's no easy way to check for overlap (or maybe there is, but it will take more time than just checking the cell several times), and in a dense figure this will really make the difference.
Oh, and if you set up the screen right you can use pxlTest( for checking the points. 

Back to top 


axcho
Active Member
Joined: 09 Nov 2004 Posts: 555

Posted: 17 Dec 2004 04:28:01 pm Post subject: 


Thanks for going through and explaining all that stuff, Sir Robin. That's a great way to use Plotsprites. I'll try out your program soon. 

Back to top 


Toksyuryel Crimson Dragon Software
Elite
Joined: 14 Jun 2003 Posts: 880

Posted: 18 Dec 2004 05:54:11 am Post subject: 


Well, unless you absolutely have to use smileys in your post, you don have to use a code block problem solved 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 18 Dec 2004 10:53:14 am Post subject: 


Hm, I wonder if you can easily check the density of the shape.
dim(LX)/(max(LX)min(LX))/(max(LY)min(LY
If Ans > /some threshold/
Then //the shape is dense, use one method
For(X,min(LX)1,1+max(LX
For(Y,min(LY)1,1+max(LY
sum(1=max(abs(LXX,LYY
If 3=Ans or 3=Ansmax(LX=X and LY=Y
Then
S+1>S
X>LP(S
Y>LQ(S
End
End
End
Else //If the shape isn't dense, use another method
For(D,1,1
LX+D>U
For(E,1,1
LY+E>V
For(I,1,dim(LX
LU(I >X
LV(I>Y
sum(1=max(abs(LXX,LYY
If 3=Ans or 3=Ansmax(LX=X and LY=Y
Then
S+1>S
X>LP(S
Y>LQ(S
End
End
End
End
End
The tough part is figuring out a good threshold for D.
Last edited by Guest on 18 Dec 2004 10:57:47 am; edited 1 time in total 

Back to top 


axcho
Active Member
Joined: 09 Nov 2004 Posts: 555

Posted: 07 Jan 2005 12:02:58 am Post subject: 


I tried out your (Sir Robin's) program a several weeks ago, but it didn't work because I didn't know how to set up the screen correctly. What code would you use to initialize the program? 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 17 Jan 2005 02:08:41 pm Post subject: 


Just storing all xcoordinates to L_X and all ycoordinates to L_Y. 

Back to top 


BarrenSoul
Member
Joined: 22 Dec 2004 Posts: 189

Posted: 01 Mar 2005 02:40:39 pm Post subject: 


soo.... whats the final code we ended up with? I want to test teh speed vs mine
Last edited by Guest on 01 Mar 2005 02:40:51 pm; edited 1 time in total 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 01 Mar 2005 07:42:08 pm Post subject: 


The one in my last post, I think... 

Back to top 


