Amazing new FIGgy program!

[Julian Skidmore]

Hi folks,

And literally so! I took a Computes! Maze generator and converted it
to FIGnition. It's just a little 3 screen program given at the end of
this email.

FIGnition can generate 23x21 mazes in about 3s per maze which isn't
bad. With a little bit of 3d code we could generate a program for you
to walk through a 3D maze, rather like the Jupiter Ace version.

How does it work? Well it's a pretty simple brute-force random maze
generator. We have the maze array which stores 128's in empty
locations and any other value represents a filled location in the
maze. At each step it just picks a random direction to go in and if
it's empty it calculates the new location and stores the direction in
the new location in the maze. If it was filled it tries for the next
direction in a clockwise sequence and if it gets back to the first
direction it backtracks.

Backtracking is pretty simply too: by storing the direction in each
new location we visit, it provides backtracking information, so to
backtrack we simply retrieve the direction in the current maze
location and move in the opposite direction (by subtracting rather
than adding its displacement). Eventually we'll fill the entire screen
with maze walls.

To set it up, we need to make sure the outer edges of the maze are
no-go areas, which we do by filling them with 0s (not empty).

The clever part about FIGnition's algorithm is that we don't need
special checks for when we backtrack to the start, instead we simply
define the direction at our starting position (which is (1,1) ) as 1
(=right) and then set maze[0] to empty. Then when we backtrack from
(1,1) we move left to (0,1) and do a search. The algorithm finds that
to the right it's filled, as is the bottom, as is the left (which
corresponds to the top, right corner of the maze). But then it finds
that (0,0) is empty so it moves there and since the terminating
condition happens before the move is displayed, the maze generation
stops.

The maze is plotted as though walls were the same width as the paths,
but in fact since the walls aren't used in the maze calculation they
can be replaced with any width walls, which is why a conversion to 3D
is pretty trivial (you can convince yourself of this by considering
the fact that all the walls are on even coordinates; which means you
could change their thicknesses without changing the maze itself).

Maze generation is good for chase games, e.g. the classic ZX81 3D
Monster Maze. The algorithm here only uses 1030b including 575b for
the maze array itself. Here's the code itself: (wall would be better
termed as 'empty').

128 const wall
25 const w 23 const h
6706 var d 6144 ,
0 var maze w h * allot

: backtrack
drop dup maze + c@
dup >r d + c@ 25 - -
r> ;
: findPass ( pos dir)
dup >r begin
over over d + c@ 25
- + dup maze + c@
wall = 0= while
drop 1+ 3 and
dup r = if r>
drop backtrack
dup >r then
repeat r> drop
; ( -- pos dir pos' )
513 var dxy 258 ,
1 , 256 , 257 ,

: passPlot ( x y dxy+dir)
dup >r 1+ c@ 1- + swap
r c@ 1- + swap
2dup plot r> ;
: passage ( pos dir)
dup + dxy + swap 0 25
u/ dup + swap dup +
swap rot passPlot
passPlot drop drop
drop ; ( --pos)

0 var seed
: rnd seed @ 1+ 75 *
dup seed ! u* swap
drop ;


: init
maze w h * -1 fill
maze w + 1+ h 2 do
dup w 2 - wall fill
w + loop drop
vram w h * 160 fill
0 maze w + 1+ c! 2 pen
wall maze c! ;

: gen ( cpos ) init
w 1+ 4 over begin
rot rot passage
4 rnd findPass
2dup maze + c!
dup 0= until drop drop
;

: mazes begin
clock i@ seed !
gen key 32 = until ;

--

                  The DIY 8-bit computer from nichemachines™

[Carl Attrill]

That looks great, so for a game, you would have to put a character on the screen at a start point, this could be where it is always empty.

dokey could move the char, and coll could see if the next move is into a wall, if it is it will not move there, but if its empty it can move on.

A timer could be added as a limit, and other chars on a loop could patrol the maze and if coll finds the value of this it could be game over.

One question, how many enemies can the program support? I never seem to work it out as the way I do it relies on two sprites moving at the same time and speed, ie blitz! the bomb and the planes use the same timeout delimiter

It would be great to do this with meanies in the maze in areas that need to be avoided.

 

[Tony Kingsmill]

Look a really good basis for a game :)

