Slow map woes (in BASIC)

[rje]

So I started to make my Scary Forest program more Roguelike... and the first thing I did was implement a "fog of war" on the map.

It's a great idea: don't draw the map!  Saves time!  Only draw new bits when you get within, say, 4 moves.  And then you can "see" monsters... and they can see you... and start lumbering towards you.  I mean this is a win-win, right?

 

So I'll tell you: it DOES improve the feel of the game... a LOT.  It adds some suspense.  It adds an exploration element to the game.  So there's emergent gameplay that I didn't realize was there.  Once I add treasure, it'll be a whole new ball game.

...BUT...

...What I've found is that even drawing a 9 x 9 map from a 2D array, then handling player and monster movement, is too slow.  Yeah, even with the Commander X16, it's too slow.

 

I optimized.  I went memory-lazy and use an array of floats instead of ints.  I got rid of newline printing and went all cursor controls.  Up, down, left, right.  It helps.  But... it's still slow.  It turns out that adding a line of logic here and there really add up fast... and this is just PETSCII!

 

So I'm fishing for suggestions.  I've started asking myself what assembly language I can write to get the most speedup for the least amount of pain.  Maybe the map drawing routine: fairly straightforward, no funny checking of data and switching around, so not a big chunk of code.  I guess I'd POKE the map into a bank, and the ML would use ZP indirect indexing to find the right data, do a PLOT, and render the PETSCII.  Next square.  Do it from x-4 to x+4, y-4 to y+4.  Maybe?

Or maybe I should use sprites for the player and monsters?  They would sit "on top" of the map, so I wouldn't be drawing over it; surely that might help?

 

Anyone got better ideas?

 

Edited August 19, 2020 by rje

[TomXP411]

Here's an example of how to show and fill the second layer:

10 FOR P=$9F2D TO $9F33:READ A:POKE P,A:NEXT
20 DATA 96,128, 124, 0, 0, 0, 0,
30 COLOR 1,0:CLS
40 C=65:REM "\XC1"
50 POKE $9F29,$31
60 PRINT "\X13\X11\X11\X11\X11COLOR 1,6\X13"
100 FOR Y=0 TO 59:Y0=Y*$100
105 FOR X=0  TO 158 STEP 2:P=Y0+X
110 VPOKE 1,P,C:VPOKE 1,P+1,$51
120 NEXT:NEXT
 

The trick is the color: you need to use color 0 on the foreground layer to make the background layer visible. The simple way to make that happen is COLOR 1,0:CLS. This sets the foreground color to white, clears the background color, then clears the text layer. 

And you can hide the entire background at once with 

COLOR 1,6:CLS

Then expose parts of the background with COLOR 1,0 and then printing a block of spaces:

COLOR 1,0:FOR I=1 TO 9:PRINT TAB(X);"         ":NEXT

This is a rough example that includes clearing the fog of war as you move across the screen.... 

10 FOR P=$9F2D TO $9F33:READ A:POKE P,A:NEXT
20 DATA 96,128, 124, 0, 0, 0, 0,
30 COLOR 1,0:CLS
40 C=65:REM "\XC1"
50 POKE $9F29,$31
60 PRINT "\X13\X11\X11\X11\X11COLOR 1,6\X13"
70 IF VPEEK(1,0)=C THEN 200
100 FOR Y=0 TO 59:Y0=Y*$100
105 FOR X=0 TO 158 STEP 2:P=Y0+X
110 VPOKE 1,P,C:VPOKE 1,P+1,$51
120 NEXT:NEXT
200 COLOR 1,6:CLS:X=1
300 PRINT"\X13\X11\X11\X11\X11\X11\X11\X11\X11\X11\X11";
310 COLOR 1,0
320 FOR I=1 TO 9
330 PRINT TAB(X);"         "
340 NEXT
350 GET A$:IF A$=""THEN 350
360 IF X<70 THEN X=X+1:GOTO 300
400 COLOR 1,6

Everything up to line 120 is just setting up the background. 

200 hides the background.

300-400 clears the fog of war in a 9x9 grid.

In line 300, we reset the cursor and move it down by a set number of spaces (11, in this case)

Then in 310, we switch to color 1,0. This exposes the background layer when we draw a space character. 

320-340 draws 9 rows of spaces. 

350-360 just waits for a keypress and repeats the cycle. This gives you an idea of the timing of the process. 

 

 

 

 

[Johan Kårlin]

