Jump to content
IGNORED

Mazes and Memory and Dungeons


jchase1970

Recommended Posts

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 by jchase1970
  • Like 2
Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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!!!!!!! :)

Link to comment
Share on other sites

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

65792167.png

 

Now I draw a basic dungeon that looks nice.

add some doors and secret doors.

86595704.png

 

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.

15186723.png

 

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.

  • Like 1
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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 by jchase1970
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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. :)

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...