Author Topic: "Escheron: Twilight over Ragnoth" — progress updates and discussion (Read 126222 times)

Sorunome · « **Reply #60 on:** July 29, 2015, 05:52:34 am »

This is looking great indeed, can't wait for a playable demo!

Iambian · « **Reply #61 on:** July 31, 2015, 08:00:47 pm »

My latest jaunt into bresenhamming kinda failed. I got this algo from Xeda which, from what I understood, basically does this:

Code: [Select]

;NOTE: these are comments in the main source
;setup: dx = 2*(x2 - x1) , dy= 2*(y2 - y1). Use (camera_pos) for x1y1 dir.
;do:
;if (acc >= dy) && (y1 <= y2):
;  y++
;  acc = acc - dy
;  if acc < 0:
;    acc = acc + dx
;elseif (acc >= dx) && (y1 <= y2):
;  x++
;  acc = acc - dx
;  if acc < 0:
;    acc = acc + dy

The wrapper looks like this:

Code: [Select]

 ld (camera_pos_goto),hl
 scf
 rl L
 scf
 rl H  ;shift in 1's for each to extend to new mapping
 ld (_end_yx),hl
 ex de,hl  ;DE=dest
 ld hl,(camera_pos)
 ld a,(camera_subxy)
 rrca  ;shift out x
 rl L  ;put X into low
 rrca  ;shift out Y
 rl H  ;put Y into low
 ld (_cam_yx),hl ;CURRENT POSITION
 push hl
   push de
     ld h,0  ;x1 = L
     ld d,h  ;x2 = E. High bytes zero.
     or a
     ex de,hl
     sbc hl,de
     add hl,hl  ;dx=2*(x2-x1)
     ld a,1
     jr nc,{+}
     call _negHL
     ld a,-1  ;if carry, moving in negative direction
+:   ld (_cam_mover+0),a
     ld (_cam_dx),hl
   pop de
 pop hl
 ld e,H
 ld l,D  ;quick exchange instead of having to do ex de,hl. set high to low.
 ld H,0
 ld d,H
 or a
 sbc hl,de
 add hl,hl ;dy=2*(y2-y1)
 ld a,1
 jr nc,{+}
 call _negHL
 ld a,-1
+:
 ld (_cam_mover+1),a
 ld (_cam_dy),hl
 ld hl,0
 ld (_cam_acc),hl
-:
 call _iterateBresenham 
 call key_input_mapper._test_variable_delay
 ld hl,(_cam_yx)
 push hl
   xor a
   rr h
   rla
   rr L
   rla
   ld (camera_pos),hl
   ld (camera_subxy),a
   call showMapFrameRoutine
 pop hl
 ld de,(_end_yx)
 or a
 sbc hl,de
 jr nz,{-}
 ret

Note: delta x and y are always positive. The increment/decrement is kept in _cam_mover high and low bytes (y an x respectively)

The actual implementation is as thus:

Code: [Select]

_iterateBresenham:
 ld hl,(_cam_acc)
 ld de,(_cam_dx) ;handle (acc >=dy) condition
 push hl
   or a
   sbc hl,de  ;carry if condition doesn't hold up
 pop hl
 jr c,_iBr_skip_to_elseif
 push hl
   ld hl,(_cam_yx)
   ld a,(_end_yx+1)
   sub H      ;handle (y2 >= y1). Carry if condition doesn't hold.
 pop hl
 jr c,_iBr_skip_to_elseif
 push hl
   ld hl,_cam_yx+1
   ld a,(_cam_mover+1)
   add a,(hl)
   ld (hl),a  ;y++ (or y-- if running negative y)
 pop hl
 ld de,(_cam_dy)
 or a
 sbc hl,de  ;acc = acc-dy
 jr nc,_iBr_collect
;if made it here, run if acc < 0
 ld de,(_cam_dx)
 add hl,de
 jr _iBr_collect
_iBr_skip_to_elseif:
 push hl
   ld hl,(_cam_yx)
   ld a,(_end_yx+0)
   sub L      ;handle (x2 >= x1). Carry if condition doesn't hold.
 pop hl
 jr c,_iBr_collect
 push hl
   ld hl,_cam_yx+0
   ld a,(_cam_mover+0)
   add a,(hl)
   ld (hl),a  ;x++ (or x-- if running negative x)
 pop hl
 ld de,(_cam_dx)
 or a
 sbc hl,de  ;acc = acc-dx
 jr nc,_iBr_collect
;if made it here, run if acc < 0
 ld de,(_cam_dy)
 add hl,de
_iBr_collect:
 ld (_cam_acc),hl
 ret

