Trying to convert JavaScript to ASM....

[PacManPlus]

Hi guys.

 

I actually spent the entire day today (I took a PTO day from work) to try and work on this and I haven't been able to get anywhere.

Here is a Pac-Man maze generator written in JavaScript: https://shaunlebron.github.io/pacman-mazegen/

 

He did an excellent job with this; he talks about how he only uses certain pieces ('T', '|', '+', and 'L') rotated to fit (like 'Tetris'), but I noticed that some pieces have longer ends than others, and that's just one of the things I'm not understanding about this.  How does he decide which pieces get a longer edge?  Which edge?  If you right-click and choose 'view source' you can see the JavaScript source code used to do this.

 

I've decided that it would be better to understand the steps involved to do this and write my own 'version' of the maze generator rather than try and convert Java Script to 6502.  Trouble is, I don't follow some of the steps involved (like what I mentioned above).

Can anyone look at this and put this into steps so I can try and get this going?

Thanks, guys

Bob

Edited April 17, 2020 by PacManPlus

[RevEng]

I was hoping you'd get a more informed reply, but no luck so far. Maybe my bump will get some more eyes on it.

 

I think you're entirely right that there's no reasonable way to literally translate this to 6502, and instead you need to embody the general principals. For one, the edge of the tetris block is supposed to represent the path travelled and the center of the block is supposed to represent solid stuff, and those paths can be stretched or grown - pulling that dual representation on the 6502 out of a block array will be a bit of an unnatural act.

 

The source is pretty abstruse and long, and javascript isn't my wheelhouse, but I'll give an overview of some principals a shot. A lot of my comments here are based more on his overview comments and intermediate result displays, rather than fully gleaning details extracted from the code, so it's bound to be a bit wrong and superficial. It looks to me like the source doesn't match his own high level description - e.g. he doesn't seem to be dropping tetris pieces so much as growing tetris-like pieces into open areas. Since you need to re-implement, I think it's easier on us both to just use his high level description and infer rules from source where possible, even though this doesn't exactly match his source. 

 

1. drop the randomly selected tetris pieces from right to left into the 5x9 grid - pieces are tetronimos plus 3, 2 and 1 block pieces. The 1 block pieces are only allowed to exist in the top and bottom row, and even then only one is allowed in each of those areas.

2. Grow dropped pieces to fill unused spots - no piece can grow more than 5 cells.

3. mirror the 5x9 grid over the leftmost row to 9x9, and then scale 3x. This leaves you with 27x27, which needs to become the 28x31 pac-man tile grid, but according to the author it's one tile row and column short, so on to height and width adjustments, where some 3x3 tiles become 3x4 or 4x3 (or 4x4 if adjusted vertically and horizontally), in the next step. (I'm not sure how 28 vertical tiles becomes 31 vertical. maybe he's counting score area)

4. height adjustment...
pick one desirable-candidate block from each column, to grow vertically. Which blocks are desirable-candidates depends on the piece they're in:
  -blocks in pieces with one or two blocks are always fair game to grow.
  -blocks in pieces with three or more blocks, without horizontal neighbors, are desirable-candidates.

5. width adjustments...
pick one desirable-candidate block from each row, to grow horizontally. Which blocks are desirable candidates depends on the row and the piece they're in:
  -blocks in column 0 (left-most) are never valid candidates.
  -blocks in pieces with one or two blocks are always fair game to grow.
  -blocks in pieces with three or more blocks, without vertical neighbors, are desirable-candidates.

6. Do special case fixes for tunnels. (haven't dug into this yet)

 

Here's where I would start, to try and replicate the overall basic concept in 6502.

i.e.

1. drop tetronimos into the 5x9, picking the leftmost empty spot as the landing spot, and rotate the selected piece as required. Tetronimos here are extended to include one and two block pieces, though those should be limited in probability. I don't think you should grow pieces, at least not initially, because this complicates your grid->tile-grid conversion.

2. for gaps where tetronimos didn't fit together, add in one or two blocks.

3. have basic 1:1 rules for converting the 9x9 grid to tiles.

[see what you get]

4. add some specific-case rules for changing tiles in each 3x3 grid to make connections, based on observations

 

I think I might be inclined to see if I could skip the 3x3->3x4/4x3 expansions. Really I think you're just going to have to get your hands dirty with the above approach, and work through problems on the fly, since nobody has a roadmap for this 6502 problem-space.

 

This is all still quite a tangle to deal with, but maybe I've given you a thread or two to pull on.

[swapd0]

Maybe you can convert it to C, use the cc65 compiler and have a look at the source code.

Edited April 19, 2020 by swapd0

[PacManPlus]

Thanks guys...

 

I'm looking...  BTW, RevEng, I understand where he gets the 5x9 grid - the outside paths are also valid, which means out outermost walls (even though they aren't accounted for in the 5x9) are there also.  So you get the 27 + another 'cell' of 3 for the outsize walls to = 30.  Then we need the 'expansion' of one cell to be '4' tiles and then we have 31.

 

