I am making a random labyrinth generator to be used in a small Dungoen RPG style game... unfortunately I can't quite get the backtracking to work. I have an eerie feeling that it's just some little detail, but I have looked at it till I was crosseyed and still couldn't get it to work... maybe you guys can help me?
It is supposed to go back through it's own track if it gets to a poing where it can go no further. Then when it goes back it should find a spot where it can go in a new direction and go forward again. This way it would generate a labyrinth that fills the whole array, and where you have access to all areas of the labyrinth.
Here's the code, hope you can help...
set display mode 640,480,16
sync on
sync rate 25
REM ** Randomize, somehow it always generates the same "random" numbers anyway I do it...
randomize 5
REM ** Some "constants" (size of labyrinth, starting position)
XSIZE = 100
YSIZE = 100
STARTX = 49
STARTY = 49
REM ** Dim the map, the ways, and the backtracking memory...
dim map(XSIZE,YSIZE)
dim way(4)
dim oldx(10000)
dim oldy(10000)
REM ** Make sure the map is clear before we draw to it...
for y=0 to YSIZE-1
for x=0 to XSIZE-1
map(x,y) = 0
next x
next y
REM ** Clear the screen... ;)
cls
REM ** Start drawing the labyrinth...
gosub drawmap
REM ** The main program... (will be later anyhow)
main:
print "DONE!!"
end
drawmap:
REM ** Just some Initializing.
cx = STARTX
cy = STARTY
REM ** Set the starting position.
map(cx,cy)=2
q=1
kanin:
REM ** Just prints some values for debugging...
ink rgb(0,0,0),rgb(0,0,0)
box 0,0,400,14
set cursor 0,0 : ink rgb(255,255,255),rgb(0,0,0)
print cx ;: print "," ;: print cy ;: print " - " ;
print oldx(q-1) ;: print "," ;: print oldy(q-1)
REM ** Reset the ways we can go...
for i=0 to 3
way(i) = 0
next i
REM ** Check which directions are ok to move into...
if cy>2 and map(cx,cy-2)=0 and map(cx,cy-1)=0 and map(cx-1,cy-1)=0 and map(cx+1,cy-1)=0 then way(0)=1
if cx2 and map(cx-2,cy)=0 and map(cx-1,cy)=0 and map(cx-1,cy-1)=0 and map(cx-1,cy+1)=0 then way(3)=1
REM ** This is the part that backtracks... supposedly...
REM ** Something seems to fail just around this area!
noway=1
REM ** If any of the ways are possible, then don't backtrack...
for i=0 to 3
if way(i)=1 then noway=0
next i
REM ** Else, backtrack please!!
if noway=1
q=q-1
if q=1 then goto done
cx=oldx(q)
cy=oldy(q)
goto kanin
endif
REM ** This part generates a random direction from the ones that are possible...
REM ** This part "seems" to work...
newdir:
ndir = int(rnd(4))
if ndir = old_dir then goto newdir
if way(ndir)=0 then goto newdir
REM ** These 4 if-statements updates the coordinates and saves the old direction...
REM ** It saves the opposite direction due to that it shouldn't go towards the old spot...
if ndir=0
cy=cy-1 : old_dir=2
endif
if ndir=1
cx=cx+1 : old_dir=3
endif
if ndir=2
cy=cy+1 : old_dir=0
endif
if ndir=3
cx=cx-1 : old_dir=1
endif
REM ** These saves the coordinates of the current block, for use with backtracking...
oldx(q)=cx
oldy(q)=cy
q=q+1
REM ** Updates the map-array and draws to the screen...
map(cx,cy)=1
dot cx,cy
sync
REM ** Go back and do it again...
goto kanin
done:
return
