Author Topic: Geometry Wars Update  (Read 17746 times)

0 Members and 2 Guests are viewing this topic.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Geometry Wars Update
« Reply #15 on: June 13, 2010, 02:49:13 pm »
aaaah ok, nice :D

I guess that's the power of assembly ^^

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Geometry Wars Update
« Reply #16 on: June 13, 2010, 02:56:34 pm »
Yeah because with 30 bullets and 90 enemies you're doing some 3000 collision detections every frame :O Are you using any sort of space partitioning to decrease this amount?

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Geometry Wars Update
« Reply #17 on: June 13, 2010, 03:22:49 pm »
I'm not because I can't think of any fast way to do it. Unlike Galaga-like games, there's not really any pattern as to what is going to hit what.

One thought was to only check for enemies that are in it's path, but this takes more time than just checking all.
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Geometry Wars Update
« Reply #18 on: June 13, 2010, 04:06:03 pm »
Well lets see, if you divided your square into 4 partitions, you would need 2 comparisons for each object to determine which partition it resided in.  If you assumed a relatively normal distribution of enemies and bullets, one quarter of all your enemies would reside inside each partition.  Obviously you dont have to check accross partitions, so each partition would check all of the objects inside of it.  So instead of

Code: [Select]
B*N checks,      Where B = number of bullets and N = number of enemies
you would have

Code: [Select]
4((B/4)*(N/4)) + 2(N+B) checks, Where:

(B/4)*(N/4) represents the checks inside of each partiton, time 4 for all 4 partitions. 
 Plus 2(N+B) for the checks needed to partition the objects in the first place.

Which is roughly 3 times less collision checks than using a regular N^2 method.  Including speed loss due to partition handling and the such, it might drop down to 2 times as fast, but if you have partitioning working, you could even go as far as split the screen into 9 segments, which is

Code: [Select]
9((B/9)*(N/9)) + 4(N+B) checks.  Although this only gets you to a 3.7 speed increase, not significant over 4 part partitioning.
Partitioning might be too big of a step however, and i can understand if you dont want to use it, i can imaging it would be a nightmare to get working correctly O.O

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Geometry Wars Update
« Reply #19 on: June 13, 2010, 04:19:04 pm »
Wow!  You plan to use x^2, /, Enter, and On as the boundaries of the square?  That's a big square! :D  Also, if you're using On you must use check it differently than the other keys and use some combination of Mode 1 and Mode 2 interrupts (I'm assuming you're already using some.)  That sounds hectic.  Good luck!
I can't wait for this game. ;D

Oh, and are you going to update your other games so they don't display the warning?  Thanks! ^-^

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: Geometry Wars Update
« Reply #20 on: June 13, 2010, 04:23:35 pm »
You don't necessarily need to use your own interrupts. In fact, it may be counter-productive.
IMO, the best option would be to disable interrupts entirely if you don't use them (you probably either have a certain routine, or they are already disabled) and read port 4, bit 3, which is reset if the ON key is being pressed. Of course, you might know better than me, in which case you might find it better to use interrupts.
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Geometry Wars Update
« Reply #21 on: June 13, 2010, 04:30:03 pm »
I see how I could do that, I would just add an extra byte to each enemy data set. That is a good idea but I see a few problems that it would cause.

1. When an enemy or bullet straddles two partitions, (I guess I could just use a bitmap system and check both)

2. The other problem I see is the guys who dodge bullets, but they could just always be checked for collision.


Well with that out of the way I guess I'll do this. I'll relocate the enemy data buffer to extra ram because it completely fills saveSScreen. I will use 8 sections so that it will bitmap one byte. Four vertical columns with a middle splitter.

I don't feel like doing all the math for this, but this should give a significant increase in speed. In your math, couldn't you just simplify 4((B/4)*(N/4)) to 1/4 * B * N. I also don't understand why you add in the 2(N + B).

The only last problem that I see is when original problem 2 occurs. Partitioning won't work here and when the circles are the only enemy on screen, it will be right back where we started.


In response to the new posts while I was previewing this.

I currently have mirage interrupts enabled, but that obviously won't work so I will probably kill them completely as I don't actually use them.

The attachment doesn't display the message. But then again, a lot of stuff is changed, this is just my current updating version.

Edit:
    As far as too big of a change, I just converted the whole program from 3 bit physics to 8 bit, I will basically change anything if it is for the better.
« Last Edit: June 13, 2010, 04:34:35 pm by thepenguin77 »
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: Geometry Wars Update
« Reply #22 on: June 13, 2010, 04:48:41 pm »
Make sure to only use page 82h for more RAM than 80h and 81h provide, otherwise it won't work with the newer 84+(SE)'s. The slight problem to this is that TI-OS v2.53 MP uses page 82h to store some data, and I'm not sure how well-documented this usage is (i.e. what areas are safe RAM)
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Geometry Wars Update
« Reply #23 on: June 13, 2010, 04:51:22 pm »
Actually storing the data by adding on a byte to each object would not work in speed critical scenarios i think.  The fastest way that i can think of is to have 4 stacks, one for each partition.  At the start of each frame, when you figure out which partition an object resides in (it may reside in more than one, as you said) it would add a pointer to that object to the appropriate stack. Then when collision is calculated, you would go through each individual stack and calculate the collision inside of them.