My first thought is to write a simple interrupt handler that is triggered on vertical blank. This avoids flickering. It checks a flag and updates a selected area of the map if  the flag is set. Finally it sets the flag to false. I would update the map by copying memory  directly to VRAM, no need to use kernal routines as I see it. Maybe you don't need to copy the color bytes? If that's the case  you will reduce CPU time by 50%.

In your Basic code, when the map should be updated - set the flag and also the row and the column of the topleft corner of the selected area by poking it somewhere in memory to pass the information to the ISR.

(Of course, the flag isn't really necessary, you can also choose to set row and col to -1 when update shouldn't be done.)

[SerErris]

Are you doing it in Basic? Maybe the drawing routines should be Assembler at least? Or you might want to translate into C and compile with CC65...

 

[TomXP411]

Take advantage of the second layer. Draw the fog of war on the character on the foreground layer and draw the map on the background layer. 

Then all you need to update is the character's position and to clear the fog around the character. That should go a bit faster, since you're not drawing everything all the time. 

As to moving the character and monsters: you could use sprites. You could also use VPOKE instead of direct printing. 

And personally, I would stick to BASIC. Even if it slows things down a little, part of the challenge is in doing a pure BASIC game, and if you can manage to keep the game in pure BASIC, you will have accomplished something pretty significant.

 

[DusanStrakl]

I wrote few games in BASIC and it can be done. Even with faster CPU speed you still have to design it very carefully though. Like you found out graphics is usually a bottleneck so whenever you can use hardware to help use it. So perhaps instead of continuously drawing to screen, try to load the whole map at once directly into VRAM and move around by scrolling which typically only requires couple of POKEs instead of drawing. In my experience any time you have to do X times Y loop for drawing from BASIC it is time to reconsider the design.

If assembly is an option of course that changes everything but it is not a BASIC game anymore and that is a special kind of challenge.

Perhaps some of the examples and resources from my blog would be helpful:

https://www.8bitcoding.com/p/commander-x16.html

 

[rje]

5 hours ago, TomXP411 said:

Take advantage of the second layer. Draw the fog of war on the character on the foreground layer and draw the map on the background layer. 

Then all you need to update is the character's position and to clear the fog around the character. That should go a bit faster, since you're not drawing everything all the time. 

That speeds things up quite a bit.  Thanks!

Edited August 19, 2020 by rje

[rje]

Brilliant, Tom, thank you.  I'm slowly working your code sample out.

I wish there were a "code" or "monospace" format in this forum.  Is there?

 

10 REM
20 REM  SET UP VIDEO REGISTERS
30 REM
40 POKE $9F2D, %01100000 :REM MAP HEIGHT=1, WIDTH=2 = 64X128 TILES
50 POKE $9F2E, %10000000 :REM MAP BASE ADDR = 128 X512 = $10000.
60 POKE $9F2F, %01111100 :REM TILE BASE ADDR = 31 X2K  = $F800.
70 REM ALSO, TILE HT=0, WD=0, SO 8 PIXELS X 8 PIXELS

80 REM
90 REM  NO SCROLLING, PLEASE ($9F30-$9F33)
100 REM
110 POKE $9F30, 0
120 POKE $9F31, 0
130 POKE $9F32, 0
140 POKE $9F33, 0

150 REM
160 REM   BUILD FOREST
170 REM
180 COLOR 1,0 :CLS  :REM SET BACKGROUND MODE
190 FO(0)=$41 :REM "\XC1" (TREE)
200 FO(1)=$2E :REM DOT
210 FO(2)=$2E :REM DOT

220 POKE $9F29, %00110001 :REM $31=LAYERS 1,0. OUTPUT MODE=1 (VGA)
230 PRINT "\X13\X11\X11\X11\X11COLOR 1,6\X13"
240 IF VPEEK(1,0)=FO(0) GOTO 380
	260 FOR Y=0 TO 39
270    Y0=Y*$100
280    FOR X=0 TO 158 STEP 2
290       P=Y0+X
300       VPOKE 1,P,FO(RND(1)*3)  :REM CHARACTER INDEX
310       VPOKE 1,P+1,$15         :REM BG/FG COLOR NYBBLES
320    NEXT
330 NEXT
340 VPOKE 1,0,FO(0)  :REM 0 IS ALWAYS A TREE

350 REM
360 REM  HIDE BACKGROUND
370 REM
380 COLOR 1,6 :CLS

390 REM
400 REM  SET PLAYER POSITION
410 REM
420 X=10 :Y=10

