jchase1970 Posted November 20, 2010 Share Posted November 20, 2010 (edited) Here is my take on the Recursive Backtracker algo for mazes. What's different? Well a true RB will remember every maze path square. I only remember when the maze makes a turn in direction. I'm not sure my way is any faster but this way requires less memory stack. This first program uses CALL GCHAR and doesn't store the maze so all math is done by reading the screen for info. 10 CALL CLEAR :: CALL COLOR(1,2,16):: CALL SCREEN(2) 100 RANDOMIZE 120 CALL CHAR(33,"FFFFFFFFFFFFFFFF") 130 CALL HCHAR(1,1,33,768) 140 Y=INT(RND*15)+5 :: X=1 150 LD=2 155 CALL HCHAR(Y,X,32) 156 X=X+1 160 CALL HCHAR(Y,X,32) 170 U=0 :: R=0 :: D=0 :: L=0 180 IF U+R+D+L=4 THEN 580 190 ND=INT(RND*4)+1 200 NX=X :: NY=Y 210 IF (ND=1)*(U=0)THEN NY=NY-1 :: GOTO 260 220 IF (ND=2)*(R=0)THEN NX=NX+1 :: GOTO 330 230 IF (ND=3)*(D=0)THEN NY=NY+1 :: GOTO 400 240 IF (ND=4)*(L=0)THEN NX=NX-1 :: GOTO 470 250 GOTO 190 260 IF NY<2 THEN 320 270 CALL GCHAR(NY,NX,S):: IF S=32 THEN 320 280 IF NY-1>0 THEN CALL GCHAR(NY-1,NX,S):: IF S=32 THEN 320 290 IF NX+1<33 THEN CALL GCHAR(NY,NX+1,S):: IF S=32 THEN 320 300 IF NX-1>0 THEN CALL GCHAR(NY,NX-1,S):: IF S=32 THEN 320 310 GOTO 540 320 U=1 :: GOTO 180 330 IF NX>31 THEN 390 340 CALL GCHAR(NY,NX,S):: IF S=32 THEN 390 350 IF NX+1<33 THEN CALL GCHAR(NY,NX+1,S):: IF S=32 THEN 390 360 IF NY+1<25 THEN CALL GCHAR(NY+1,NX,S):: IF S=32 THEN 390 370 IF NY-1>0 THEN CALL GCHAR(NY-1,NX,S):: IF S=32 THEN 390 380 GOTO 540 390 R=1 :: GOTO 180 400 IF NY>23 THEN 460 410 CALL GCHAR(NY,NX,S):: IF S=32 THEN 460 420 IF NY+1<25 THEN CALL GCHAR(NY+1,NX,S):: IF S=32 THEN 460 430 IF NX+1<33 THEN CALL GCHAR(NY,NX+1,S):: IF S=32 THEN 460 440 IF NX-1>0 THEN CALL GCHAR(NY,NX-1,S):: IF S=32 THEN 460 450 GOTO 540 460 D=1 :: GOTO 180 470 IF NX<2 THEN 530 480 CALL GCHAR(NY,NX,S):: IF S=32 THEN 530 490 IF NX-1>0 THEN CALL GCHAR(NY,NX-1,S):: IF S=32 THEN 530 500 IF NY+1<25 THEN CALL GCHAR(NY+1,NX,S):: IF S=32 THEN 530 510 IF NY-1>0 THEN CALL GCHAR(NY-1,NX,S):: IF S=32 THEN 530 520 GOTO 540 530 L=1 :: GOTO 180 540 IF ND=LD THEN X=NX :: Y=NY :: GOTO 160 550 XS$=XS$&CHR$(X):: YS$=YS$&CHR$(Y):: DS$=DS$&CHR$(LD) 560 X=NX :: Y=NY :: LD=ND 570 GOTO 160 580 IF LEN(XS$)=0 THEN 630 590 X=ASC(SEG$(XS$,LEN(XS$),1)):: XS$=SEG$(XS$,1,LEN(XS$)-1) 600 Y=ASC(SEG$(YS$,LEN(YS$),1)):: YS$=SEG$(YS$,1,LEN(YS$)-1) 610 LD=ASC(SEG$(DS$,LEN(DS$),1)):: DS$=SEG$(DS$,1,LEN(DS$)-1) 620 GOTO 170 630 Y=INT(RND*20)+2 640 CALL GCHAR(Y,31,S) 650 IF S=33 THEN 630 660 CALL HCHAR(Y,32,32) 670 GOTO 670 Here's a compiled version of the 1st listing CMAZE.zip This program stores all the info in a 2d array but still draws it as it goes along. 10 CALL CLEAR :: CALL COLOR(1,2,16):: CALL SCREEN(2) 20 DIM MAZE(24,32) 30 FOR X=1 TO 32 :: FOR Y=1 TO 24 :: MAZE(Y,X)=33 :: NEXT Y :: NEXT X 100 RANDOMIZE 120 CALL CHAR(33,"FFFFFFFFFFFFFFFF") 130 CALL HCHAR(1,1,33,768) 140 Y=INT(RND*15)+5 :: X=1 150 LD=2 155 CALL HCHAR(Y,X,32):: MAZE(Y,X)=32 156 X=X+1 160 CALL HCHAR(Y,X,32):: MAZE(Y,X)=32 170 U=0 :: R=0 :: D=0 :: L=0 180 IF U+R+D+L=4 THEN 580 190 ND=INT(RND*4)+1 200 NX=X :: NY=Y 210 IF (ND=1)*(U=0)THEN NY=NY-1 :: GOTO 260 220 IF (ND=2)*(R=0)THEN NX=NX+1 :: GOTO 330 230 IF (ND=3)*(D=0)THEN NY=NY+1 :: GOTO 400 240 IF (ND=4)*(L=0)THEN NX=NX-1 :: GOTO 470 250 GOTO 190 260 IF NY<2 THEN 320 270 IF MAZE(NY,NX)=32 THEN 320 280 IF NY-1>0 THEN IF MAZE(NY-1,NX)=32 THEN 320 290 IF NX+1<33 THEN IF MAZE(NY,NX+1)=32 THEN 320 300 IF NX-1>0 THEN IF MAZE(NY,NX-1)=32 THEN 320 310 GOTO 540 320 U=1 :: GOTO 180 330 IF NX>31 THEN 390 340 IF MAZE(NY,NX)=32 THEN 390 350 IF NX+1<33 THEN IF MAZE(NY,NX+1)=32 THEN 390 360 IF NY+1<25 THEN IF MAZE(NY+1,NX)=32 THEN 390 370 IF NY-1>0 THEN IF MAZE(NY-1,NX)=32 THEN 390 380 GOTO 540 390 R=1 :: GOTO 180 400 IF NY>23 THEN 460 410 IF MAZE(NY,NX)=32 THEN 460 420 IF NY+1<25 THEN IF MAZE(NY+1,NX)=32 THEN 460 430 IF NX+1<33 THEN IF MAZE(NY,NX+1)=32 THEN 460 440 IF NX-1>0 THEN IF MAZE(NY,NX-1)=32 THEN 460 450 GOTO 540 460 D=1 :: GOTO 180 470 IF NX<2 THEN 530 480 IF MAZE(NY,NX)=32 THEN 530 490 IF NX-1>0 THEN IF MAZE(NY,NX-1)=32 THEN 530 500 IF NY+1<25 THEN IF MAZE(NY+1,NX)=32 THEN 530 510 IF NY-1>0 THEN IF MAZE(NY-1,NX)=32 THEN 530 520 GOTO 540 530 L=1 :: GOTO 180 540 IF ND=LD THEN X=NX :: Y=NY :: GOTO 160 550 XS$=XS$&CHR$(X):: YS$=YS$&CHR$(Y):: DS$=DS$&CHR$(LD) 560 X=NX :: Y=NY :: LD=ND 570 GOTO 160 580 IF LEN(XS$)=0 THEN 630 590 X=ASC(SEG$(XS$,LEN(XS$),1)):: XS$=SEG$(XS$,1,LEN(XS$)-1) 600 Y=ASC(SEG$(YS$,LEN(YS$),1)):: YS$=SEG$(YS$,1,LEN(YS$)-1) 610 LD=ASC(SEG$(DS$,LEN(DS$),1)):: DS$=SEG$(DS$,1,LEN(DS$)-1) 620 GOTO 170 630 Y=INT(RND*20)+2 640 IF MAZE(Y,31)=32 THEN 630 650 IF S=33 THEN 630 660 CALL HCHAR(Y,32,32) 670 GOTO 670 And lastly, this program computes the maze in memory in an array and then when done draws the map from memory. 10 CALL CLEAR :: CALL COLOR(1,2,16):: CALL SCREEN(2) 20 DIM MAZE(24,32) 30 FOR X=1 TO 32 :: FOR Y=1 TO 24 :: MAZE(Y,X)=33 :: NEXT Y :: NEXT X 100 RANDOMIZE 120 CALL CHAR(33,"FFFFFFFFFFFFFFFF") 130 CALL HCHAR(1,1,33,768) 140 Y=INT(RND*15)+5 :: X=1 150 LD=2 155 MAZE(Y,X)=32 156 X=X+1 160 MAZE(Y,X)=32 170 U=0 :: R=0 :: D=0 :: L=0 180 IF U+R+D+L=4 THEN 580 190 ND=INT(RND*4)+1 200 NX=X :: NY=Y 210 IF (ND=1)*(U=0)THEN NY=NY-1 :: GOTO 260 220 IF (ND=2)*(R=0)THEN NX=NX+1 :: GOTO 330 230 IF (ND=3)*(D=0)THEN NY=NY+1 :: GOTO 400 240 IF (ND=4)*(L=0)THEN NX=NX-1 :: GOTO 470 250 GOTO 190 260 IF NY<2 THEN 320 270 IF MAZE(NY,NX)=32 THEN 320 280 IF NY-1>0 THEN IF MAZE(NY-1,NX)=32 THEN 320 290 IF NX+1<33 THEN IF MAZE(NY,NX+1)=32 THEN 320 300 IF NX-1>0 THEN IF MAZE(NY,NX-1)=32 THEN 320 310 GOTO 540 320 U=1 :: GOTO 180 330 IF NX>31 THEN 390 340 IF MAZE(NY,NX)=32 THEN 390 350 IF NX+1<33 THEN IF MAZE(NY,NX+1)=32 THEN 390 360 IF NY+1<25 THEN IF MAZE(NY+1,NX)=32 THEN 390 370 IF NY-1>0 THEN IF MAZE(NY-1,NX)=32 THEN 390 380 GOTO 540 390 R=1 :: GOTO 180 400 IF NY>23 THEN 460 410 IF MAZE(NY,NX)=32 THEN 460 420 IF NY+1<25 THEN IF MAZE(NY+1,NX)=32 THEN 460 430 IF NX+1<33 THEN IF MAZE(NY,NX+1)=32 THEN 460 440 IF NX-1>0 THEN IF MAZE(NY,NX-1)=32 THEN 460 450 GOTO 540 460 D=1 :: GOTO 180 470 IF NX<2 THEN 530 480 IF MAZE(NY,NX)=32 THEN 530 490 IF NX-1>0 THEN IF MAZE(NY,NX-1)=32 THEN 530 500 IF NY+1<25 THEN IF MAZE(NY+1,NX)=32 THEN 530 510 IF NY-1>0 THEN IF MAZE(NY-1,NX)=32 THEN 530 520 GOTO 540 530 L=1 :: GOTO 180 540 IF ND=LD THEN X=NX :: Y=NY :: GOTO 160 550 XS$=XS$&CHR$(X):: YS$=YS$&CHR$(Y):: DS$=DS$&CHR$(LD) 560 X=NX :: Y=NY :: LD=ND 570 GOTO 160 580 IF LEN(XS$)=0 THEN 630 590 X=ASC(SEG$(XS$,LEN(XS$),1)):: XS$=SEG$(XS$,1,LEN(XS$)-1) 600 Y=ASC(SEG$(YS$,LEN(YS$),1)):: YS$=SEG$(YS$,1,LEN(YS$)-1) 610 LD=ASC(SEG$(DS$,LEN(DS$),1)):: DS$=SEG$(DS$,1,LEN(DS$)-1) 620 GOTO 170 630 Y=INT(RND*20)+2 640 IF MAZE(Y,31)=33 THEN 630 650 MAZE(Y,32)=32 660 FOR X=1 TO 32 :: FOR Y=1 TO 24 :: CALL HCHAR(Y,X,MAZE(Y,X)):: NEXT Y :: NEXT X 670 GOTO 670 Now TI Basic causes a person to step back and think because what you might expect to be normal and true is sometimes wrong. One would think reading the screen for info would be the slowest way to do this. But when running this examples you will see just the opposite. In fact it is quite a bit faster. I believe the reason why is this. When we use CALL GCHAR the computer reads 1 byte of VDP memory and stores it in a variable. Now since all variables in basic are floating point you might think this would be a double word operation but it's not, just a single byte. Arrays on the other had are one sizes fits all. So they are all double word for floating point storage and therefore every access is copying 4 bytes of memory. Anyway that is my reasoning for it. Edited November 21, 2010 by jchase1970 2 Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 20, 2010 Share Posted November 20, 2010 Hmmm.... Well, that makes sense... You a**hole--- I've been hacking a bunch of crap code together to try and make a maze algorithm and you punch 3 out like THAT.... I'll be studying THESE as well. Nice research though, man. Berylrogue will be all assembly, so I won't have to worry about BASIC speed limitations. But I gotta understand the "why's" and "how's" first. Great post, John! Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 20, 2010 Share Posted November 20, 2010 Hey John... that last program turns black and never shifts out of it. I ran the program, waited 3-4 minutes... then ran it again in CPU OD and it did the same thing... any ideas? Should i just wait longer? Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 20, 2010 Author Share Posted November 20, 2010 Well lets go though it Owen, 10 CALL CLEAR :: CALL COLOR(1,2,16):: CALL SCREEN(2) 100 RANDOMIZE 120 CALL CHAR(33,"FFFFFFFFFFFFFFFF") 130 CALL HCHAR(1,1,33,768) Nothing here so far, colors and wall character 140 Y=INT(RND*15)+5 :: X=1 150 LD=2 155 CALL HCHAR(Y,X,32) 156 X=X+1 I cheated abit here and picked a start point only on the left side of the map. The rnd*15+5 is just to hold it in abit from the corners. LD is var for last direction, we are starting on left moving right. 1 up 2 right 3 down 4 left. Draw the entrance tile then move right 1 space for the maze algo to take off. At the end you'll see another to locate the entrance or exits after the map is drawn. This could have been left out here and done later. 160 CALL HCHAR(Y,X,32) 170 U=0 :: R=0 :: D=0 :: L=0 180 IF U+R+D+L=4 THEN 580 This is the start of the algo loop. Draw the tile. Then set up some vars to test for if we are done randomly picking directions. A check to see if all 4 possible directions have been tried or not. During the process it will check a tile in a direction and if it's bad it will mark that direction with a 1 then jump back to 180 check to see if all 4 directions have been tired or not. Once it is happy with a choice it jumps back to 160 and draws it and resets the 4 var. 190 ND=INT(RND*4)+1 200 NX=X :: NY=Y 210 IF (ND=1)*(U=0)THEN NY=NY-1 :: GOTO 260 220 IF (ND=2)*(R=0)THEN NX=NX+1 :: GOTO 330 230 IF (ND=3)*(D=0)THEN NY=NY+1 :: GOTO 400 240 IF (ND=4)*(L=0)THEN NX=NX-1 :: GOTO 470 250 GOTO 190 Picks a random direction to try, I could have made it faster here because it randomly picks until it tries all 4 direction and that means it may try the same directions many times before it tries them all. Would it have made a big difference? maybe since when you watch it you can see it take longer to move sometimes. So how would be the best way to do it? Maybe put all 4 directions in a list and shuffle it? Still alot of extra swapping stuff around, might be saving time just to use it up elsewhere. 260 IF NY<2 THEN 320 270 CALL GCHAR(NY,NX,S):: IF S=32 THEN 320 280 IF NY-1>0 THEN CALL GCHAR(NY-1,NX,S):: IF S=32 THEN 320 290 IF NX+1<33 THEN CALL GCHAR(NY,NX+1,S):: IF S=32 THEN 320 300 IF NX-1>0 THEN CALL GCHAR(NY,NX-1,S):: IF S=32 THEN 320 310 GOTO 540 320 U=1 :: GOTO 180 The first of 4 directional checks. AAAAA AAAAA XAA AAAAA AAAAA ok you see the 2 blank squares, that is you path cutting into the A's. The X is the spot you are checking to see if you can move to. You have to first check that spot and see if it's a wall or not. Then you have to check each other side of it and make sure no paths are next to where you want to go. AAA A AA A XAA AAAAA AAAAA See if a path is touching the spot you want to go you would connect 2 paths by going there. Not a bad thing if that's something you want but it's a different algo and not a normal "perfect" maze algo. hint...works good for dungeons. 540 IF ND=LD THEN X=NX :: Y=NY :: GOTO 160 550 XS$=XS$&CHR$(X):: YS$=YS$&CHR$(Y):: DS$=DS$&CHR$(LD) 560 X=NX :: Y=NY :: LD=ND 570 GOTO 160 If there is a direction change store it. I'm using strings here because strings are the fastest way to store fluctuating lists in basic. And they are fast but limited to bytes. Something I learned when doing WORMWARS was using x$ and y$ to store the worm info was twice as fast as using a 2d array. And the seg$ function is powerful since you can alter the string in anyway you want. TI basic has no functions to alter an array list. ie if you want to remove a list item in the middle and collapse it down, there's no easy way. with a string it is easy with SEG$. 580 IF LEN(XS$)=0 THEN 630 590 X=ASC(SEG$(XS$,LEN(XS$),1)):: XS$=SEG$(XS$,1,LEN(XS$)-1) 600 Y=ASC(SEG$(YS$,LEN(YS$),1)):: YS$=SEG$(YS$,1,LEN(YS$)-1) 610 LD=ASC(SEG$(DS$,LEN(DS$),1)):: DS$=SEG$(DS$,1,LEN(DS$)-1) 620 GOTO 170 If we check all 4 directions we go to the stack and find out last junction. Reset our vars and move forward from there until we can't move again. This is why it's call the Backtracker. We go forward till we can't go again then back up to another place to go a different direction. Line 580 checks to see if we have anything on the stack, if we don't we have backed all the way to the beginning and therefore are done. 630 Y=INT(RND*20)+2 640 CALL GCHAR(Y,31,S) 650 IF S=33 THEN 630 660 CALL HCHAR(Y,32,32) This finds a exit spot. simply look for a edge path and carve out a spot next to it. same thing could be done to make a start point to. As well as alternate endings if you wanted. Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 20, 2010 Author Share Posted November 20, 2010 Hey John... that last program turns black and never shifts out of it. I ran the program, waited 3-4 minutes... then ran it again in CPU OD and it did the same thing... any ideas? Should i just wait longer? It works, just wait longer. Run the last 2 side by side in 2 classic99 windows in OD. They should finish about the same time. Sometimes it's slower then other depending on the number of junctions to backtrack on. Quote Link to comment Share on other sites More sharing options...
+adamantyr Posted November 20, 2010 Share Posted November 20, 2010 I believe the reason why is this. When we use CALL GCHAR the computer reads 1 byte of VDP memory and stores it in a variable. Now since all variables in basic are floating point you might think this would be a double word operation but it's not, just a single byte. Arrays on the other had are one sizes fits all. So they are all double word for floating point storage and therefore every access is copying 4 bytes of memory. Anyway that is my reasoning for it. Nice work! I thought I could use subprograms in Extended BASIC to do a little recursion but no such luck... the TI engineers specifically state that recursion is not supported. Bugger all. One small correction, though. Floating point on the TI is 8 bytes, not 4. The reference guide certainly says that 13-14 significant digits is there, I imagine that they just don't show you the entire thing in BASIC. BASIC may only be copying the most significant 4 bytes of the mantissa, though, I've never looked closely at the interpreter. Adamantyr Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 20, 2010 Share Posted November 20, 2010 (edited) Sick sick sick sh** John.... I'm thoroughlly impressed. =) Edited November 20, 2010 by Opry99er Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 20, 2010 Author Share Posted November 20, 2010 (edited) The 1st program compiled using Wilhems Basic Compiler. With out over drive on it makes a maze in about 30 sec. CMAZE.zip Edited November 20, 2010 by jchase1970 Quote Link to comment Share on other sites More sharing options...
matthew180 Posted November 20, 2010 Share Posted November 20, 2010 Now TI Basic causes a person to step back and think because what you might expect to be normal and true is sometimes wrong. One would think reading the screen for info would be the slowest way to do this. But when running this examples you will see just the opposite. In fact it is quite a bit faster. I believe the reason why is this. When we use CALL GCHAR the computer reads 1 byte of VDP memory and stores it in a variable. Now since all variables in basic are floating point you might think this would be a double word operation but it's not, just a single byte. As I mentioned in the other thread (plotting a dungeon), BASIC stores arrays in VDP RAM, so it does not matter if you implement the "array" using DIM or with GCHAR, both are going to cause VRAM access. Using a numeric array will cause more storage (8 bytes per subscript to store the floating point value), and thus reading a minimum of 8-bytes per array subscript, vs. reading back a single byte via GCHAR. However, that single byte that is read from VRAM via GCHAR is still going to held in an 8-byte numeric variable, and BASIC will do internal conversion to integers as necessary based on certain operations. The more I think about it, using strings, or a string array, might turn out to be the fastest way to do the maze storage in stock BASIC or XB. Matthew Quote Link to comment Share on other sites More sharing options...
matthew180 Posted November 20, 2010 Share Posted November 20, 2010 Hmmm.... Well, that makes sense... You a**hole--- I've been hacking a bunch of crap code together to try and make a maze algorithm and you punch 3 out like THAT.... I'll be studying THESE as well. Nice research though, man. Berylrogue will be all assembly, so I won't have to worry about BASIC speed limitations. But I gotta understand the "why's" and "how's" first. Great post, John! Owen, you need to make sure you are not trying to "invent" a new maze algorithm vs. coming up with different ways to "implement" an algorithm. I think you are trying to do the former, while the rest of us are doing the latter. Sometimes you will see a clever way to do something, but the math or science behind the implementation existed before the code. I think you will have another "Ah Ha" moment soon when you realize we are simply implementing algorithms or theories that are already worked out, and adding variations here and there based on our needs. In this capacity we are practicing our trade and being clever programmers. Don't get disillusioned, you will get there too. Understanding the math and science behind something like a maze totally different than implementing it in code. Matthew Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 20, 2010 Author Share Posted November 20, 2010 Now TI Basic causes a person to step back and think because what you might expect to be normal and true is sometimes wrong. One would think reading the screen for info would be the slowest way to do this. But when running this examples you will see just the opposite. In fact it is quite a bit faster. I believe the reason why is this. When we use CALL GCHAR the computer reads 1 byte of VDP memory and stores it in a variable. Now since all variables in basic are floating point you might think this would be a double word operation but it's not, just a single byte. As I mentioned in the other thread (plotting a dungeon), BASIC stores arrays in VDP RAM, so it does not matter if you implement the "array" using DIM or with GCHAR, both are going to cause VRAM access. Using a numeric array will cause more storage (8 bytes per subscript to store the floating point value), and thus reading a minimum of 8-bytes per array subscript, vs. reading back a single byte via GCHAR. However, that single byte that is read from VRAM via GCHAR is still going to held in an 8-byte numeric variable, and BASIC will do internal conversion to integers as necessary based on certain operations. The more I think about it, using strings, or a string array, might turn out to be the fastest way to do the maze storage in stock BASIC or XB. Matthew well I know from experience that string storage is much faster but I never thought about string arrays. The word array always triggered in my mind slow storage from past programs. but I bet a string array would just assign a byte per unit. you know sometimes you get something in you mind that blocks you from seeing other options. I'll test this later. Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 20, 2010 Author Share Posted November 20, 2010 Two test programs one number array, one string array. they both fill a 24x32 array with a random number and then access the array and fill the screen. 5 CALL CLEAR 10 DIM MAZE(24,32) 20 FOR X=1 TO 32 30 FOR Y=1 TO 24 40 MAZE(Y,X)=INT(RND*50)+33 50 NEXT Y 60 NEXT X 70 FOR X=1 TO 32 80 FOR Y=1 TO 24 90 CALL HCHAR(Y,X,MAZE(Y,X)) 100 NEXT Y 110 NEXT X 5 CALL CLEAR 10 DIM MAZE$(24,32) 20 FOR X=1 TO 32 30 FOR Y=1 TO 24 40 MAZE$(Y,X)=CHR$(INT(RND*50)+33) 50 NEXT Y 60 NEXT X 70 FOR X=1 TO 32 80 FOR Y=1 TO 24 90 CALL HCHAR(Y,X,ASC(MAZE$(Y,X))) 100 NEXT Y 110 NEXT X The Number array is noticeably faster then the string array. Must have something to do with the internal structure of array. Maybe a string array still allocates the same bytes per unit as the number array. Or maybe the string to number conversion affect it this much, but in single strings they don't slow it down. Interesting test anyway. Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 21, 2010 Author Share Posted November 21, 2010 Ok 2 more programs that carve out space. I'm trying to make it erode out a chamber. You can input different values and retry them. Program 1 randomly fills the screen with blanks and then erodes around them if (the 8 squares around the tile) more then 4 squares are blank. I was thinking that is water was washing out and it had more water then land the land would loose out. Program 1 a value of 45 works good 5 CALL CLEAR rem initial crave out persent 10 INPUT"ENTER INITIAL CARVE OUT%(1-100):":C rem draw the screen all filled 20 call char(33,"FFFFFFFFFFFFFFFF") 30 CALL HCHAR(1,1,33,768) REM NOW START AT TOPAND SCAN PAGE REMOVE TILES BASED ON C 40 FOR X=2 TO 31 50 FOR Y=2 TO 23 60 IF INT(RND*100)<C THEN 70 ELSE 80 70 CALL HCHAR(Y,X,32) 80 NEXT Y 90 NEXT X REM ERRODE 110 FOR X=2 TO 31 120 FOR Y=2 TO 23 REM COUNT OPEN TILES 121 T=0 122 FOR I=-1 TO 1 123 FOR J=-1 TO 1 124 CALL GCHAR(Y+I,X+J,A) 125 IF A=32 THEN 126 ELSE 130 126 T=T+1 127 IF T=5 THEN 128 ELSE 130 128 CALL HCHAR(Y,X,32) 129 GOTO 150 130 NEXT J 140 NEXT I 150 NEXT Y 160 NEXT X 190 DISPLAY AT(1,1):"PRESS ANYKEY TO REPEAT" 200 CALL KEY(0,K,S) 210 IF S=0 THEN 200 ELSE 5 and the compiled version M1F.zip Program 2 works kinda the same except only looks for connections up,down,left and right. Little more control in this one, enter a fill percent and a minimum number of connections. Program 2 try values 55 and 3 to begin with 5 CALL CLEAR rem initial crave out persent 10 INPUT"ENTER INITIAL CARVE OUT%(1-100):":C 15 INPUT"ENTER MIN CONNECTIONS(1-4):":N rem draw the screen all filled 20 call char(33,"FFFFFFFFFFFFFFFF") 30 CALL HCHAR(1,1,33,768) REM NOW START AT TOPAND SCAN PAGE REMOVE TILES BASED ON C 40 FOR X=2 TO 31 50 FOR Y=2 TO 23 60 IF INT(RND*100)<C THEN 70 ELSE 80 70 CALL HCHAR(Y,X,32) 80 NEXT Y 90 NEXT X REM ERRODE 110 FOR X=2 TO 31 120 FOR Y=2 TO 23 REM COUNT OPEN TILES 121 T=0 122 FOR I=-1 TO 1 123 CALL GCHAR(Y+I,X,A) 124 IF A=32 THEN 125 ELSE 126 125 T=T+1 126 CALL GCHAR(Y,X+I,A) 127 IF A=32 THEN 128 ELSE 129 128 T=T+1 129 IF T>N-1 THEN 130 ELSE 140 130 CALL HCHAR(Y,X,32) 131 GOTO 150 140 NEXT I 150 NEXT Y 160 NEXT X 190 DISPLAY AT(1,1):"PRESS ANYKEY TO REPEAT" 200 CALL KEY(0,K,S) 210 IF S=0 THEN 200 ELSE 5 and the compiled version M2F.zip Stay tuned for more. Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 21, 2010 Share Posted November 21, 2010 Good stuff John.... I can't wait to try this out!!! I'm staying at my sister's tonight with the wife and kid and I have no access to my laptop or an emulator. I am trying a few new tapes out tonight... See what I've got. Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 21, 2010 Share Posted November 21, 2010 I think you will have another "Ah Ha" moment soon when you realize we are simply implementing algorithms or theories that are already worked out, and adding variations here and there based on our needs. In this capacity we are practicing our trade and being clever programmers. Don't get disillusioned, you will get there too. Understanding the math and science behind something like a maze totally different than implementing it in code. Well, you are once again way ahead of me. Thank you sir. For the record... AHA!!!!!!! Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 22, 2010 Author Share Posted November 22, 2010 The way that I'm doing the random dungeons for ROGUE is if you tried it, noticeably faster then these mazes. Well I'm doing them very different. For speed because of basic I don't want to try and plot out any random dungeon. At best in non-overdrive it will be at least a 3 minute process. So the solution is to combine sets of strings that from a complete dungeon. Nothing new here to anybody that was programming in the 80's but I know Owen will enjoy it. Maze Man uses random strings but the output is sporadic to say the least. So I came up with this method to produce nice looking dungeons very fast. The screen needs 1 text line, a top and bottom border. That leaves 21 lines. I cut that into 3rds. I opened paint and made me a template for this for the screen area and showing my 3rds Now I draw a basic dungeon that looks nice. add some doors and secret doors. Now cut the middle 3rd out and paste it in a new temple as the middle 3rd and then draw a top and bottom 3rd that matches up to it that are different then the 1st ones. Now I have 1 middle piece and 2 top and 2 bottom pieces that all seem to fit together. Repeat this process by cutting out the middle and making a couple of more middles that fit together. So say we make 3 top and 3 middle and 3 bottoms, 3^3 27 possible mazes. not bad on memory usage as just strings, but they could be compressed since there are only 4 tiles, floor, wall, door,secret door. but uncompressed they are 28x21 maps, 588 bytes per set of 3. Not to bad. Now how to code it to work. Type out the ascii code for each string store them as DATA keeping the tops together the middle together and the bottoms together. Read them as sets of 7 and store them in arrays for top,bottom, middle. randomly pick a top print it, pick a middle print it, pick a bottom print it. This code here doesn't use data, but I compress 7 lines of ascii to 1 string and it fits with room to spare, If you had the whole screen 24 lines 8 would fit per string. 10 REM BASIC ROUGE 11 CALL SCREEN(15) 20 A$="....#....#...........#........../....+...........#..........#....#...........#..........#....#####" 21 Z$="########..........#....#...........#..........#....+...........+..........#....#...........#......" 22 A$=A$&Z$ 30 B$="....#.....#..#.....#......#...../.....#..#.....+......#.....#######..#######......+...........#..." 31 Z$=".....#......#...........#........#......#.###+##########+############..........#...........#......" 32 B$=B$&Z$ 33 C$="###+#########+##############.......#...........#...............#...........+...............+......" 34 Z$=".....#...............#...........#...............#...........#........#####/###################+##" 35 C$=C$&Z$ 36 D$="....#....#...........#......######################........#...#.......#......#........#...+......." 37 Z$="#......+........#...#.......#......#######..#####.......#......#............###/#####......#......" 38 D$=D$&Z$ 40 E$="..........#...########................#......+....................##+######/####.........######..." 41 Z$=".#.......#.........+....+....#.......#.........#....#....#.......#....############################" 42 E$=E$&Z$ 43 F$=".....................#...........................#......###+################/#######.........#...." 44 Z$="....#..........#+#.....+........#..........#.#.....#........#.........############################" 45 F$=F$&Z$ 46 G$="##+##....#...........######.....#....#...######..#../.#.....##...#...#....#..#..#.#......#...+.../" 47 Z$="....#..+..#.#.....##...#...#....#..####.#.....#....#...######..#....#.#####....#...........#/####." 48 G$=G$&Z$ 99 CALL CLEAR 100 IF INT(RND*2)=0 THEN 101 ELSE 103 101 PRINT A$ 102 GOTO 109 103 PRINT B$ 109 M=INT(RND*3) 110 IF M=0 THEN 111 ELSE 113 111 PRINT C$ 112 GOTO 120 113 IF M=1 THEN 114 ELSE 116 114 PRINT D$ 115 GOTO 120 116 PRINT G$ 120 IF INT(RND*2)=0 THEN 121 ELSE 123 121 PRINT E$ 122 GOTO 130 123 PRINT F$ 130 CALL HCHAR(2,2,35,30) 131 CALL VCHAR(1,2,35,24) 132 CALL VCHAR(1,31,35,24) 150 CALL KEY(O,K,S) 151 IF S=0 THEN 150 152 GOTO 99 The sample here is 2 tops 3 middles 2 bottoms for 2*3*2 or 12 possible maps. Hit a key to make a new map. So you see you can put design into a dungeon with some random elements to it. But this way you can create wandering halls and odd rooms that all fit well that would be hard to remake in a totally random fashion. 1 Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 22, 2010 Share Posted November 22, 2010 That's what I call "coooool!!!" . I learned something from this post... Thank you sir Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 23, 2010 Author Share Posted November 23, 2010 Interestingly I used X for walls and . for floor and S for secert door and D for doors and if you look in the code I didn't use those letters at all. They didn't work out for my charset places. So I didn't want to retype them in? So I wrote a basic program to read the strings convert them then build a string for output that started with DATA included 3 stings separated by ",". Had the program write the strings to a file, opened it and copied and pasted it back into my source editor, just added line numbers to them. Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 24, 2010 Author Share Posted November 24, 2010 (edited) Here is a cavern made with one of the top algos, I added some LOS about as much as I dare in basic. 100 RANDOMIZE 110 DIM MZ$(12,5) 120 CALL CLEAR 130 CALL COLOR(8,11,2) 140 CALL COLOR(9,2,7) 150 C=65 160 N=4 170 CALL CHAR(33,"FFFFFFFFFFFFFFFF") 180 CALL CHAR(34,"FFFFFFFFFFFFFFFF") 190 CALL CHAR(88,"8800220088002200") 200 CALL CHAR(89,"80081C08BE081422") 210 CALL CHAR(96,"FF44FF11FF44FF11") 220 CALL HCHAR(2,1,33,736) 230 FOR X=2 TO 31 240 FOR Y=3 TO 23 250 IF INT(RND*100)<C THEN 260 ELSE 270 260 CALL HCHAR(Y,X,34) 270 NEXT Y 280 NEXT X 290 FOR X=2 TO 31 300 FOR Y=3 TO 23 310 T=0 320 FOR I=-1 TO 1 330 CALL GCHAR(Y+I,X,A) 340 IF A=34 THEN 350 ELSE 360 350 T=T+1 360 CALL GCHAR(Y,X+I,A) 370 IF A=34 THEN 380 ELSE 390 380 T=T+1 390 IF T>N-1 THEN 400 ELSE 420 400 CALL HCHAR(Y,X,34) 410 GOTO 430 420 NEXT I 430 NEXT Y 440 NEXT X 450 T=0 460 X=INT(RND*30)+2 470 Y=INT(RND*22)+2 480 FOR I=-1 TO 1 490 CALL GCHAR(Y+I,X,A) 500 CALL GCHAR(Y,X+I,A1) 510 IF A=34 THEN 520 ELSE 530 520 T=T+1 530 IF A1=34 THEN 540 ELSE 550 540 T=T+1 550 NEXT I 560 IF T<6 THEN 450 570 DATA 0,1,0,2,0,3,0,1,1,2,1,3,1,1,2,2,2,2,1,0,2,1,3,1 580 DIM LOS(12,2) 590 FOR I=1 TO 12 600 READ A,B 610 LOS(I,1)=A 620 LOS(I,2)=B 630 NEXT I 640 CALL HCHAR(Y,X,89) 650 LO=0 660 FOR S=1 TO 4 670 FOR I=1 TO 3 680 LO=(S-1)*3+I 690 CALL GCHAR(Y+LOS(LO,1),X+LOS(LO,2),A) 700 IF (A=34)+(A=88)THEN A=88 ELSE A=96 710 CALL HCHAR(Y+LOS(LO,1),X+LOS(LO,2),A) 720 IF A=96 THEN 740 730 NEXT I 740 NEXT S 750 LO=0 760 FOR S=1 TO 4 770 FOR I=1 TO 3 780 LO=(S-1)*3+I 790 CALL GCHAR(Y+LOS(LO,2),X-LOS(LO,1),A) 800 IF (A=34)+(A=88)THEN A=88 ELSE A=96 810 CALL HCHAR(Y+LOS(LO,2),X-LOS(LO,1),A) 820 IF A=96 THEN 840 830 NEXT I 840 NEXT S 850 LO=0 860 FOR S=1 TO 4 870 FOR I=1 TO 3 880 LO=(S-1)*3+I 890 CALL GCHAR(Y-LOS(LO,1),X-LOS(LO,2),A) 900 IF (A=34)+(A=88)THEN A=88 ELSE A=96 910 CALL HCHAR(Y-LOS(LO,1),X-LOS(LO,2),A) 920 IF A=96 THEN 940 930 NEXT I 940 NEXT S 950 LO=0 960 FOR S=1 TO 4 970 FOR I=1 TO 3 980 LO=(S-1)*3+I 990 CALL GCHAR(Y-LOS(LO,2),X+LOS(LO,1),A) 1000 IF (A=34)+(A=88)THEN A=88 ELSE A=96 1010 CALL HCHAR(Y-LOS(LO,2),X+LOS(LO,1),A) 1020 IF A=96 THEN 1040 1030 NEXT I 1040 NEXT S 1050 CALL JOYST(1,JX,JY) 1060 IF (JX<>0)*(JY<>0)THEN 1050 1070 X=X+JX/4 1080 Y=Y-JY/4 1090 CALL GCHAR(Y,X,A) 1100 IF A=88 THEN 1110 ELSE 1130 1110 CALL HCHAR(Y+JY/4,X-JX/4,88) 1120 GOTO 640 1130 X=X-JX/4 1140 Y=Y+JY/4 1150 GOTO 1050 and here is the compiled version CLOS1.zip http://www.youtube.com/watch?v=rm77AAKWtSo Edited November 24, 2010 by jchase1970 Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 24, 2010 Share Posted November 24, 2010 nicely done! =) I believe we're going to get some good use out of that poor ol' Compiler this year, what you say John?? =) BTW... I believe I'll let the winner decide whether he/she will compile his/her game before we put it on cart... It will change the nature of the final product... I might have to consult with those more informed on the matter... Do we want to stay with strict BASIC on this cart, or will a compied BASIC be acceptable, per the winner? Also, John... you DID successfully get a cart bin file of one of your compiled BASIC games correct? I don't know the process all that well, but I'm sure someone who knows will chime in here. Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 24, 2010 Author Share Posted November 24, 2010 EA5 file to cartridge Retroclouds wrote a very nice how to on making it a cartridge Owen. As for the contest, you made a basic contest and it wouldn't be fair to throw in compiled options now. The contest has to proceed on the idea of a basic program on a cart. After the winner is decided on that then if anyone wants to compile their code I'll gladly help out. Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 24, 2010 Share Posted November 24, 2010 I obviously will be judging on the BASIC games... But let's say Adam wins and he would like his game compiled before being put on cart... I think that should be the option of the winner... You think? And yea.... I'm judging the real BASIC games on a real TI for the contest... I was speaking about after the contest.. And thanks for the link... I'll look that up now. Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 24, 2010 Author Share Posted November 24, 2010 I obviously will be judging on the BASIC games... But let's say Adam wins and he would like his game compiled before being put on cart... I think that should be the option of the winner... You think? And yea.... I'm judging the real BASIC games on a real TI for the contest... I was speaking about after the contest.. And thanks for the link... I'll look that up now. I agree, If the cart version of a game can benefit from compiling then it should be done. Quote Link to comment Share on other sites More sharing options...
Opry99er Posted November 24, 2010 Share Posted November 24, 2010 Wilhelm's compiler handles "DISPLAY AT" and multiple-line statements, correct? If I remember back to my speed tests with it, it handled everything but SPRITEs and Disk access..... Quote Link to comment Share on other sites More sharing options...
jchase1970 Posted November 24, 2010 Author Share Posted November 24, 2010 No DISPLAY AT you have to make a routine to write strings using hchar, not a biggie. It's more a basic compiler, but uses multiple statments on a line like XB, big char values like XB everything is integer math no flaoting point. Well here is the list from his docs for anyone that wants to see them, Following is a list of the TI BASIC operations supported by the compiler:. . As in XB, simple multiple statement lines can be used, separating the statements with the double colon. . CALL LINK("RUN") - same as RUN in XB. Cannot use RUN or RUN line # within a program.. CALL LINK("CON") - same as CON in XB. <FCTN 4> breaks the program as in XB except during INPUT.. . . All relational operators work the same as in BX. These include < > = <> <= >= . . Arithmetic operators all work as they do in BX. Exponentiation (|) not supported. Remember that dividing 5/2 will give 2, not 2.5. You can use INT in the BASIC program when dividing (for example INT(5/2) to be certain that BASIC and the compiler give the same results.. . Logic operators from XB have been included: NOT; AND; XOR; OR . . . LET - optional. REM - All remarks will be removed from the compiled program, but you can GOTO a REM statement just like in BX. Use of REM will not increase the size of the compiled program.. ! - the exclamation point REM from XB has been included.. END . STOP . GOTO . ON-GOTO . IF-THEN-ELSE - works only with line numbers, just like in BASIC. XB style of IF-THEN-ELSE not supported.. FOR-TO-STEP - step optional; +1 assumed. NEXT. . INPUT - Can use the optional prompt, but can input only 1 string or number per INPUT statement.. READ . DATA (Do not GOTO a DATA statement!). RESTORE . PRINT works like TI BASIC, including TAB and the print separators ;,:. DISPLAY - equivalent of PRINT.. . CALL CLEAR . CALL COLOR - expanded to work like XB except for color of sprites.. CALL SCREEN . CALL CHAR - expanded to work like XB.. CALL HCHAR . CALL VCHAR . CALL SOUND - cannot handle frequencies greater than 32767. (Neither can my ears!). CALL GCHAR . CALL KEY . CALL JOYST. . ABS . INT . RANDOMIZE - can be used, but has no effect; it is done automatically. RND - returns a value of 0. RND is only useful when it is multiplied by another number. i.e. INT(RND*6) gives the same results (0,1,2,3,4,5) when compiled as it does when used in BX.. SGN . SQR - gives same number as INT(SQR(N)) in BX. . ASC . CHR$ . LEN . POS . SEG$ . STR$ . VAL . String concatenation (i.e. A$&&B$) works the same as in XB. String truncated if over 255 characters; no warning given.. . DIM is optional but using it can reduce size of the compiled program.. OPTION BASE . ARRAY LIMITATION - Important!! The program being compiled cannot use nested arrays. For example, if you have the two arrays DIM A(10),DIM B(10); you can use Q=A(X+Y-Z) but you can't nest the arrays like this: Q=A(B(7)). Use of nested arrays will cause the compiled program to crash!!! For the above example you would have to split up the statement something like this: X=B(7)::Q=A(X). . GOSUB . RETURN . ON-GOSUB . . . NOT SUPPORTED:. . DEF. ATN. COS. EXP. LOG. SIN. TAN. . No File processing capabilities have been implemented at this time.. . The following have no meaning in a compiled program:. LIST. NUM. RES. BREAK. UNBREAK. CON - use CALL LINK("CON"). TRACE. UNTRACE. EDIT. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.