"Sierra Maestra", an Early WIP

[Thomas Jentzsch]

Just like you, I am creating a 2D world in "The Stacks" using a 16-bit LFSR too. When moving between columns (in worlds with too many rows), I am simply adding a (synchronized!) blank frame. There I have plenty of time to calculate everything I need.

 

And alternative would be speculative pre-calculation, based on the players current position. So when he is e.g. closer to the right, you use some spare time to forward a bit each frame. That's a bit more complicated and you need another set of variables.

Edited April 1, 2018 by Thomas Jentzsch

[bogax]

 

As I am writing this, I'm wondering if it isn't possible somehow to "buffer" the surrounding screens of the current screen the player might be inhabiting. Calculating the left and right screen only requires one iteration of the feedback register. I wonder if there's a mathematical trick to reduce the amount of cycles required to go through in order to calculate a new Y-index of the overworld, instead of a new X-index. Perhaps a lookup table? A lookup table could perhaps be used to do multiple loops through the feedback register, just a row up and a row down. It might be possible to do some algebra and find out what XOR $D4 to XOR $D4 to XOR $D4 to an unknown number is...

 

Otherwise every movement up or down a Y-index is a full-row's worth of screens' calculations...

 

There has got to be a faster way... Feel free to jump in and give your two cents!

 

==

 

 

This is what you want jumpf2.pdf (warning: the math is kind of dense )

 

This one deals with LCGs anl-rn-arb-stride.pdf

 