BTW, did you know that the Pac-Man maze actually allows for 32 rows but only uses 31?  You can see this in Hangly-Man, where the 'empty' maze has the exit at the top.  This is the only time that the top row is used.  For two lousy maze pieces.

[RevEng]

Didn't know that about it using 32 rows, but I'm not surprised you do.     ⍩⃝. ?   

 

I wonder if you could exploit that to avoid the vertical expansions, and instead just use a 5x8 grid with 3x4 tiles. That may stretch the maze elements too much, but might be worth looking at.

 

Or perhaps still use 5x9 expanding to 28x31, and pre-defined 3x4 piece versions of the 3x3 pieces could be used to easily do the vertical expansion.

 

 

 

[PacManPlus]

Ok, with regard to this step-by-step picture:

 

I am almost complete with the 'Simple Model'.  I am generating the following:

     

 

NOTE: I am using the left side instead of the right side of the maze as that is how my mazes are stored in the game.

Legend:

(C) = Blank Cell

Filled In Location = Monster Pen

A = T FACING RIGHT: ├

B = T FACING DOWN: ┬

C = T FACING LEFT: ┤

D = T FACING UP: ┴

E = L FACING RIGHT: └

F = L FACING DOWN: ⌐

G = L FACING LEFT: ┐

H = L FACING UP: _|

M = PLUS SIGN: ┼

N = BOX: █

O = HORIZONTAL BAR: -

P = VERTICAL BAR: |

 

The (C) characters at the top-most, left-most, and bottom-most cells I can extend the outer maze wall into.  It's the ones in the other areas I will have to pick a surrounding cell to extend into.  OR, I could just use a single cell wall like they do in some bootlegs.

 

Also, I am probably only going to use the 30 rows so I don't have to worry about extending one of the tiles downward and just keep what I've got.  The columns I'll obviously have to reduce by one, so I'll need to figure that out.

 

 

 

 

Side Note, @RevEng  Do you know how long it took me to realize that your avatar changes color?  I had this screen up on my other monitor while I worked on PMC_XM on the main one.  Out of the side of my eye I kept seeing *something* change on the other screen.  Couldn't figure out what it was until I just had enough and stared at this page until I saw your avatar change colors.  Very cool. and sneaky.

 

 

[PacManPlus]

Ok, I've already changed a bunch of things since posting this...

 

[RevEng]

1 hour ago, PacManPlus said:

Couldn't figure out what it was until I just had enough and stared at this page until I saw your avatar change colors.  Very cool. and sneaky.

Huh, don't know what you're talking about. Maybe you've been working too hard.

 

 

 

 

Glad to see you making great progress. Those simple models look like tetris boards to me.

[PacManPlus]

Here we go again...

 

Ok with this as a starting point:

 

 

I believe I now have the 'Simple Model' Done.  It's not quite as elegant as his, but it works:

     

 

No empty cells.

LEGEND:

A = T FACING RIGHT: ├

B = T FACING DOWN: ┬

C = T FACING LEFT: ┤

D = T FACING UP: ┴

E = L FACING RIGHT: └

F = L FACING DOWN: ⌐

G = L FACING LEFT: ┐

H = L FACING UP: _|

I = PLUS SIGN: ┼

J = BOX: █

K = 2 CELL HORIZONTAL LINE: -

L = 2 CELL VERTICAL LINE: |

M = OUTER MAZE EXTENSIONS INWARD (TOP AND BOTTOM)

N = OUTER MAZE EXTENSIONS INWARD (LEFT AND RIGHT)

O = SINGLE CELL WALL (LIKE THE 6 CIRCLES IN HANGLY-MAN)

 

I'm ready to take this to the next step.

 

[PacManPlus]

 

I got the random mazes finally.  Now it's just adding side tunnels (if needed) and dots:

 

   

 

   

 

Took me two weeks (including a PTO day from work) to do this. ugh.

 

Notes:

- After this, the next step is adding the incredible sounds/music done by @tep392 - you guys are going to be blown away!

- 'The Largest Pac-Man' is not going to be a 1:1 port.  Namely:

  * No two player simultaneous play (alternate will still be there).  I don't have enough sprites for that - we would start to get 'disappearing' acts.

  * No maze cycling color.  It interferes with Inky's color, and the 'Blue monster' color as well.

  * I do want to keep the ever changing / bouncing fruit, the bonus screen at the end of the level, and the 'random' direction the monsters take when coming out of the pen...  and as much of the other aspects of the game that I can.

 

Then there's only:

- Adjust scatter times

- Rewrite monster 'destination tile' algorithm

- Keep an eye on player moving through the monsters... it doesn't seem to happen as much now.

 

It's almost time for a ROM.

 

Bob

 

EDIT...  Maybe a ROM earlier than I thought.  I'm going to need debug help with this one.  There's *ONE* instance where the random maze fails.  When it does, the screen goes black (because the maze piece picking routine is in an endless loop trying to fit specific pieces in the maze.  I'm going to put some display debug statements in, as this is going to be VERY difficult to catch.  growl.  All I'll need is the numbers you will see on the screen.

Edited April 26, 2020 by PacManPlus

[RevEng]

Those boards look super-legit, Bob. Kudos on pulling off the super-slim 6502 variant of the tetris algorithm. ?

[SlidellMan]

I see something Grade Amazing in development...keep going, Mr. DeCresenzo!

[PacManPlus]

Hey Guys!

 

Ok, I have the random maze part completed.  I actually had to manually create the side tunnels, and there are some rare instances where there aren't any!  (It's ok, though, the fruit comes through the wall for Ms. Pac-Man)

 

Anyway, I have a STRANGE issue that I'm dealing with: I turn off the screen when generating a maze (as to not display garbage on the screen while doing so).  I use this routine (from GCC themselves):

;	TURN THE SCREEN OFF WITHOUT ZEROING THE SCREEN
SCREENNO
	JSR WAITVBL									;WAIT TILL VBLANK STARTED
	LDA #$7F									;TURN GRAPHICS OFF
	STA CTRL
	LDA #$00
	STA SCRNSTAT								;ZERO SOME STATE
	RTS

 

I'm finding that sometimes (I would say 1 out of every 100 times) the game crashes while creating a maze (while the screen is off).  In troubleshooting this, I turned the screen back on to show some display statements.  However, when I turn the screen back on, the issue *NEVER* happens.  I've left it on for hours and it's fine.

 

As soon as I take the call to turn on the screen out, it happens after a few runs (like I said, about 1 out of every 100 times it has to create a maze).

This is the routine to turn on the screen:

;	TURN THE SCREEN ON
SCREENON
	LDA SCRNSTAT								;SEE IF SCREEN WAS EVEN OFF
	BNE SOOUT
	JSR LOADER									;INITIALIZE KERNAL STATE
	JSR WAITVBL
	INC SCRNSTAT								;SAY THE SCREEN IS ON
	LDA #KGRAPHON
	STA CTRL									;TURN GRAPHICS ON
SOOUT
	RTS

Now, I've tried just calling 'loader' and 'waitvbl' while the screen is still off, but that doesn't help.

I have not tried this on the real thing yet... and I'm using A7800 to test with.

 

WTH is going on?

 

Thanks, Bob

Edited April 29, 2020 by PacManPlus

[RevEng]

That looks fine to me. I know your WAITVBL routine waits for VBLANK to be disabled, and again waits for it to be enabled, so that rules out an edge case where you happen catch the ending edge of VBLANK.

 

I'd say code up a version that repeatedly generates the mazes and enables the display for a frame or two. If that reliably crashes, then you run it through a7800 with the all executed 6502 instructions being traced to a file. After it crashes, you stop it. Then just open up your trace text file in an editor, and starting reading it backwards from the end.

 

I'd be glad to show you the ropes with the above, or you could look into it solo, or I'd be glad to run it for you. I'd recommend the first two, mainly because once you get your feet wet, the debugger really does help track down a good deal of hair-pulling issues.

[PacManPlus]

ugh....

 

 

It's not doing it when I run it in debug either.   

But when I don't run it in debug...

 

EDIT - ok - hold on...  I got it to happen with debug ... but the file is almost 2Gb...  I'll be back

 

Edited April 29, 2020 by PacManPlus

[PacManPlus]

Question:

 

In the debugger, how do I just show the contents of a RAM location?  E.G. I just want to see what is in the address $40 while the program is stopped.

 

Thanks!

 

Edited April 30, 2020 by PacManPlus

[PacManPlus]

Wow, this is VERY odd.

 

So, it's looking like my Pseudo Random Number Generator is skewed.  I've used that same random number generator in every single game and this is the first time I've had an issue with it.

Every single time it's picking either a variation of 3 or 7 (I do an AND #$07), both of which are invalid numbers.  Very strange to watch happen.

 

To be exact, it's picking these numbers in this order:

$83,$AB,$2F,$DB,$0B,$E7,$F3,$DB,$CF,$AB,$7B,$27,$A3,$CB... and so on.

If you look at the second nybble, you can see that it gives the pattern 3, 3, 7, 3, 3, 7, 3, 3, 7, etc.  when ANDed with $07.

 

This is my PRNG:

;	RANDOM NUMBER GENERATOR - BOTH MAKES A NEW ONE AND LEAVES IT IN A
;	INPUT: NONE
;	OUTPUT: NEW RANDOM NUMBER IN A AND IN NEWRAND
;	USES: A, OLDRAND, NEWRAND
RAND
	LDA OLDRAND									;PREVIOUS RANDOM NUMBER OF PREVIOUS RANDOM NUMBER
	ADC RTLOCAL+1								;FRAME COUNTER
	ADC NEWRAND									;PREVIOUS RANDOM NUMBER
	PHA
	LDA NEWRAND									;PUT PREVIOUS RANDOM NUMBER INTO PREVIOUS PREVIOUS RANDOM NUMBER
	STA OLDRAND
	PLA
	STA NEWRAND									;NEW VALUE - LEFT IN A, AND STORED AS PREVIOUS RANDOM NUMBER
	RTS

It looks like I'll need a better random number algorithm.

Edited April 30, 2020 by PacManPlus

[RevEng]

1 hour ago, PacManPlus said:

Question:

 

In the debugger, how do I just show the contents of a RAM location?  E.G. I just want to see what is in the address $40 while the program is stopped.

 

Thanks!

 

In the debugger "Debug" menu, pick "New Memory Window". The memory window will display the 6502 address space, and it will update in real-time and while stepping too. A few tips... In the menus in the memory window you can fine tune how many bytes are displayed per column. Clicking on any of the memory values will drop a highlight there, so it's easier to pick out from the other locations.

[RevEng]

1 hour ago, PacManPlus said:

It looks like I'll need a better random number algorithm.

I'd give an LFSR a shot. The 16-bit one in bB, which came to 7800basic, is pretty good...

 

randomize
     lda rand
     lsr
     rol rand16
     bcc noeor
     eor #$B4
noeor
     sta rand
     eor rand16
     rts

...even LFSRs can run through a bit of regular patterns with ANDing, though I've never seen it bad as the problem you ran into with yours.

 

[PacManPlus]

Thank you RevEng - although this one seems to be worse; it crashes *every* time, and looking at the trace (and the memory locations) it seems to return all variations of %XXXXXX00 when ANDed with $03 (in this case).

 

I think I need to somehow put some sort of safety in there when this happens.

What it's doing in this section is randomly choosing a maze shape, and seeing if the 'cells' are free to place this shape.  i.e. it's looking at row3, column4 and seeing if a left-down elbow ┐ will fit.  So it checks the 'cell' to the left and the 'cell' below.  If it won't fit, it goes back to the routine and randomly chooses another shape.

 

Each 'column' has it's own set of shapes to choose from, depending on the 'row' it's on as well (that 5x9 one from above).

 

EDIT: Update - so I did an 'ADC RTLOCAL+1' (the frame counter) and then a 'CLC' in between 'NOEOR' and 'STA RAND' above and it seems to work so far.

After all this I don't trust that completely though.  I'll still need to figure out some sort of safety net when doing this.

 

EDIT2: Been running for about an hour... so far so good! 

Edited April 30, 2020 by PacManPlus
Update on issue

[RevEng]

2 hours ago, PacManPlus said:

Thank you RevEng - although this one seems to be worse; it crashes *every* time, and looking at the trace (and the memory locations) it seems to return all variations of %XXXXXX00 when ANDed with $03 (in this case).

Oh, I should have mentioned that it needs to be initialized with non-zero values. If it starts with 0 it will remain 0.

 

Anyway, great that you resolved it with your code. ?

[PacManPlus]

oops... guess I should have seen that huh? (sorry)

 

anyway, thank you - and it's still running!

Edited April 30, 2020 by PacManPlus

[RevEng]

I should have mentioned it.

 

I'm stoked that you figured your issue out with a bit of help from the debugger. Another tool in your kit now. ?

[PacManPlus]

Yes - thank you so much for showing this to me.  Is there a way I can use the debugger to tell if I'm using too much CPU time per frame?  (i.e. my routines that should happen within one frame are actually overrunning into another frame)...

 

Thank you so much!

Bob

[RevEng]

You're totally welcome!

 

To do that from the debugger solely, I think there's too many high level concepts to encode. i.e. what constitutes a frame, and what constitutes too much time.

 

You can help the debugger figure out that with a little extra code. If your frame based routines are initiated from an interrupt, just increment a "frameskipped" variable at the start of the interrupt, and decrement it at the end of the interrupt. If your frame based routines are initiated in a main loop, increment "frameskipped" at the start of the loop and decrement it somewhere in the interrupt. If at any time "frameskipped" is bigger than 1, you've missed a frame. This is something you can either look for in the memory window, or you can set a watchpoint that specifically checks for the wpdata>1. (see this reference for an example of the latter)