I was told that the implementation is supposed to get me a line going from point A to point B. What I actually get is a straight line going down, then a straight line going right. The loop never terminates since the algo doesn't advance to the final x,y coordinate (I examined it being just 1 off).

Geekboy1011 · « **Reply #62 on:** July 31, 2015, 08:04:40 pm »

Hmm I shall take a look in a moment why not.
@Xeda112358 Care to take a peak as well?

@Iambian if you missed it we have @ mentions how so if you need a specific person tag them with @<nick> so that they get a notification saying Hey this person wants you

c4ooo · « **Reply #63 on:** August 01, 2015, 08:37:56 pm »

Quote from: Iambian on July 31, 2015, 08:00:47 pm

-snip-

Your slang intrigues me. This is the first time I heard of "bresenhammering". And when you said "algos" the other night I had no idea what you meant so I made a joke in [grammaticly wrong] Latin telling you not to talk about grief ("Algo" is Greek for "sorrow" (the joke was that algos is Greek and I told you not to talk about grief in Latin lol))

Also I came upon Escheron.pdf on the interwebs. I don't know if you are still using the story line as found in that file, but hell, the first two paragraphs sounded like something from a Sumerian legend.

The only way you could have made it better is if you said the gods made humanity by molding them from clay and sacrificing one of there own to bring them to life.

Geekboy1011 · « **Reply #64 on:** August 01, 2015, 08:50:43 pm »

Can you by chance link that pdf? Also bresenhammering is a made up word of his to describe the code he is working on

. And algos is short for algorithms because to be honest that is way to much to type out

TIfanx1999 · « **Reply #65 on:** August 01, 2015, 09:16:18 pm »

@c4ooo : You could always ask @Escheron what his influences were. He's the one that wrote the story and planned the scenarios.

Xeda112358 · « **Reply #66 on:** August 02, 2015, 11:11:06 am »

Sorry, I never noticed the mention. I don't have a lot of time, so I am going to make it quick. I may have given you bad pseudocode, I dunno. Here is some tested and working BASIC code:

First the sub program which would be equivalent to the subroutine thing to get the next X,Y. It's BASIC, so I can't use the Y var, so I just use Z:

Code: [Select]

