Jump to content
IGNORED

Binary trees in TMS9900 assembly


adamantyr

Recommended Posts

So I'm working on a new game... check out my blog for some details.

 

I was testing out using Binary Space Partitioning (BSP) to divide a map into non-static grid areas that could populate rooms and corridors with child dependencies. (See this link for a nice illustration of how the finished product looks.)

 

I managed to implement the splitting algorithm in assembly, but the complexities of maintaining a tree structure is just maddening. And wasteful in memory; dividing a 64x64 map is costing around a kilobyte to store. (4 bytes per grid indicating position, length and width) Also, the most efficient method to store the tree linearly is with breadth-first organization, which creates a lot of wasted null entries at the bottom. PLUS to traverse the tree I still need yet another stack-structure for indicating visited state! ARGH!

 

I'm probably going to abandon this approach for maze/dungeon generation, because it's too memory-intensive and I'm pretty certain I can find a better method that's more asyncronous than a tree (which is somewhat predictable). But I am wondering if I may be missing some very simple way to make this easier.

 

Here's some code to generate the BSP... please note it doesn't actually generate anything visible, the only way you can view the resulting grid is to dump the memory and examine the blocks in the tree.

 

Adamantyr

 

* Binary Search Partition
* Stored in linear array, in breadth-first order
* Index of children at node i is: 2i + 1, 2i + 2
* index of parent of node i is i - 1 / 2
 DEF START
 REF VMBW,VSBW,KSCAN
WS	 EQU >8300
WS2 EQU >8320
SCRADR EQU >0000
COLADR EQU >0380
PATADR EQU >0800
STATUS EQU >837C
KEYADR EQU >8374
KEYVAL EQU >8375
VDPTMR EQU >8378
RSTACK BSS 32
DIRX BYTE 0,-1,1,0
DIRY BYTE -1,0,0,1
KEYS BYTE 'E','X','S','D',0
B1	 BYTE 1
B2	 BYTE 2
B14 BYTE 14
B48 BYTE 48
B97 BYTE 97
B128 BYTE 128
ANYKEY BYTE >20
 EVEN
KSUB DATA MOVEUP,MOVEDN,MOVELF,MOVERT
ZERO DATA 0
W1	 DATA 1
W4	 DATA 4
W8	 DATA 8
BSPEND DATA >8080
POSX BSS 2
POSY BSS 2
BSPIDX BSS 2
NODECT BSS 2
RMDATA BYTE 0,0,64,64
CHARS DATA >FFFF,>FFFF,>FFFF,>FFFF
 DATA >0000,>0000,>0000,>0000
BSP BSS 1024
MAZE BSS 4096
* Main routine
START LWPI WS
 LI R10,RSTACK
 LI R0,COLADR+16
 LI R1,>1F1F
 BLWP @VSBW
 LI R0,PATADR+1024
 LI R1,CHARS
 LI R2,16
 BLWP @VMBW
 BL @CLRSCR
* Clear BSP area with terminal characters
 LI R0,BSP
 LI R1,512
 LI R2,>8080
MZ1 MOV R2,*R0+
 DEC R1
 JNE MZ1
* Clear maze buffer with blocks
 LI R2,>8080
 LI R1,2048
MZ2 MOV R2,*R0+
 DEC R1
 JNE MZ2
* Create Grid
 BL @MKGRID
* Create Rooms on map
*	 BL @MKROOM
* Create Connections on map
*	 BL @MKCONC
* Go to Maze look mode
 B @MZLOOK
MKGRID CLR @BSPIDX
 LI R9,BSP
 MOV @RMDATA,*R9+
 MOV @RMDATA+2,*R9+
MKG0 BLWP @RANDOM
 ANDI R4,>0001
 MOV R4,R7
 JEQ MKG0A
 CB @RMDATA+3,@B14
 JHE MKG2
 CLR R7
 CB @RMDATA+2,@B14
 JHE MKG2
 JMP MKG1
MKG0A CB @RMDATA+2,@B14
 JHE MKG2
 SETO R7
 CB @RMDATA+3,@B14
 JHE MKG2
* Node end reached; insert node-end references (>FFFF)
MKG1 SETO R0
 MOV R0,*R9+
 INCT R9
 MOV R0,*R9+
 INCT R9
* Move to next node
 B @MKG7
* Split the grid in half
MKG2 CLR R3
 MOV R7,R7
 JEQ MKG3
 MOVB @RMDATA+3,@WS+7
 JMP MKG4
MKG3 MOVB @RMDATA+2,@WS+7
MKG4 MOV R3,R1
 SRL R3,2
 S R3,R1
 SRL R1,1
 BLWP @RNDNUM
 A R1,R4
 CLR R3
 MOVB @RMDATA,R5
 MOVB @RMDATA+1,@WS+11
 MOV R5,R0
 MOV R7,R7
 JEQ MKG5