I remember doing something like this in Basic but I have to admit to me it looks a bit daunting in Forth..!

[Julian Skidmore]

Hi Carl,

>> That looks great, so for a game, you would have to put a character on the
>> screen at a start point, this could be where it is always empty.

Indeed, you'd want to draw thin walls to leave room for the UDG.

> dokey could move the char, and coll could see if the next move is into a
> wall, if it is it will not move there, but if its empty it can move on.

Coll is for collision? Yes. You can test to see if you

> A timer could be added as a limit, and other chars on a loop could patrol
> the maze and if coll finds the value of this it could be game over.

> One question, how many enemies can the program support? I never seem to work
> it out as the way I do it relies on two sprites moving at the same time and
> speed, ie blitz! the bomb and the planes use the same timeout delimiter

Well, as many as the computer has the performance for. Remember a game
is like a movie; so, there's only 1 pause between frames:

begin
MoveAllTheMeanies
doKey DoPlayer
speed @ timeout
gameover @ until

All the meanies move in the same frame using a loop moving one meanie
at a time, but without a pause between moving one meanie and the next
because we only need to see the meanies have moved at the end of the
frame (in the same way that actors in a film move simultaneously; they
don't wait for the previous actor to move before they take a step). In
reality because the computer only moves one meanie at a time there are
slight timing differences between each move, but the computer does it
so quickly the user won't notice - s/he just sees each new frame when
we pause in the main loop ( speed @ timeout ) .

In practice video generation makes it smoother than it might be.
FIGnition executes most of its Forth programs during the top and
bottom margins of the image; so when we move a number of meanies
several (probably all of them in our case) will move during that time
and the screen will only show the update when it regenerates the image
after the top margin. Have a look at the gdemo example:

https://sites.google.com/site/libby8dev/fignition/examples#gdemo

The command for moving all the characters is udgmove:

: udgmove ( lim -- )
0 do
i poz @ dup
vcalc ( old new )
swap 32 swap ic!
i 7 and over ic!
i poz !
loop ;

There's no pausing there! If there was a pause in the game it would go
in the gdem loop later in the program, but in gdem we just want to
know how many udgs we can move around in Forth before it slows down.
In practice we can move about 80 UDGs at about 10fps.

Hope this helps!

-cheers from julz

[Julian Skidmore]

Hi folks,

Supporting thin walls isn't too hard. We just use the box characters
15 (a line at the bottom and right), 14 (a line at the bottom), 12 (a
line at the right) and 32 to represent the various walls. They all
start off with character 15 and when we move through the maze we punch
holes in the walls. Moving right turns a 15 into a 14 or a 12 into a
32 on the current square, moving down turns a 15 into a 12 or a 14
into a 32; moving left or up is the same, but it affects the location
we're moving to rather than the current square. As you can see, the
mazes look better - this is the kind of thing you'd need for a 2D maze
game with UDG characters.

You can see thin mazes look great!

: passage ( pos dir)
swap over 2 and if

over d + c@ 25 - +

then vram + dup ic@ rot
1 and dup + 1+ - dup
12 < if drop 23 then
swap ic! ;

: init
maze w h * -1 fill

vram w h * 160 fill

maze w + 1+ vram 26 +
h 2 do swap dup w
2 - wall fill
w + swap dup w 2 -
15 fill 25 +
loop drop

0 maze w + 1+ c! 2 pen
wall maze c! ;

0 var seed
: rnd seed @ 1+ 75 *
dup seed ! u* swap
drop ;

: gen ( cpos ) init

w 1+ begin

4 rnd findPass
2dup maze + c!

rot rot passage