If A>=0 and X!=R
Then
X+E->X      ;X coord, E is 1 or -1 (or possibly 0, but we don't actually need that)
A-V->A
End
If A<0 and Z!=S
Then
Z+F->Z     ;F is like E
A+U->A
End

Now the actual program. In this case, I just use the X,Z to draw pixels, you would use it to render the map.

Code: [Select]

;;Input a list as any {X1,Y1,X2,Y2}, just make sure they are in bounds as my code doesn't check
Ans->L1
Ans(1->X
L1(2->Z
L1(3->R    ;x2
L1(4->S    ;y2
R-X->U     ;deltax
S-Z->V     ;deltay
(U>0)-(U<0->E   ;sign(deltax)->xinc
(V>0)-(V<0->F   ;sign(deltay)->yinc
abs(U->A
2Ans->U
2abs(V->V
Pxl-On(X,Z
Repeat getKey
prgmLINESUB
Pxl-On(X,Z
End

I hope this helps ^~^

Iambian · « **Reply #67 on:** August 04, 2015, 07:20:21 pm »

Thank you very much Xeda112358, that TI-BASIC code translated to assembly works great, though I did have to add in some extra logic that would prevent the routine from locking if the accumulator is the wrong sign for the final iteration (it just flips it if the routine did nothing that cycle).

The calling routine pretty much did exactly what you did in the BASIC code. The only thing I had to change was where the "ld (_cam_acc),hl" instruction was located.

The actual algorithm, tho. This is what I got:

Code: [Select]

 res did_it_bresenhamming,(iy+stateflags)
 ld hl,(_cam_acc)
 bit 7,h  ;sign check
 jr nz,_br_xfail ;skip if acc less than zero
 ld a,(_cam_yx+0) ;xpos
 ld c,a
 ld a,(_end_yx+0)
 cp c
 jr z,_br_xfail  ;skip if x1==x2
 ld a,(_cam_mover+0)
 add a,c
 ld (_cam_yx+0),a
 ld de,(_cam_dy)
 or a
 sbc hl,de ;acc-dy
 set did_it_bresenhamming,(iy+stateflags)
_br_xfail:
 bit 7,h  ;sign check
 jr z,_br_yfail ;skip if acc is non-negative.
 ld a,(_cam_yx+1) ;ypos
 ld c,a
 ld a,(_end_yx+1)
 cp c
 jr z,_br_yfail ;skip if y1==y2
 ld a,(_cam_mover+1)
 add a,c
 ld (_cam_yx+1),a
 ld de,(_cam_dx)
 add hl,de ;acc+dx
 set did_it_bresenhamming,(iy+stateflags)
_br_yfail:
 bit did_it_bresenhamming,(iy+stateflags)
 jr nz,_br_nofail
 ld a,h
 xor $80  ;flip sign bit to force next iter to do something
 ld h,a
 ld (_cam_acc),hl
; call _cmp_cur_to_end_pos
 jr nz,_iterateBresenham  ;reiterate bresenhammer.
_br_nofail:
 ld (_cam_acc),hl
 ret

The end result:

Xeda112358 · « **Reply #68 on:** August 05, 2015, 07:47:56 am »

Okay, I have a few ideas for modifying this, and I'll try to figure out if I can optimize it further.

The only case where the algorithm does nothing is when it has reached the end of the line, otherwise it *always* does something.
Proof: When (x1,y1) != (x2,y2), then we have 2 case: bit 7 of HL is 0 or it is 1.
Case 1: It is 0. Then the first step of incrementing x1 is carried through (since x1 != x2)
Case 2: It is 1. Then the second step of incrementing y1 is carried through (since y1 != y2)

So basically, if you check bit 7 and it is 1, skip the X step and go straight into the Y step. You only need to check bit 7 for the Y step if you did the X step, and in that case, you can directly use the sign flag from the sbc hl,de... which by the way you can just negate the deltax value during the setup phase and use an add hl,de.

I also noticed the B register was unused, so instead of using flags, I just set b=1 in the beginning, then inc b instead of setting the flag. At the end, check if b is still 1, in which case nothing was updated, so the algorithm is done.

Here is how I modified it:

Code: [Select]

    ld b,1             ;use this to check if we bresenhammed
    ld hl,(_cam_acc)
    bit 7,h            ;sign check
    jr nz,_br_xfail    ;skip if acc less than zero
    ld a,(_cam_yx+0)   ;xpos
    ld c,a
    ld a,(_end_yx+0)
    cp c
    jr z,_br_xfail     ;skip if x1==x2
    ld a,(_cam_mover+0)
    add a,c
    ld (_cam_yx+0),a
    ld de,(_cam_dy)    ;negate this in the setup code
    inc b
    add hl,de
    inc b
    jr c,_br_yfail     ;skip if acc is non-negative.
_br_xfail:
    ld a,(_cam_yx+1)   ;ypos
    ld c,a
    ld a,(_end_yx+1)
    cp c
    jr z,_br_yfail     ;skip if y1==y2
    ld a,(_cam_mover+1)
    add a,c
    ld (_cam_yx+1),a
    ld de,(_cam_dx)
    add hl,de          ;acc+dx
    inc b
_br_yfail:
    ld (_cam_acc),hl
    dec b
    ret

So question: What is the range of values for the coordinates? Are they 0~127 ? (It seems like it based on the code).

EDIT: Here, this code might work. First routine is setup, second routine is the iteration.

Code: [Select]

br_setup:
;;(b,c) = (y1,x1)
;;(d,e) = (y2,x2)
    ld (_cam_yx),bc
    ld (_end_yx),de
    ld hl,0
    ld a,d
    sub b
    add a,a
    jr nc,$+5
    dec h       ;yinc
    neg
    ld (_cam_dy),a

    ld a,e
    sub c
    jr nc,$+5
    dec l       ;xinc
    neg
    ld (_cam_mover),hl
    ld h,0
    ld l,a
    ld (_cam_acc),hl
    add a,a
    ld (_cam_dx),a
    ret

br_iter:
;;return nc if br is finished
;;x1y1=x2y2  66
;;x1+       211 or 220, save 24~33cc
;;y1+       206 or 207, save 22~23cc
;;x1+, y1+  265 or 266, save 83~84cc
    ld hl,(_cam_end)
    ld de,(_cam_yx)
    or a
    sbc hl,de
    ret z
    ld hl,(_cam_acc)
    ld bc,(_cam_mover)
    bit 7,h            ;sign check
    jr nz,_br_doy
    
    ld a,c
    add a,e
    ld e,a
    ld a,(_cam_dx)
    ld c,a
    ld a,l
    sub c
    ld l,a
    jr nc,_br_done
    dec h
    jp p,_br_done
_br_doy:
    ld a,b
    add a,d
    ld d,a
    ld a,(_cam_dy)
    add a,l
    ld l,a
    jr nc,$+3
    inc h
_br_done:
    ld (_cam_acc),hl
    ld (_cam_yx),de
    scf
    ret

EDIT: There was an error in my latter code that should be ld (_cam_acc),hl as opposed to ld hl,(_cam_acc). The algo would still work, but this makes it work better.

Iambian · « **Reply #69 on:** August 08, 2015, 02:15:09 pm »

The original non-bresenham based algorithm produced this result:

The algorithm that I called this done with, reposted here for visual comparison:

The code from the post above (code below)

Quote from: Xeda112358 on August 05, 2015, 07:47:56 am

Code: [Select]
ld b,1 ;use this to check if we bresenhammed ld hl,(_cam_acc) bit 7,h ;sign check jr nz,_br_xfail ;skip if acc less than zero ld a,(_cam_yx+0) ;xpos ld c,a ld a,(_end_yx+0) cp c jr z,_br_xfail ;skip if x1==x2 ld a,(_cam_mover+0) add a,c ld (_cam_yx+0),a ld de,(_cam_dy) ;negate this in the setup code inc b add hl,de inc b jr c,_br_yfail ;skip if acc is non-negative. _br_xfail: ld a,(_cam_yx+1) ;ypos ld c,a ld a,(_end_yx+1) cp c jr z,_br_yfail ;skip if y1==y2 ld a,(_cam_mover+1) add a,c ld (_cam_yx+1),a ld de,(_cam_dx) add hl,de ;acc+dx inc b _br_yfail: ld (_cam_acc),hl dec b ret

Produced this result:

That wasn't exactly the results I was looking for, tho since I dropped that in, I might have messed up somewhere?

When I transcribed the BASIC program into assembly, I did it to the best of my knowledge. The additional check that I added to determine if the bresenhammer did something that cycle was not of paranoia, but of an actual bugfix when the loop never exited. The loop exits when it sees that (x1,y1)==(x2,y2). I saw that no matter how many times the thing ran, it never reached y1==y2 and the sign on the accumulator was wrong so that would never get checked, so I added code that would flip that sign to force the routine to do *something* so the external coordinate check might eventually exit.

As for the positional values themselves, they're all 8-bit unsigned with the range 0-255 (7bit map + 1bit subtile), which is part of the reason why the accumulator, and delta x/y are kept as words instead of bytes.

----
And in other news, minor work was done to slightly re-arrange the shop's buy-confirm prompt to make buying consumable items more meaningful and provide slight consistency between equipment and consumable purchases in light of that change:

Sorunome · « **Reply #70 on:** August 08, 2015, 04:41:51 pm »

It's moving so fast the water looks gray xD

Anyhow, looking awesome as usual ^^

TIfanx1999 · « **Reply #71 on:** August 08, 2015, 07:01:21 pm »

So what was the point with trying the bresenham technique versus the original one? The original one seems to pan much more smoothly than the new one.

Iambian · « **Reply #72 on:** August 08, 2015, 07:17:03 pm »

Quote from: Sorunome on August 08, 2015, 04:41:51 pm

It's moving so fast the water looks gray xD

Anyhow, looking awesome as usual ^^

I suppose it does, though I think it's more of an illusion provided by how the water's dithered. Kudos to Escheron/Zera for that.

Quote from: Art_of_camelot on August 08, 2015, 07:01:21 pm

So what was the point with trying the bresenham technique versus the original one? The original one seems to pan much more smoothly than the new one.

Hindsight's 20/20, I guess. None of us would really know what it would look like until it happened, and now that it did, Geekboy isn't exactly sure this is any better either. We have the old panning algorithm sitting around in case that needs to be used once more, but we're also going to keep the bresenhammy thing in case we do so we'll have something if or when this project goes full smoothscrolling. I'm convinced that it would look far better there.

Xeda112358 · « **Reply #73 on:** August 10, 2015, 08:43:33 am »

Oh, the coords are 8-bit? Mine might not work for that in some situations.So did my code work? It seemed to scroll pretty smoothly and accurately.

TIfanx1999 · « **Reply #74 on:** August 25, 2015, 12:38:51 am »

Don't remember if it's been discussed before, but it came up while chatting with Iambian and Geekboy yesterday. Quicksaving would be a lovely addition to this game if it isn't planned already. By quicksave, I mean being able to quit and save most anywhere (aside from if you are involved in a battle). When you return, the quicksave restores you where you were, but is deleted immediately thereafter. Since this is a portable game that will likely be played in short(ish) increments at a time I think it is a must IMHO.

Author Topic: "Escheron: Twilight over Ragnoth" — progress updates and discussion (Read 126222 times)

Sorunome

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Iambian

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Geekboy1011

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

c4ooo

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Geekboy1011

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

TIfanx1999

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Xeda112358

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Iambian

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Xeda112358

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Iambian

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Sorunome

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

TIfanx1999

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Iambian

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

Xeda112358

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion

TIfanx1999

Re: "Escheron: Twilight over Ragnoth" — progress updates and discussion