* Horizontal split
 MOVB @RMDATA+2,R6
 MOVB R6,R1
 MOVB @RMDATA+3,@WS+7
 S R4,R3
 MOVB @WS+7,@WS+13
 AB @WS+7,@WS+1
 MOVB @WS+9,@WS+3
 JMP MKG6
* Vertical split
MKG5 MOVB @RMDATA+3,@WS+13
 MOVB @RMDATA+3,@WS+3
 MOVB @RMDATA+2,@WS+7
 S R4,R3
 MOVB @WS+7,R6
 AB @WS+7,R0
 MOVB @WS+9,R1
* Populate BSP with child nodes in breadth-first order
MKG6 MOV R5,*R9+
 MOV R6,*R9+
 MOV R0,*R9+
 MOV R1,*R9+
* Calculate next node
MKG7 A @W4,@BSPIDX
 MOV @BSPIDX,R1
 MOV @BSP(R1),R0
 C R0,@BSPEND
 JEQ MKGEND
 C R0,@CHARS
 JEQ MKG7
 MOV R0,@RMDATA
 MOV @BSP+2(R1),@RMDATA+2
 B @MKG0
MKGEND SRL R1,2
 MOV R1,@NODECT
 RT
MKROOM MOV R11,*R10+

 B @SUBRET
* Draw room
* RMDATA contains room information
DRAWRM CLR R3
 MOVB @RMDATA+2,@WS+7
 BLWP @RNDNUM
 CI R4,3
 JHE DRWRM1
 LI R4,3
DRWRM1 MOV R4,R5
 DEC R4,R3
 BLWP @RNDNUM
 MOV R4,R6

 MOVB @RMDATA+3,@WS+7
 BLWP @RNDNUM
 CI R4,3
 JHE DRWRM2
 LI R4,3
DRWRM2 MOV R4,R6
 LI R1,MAZE
 CLR R0	
 MOVB @RMDATA,@WS+1
 A R6,R0
 SLA R0,6
 A R0,R1
 CLR R0	
 MOVB @RMDATA+1,@WS+1
 A R0,R1
 A R8,R1
 MOV R7,R2
 MOV R5,R3
 MOVB @B129,*R1+
 DEC R2
 JNE
 MOV R7,R2
 AI R1,64
 DEC R3
 JNE
 RT
MKCONC RT
* Maze look routine
MZLOOK CLR @POSY
 CLR @POSX
MZL1 BL @MZDRAW
KSC1 CLR @KEYADR
KSC2 CLR @STATUS
 LIMI 2
 LIMI 0
KSC3 BLWP @KSCAN
 CB @ANYKEY,@STATUS
 JNE KSC2
 CB @KEYVAL,@B97
 JLT KSC4
 SB @ANYKEY,@KEYVAL
KSC4 LI R2,KEYS
KSC5 CB *R2,@KEYVAL
 JEQ KSC6
 MOVB *R2,*R2+
 JEQ KSC2
 JMP KSC5
KSC6 LI R3,KEYS
 LI R0,KSUB
 S R3,R2
 SLA R2,1
 A R2,R0
 MOV *R0,R1
 BL *R1
 JMP MZL1
MOVEUP MOV @POSY,@POSY
 JEQ MU1
 DEC @POSY
MU1 RT
MOVEDN MOV @POSY,R0
 CI R0,40
 JEQ MD1
 INC @POSY
MD1 RT
MOVELF MOV @POSX,@POSX
 JEQ ML1
 DEC @POSX
ML1 RT
MOVERT MOV @POSX,R0
 CI R0,40
 JEQ MR1
 INC @POSX
MR1 RT
MZDRAW MOV @POSY,R2
 SLA R2,6
 A @POSX,R2
 LI R0,SCRADR
 LI R1,MAZE
 A R2,R1
 LI R2,32
 LI R3,24
MZD1 BLWP @VMBW
 AI R0,32
 AI R1,64
 DEC R3
 JNE MZD1
 RT
* Clear screen
CLRSCR LI R0,SCRADR
 LI R1,>2000
 LI R4,768
CSLOOP BLWP @VSBW
 INC R0
 DEC R4
 JNE CSLOOP
 RT
* Random number generator (Range in R3, Result in R4)
* Returns 0 to R3-1
RNDNUM DATA WS2,RAND2
RAND2 BL @RNDGEN
 MOV @>0006(R13),R3
 CLR R4
 DIV R3,R4
 MOV R5,@>0008(R13)
 RTWP
