Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's TI-BASIC subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. TI-Basic => TI-BASIC
United-TI Archives -> TI-Basic
 
    » Goto page 1, 2  Next
» View previous topic :: View next topic  
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_X-I),abs(L_Y-J
3=Ans or 3=Ans-max(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_X-I),abs(L_Y-J
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 small-scale 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(A-1,B-1,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(A-1,B-1,"+
(C=21)+[A](A,B
Ans-2(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(A-1,B-1,sub(" O",Ans+1,1
End
End
End
While 1
For(A,2,8
[A](A-1,2)+[A](A-1,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(A-1,1,sub(" O",Ans+1,1
[A](A-1,2)+[A](A-1,3)+[A](A-1,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(A-1,2,sub(" O",Ans+1,1
[A](A-1,3)+[A](A-1,4)+[A](A-1,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(A-1,3,sub(" O",Ans+1,1
[A](A-1,4)+[A](A-1,5)+[A](A-1,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(A-1,4,sub(" O",Ans+1,1
[A](A-1,5)+[A](A-1,6)+[A](A-1,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(A-1,5,sub(" O",Ans+1,1
[A](A-1,6)+[A](A-1,7)+[A](A-1,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(A-1,6,sub(" O",Ans+1,1
[A](A-1,7)+[A](A-1,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(A-1,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=Ans-max(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(I-10), L1(I-9), L1(I-Cool, L1(I-1), L1(I+1), L1(I+Cool, 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
B-1->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_X-X),abs(L_Y-Y
3=Ans or 3=Ans-max(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 X-loop. 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
`semi-hippie`


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 pxl-Test. 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: pxl-Test(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
pxl-On(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 x-coordinates to LX and the y-coordinates 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(LX-X)>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 X-axis. If you want to do the same thing for the Y-axis, 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(LX-X)<2),X,M,O->U
seq(min(LY-Y)<2),Y,N,P->V
For(X,M,O
If LU(X-M+1
Then
For(Y,N,P
If LV(Y-N+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 pxl-Test( 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 Smile problem solved Wink
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(LX-X,LY-Y
If 3=Ans or 3=Ans-max(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(LX-X,LY-Y
If 3=Ans or 3=Ans-max(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 x-coordinates to L_X and all y-coordinates 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
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    » Goto page 1, 2  Next
» View previous topic :: View next topic  
Page 1 of 2 » All times are GMT - 5 Hours

 

Advertisement