My Final Four Wants for the TI-99/4A

[+Torrax]

There was a TMS9918A version of Qix called "Cix" for the Colecovision.

[Omega-TI]

36 minutes ago, Torrax said:

There was a TMS9918A version of Qix called "Cix" for the Colecovision.

Interesting.  I had to look it up on YouTube after you mentioned it and only found two videos...

 

1) Small cellphone video

2) Larger non-english review with better video  Jump to 2:17

Cix-Manual.pdf

[Asmusr]

Two links about the algorithm:

https://forum.unity.com/threads/qix-game-logic.452628/

https://www.daniweb.com/programming/game-development/threads/471199/retro-game-qix-logic

There seems to be agreement that you have to fill the area where the QIX is not found (not the smaller area), but the suggestion is to use flood fill to discover where the QIX is. Two exceptions are mentioned: 1) when the QIX is found in both areas, in which case it should be split. 2) When the QIX is not found, in which case the smaller area should be filled. I don't know when those exceptions would actually happen?

[Asmusr]

It appears to me that if your last turn was a left turn the best guess is that you have to fill the area to the left (as see from the marker) and vice versa. If you happen to find the QIX in that area you have to fill the other one.

[JB]

6 hours ago, Asmusr said:

Two exceptions are mentioned: 1) when the QIX is found in both areas, in which case it should be split. 2) When the QIX is not found, in which case the smaller area should be filled. I don't know when those exceptions would actually happen?

Exception 1 can happen easily on stages with 2 qixes. 

Exception 2 is probably a safety net to prevent the game crashing outright if something goes wrong.

[Tursi]

On 8/6/2019 at 10:58 PM, Asmusr said:

That doesn't seem to work. For instance if the QIX is on the left side of the screen and you are at the middle bottom. You go a bit up, right, and down again. You now need to fill the rectangle to the left of you, but that's also where the QIX is. 

Ah, darn. I knew it was too easy to cover all the cases.

 

Lots of 8-bit systems have solved this, so it can't be that tricky...

 

[Tursi]

17 hours ago, Asmusr said:

Two links about the algorithm:

https://forum.unity.com/threads/qix-game-logic.452628/

https://www.daniweb.com/programming/game-development/threads/471199/retro-game-qix-logic

There seems to be agreement that you have to fill the area where the QIX is not found (not the smaller area), but the suggestion is to use flood fill to discover where the QIX is. Two exceptions are mentioned: 1) when the QIX is found in both areas, in which case it should be split. 2) When the QIX is not found, in which case the smaller area should be filled. I don't know when those exceptions would actually happen?

Huh. Well.. the double flood fill would both explain the pause, and the fact that the arcade is always able to draw the fill from left to right. Still feels like there oughta be a more efficient approach.

 

Edit: probably should be on a new thread, but... this one seems to work on paper. See if you can poke holes in it?

It's based on casting rays to determine whether something is inside, or outside of a polygon. If you cast rays from an arbitrary point, the number of borders it crosses indicates whether that point is inside, or outside. An even count is inside, an odd count is outside.

When the player finishes drawing a line (indicated by colliding with an existing drawn line), we cast a ray from the center of the new line to the QIX. If we pass over an even number of polygon lines, the QIX is "inside" and so we fill on the 'away' side of the vector. If we pass over an odd number, then the QIX is "outside" and so we fill on the near side. Terminology is kind of loose but it worked with simple and complex paths that I tried.

There is a complication I don't have a solution for. To work, we need the border of the new polygon. We can trace around it into a new buffer to get it, but the problem comes when the player has closed a concave opening. We know which way to start because we saw it drawn (just start copying pixels in reverse). This is also fine if the line is not straight. But at the other end, where the line started, there are two choices on the original polygon. One line remains on the outside, and one line is now inside the new one. I'm not sure how to determine that. Since we don't know which side is going to be filled yet, we don't know which line on the original polygon is about to be obsoleted.

 

Double fill does solve this, I just can't believe that the Apple 2 pulled that off...  Seems not a lot of people have dug into the arcade QIX.
 

Edited August 8, 2019 by Tursi

[Asmusr]

I think that's known as the point in polygon routine. But as you mention, that may also become quite complicated.

https://en.wikipedia.org/wiki/Point_in_polygon

 

If we don't have to deal with the two or zero QIX cases, and we can make an educated guess about which area to fill, we would usually only have to fill one smallish area. That is provided that we do the filling off screen where we can retry if we're wrong.

 

There's some info about the arcade machine in the MAME driver:

Quote

The screen is 256x256 with eight bit pixels (64K). The screen is
    divided into two halves each half mapped by the video CPU at
    $0000-$7FFF. The high order bit of the address latch at $9402
    specifies which half of the screen is being accessed.

Maybe they used the split screen to implement an offline fill buffer?

qix.cpp

Edited August 8, 2019 by Asmusr

[Tursi]

I think you need an off-screen fill buffer, I'm just stuck on believing there's a more efficient way to detect. Just silliness really. It's too bad nobody has reversed the code for us to just look!

 

[Asmusr]

I haven't decided if I want to try to do this, but it's interesting because it's far from trivial. And it's almost so problematic to do on a 9918A that it would warrant a F18A implementation.

[+arcadeshopper]

On 8/6/2019 at 10:58 PM, Asmusr said:

That doesn't seem to work. For instance if the QIX is on the left side of the screen and you are at the middle bottom. You go a bit up, right, and down again. You now need to fill the rectangle to the left of you, but that's also where the QIX is. 