430 REM
440 REM   CLEAR FOG IN A CLEARED 9X9 GRID
450 REM
460 PRINT "\X13"; :FOR D=1 TO Y: ? "\X11"; :NEXT
470 COLOR 1,0
480 FOR I=1 TO 9
490    ? TAB(X); "         "
500 NEXT
510 GET A$ :IF A$="" GOTO 510
520 IF X<70 THEN X=X+1 :GOTO 460
530 COLOR 1,6

 

Edited August 20, 2020 by rje

[TomXP411]

That's interesting. I couldn't figure out how to set a code style. But you seem to have found it. That's good. (And yes - a programming forum definitely needs a CODE tag or style.) (Ah... the BBCode CODE tag works)

Another tip for vertical positioning:
    Create a string early on with a HOME and 60 DOWNs. 

PY$="{HOME}{DOWN}{DOWN}...{DOWN}"

Then just print a substring of that string to position the cursor later:

PRINT LEFT$(PY$,Y);TAB(X);"This is on row Y, column X"

When Y is 1, it will just print the HOME. When Y is 2, it will print HOME and one DOWN. And so on. That's a bit quicker than using a for/next loop to position the cursor.

 

Edited August 20, 2020 by TomXP411
Adding image

[rje]

4 hours ago, TomXP411 said:

Another tip for vertical positioning:
    Create a string early on with a HOME and 60 DOWNs. 

PY$="{HOME}{DOWN}{DOWN}...{DOWN}"

Then just print a substring of that string to position the cursor later:

PRINT LEFT$(PY$,Y);TAB(X);"This is on row Y, column X"

 

 

O. M. G.  brilliant, thanks.   To think that I didn't figure that out 35 years ago... sheesh.

[TomXP411]

2 hours ago, rje said:

 

O. M. G.  brilliant, thanks.   To think that I didn't figure that out 35 years ago... sheesh.

To be fair... you shouldn't have had to. Commodore actually has a PLOT function (set cursor location) in the KERNAL. That really should have been exposed as a BASIC command. I have no idea why it was not. 

 

[rje]