* Random number generator 16-bit (Result in R4)
* returns 0-65535
RANDOM DATA WS2,RAND1
RAND1 BL @RNDGEN
 MOV R5,@>0008(R13)
 RTWP
* Random number generation
RNDGEN LI R4,23729
 MPY @>83C0,R4
 AI R5,31871
 SRC R5,5
 MOV R5,@>83C0
 RT
* Nested return from subroutine
SUBRET DECT R10
 MOV *R10,R11
 RT
* Program end
 END START

Link to comment
Share on other sites

Hmm, seems like a BSP tree would be a hard way to go about dungeon generation. A long time ago there was a guy named Jamis Buck who made a cool dungeon generator. He went offline for a long time, but a quick search shows he seems to have a blog now. However, his dungeon generator seems to be missing from his blog. Thanks to the WayBack machine, his original pages can be viewed. Although you can't use the interactive generator, the code download and text write-up is still intact. I have used his methods to generate dungeons and it works very well.

 

http://web.archive.org/web/20080725005023/http://www.aarg.net/~minam/dungeon.cgi

 

That is the link to the CGI generator, but there is a link on that page to the description on how the generator works:

 

http://web.archive.org/web/20080724221817/http://www.aarg.net/~minam/dungeon_design.html

Link to comment
Share on other sites

I'm with Matt on this! Regarding the code itself, I'm afraid there's not nearly enough comments in it for me to be able to understand it! I do appreciate that it's much easier for the author of the code, however!

 

Here's an example of some code from TurboForth:

 

;[ FIND		 addr1 -- addr2 n			  83				  
; addr1 is the address of a counted string.  The string contains a word name to be located
; in the currently active search order.  If the word is not found, addr2 is the string
; address addr1, and n is zero.  If the word is found, addr2 is the compilation address and
; n is set to one of two non-zero values.  If the word found has the immediate attribute,
; n is set to one.  If the word is non-immediate, n is set to minus one (true).
findh data blh,4
 text 'FIND'
find data docol,lit,fndvec,fetch,execut,exit
vfind data $+2	    ; vectored find
 mov @blknum,r2 ; processing vdp/cpu memory flag
 mov *stack,r6 ; length to r6
 dect stack
    mov @pvocab,r7  ; if vocabularies are active, get pointer to vocab to search
    jne fndnxt	  ;
 mov @latest,r7 ; otherwise get address of last dictionary entry
fndnxt mov @2(r7),r8 ; length of dictionary entry
 andi r8,>400f ; mask out immediate bit and block numbers
 c r8,r6   ; are they the same length?
 jeq lmatch  ; jump if yes
find1 mov *r7,r7  ; point to next dictionary entry
 jeq nomatch  ; if 0 then we hit the end of the dictionary - no match
 jmp fndnxt  ; else check the next entry
; the length matches, now do a character comparison between the word in the buffer
; and the word in the dictionary
lmatch mov r7,r10
 ai r10,4  ; point to text of dictionary entry
 mov *stack,r0 ; buffer address in r0
cnxtch mov r2,r2  ; working in vdp?
 jne fndvdp  ; if so then read VDP
 cb *r0+,*r10+ ; otherwise compare bytes in cpu memory
find2 jne find1  ; if not equal then check next dictionary entry
 dec r8   ; decrememnt length
 jne cnxtch  ; if not 0 then check next character
; we have a match push cfa and word type
 mov @2(r7),r8 ; get length of dictionary entry
 mov r8,r9  ; make a copy
 andi r8,>f  ; retain length only
 a r8,r7   ; add length
 ai r7,4   ; take account of address & link field
 inc r7   ; round up...
 andi r7,>fffe ; ...to even address
 mov r7,*stack+ ; push cfa
 andi r9,>8000 ; check immediate bit
 jeq noimm  ; if not set then push -1 for status
 li r1,1   ; else push a 1
 mov r1,*stack
 b *next
noimm seto *stack  ; not immediate - push -1
 b *next
nomatch inct stack  ; leave address unchanged on stack
 clr *stack  ; 0=not found
 b *next
fndvdp bl @vsbr  ; read a byte from vdp
 inc r0
 cb *r10+,r1  ; compare byte in buffer to byte from vdp
 jmp find2  ; and resume as normal
;]

 

Just a case of different of programming styles, I guess! In my case, I *know* that in six months *I* will have no idea how my code works (never mind a 3rd party observer!) so I tend to comment the living daylights out of it!

 

Assembly that is. I'm not so religious in other languages! ;)

 

