Jump to content
--- Ω ---

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

Recommended Posts

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?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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.

  • Like 1

Share this post


Link to post
Share on other sites
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...

 

Share this post


Link to post
Share on other sites
Posted (edited)
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 by Tursi
  • Like 2

Share this post


Link to post
Share on other sites
Posted (edited)

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 by Asmusr
  • Like 1

Share this post


Link to post
Share on other sites

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!

 

Share this post


Link to post
Share on other sites

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.

  • Like 3

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
6 hours ago, arcadeshopper said:

you fill where the qix isn't

And where is that? ;-)

  • Like 1

Share this post


Link to post
Share on other sites

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 by ti99iuc
  • Like 1

Share this post


Link to post
Share on other sites

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 by Tursi
  • Like 1

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...