It occurs to me that, in order to be safe from the 2.0 garbage collector, I might want an array of position-strings... but I wonder if it matters.  (And, I read an ooold Butterfield article that hinted that BASIC 4.0 didn't have the GC problems that 2.0 has.  So, shouldn't we be forking 4.0?)

	po$(0) = "{home}"
	po$(1) = "{home}{down}"
	...
	po$(40) = "{home}{down}....{down}"         (forty {down}'s, you know)
	...
    

Edited August 22, 2020 by rje

[rje]

Now as for sprites...

OK, I wrote some sprite demo code for the X16... but I think it's r37 code.  And we all know that the VERA registers in r38 is a bit different. So.... maybe I want to wait.  Maybe I'd rather print PETSCII in front of the background layer.

 

ALTHOUGH, if I'm careful, maybe it only affects an offset, like so:

100 S0 = $5000                  :REM OFFSET
110 VPOKE $F, S0+0, %00000000   :REM LSB
120 VPOKE $F, S0+1, %10001000   :REM MODE=8BPP(7); ADDR = $10000(0-3 + LSB << 5)
130 VPOKE $F, S0+2, 220         :REM X = 220
140 VPOKE $F, S0+3, 0           :REM (X MSbit)
150 VPOKE $F, S0+4, 55          :REM Y = 55
160 VPOKE $F, S0+5, 0           :REM (Y MSbit)
170 VPOKE $F, S0+6, %00001100   :REM Z = LAYER 2, NO H/V FLIP (0,1)
180 VPOKE $F, S0+7, %01010000   :REM H=16(6-7), W=16(4-5)
200 FOR I = 0 TO 3519
210 READ X
220 VPOKE $1, I, X
230 NEXT
300 VPOKE $F, $4000, 1
	

Edited August 22, 2020 by rje

[rje]

Okay, we're moving the right direction!!

I've got the random forest (1/3 impassable trees), and the player placed in the de-fog zone.  

The trees are impassable, and there's a top and bottom border that's also impassable.

There are treasures and monsters scattered about, but they don't do anything.  There's also the Amulet of Yendor placed -- it also doesn't do anything.  These are all MAP features.  That means when monsters eventually "move", I'll have to VPOKE the map. I record the address of the monsters, and I only allow 32 monsters.  I haven't thought up a good way to "know" when the player is "near" a monster.  I can loop through the monster addresses, if it doesn't slow things down too much, or I can figure out something clever -- for instance, a quadtree-like approach to the monster locations, storing them into buckets based on general area of the map.

 

I've attached the importable BASIC, as well as the original listing, which I use because I'm old and spoiled on things like labels.  It's my own flavor, which I transpile with a Perl script -- again of my own making -- to Commodore BASIC.

 

 

scary-forest.lis scary-forest.bas

Edited August 23, 2020 by rje

[TomXP411]

If the monsters can walk over treasure tiles, then you need store their locations off-screen. 

The simple way is a pair of arrays: MP(x) for Monster Position, and TP(x) for Treasure Position. Store just the screen cell where the thing lives (ie: the VPOKE address) and loop through and VPOKE those back into the screen after your movement pass...

Assume MP is the Monster max index, so if MP=3 there are 4 monsters out there (0-4).  
MC is the Monster Character code. 

	1000 FOR I=0 TO MP 
	1010 VPOKE 1,MP(I),MC
	1020 NEXT

You can do the same thing for the treasure, refreshing the position of the treasure items to make sure they're visible. 

 

[rje]

On 8/22/2020 at 9:27 PM, TomXP411 said:

If the monsters can walk over treasure tiles, then you need store their locations off-screen. 

Ahhh, good point, I’ll have to worry about that.

Instead of a treasure array, I've got a “what the monster is standing on” array for restoring the tile when it moves.  This gives monsters the flexibility of, for example, crashing through “impassable” forest.

Currently, only monsters within +/-5 squares (x,y) of the player move... and they move toward the player.  It will be faster to just run through the monster array - I bet there will be less VPEEKing.

Anyway, the monsters move, and the player "picks up" treasures.  Monsters don't step on each other, so they tend to pile up when you're trying to run away.  That's a nice feature.  Monsters don't care about terrain features, crashing through the tree cover like it's not there.  That's a nice feature, too.  I want to NOT draw them when they're in the cover of the trees. 

The loop slows things down, so 75% of the time I skip over the current tile.  It's still slow, since there's a lot of VPEEKing going on.  I'll clean that up!

 

I'm going to rename this "rogue forest".

 

 

rogue-forest.lis rogue-forest.bas

Edited August 24, 2020 by rje

[rje]

I'm thinking I should store the map in an array, even though I'm also VPOKEing it into a layer, because VPEEKs are probably slower than an array lookup.  Am I right?

 

[rje]

Updated.  The monsters scurry towards you if you're in range, and they'll attack you.  You can't die, yet. 

The forest is a bit claustrophobic, often consisting of narrow corridors and small clearings.  Monsters can't step on you or other monsters, so they'll tend to block one another.  You can't step on them, either, so they'll also tend to block your way.  It's a feature.

Treasures are currently of two kinds: weapons and armor.  Armor is currently useless, but weapons boost your attack.

I am thinking that the Axe weapons should be able to clear bits of the forest, slowly.

The UI is still rough.

The Amulet of Yendor doesn't benefit you, yet.

...But it's getting there, and the game is still, encouragingly, responsive.

rogue-forest.lis rogue-forest.bas

Edited August 25, 2020 by rje

[rje]

I'm going to take this to a "Rogue Forest" thread, now that y'all've helped me fix the slow map!

[Ender]

Can someone explain why setting the color to 0 makes it use layer 0 if it's enabled instead of black? Is this documented anywhere?  I couldn't find it.

[TomXP411]

6 minutes ago, Ender said:

Can someone explain why setting the color to 0 makes it use layer 0 if it's enabled instead of black? Is this documented anywhere?  I couldn't find it.

It used to be documented in the VERA manual, but the manual has been re-written, since VERA changed a lot. It was also discussed at length on the Facebook forum. 

Short version is... you need some way to make a layer transparent, and using a color index was apparently the simplest way to do it. 

The color palette is easy enough to re-program, so if you do need a black background on the front layer, you can swap black with another color in the palette. 

[Ender]

6 minutes ago, TomXP411 said:

It used to be documented in the VERA manual, but the manual has been re-written, since VERA changed a lot. It was also discussed at length on the Facebook forum. 

Short version is... you need some way to make a layer transparent, and using a color index was apparently the simplest way to do it. 

The color palette is easy enough to re-program, so if you do need a black background on the front layer, you can swap black with another color in the palette. 

Ah I see. Makes sense, thanks.