you fill where the qix isn't

[JB]

7 hours ago, Asmusr said:

I haven't decided if I want to try to do this, but it's interesting because it's far from trivial. And it's almost so problematic to do on a 9918A that it would warrant a F18A implementation.

I admit to being impressed that the Colecovision clone works as fast as it does, even if the not-a-qix is a square sprite instead of the dynamic lines of the original.

[Asmusr]

6 hours ago, arcadeshopper said:

you fill where the qix isn't

And where is that? 

[ti99iuc]

Just if it could be an idea in this thread, my two cents.

I also remember this variant of Qix developed on spectrum and named Robo Xonix (Xonix was also an old DOS games I played a lot), it use balls as enemy
 

In Volfied, another dos game, as enemy is used a Sprite instead:
 

 

Edited August 10, 2019 by ti99iuc

[Tursi]

I don't think it matters much if the QIX is lines or a sprite -- Super QIX used a sprite too. I remember Volfied though!

 

I spent some more time on this, even going so far as printing off a bunch of downloaded screenshots and littering them with lines.  In the end, I'm now pretty convinced that it's the off-screen flood fill approach that must be used. This covers all the cases, including dual QIX. Choose a side from the final vector, doesn't really matter which, and fill it. If you detect a QIX at any point, stop and flood fill the other side. (If you detect another QIX, the player split the QIX and gets a multiplier bonus instead of fill percentage ).

 

I did come up with a ray casting approach that worked on all the screenshots, but failed on any simple case where the fill area was on the same side of the final vector as the QIX was (ie: any time the QIX was behind a wall). Looking at the data available to that ray, and various casts near it, made it clear that it was not going to be able to catch all cases. So yeah, like you thought Rasmus

I was curious about the sparx movement too. Watching them on playthroughs makes it clear that they follow the player's lines as drawn. They prefer outside lines but have to follow old lines for when they get trapped by new fills. Even better, it's possible with two fills to trap the sparks in an inside loop for long periods of time. That said, I couldn't determine for sure how they decide which way to turn, but I think there's a tiny bit of randomness, because even trapped sparx eventually escape.

Edited August 10, 2019 by Tursi

[JB]

1 hour ago, Tursi said:

I don't think it matters much if the QIX is lines or a sprite -- Super QIX used a sprite too. I remember Volfied though!

 

It is mostly just less cool-looking. Though the varying size of the qix makes getting around the "tail" a more interesting task.

(Also, Taito's own Super Qix and Volfied use a chain of sprites, not a single one, with Volfied's segments even being animated like they're connected.)

[Omega-TI]

Obviously a lot going on under the floorboards in that game. 

[Asmusr]

I have been working on an idea for a Qix-like game, basically that the resolution doesn't matter so much as long as everything moves smoothly, so even character resolution is OK.

I couldn't resists adding some smooth scrolling to expand the play field, but I'm not sure if it actually improves the game. It could run a lot faster without it.

The Tix (Qix) is currently harmless, and there are no sparks. 

The plan is that if you hold down fire you will move slower and get more points (red filling) whereas normal speed gives fewer points and blue filling. But right now it's filling blue to the right and red to the left, depending on where you end your trail.  

 

 

 

[HOME AUTOMATION]

LifeLine... This is TIX... I'm trapped and I can't get out!

 

This ME LIKES!

[+save2600]

+1 for faster gameplay and a non-scrolling playfield. Looks nice otherwise! 

[+eebuckeye]

Looks great! I like the smooth scrolling myself!

[Omega-TI]

2 hours ago, HOME AUTOMATION said:

This ME LIKES!

Me Too!

[Tursi]

That's great! I really like the way the sprite-based TIX looks, too.

 

Newly drawn lines should be a different tint to show they are unfinished - remember in the original that if you stop moving on a new draw for any reason, a spark will chase you down the line and kill you if it reaches your point. (If you resume motion, then stop again, it resumes from where it was).

 

I also like the scrolling. That game would be a great addition.

 

[Asmusr]

8 hours ago, HOME AUTOMATION said:

LifeLine... This is TIX... I'm trapped and I can't get out!

I feel sorry for the poor thing. It's like a wild animal trapped.

[Asmusr]

5 hours ago, Tursi said:

Newly drawn lines should be a different tint to show they are unfinished - remember in the original that if you stop moving on a new draw for any reason, a spark will chase you down the line and kill you if it reaches your point. (If you resume motion, then stop again, it resumes from where it was).

The way the scrolling is set up I only have four colors available: black, white, blue, red. That gives 16 different combinations, and with 8 scroll frames that's 128 patterns. Adding one more color would fill the entire pattern table. So I keep track of the trail that the player is drawing in a separate list. It shouldn't be a problem to add the sparks - I just need to set them off from the start of the trail in the right direction.

 

This is the core code to upload a screen from the map to the VDP name table. The map is stored as a 2D byte array where each byte can have a value between 0 and 3 (two bits). The code is taking those two bits from one row, shifting them up, and combining the result with the two bits from the next row. That gives four bits with the 16 combinations mentioned above. It then adds a value for the scroll offset, and sends the byte to the VDP (r4=VDPWD).

upload_map_1:
       movb *r1+,r3          ; get 2 bits from row 1
       sla  r3,2             ; shift up
       socb *r0+,r3          ; combine with 2 bits from row 2 
       ab   r5,r3            ; add scroll offset
       movb r3,*r4           ; send to VDP
       dec  r2               ; counter
       jne  upload_map_1     ; loop

Can anyone see a way to make this code faster?