This one also deals with LCGs but it has a couple of paragraphs (mostly I'm just throwing it in 'cause it's a good read ) hmc-cs-2014-0905.pdf

 

 

edit: not sure I understand what you're doing Why not just run two polynomial counters, one for X and one for Y?

better yet if you've got the ROM just run two counters and look up the room configuration ie a mapping from

a straight counter to (something like) your polynomial counter's state except it could be completely arbitrary

and taylored more to what you want the rooms to be instead of what you'ld get from the polynomial counters

Edited April 1, 2018 by bogax

[vidak]

Holy shit! Thanks Bogax!

 

Also thanks Thomas Jentzsch!

 

I'm not too bad with maths - so I may be able to wrap my head around this.

 

I was thinking about running 2 counters in each dimension, but the problem is that doesn't necessarily solve the problem - it would only give you one row and one column of the world.

 

For instance, you would get the same value on every Y coordinate of a /different/ X coordinate. So you'd move left and right, and the Y random number would stay the same.

 

You could combine the two counters though... I wonder if XOR with a proper tap would create a sufficiently random but reversible number...

[JeremiahK]

Hey, vidak! I am also back from quite a long break, haha.

I am glad to know that you are over the other side of this depression bout. I had to quit my first job over a year ago, and I was out of work for 10 months. It could have been a lot worse, but I would say I had a bit of depression, as well. Thankfully, I now have a better job that I am enjoying, and have some side projects going on as well, training for an upcoming marathon, learning to play guitar, and building my first AR-15, to name a few. Today I had the day off for Easter, and I am off tomorrow, as well. This will be my first time having two days off in a row, so I hope to spend some time on my game tomorrow.

 

I took a look at your latest .bin, and I see you have completed the player movement and animation. Looking good! I will have to pay attention to how you generate your random numbers, it sounds promising.

Edited April 2, 2018 by JeremiahK

[vidak]

From looking at the Jump2 paper Bogax posted, it does look like one can come up with a simple mathematical function for a vector of fixed number of jumps forwards and backwards on a Linear Feedback Shift Register.

 

However Ockham's Razor would really favour the "single blank frame every screen transition" solution. You'd have 192x76 cycles to play with.

 

I am really intruged by the maths of the fixed jump number vector though.

 

I am gonna experiment with the math function just for fun, to see if it can fit into overscan. Why not have a bit of fun? It would make for insanely large RNG worlds if combined with the blank frame method.

 

This is very typical of me, I make things way more difficult than they have to be.

 

Another method that occured to me is to have maybe 2 8 bit counters, and swap between them when you move off the edge of one of them - like what happens in Fallout 4 - you only load certain areas into memory when you're actually in them.

[vidak]

Hey, vidak! I am also back from quite a long break, haha.

I am glad to know that you are over the other side of this depression bout. I had to quit my first job over a year ago, and I was out of work for 10 months. It could have been a lot worse, but I would say I had a bit of depression, as well. Thankfully, I now have a better job that I am enjoying, and have some side projects going on as well, training for an upcoming marathon, learning to play guitar, and building my first AR-15, to name a few. Today I had the day off for Easter, and I am off tomorrow, as well. This will be my first time having two days off in a row, so I hope to spend some time on my game tomorrow.

 

I took a look at your latest .bin, and I see you have completed the player movement and animation. Looking good!

Thanks man!! The AR-15 sounds super cool!

 

I have loads of cycles left over in the kernel, so I will return at put more stuff in!

[Thomas Jentzsch]

One question: Do you really only want to jump forward in number generation? Or isn't there something more happening between screens, like e.g. updating other counters which make the screens depend on each other?

[vidak]

At this stage, all I want to do is increment and decrement the random number generator.

 

I have variables for controlling map movement and map coordinates, and I suppose I can add "teleportation".

 

I will have variables for controlling the number of soldiers in your company, but the whole point of the game is to walk around the randomly generated world at this point.

 

It's just an overworld, at this stage.

 

I'm not sure if that answers your question?

[Thomas Jentzsch]

Partially.

 

If you plan to add more to the game later, than abbreviating the random number calculation might not help you. At least in "The Stacks" it wouldn't work. There I have to do calculations for each intermediate screen. E.g. there are things to pick up, which are also randomly generated. There I have to keep track, about the number and which have been collected.

[vidak]

Riiiigght - well in this game you don't pick up items, you don't have an inventory, and you only really have HP - but I don't like the idea of "loss" in games, so I think i will only count conquering a finite number of bosses.

 

Having items and upgradable weapons sounds fun, but I don't want to put them in this game.

 

I think the only other thing I can think of to also include would be randomly generated playfield graphics - so that some parts of a map look more like rocky mountains, some others look more like jungle, and others the beach.

 

But that would require adding to the kernel, and I am not focusing on that right now.

 

Thanks for the communication. It makes me feel more positive.

[vidak]

Okay!

 

Remember the git repository is here:

https://github.com/bootlicker/guerrilla-game

 

I have written the code for:

• Walking off the side of one screen and entering in on another
• Updating the map coordinates (I may make a mini-map)
• Created the structure for the code to swap out the kernel and draw the blank frame
• Updated the placeholder graphics to include 2 digits - the kernel will draw $00 to $40, as there are 64 unique objects in the overworld

I still have to:

• Create the logic to switch out the kernel and draw a blank frame on screen-change
• Link the random number generator to the Environment Graphics pointers

Then the scaffolding of the randomly generated overworld will be finished, really. A demo should be available after these things have been achieved.

[vidak]

Open World Atari 2600 Game Progress: Out of nowhere, I figured out how to simulate progressing from the beach, to the jungle, to the mountain in the game.

I am gonna use randomly generated "speckles" of playfield graphics on top of layered background colours.

What I will do is allow colours between certain vertical bands of screens up and down the map. I will just have a forward counting, non-rerversible polynomial counter for the random speckles. The playfield of course will be reflected.

[vidak]

Okay I have written the code for transforming the output of the 16 bit random number generator into (what I think are) unique indexes for the four zones to be drawn on the screen.

 

This is the code:

;=================================
; Forming the input of the Random Number Generator
;=================================

; Bit 5 of Map_Coords, the Up bit, is in the carry bit.
; The status register should look like this now:
;
; C76543210
; UXXXX0RLD

;==================================
;Is the UP flag set in Map_Coords?
;==================================

    bcc CheckRNG_Down   ; If UP flag not set, check DOWN flag
    ldx #0
    jmp ShiftBackwards
    
.CheckRNG_Down

    ror                 ; Put D in carry bit
    bcc CheckRNG_Left   ; If DOWN flag not set, check LEFT flag
    ldx #0
    jmp ShiftForwards
    
.CheckRNG_Left

    ror                 ; Put L in carry bit
    bcc CheckRNG_Right  ; If LEFT flag not set, check RIGHT flag
    ldx #255
    jmp ShiftBackwards
    
.CheckRNG_Right

    ror           ; Put R in carry bit
    bcc No_RNG    ; If RIGHT flag not set, then no flags set, then exit
    ldx #255
    
;=================================
; Wait for Vertical Blank to End
;=================================

; What we're going to do is use up a blank frame of kernel time
; in order to have enough time to calculate a full row of screens:
; 256 positions on the RNG counter.

	lda #$00        ; 2 13
	sta COLUBK      ; 3 16

RNGStartWait:
	
    sta WSYNC
;---------------------------------
	lda INTIM		    ; 4  4
	bne RNGStartWait    ; 2  6
	sta VBLANK		    ; 3  9 - Accumulator D1=0

;=================================
; Set timer for blank frame
;
; (192 * 76) / 64 = 228
;=================================

RNG_Timer:
	ldx #228
	stx TIM64T

;=================================
; Random Number Generator Routine
;=================================

; SHIFT FORWARDS 

ShiftForwards:
    lda Rand8   ; 3  3
    lsr         ; 2  5
    rol Rand16  ; 5 10
    bcc noeor   ; 2 12
    eor #$D4    ; 2 14 - $D4 is the only number I know the inverse to 

.noeor          ;
    sta Rand8   ; 3 17
    eor Rand16  ; 3 20
    
    inx
    clc
    bne ShiftForwards
    beq Pointer_Calc
    
; SHIFT BACKWARDS

ShiftBackwards:

    lda Rand8
    lsr
    rol Rand16
    bcc noeorleft
    eor #$A9    ; $D4 is the only number I know the inverse to 

.noeorleft 
    sta Rand8
    eor Rand16
        
    inx
    clc
    bne ShiftForwards
    beq Pointer_Calc

;================================================
; Translation of the output of the random number
; generator into a useful index for selecting
; a random object in ROM.
; 
; Here we:
; - Buffer the output of the RNG into RAM
; - Enter into a 4 cycle loop, which masks off
;   different portions of the 16 bit random number
;   so that a number between 0-63 is produced.
;
; This translates the random number output into
; an index that is 64 positions long, and allows
; us to randomly select 4 different objects from
; that 64 bit number.
;
; A second level of randomness could be introduced
; by generating an 8 bit random number, and masking
; THOSE bits off. But that would make the game
; impossible to seed the same way every time.
;
;================================================
    
Pointer_Calc:
    
    ldy #3
    
.Pointer_Calc_Loop

    ldx Rand8
    stx Rand_Pointer_Calc8
    
    ldx Rand16
    stx Rand_Pointer_Calc16
    
    cpy #3
    beq Band_3_Calc
    cpy #2
    beq Band_2_Calc
    cpy #1
    beq Band_1_Calc
    cpy #0
    beq Band_0_Calc
    
.Band_3_Calc

    lda Rand_Pointer_Calc16
    and #%11111100
    lsr
    lsr
    sta Band_3_Index

    jmp Done_Calc
    
.Band_0_Calc

    lda Rand_Pointer_Calc8
    and #%00111111
    sta Band_0_Index
    jmp Done_Calc
    
.Band_2_Calc

    lda Rand_Pointer_Calc16
    and #%00000111
    asl
    asl
    asl
    sta Rand_Pointer_Calc16
    
    lda Rand_Pointer_Calc8
    and #%11100000
    rol
    rol
    rol
    rol
    clc
    and Rand_Pointer_Calc16
    sta Band_2_Index
    
    
    jmp Done_Calc

.Band_1_Calc

    lda Rand_Pointer_Calc16
    and #%0011100
    asl
    asl
    sta Rand_Pointer_Calc16
    
    lda Rand_Pointer_Calc8
    and #%0011100
    rol
    rol
    clc
    and Rand_Pointer_Calc16
    sta Band_1_Index

.Done_Calc    

    dey
    bpl Pointer_Calc_Loop

My main concern is that masking off 6 bits from the random number generator output is actually reducing the number of random numbers from the generator.

 

I don't quite know the maths, but I am hoping that masking off 6 bits from the 16 bits is not actually making the output of the random number generator less random.

 

If it is reducing the randomness of the generator -- how else would one produce a random number between 0 and 2^6 four different times over 2^16 different screens?

 

My thinking was that 64 CHOOSE 4 combinations of objects is a larger number than 2^16, and that way there would always be a unique combination of 4 objects across the 2^16 screens.

 

The problem is, I don't quite know what mathematical function is being performed by masking off 6 bits from 16 bits.

 

Any ideas?

 

==

 

EDIT:

Is what is happening with my masking 16 CHOOSE 6 = 8008? Of which I am choosing 4 combinations?

 

Is the randomness of that choice then 6! or 6 CHOOSE 4? or is it 64! ?

There's an answer to this, but I have never been good at combinatorial logic and statistics...

Edited April 5, 2018 by vidak

[vidak]

Or it could be 65536 CHOOSE 64, which is enormous.

Edited April 5, 2018 by vidak

[vidak]

I think the solution is

 

(16 CHOOSE 6) * (16 CHOOSE 6) * (16 CHOOSE 6) * (16 CHOOSE 6)

which is 8008 * 8008 * 8008

 

which is enormous.

 

I think this is the correct solution.

EDIT: No, this is wrong, because the sets have similar objects within them.

 

Some of the sets have unique objects, and some of them don't...

Edited April 5, 2018 by vidak

[vidak]

Okay this is my new reasoning:

these are the four sets of AND masks:

1111110000000000
0000000000111111
0000011111100000
0011100000011100

So that should be, from the bottom (16 CHOOSE 6) * (16 CHOOSE 6) * (16 CHOOSE 2) * (16 CHOOSE 2)

Which is...

 

8008 * 8008 * 120 * 120

Which is... enormous. Far greater than 16^2. But that can't be right...

 

Or is it 6! * 6! * 2! * 2!, which is still enormous...

Edited April 5, 2018 by vidak

[vidak]

Someone on reddit says the number of unique combinations doesn't change! Apparently it's just 2^16.

 

What you put in, is what you get out, apparently!

[vidak]

Someone on twitter reports:

 

(16 CHOOSE 6) * 2^(16-6)

[zilog_z80a]

wow

Edited April 5, 2018 by zilog_z80a

[bogax]

You won't get more than 2^16 (2^16-1 actually 'cause you're using an LFSR)

you'd have 2^(6*4) possibilities with that many bits but they're not independent

there will be (are) overlaps.

[vidak]

Hmm.. well, I could be really careful and compute it, but I'm thinking the perceived randomness will be random enough. I'll try and get a working demo going, and if it is obviously not random, then I'll go back and try and fix it.

[vidak]

Okay. Spent another 3 hours on the game today.

Remember the source code is here:

 

https://github.com/bootlicker/guerrilla-game

 

Today I:

 

• Completed the logic for switching out the kernel, and for switching TO the kernel
• Fixed some bugs in converting the 16-bit LFSR output into four 6-bit numbers
• Restructured the code, and made lots of comments

I still have to:

• Translate the four 6-bit numbers into the pointers for four GRP1 objects

--

 

THEN I think a demo will be ready.

 

I am anticipating a LOT of bugs, and I predict the game will not compile the first time. This is the easy part: creating the final draft of the code. The awful part will be debugging everything.

[vidak]

For those interested, here is the source code as it currently stands

Season 2.zip

[vidak]

Also

• Bank Switching: I may split the overworld kernel between two banks, if I run out of space for graphics in one bank. But that is a hairy task

[vidak]

Did some more work today, but didn't finish setting up the translation of the output of the RNG into graphics pointers.

 

I am using hex debug symbols in place of proper graphics, and I have to do some masking to show $00 through to $40, and it seems I have to do that in the kernel.

 

Honestly what I think I will do is probably just create all the graphics first, because none of this nonsense about calculating the debug graphics in the kernel will actually be in the final kernel, and it is a lot of work that will in the end be wasted.

 

I would complete the game faster if I worked on graphics now, and just put them in the game, AND THEN tested the randomness of the open world.

 

Anyway, find attached the current source code.

 

==

 

PS. Someone has forked my source on github, which is flattering.

Season 2- 07 APRIL 2018.zip