Edit: As usual, the forum software broke the formatting :(

Link to comment
Share on other sites

Yeah, sorry Willsy... I really should do line-by-line comments, but even Textpad is unable to highlight comments in a different color based upon tab position. Which means it looks messy and confusing.

 

I've found that page before, and it is a good dungeon generator. It does involve a LOT of cell processing, though...

 

The main conflict I have is whether or not I should auto-generate all the dungeon levels or try and procedurally re-create them if you revisit a level. If I do the former, then I can basically burn the whole 24k of RAM on a very robust dungeon creation engine. But the latter requires it to run along side the actual game code... On the down side, 10 dungeon levels at 4-6k each makes a rather BIG saved game... more like a game disk amount of content.

 

Adamantyr

Link to comment
Share on other sites

I tried a few different approaches to this, creating a dungeon. It all depends on what you want, the requirements. Let’s say the computer needs to know nothing of the dungeon, only have to make sure that the player obeys rules of movement etc.

 

I like the simplicity of the binary approach. This boils down to simply slicing the screen vertically then horizontally, - then vertically again and so on. Already demonstrated in a link. Here’s a picture from that link showing what you could end up with.

 

split.png

 

I’m almost certain that one could make up some nice mathematical array solution, but I just went on and made a step by step XB try out. I do 1 vertical slice, - then 2 horizontal slices, - then 4 vertical slices, - and then I should do 8 horizontal slices, but I only did 2. I’m lazy, and this is only to demonstrate the nice results. I make sure that each turn of slicing, 2, 4 and 8, does not "align", - "object" - to make it a bit “organic”.

 

Run the program in Classic99 with CPU Overdrive. Try and imagine small corridors between these BIG rooms. - Yep, try and see the red rectangles as rooms, not the gray lines as - just straight lines.

 

Another hour wasted (if my wife was to say anything), but it was a bit fun (and she does appreciate me being in a good mood). If I was to go further with this, I had to, as hopefully implied, take it to a higher level of abstraction.

 

100 call screen(15)::call clear::call color(1,7,7,2,7,7)
110 v1=int(rnd*16)+9
120 call vchar(1,v1,40,24)
130 h11=int(rnd*+9
140 call hchar(h11,1,40,v1)
150 h12=int(rnd*+9::if h11=h12 then 150
160 call hchar(h12,v1+1,40,32-v1)
170 v21=int(rnd*(v1-7))+4
180 call vchar(1,v21,40,h11)
190 v22=int(rnd*(v1-7))+4::if v21=v22 then 190
200 call vchar(h11+1,v22,40,24-h11)
210 v23=int(rnd*(26-v1))+4+v1
220 call vchar(1,v23,40,h12)
230 v24=int(rnd*(26-v1))+4+v1::if v23=v24 then 230
240 call vchar(h12+1,v24,40,24-h12)
250 h31=int(rnd*(h11-7))+4
260 call hchar(h31,1,40,v21)
270 h32=int(rnd*(h11-7))+4::if h31=h32 then 270
280 call hchar(h32,v21+1,40,v1-v21)
900 call color(2,15,15)::call sound(1000,110,30)::call color(2,7,7)::goto 100 

 

PS. Yes, there's a bit of inside-intelligence to those numbers - making sure the rooms are at least 3 characters in size (any direction).

PPS. Upper left corner of course being the most interesting.

Link to comment
Share on other sites

Thanks. I would think one could add corridors along the way. The following is just to demonstrate 4 rooms connected. The corridors are distributed nicely to make it look good (avoiding corridors on the edges etc. using IF statements). Continuing with the same approach wouldn’t be too complicated (I guess testing would still only be 2 statements (hint: not testing horizontal against horizontal), but we quickly run out of space for rooms and corridors on this 32 by 24 character screen.

 

100 call screen(15)::call clear::call color(1,7,7,2,7,7)
! make vertical cut
110 v1=int(rnd*16)+9
120 call vchar(1,v1,40,24)
! make a corridor between the 2 rooms
130 v1d=int(rnd*22)+2
140 call vchar(v1d,v1,32)
! make horizontal cut on the left
150 h1=int(rnd*+9::if abs(h1-v1d)<2 then 150
160 call hchar(h1,1,40,v1)
! make a corridor between the 2 rooms
170 h1d=int(rnd*(v1-3))+2
180 call hchar(h1,h1d,32)
! make horizontal cut on the right
190 h2=int(rnd*+9::if abs(h1-h2)<2 or abs(h2-v1d)<2 then 190
200 call hchar(h2,v1+1,40,32-v1)
! make a corridor between the 2 rooms
210 h2d=31-int(rnd*(30-v1))
220 call hchar(h2,h2d,32)
! repeat
230 call color(2,15,15)::call sound(1000,110,30)::call color(2,7,7)::goto 100

 

slice5.gif

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