can this z80 code be made faster?

صفحة 1/4
| 2 | 3 | 4

بواسطة ARTRAG

Enlighted (6923)

صورة ARTRAG

19-04-2009, 02:10

This code computes the field of view starting from (center) in a tile based map.
_hidden_map holds the actual map
_clear_map holds the map as seen from center

Could this code be faster ?

Does anyone have any FoV faster algorithm ?

global drawline
global _hidden_map,_clear_map
global center

wallchr equ 'X'
doorchr equ '#'

global viewsegments


MAPW equ 20
MAPH equ 20

    psect	text,class=CODE
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Input:
; center points to the center of the FoV
;Output:
; compute the FoV in 8 octants (split in 4 quadrants)

viewsegments:
        ld      bc,-MAPW+1      ; segment 1
        ld      de,(center)
        call    segxloopinc
        
        ld      de,(center)
        call    segyloopdec

        ld      bc,MAPW+1       ; segment 2
        ld      de,(center)
        call    segxloopinc
        
        ld      de,(center)
        call    segyloopinc
        
        ld      bc,MAPW-1       ; segment 3
        ld      de,(center)
        call    segxloopdec
        
        ld      de,(center)
        call    segyloopinc

        ld      bc,-MAPW-1      ; segment 4
        ld      de,(center)
        call    segxloopdec
        
        ld      de,(center)
        jp      segyloopdec
        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        
segxloopinc:
1:
        ld      a,(de)
        ld      hl,-_hidden_map+_clear_map
        add     hl,de
        ld      (hl),a
        
        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z

        push    de
        call    drawline
        pop     de

        inc     de
        jp     1b
        
segxloopdec:
1:
        ld      a,(de)
        ld      hl,-_hidden_map+_clear_map
        add     hl,de
        ld      (hl),a
        
        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z

        push    de
        call    drawline
        pop     de

        dec     de
        jp     1b

segyloopinc:
1:
        ld      hl,MAPW
        add     hl,de
        ld      a,(hl)
        ex      de,hl
        
        ld      hl,-_hidden_map+_clear_map
        add     hl,de
        ld      (hl),a

        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z

        push    de
        call    drawline
        pop     de
        jp     1b

segyloopdec:
1:
        ld      hl,-MAPW
        add     hl,de
        ld      a,(hl)
        ex      de,hl
        
        ld      hl,-_hidden_map+_clear_map
        add     hl,de
        ld      (hl),a

        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z

        push    de
        call    drawline
        pop     de
        jp     1b

where I have also:

global drawline
global _hidden_map,_clear_map

MAPW equ 20
MAPH equ 20


    psect	text,class=CODE

wallchr equ 'X'
doorchr equ '#'

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Input :
; DE = pointer in _hidden_map to (x-coordinate,y-coordinate)

;- draw one line-of-sight

drawline:
        
1:      ex      de,hl   
        add     hl,bc
        ld      a,(hl)
        ex      de,hl
        
        ld      hl,-_hidden_map+_clear_map
        add     hl,de
        ld      (hl),a
                 
        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z
        jp      1b        

Login أوregister لوضع تعليقاتك

بواسطة mth

Champion (507)

صورة mth

19-04-2009, 21:04


Could this code be faster ?

Does anyone have any FoV faster algorithm ?

I found some microoptimizations of the code, but if a faster algorithm exists that could be a much bigger gain.

segyloopinc:
1:
        ld      hl,MAPW
        add     hl,de
        ld      a,(hl)
        ex      de,hl
        
        ld      hl,-_hidden_map+_clear_map
        add     hl,de
        ld      (hl),a

You can avoid the "ex de,hl" by changing the code after it slightly:

segyloopinc:
1:
        ld      hl,MAPW
        add     hl,de
        ld      a,(hl)
        
        ld      de,-_hidden_map+_clear_map
        add     hl,de
        ld      (hl),a

        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z

If you reorder character numbers such that all blocking characters are lower/higher numbers than all non-blocking characters, you could use a single "cp" instruction and return on (non-)carry.

بواسطة mth

Champion (507)

صورة mth

19-04-2009, 21:12

Hmm, the "ld de,-_hidden_map+_clear_map" destroys DE while the routine needs it for the next iteration. So it would only work if you move the "push de" more to the front and replace the "ret" by a relative jump to "pop de ; ret". So it becomes a bit ugly, but faster.

بواسطة mth

Champion (507)

صورة mth

19-04-2009, 21:17

Alternatively, you could make the input value of DE a pointer into the other map and repeatedly switch between the two maps by adding "_hidden_map-_clear_map+MAPW" and "-_hidden_map+_clear_map". The you don't have to mess with the push/pop instructions.

بواسطة ARTRAG

Enlighted (6923)

صورة ARTRAG

19-04-2009, 21:17

mth
thanks for the reply but i think that your proposal would disrupt the content of DE that has to be passed to "drawline"

the fact is that DE points and moves itself in _hidden_map
"drawline" starts from the current DE postion in _hidden_map

your change would disrupt the loop
[EDIT]
you already pointed this

بواسطة mth

Champion (507)

صورة mth

19-04-2009, 21:21

In "drawline", after you combine the two "cp" tests, you can replace the conditional "ret" + unconditional jump by a conditional jump + unconditional "ret". This is faster if the loop is iterated through more than once, which is probably more often the case.

بواسطة ARTRAG

Enlighted (6923)

صورة ARTRAG

19-04-2009, 21:27

yes
but actually I had to change that part already to allow circular light beams
Do you want to see?
Drop me an email and i'll send you the files

بواسطة mth

Champion (507)

صورة mth

19-04-2009, 21:33

You could win one instruction in "drawline" by passing pointers to both maps instead of alternating between maps by modifying a single pointer:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Input :
; HL = pointer in _hidden_map to (x-coordinate,y-coordinate)
; DE = pointer in _clear_map to (x-coordinate,y-coordinate)

;- draw one line-of-sight

drawline:
        
1:      add     hl,bc
        ld      a,(hl)

        ex      de,hl
        add     hl,bc
        ld      (hl),a
        ex      de,hl
                 
        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z
        jp      1b        

بواسطة mth

Champion (507)

صورة mth

19-04-2009, 21:40

It seems that the lines from the center are drawn twice. For example in segment 1, "segxloopinc" and "segyloopdec" both call "drawline" with the same values in DE and BC.

بواسطة ARTRAG

Enlighted (6923)

صورة ARTRAG

19-04-2009, 22:00

You could win one instruction in "drawline" by passing pointers to both maps instead of alternating between maps by modifying a single pointer:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Input :
; HL = pointer in _hidden_map to (x-coordinate,y-coordinate)
; DE = pointer in _clear_map to (x-coordinate,y-coordinate)

;- draw one line-of-sight

drawline:
        
1:      add     hl,bc
        ld      a,(hl)

        ex      de,hl
        add     hl,bc
        ld      (hl),a
        ex      de,hl
                 
        cp      wallchr                     ; view blocking characters
        ret     z
        cp      doorchr        
        ret     z
        jp      1b        


Good one
HL and DE can be initialized as you say outside the loop

بواسطة ARTRAG

Enlighted (6923)

صورة ARTRAG

19-04-2009, 22:19

It seems that the lines from the center are drawn twice. For example in segment 1, "segxloopinc" and "segyloopdec" both call "drawline" with the same values in DE and BC.

No, this is not correct, look e.g. at segment1:

if segxloopinc calls "drawline" with the value DE, than
segyloopdec calls "drawline" with the value DE+MAPW

the same holds for the other segments

صفحة 1/4
| 2 | 3 | 4