+adamantyr Posted August 26, 2012 Share Posted August 26, 2012 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 Quote Link to comment Share on other sites More sharing options...
matthew180 Posted August 26, 2012 Share Posted August 26, 2012 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 Quote Link to comment Share on other sites More sharing options...
Willsy Posted August 27, 2012 Share Posted August 27, 2012 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 Quote Link to comment Share on other sites More sharing options...
+adamantyr Posted August 27, 2012 Author Share Posted August 27, 2012 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 Quote Link to comment Share on other sites More sharing options...
sometimes99er Posted August 29, 2012 Share Posted August 29, 2012 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. 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. Quote Link to comment Share on other sites More sharing options...
sometimes99er Posted August 29, 2012 Share Posted August 29, 2012 Here's a video (gif) ... (for those of you who couldn't be bothered or just haven't got Classic99 at your fingertips) 1 Quote Link to comment Share on other sites More sharing options...
+adamantyr Posted August 29, 2012 Author Share Posted August 29, 2012 Nice work re-creating it in XB! Of course, you're not storing any of the rooms in a tree structure that allows you to connect them up... Adamantyr Quote Link to comment Share on other sites More sharing options...
sometimes99er Posted August 30, 2012 Share Posted August 30, 2012 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 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.