I don't feel like doing all the math for this, but this should give a significant increase in speed. In your math, couldn't you just simplify 4((B/4)*(N/4)) to 1/4 * B * N. I also don't understand why you add in the 2(N + B).


Yes you could simplify this, but that equation isnt for computational purposes, it is just an equation to show how efficient on average this partitioning is going to be.  I left it unsimplified so that we could see the math behind calculating how many collision would happen on average.  The 2(N+B) is because at the start of each frame, we dont know which partitions the objects are in, so we need to quickly run some comparisons to figure out where to put them.  It takes 2 comparisons (>middleX and >middleY) to figure out where to put them, so it would be 2 comparisons for every object (N+B), so 2(N+B), and since this is independent of the actual collision process, we add it to the end of our equation.

How to the circles dodge bullets?  That would be an interesting challenge.  Then again, we could leave the space partitioning handling when bullets actually collide with enemies, and then leave regular N^2 for all of the special effects such as dodging.  Im curios as to how the dodge though, what do they do?

EDIT: And if your running out of ram, since you have about 200 objects max, and the partition data needs only a byte (pointer) for each object, could you use perhaps appBackUpScreen?  Or tempSwapArea? Or textShadow if you want to limit yourself to 128 ish objects max? or just increase file size by a meak 200 bytes to get some free ram without breaking compatibility with newer calcs?
« Last Edit: June 13, 2010, 04:54:38 pm by Builderboy »

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Geometry Wars Update
« Reply #24 on: June 13, 2010, 05:06:57 pm »
For the extra ram page, I only have 1 so I never use more than one. And I was actually the person who put that info about 2.53 in wiki ti ;). (Missile was being restless)


Before I start, for clarification, the bullets check for collisions with enemies.

Instead of stacks, I saw making the second byte of enemy data it's partition data. When each enemy updates, it decides what partition it is in, and if it straddles it just says it's in both. The circles will say that they are in their partition and all surrounding ones which will at least save 1/4 of the screen. Then when each bullet comes through to check for enemies, it will determine it's partition and AND it with the enemies, if it returns NZ, check for collision, Z move on.


Dodgers: I am going to write this like code as it is easier than explaining.

Is enemy in bullet's way. (determine signs of sin and cos and compare to relative position)
No. return but check for kill
Yes
Is enemy within 20 x and 20 y
No. return, bullet misses
Yes. Use movement code in reverse, i.e. instead of chasing bullet, negate values and it runs.
Is enemy withing 10 x and 10 y
No. return, bullet misses
Yes. Do same as before but double the effects. Grand total of three speeds away
return and check for collisions.

Another note, these guys can only move a total of 6 speeds away per frame, this is because they got pushed so hard from the 5 shot that you couldn't kill them. Also, when I was changing to 8 bit, I had the numbers backwards and the dodgers became suicidal and flew towards the bullets.


Edit to your edit:
     Newer calcs have 1 extra ram page, no problem there.

Edit 2:
     It's too hard to control with 16 buttons, going back to the way it was before.
« Last Edit: June 13, 2010, 07:26:02 pm by thepenguin77 »
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Geometry Wars Update
« Reply #25 on: June 13, 2010, 09:01:23 pm »
The partition code sounds neat.  It also sounds hard, so good luck! ;D

It's too hard to control with 16 buttons, going back to the way it was before.
I think I'd personally prefer the way it was originally, so I would have used it that way anyway. :)

For the extra ram page, I only have 1 so I never use more than one. And I was actually the person who put that info about 2.53 in wiki ti ;). (Missile was being restless)
The Penguin, you're awesome. ;D

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Geometry Wars Update
« Reply #26 on: June 13, 2010, 11:43:56 pm »
I'll try new version soon :D

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Geometry Wars Update
« Reply #27 on: June 14, 2010, 10:26:01 am »
Nice!  I really like the new version!  Excellent job. :D

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Geometry Wars Update
« Reply #28 on: June 14, 2010, 02:08:59 pm »
Ok this is absolutely epic!

I just played it and got 609 score on the emulator and darn it runs so fast. It deserves a feature, definitively :)

Offline Galandros

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1140
  • Rating: +42/-10
    • View Profile
Re: Geometry Wars Update
« Reply #29 on: June 14, 2010, 02:19:47 pm »
Dividing the game area into 4 parts for the collision detection is a smart idea.
It can be used in any game that has a lot of objects that enter into collision checks.

Continue the progress. ^^
« Last Edit: June 14, 2010, 02:37:59 pm by Galandros »
Hobbing in calculator projects.