#167733 - brave_orakio - Tue Mar 24, 2009 4:32 am
So, how do you guys handle sprite? Do you dynamically allocate sprites, adding and removing as needed, or do you set a fixed number of sprites, say 10 or so, then just reuse as needed?
I'm asking this because in my current code, adding or removing sprites(not dynamically. Just commenting or uncommenting then recompile to test) affects the speed of the overall game probably due to OAM sorting. I'm expecting more speed changing issues once I code in the collision detection.
_________________
help me
#167735 - gauauu - Tue Mar 24, 2009 2:52 pm
Not that my way is anyway near "best", but I allocate memory for a fixed number (generally the max number), then have my own sprite allocation routines that initialize and hand out an unused sprite when asked, or turn sprites off when not needed.
My OAM sorter then doesn't sort the sprites directly -- I have a list of in-game characters, and each character has a handle to the sprites it uses. Then I sort the characters, and copy each character's sprites in turn.
Sorting shouldn't take much time at all, so unless you are squeezing every last bit of processing power out of each frame, you shouldn't see much slowdown due to sorting your sprites. (unless you are doing something wrong?)
Also, abstracting a level like I was talking about (sorting and checking collisions against characters, not sprites) helps when you suddenly have characters that take multiple sprites, or are shaped differently, etc. I highly recommend that.
#167737 - sajiimori - Tue Mar 24, 2009 10:20 pm
I recommend the following:
- Treat the concept of a 'sprite' as something higher-level than a single OAM. A sprite can consist of multiple OAMs, but it should still be a purely visual object -- don't do any collision or game logic in your sprite code.
- Sort your sprite list every frame, using an algorithm that doesn't shuffle anything around if the list is already sorted. On most frames, there will be few (if any) changes to the list order, so just quickly scan for out-of-order sprites and shift them to where they belong.
- Build the OAM list from scratch, every frame, by iterating over your sprite list and writing out the set of OAMs for each sprite. That will automatically give the correct sorting order. Do this work during VDraw, into a buffer that you then DMA to the hardware during VBlank.
- Use a full-fledged dynamic VRAM allocator for sprite pixel data. One easy and fast approach is to have an array with 1 bit per char, to signify whether it's currently in use. To allocate a sprite frame, scan for a block of contiguous zeros that's long enough to fit the frame.
- Allocate your high-level Sprite objects just like any other object; you can hold them by value, dynamically allocate them -- anything that can be done with normal objects. There's no need to force a particular allocation scheme onto all client code. Sprites can automatically register a pointer to themselves into a master list, so they'll be correctly sorted and rendered.
- Wrap it all up in a nice, clean interface, and forget about OAMs, bitfields, and VBlank interrupt handlers! =)
#167739 - brave_orakio - Wed Mar 25, 2009 2:29 am
| Quote: |
| Sorting shouldn't take much time at all, so unless you are squeezing every last bit of processing power out of each frame, you shouldn't see much slowdown due to sorting your sprites. (unless you are doing something wrong?) |
Well, not exactly slowdown. Just unstable speed(I can still decrease the delay between sprite updates). though I'm not sure if my sorting is horribly slow but I'm not using many sprites(around 4 for now because I'm only testing).
I just have no idea how you guys can make the game speed not change even if there is only one or say 5 sprites. maybe if a lot is happening some slowdown would occur but generally it wouldn't. There's not even a lot happening per frame in my code. Just the sorting and the copy to VRAM and of course the copy to OAM during Vblank.
the stuff that sajimori said hasn't quite sunk in to my head yet though. Still a bit woozy.
thanks for the replies though, and keep em coming! The more opinions I read the better!
_________________
help me
#167740 - Miked0801 - Wed Mar 25, 2009 5:11 am
Don't bubble sort your entire sprite list from scratch every tic. :)
Profile your code. That will tell you exactly where the slowdown is. You will probably be surprised.
#167741 - brave_orakio - Wed Mar 25, 2009 6:01 am
Since profiling came up, any tools that are free and easy to use? >:-) I only use PN2 for my coding.
_________________
help me
#167742 - Dwedit - Wed Mar 25, 2009 7:08 am
Either make your program for your native platform (Windows, Linux, Etc), and use those tools to profile...
But I also made a hacked version of VBA which counts the number of times an instruction is executed.
Obviously, this is only useful for profiling ASM code...
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#167743 - albinofrenchy - Wed Mar 25, 2009 8:07 am
There is a cyg-profiler port out there; I keep meaning to do a write up, but haven't found the time.
http://forum.gbadev.org/viewtopic.php?t=11985&postdays=0&postorder=asc&highlight=cygprofile&start=15
#167746 - gauauu - Wed Mar 25, 2009 2:50 pm
| brave_orakio wrote: |
I just have no idea how you guys can make the game speed not change even if there is only one or say 5 sprites. |
Assuming you are doing one frame of processing per vblank, you will, unless you are doing heavy computation, have quite a bit of processing time "wasted" at the end of every frame, where you are just waiting for vblank. So the difference between 1, 5, or 25 sprites should just be more time processing and less time waiting on the vblank, and shouldn't affect the actual game speed at all.
#167749 - brave_orakio - Thu Mar 26, 2009 2:14 am
Guys, my head is clearer and the stuff you're saying is starting to make sense. Took long enough.
this
| Quote: |
| Don't bubble sort your entire sprite list from scratch every tic. :) |
and this
| Quote: |
| Sort your sprite list every frame, using an algorithm that doesn't shuffle anything around if the list is already sorted. On most frames, there will be few (if any) changes to the list order, so just quickly scan for out-of-order sprites and shift them to where they belong. |
and this
| Quote: |
Sorting shouldn't take much time at all, so unless you are squeezing every last bit of processing power out of each frame, you shouldn't see much slowdown due to sorting your sprites. (unless you are doing something wrong?) |
make a lot of sense now. So how about more suggestions for collision though before I fully tackle that part?
_________________
help me
#167750 - brave_orakio - Thu Mar 26, 2009 2:38 am
of course this one
| Quote: |
| Also, abstracting a level like I was talking about (sorting and checking collisions against characters, not sprites) helps when you suddenly have characters that take multiple sprites, or are shaped differently, etc. I highly recommend that. |
and this
| Quote: |
| - Treat the concept of a 'sprite' as something higher-level than a single OAM. A sprite can consist of multiple OAMs, but it should still be a purely visual object -- don't do any collision or game logic in your sprite code. |
is already part of the planning in my collision process.
_________________
help me
#167751 - gauauu - Thu Mar 26, 2009 3:52 am
For collisions, it really depends on how many possible things might be colliding.
Most simple or tile-based games will need to check all "characters" against each other, and against the background map. It's easiest if you define a bounding box for each character, and check bounding boxes (which should be independent of the actual graphic sprites). For backgrounds, you can check and see which logical map tiles (abstracted from actual tiles just like characters and sprites) the bounding box intersects, and see if that tile is a "collision" tile.
If you have a relatively small number of characters, (especially if you only need to check on-screen characters) you can just brute force checking them all against each other -- it doesn't take all that long for small numbers. If you have quite a few to check, there are smarter algorithms for checking to see if the bounding boxes intersect (but don't worry about those if you've only got a few characters, and don't spend a lot of time prematurely optimizing!)
#167752 - sajiimori - Thu Mar 26, 2009 3:53 am
My favorite overall strategy for collision is to let each object handle their own collision detection, rather than having a 'collision system' control everything.
Write a function that provides an interface similar to this:
| Code: |
struct TestResult
{
// Info about what/where/how/when objects
// were impacted. At a minimum, a bool for
// 'something was hit', with no extra info.
};
TestResult hypotheticalCollisionTest(
Position startPos,
Shape, // Maybe radius, or width and height
Vector hypotheticalMotion);
|
Objects that want other things to be able to collide with them should carry a collision object that registers itself in a list of all collidable objects, and the collision test function should check against those registered objects (and possibly against background collision).
The strategy for making it fast depends on the game, but the overall goal is the same: reduce the number of objects you have to visit during a collision test. For a lot of games, sorting your objects from left to right is enough to avoid testing against most objects.
#167754 - brave_orakio - Thu Mar 26, 2009 4:30 am
I'm thinking a maximum of maybe 10 character on screen, 8 way directions for the smaller characters. 4 for bigger characters
Now then, another part of the plan in regards to actual implementation is use an array of function pointers so I can just check direction(0-7 for 8-way direction or 0-3 for 4 way direction) then the function for collision for that particular direction of movement is called.
Does that sound like a good implementation? Also the sorting from left to right sounds quite good.
Another question is, if a character where to say throw a punch or slash or close range attack for example, would the attack be a different collision object from the character itself?
_________________
help me
#167755 - sgeos - Thu Mar 26, 2009 5:02 am
| brave_orakio wrote: |
| I just have no idea how you guys can make the game speed not change even if there is only one or say 5 sprites. |
Are you synchronizing your code to the display?
#167757 - brave_orakio - Thu Mar 26, 2009 6:14 am
| Quote: |
| Are you synchronizing your code to the display? |
Yes it is synchronized. The problem is as Mike said, don't bubble sort every tic! I implemented a sort used for every frame that would go through the OAM list only once and sort only the ones out of place. I'm sure it could still use some optimization but it did have more stability with the speed changing issues.
_________________
help me
#167758 - sgeos - Thu Mar 26, 2009 8:03 am
IIRC, bubble sort is a horrible algorithm. If your current solution is not working, you could try to find a different algorithm, or split your sorting across multiple frames.
#167760 - elwing - Thu Mar 26, 2009 8:39 am
| sgeos wrote: |
| IIRC, bubble sort is a horrible algorithm. |
quite true, haven't seen it once (for more than 5element let's say...) since my college course...
#167761 - brave_orakio - Thu Mar 26, 2009 9:48 am
| Quote: |
| IIRC, bubble sort is a horrible algorithm. If your current solution is not working, you could try to find a different algorithm, or split your sorting across multiple frames. |
I had to find that out the hard way! Now I use it only to sort the list in for the first time then I use a faster sort the rest of the time.
_________________
help me
#167763 - sgeos - Thu Mar 26, 2009 11:59 am
You might want to look into sorting algorithms, if you have the time or if this is a bottleneck in your code. I suspect there is a faster way to do your initial sort.
#167766 - gauauu - Thu Mar 26, 2009 3:01 pm
| brave_orakio wrote: |
| I had to find that out the hard way! Now I use it only to sort the list in for the first time then I use a faster sort the rest of the time. |
No no no, that's backwards.
Use a faster sort the first time, because that's when bubble sort is REALLY going to be awful.
On a list where only one or two items are out of place by one or two places (A list of characters that is mostly sorted, except two need to be swapped, like a sorted sprite list where one character moved), bubble sort can be as fast as O(n). (I still don't really recommend you use it, as it can end up being REALLY slow if more things are out of place)
| Quote: |
Now then, another part of the plan in regards to actual implementation is use an array of function pointers so I can just check direction(0-7 for 8-way direction or 0-3 for 4 way direction) then the function for collision for that particular direction of movement is called.
|
Well, there are many different ways and designs to implement this, but I don't really get what you are describing. What I did (and again, this likely isn't the BEST way) is to store the original position of my character, then update it's position for movement. Then, check collisions. If there was a collision, restore the original position. (And you can make it slightly trickier by first removing the X component of movement, checking collision, then removing the Y component, checking, then restore the original, letting characters "slide" along walls diagonally).
| Quote: |
Another question is, if a character where to say throw a punch or slash or close range attack for example, would the attack be a different collision object from the character itself? |
You would probably want the attack to be a different object, as the collision characteristics are different (if the attack collides with an enemy, it damages the enemy. If the character collides with the enemy, it damages the player. If the attack hits a wall, who cares? If the character hits a wall, he will be blocked).
But again, there generally isn't one design that's always best for all cases. (And if there is, it's highly unlikely that I've stumbled upon it). You'll want to tailor all this we're telling you so that it makes sense in your overall design and game style.
#167767 - sgeos - Thu Mar 26, 2009 4:34 pm
| Quote: |
| Another question is, if a character where to say throw a punch or slash or close range attack for example, would the attack be a different collision object from the character itself? |
I'd spawn some sort of a damage object. Think of it this way, if your character shoots a fireball, "would the attack be a different collision object from the character itself"? No, right? So you can spawn an invisible "fireball" at the character's fist and have it disappear after it times out (or something similar).
#167769 - sajiimori - Thu Mar 26, 2009 6:33 pm
Even if your characters can only move in 8 directions, I still recommend writing a general collision algorithm that takes any motion vector as input (i.e. motion at any angle), for several reasons:
- It consolidates all the code into a single, generic function, rather than having 8 separate functions. You'll find that there's less repetition this way.
- If characters can move when they're half-way between two tiles (i.e. they don't have to move exactly along tile boundaries), making that work correctly is no less difficult than writing a fully generic collision function.
- You'll have the freedom to make projectiles that move at arbitrary angles.
- You can use it on future projects that allow a wider range of motion.
For attacks that hit enemies in a particular direction (e.g. swinging a sword in front of you), use a separate shape, but you don't need to make a whole collision object for it (and register it in the list of collidable objects, and so on), because nothing needs to collide against it -- the attack collision goes out and looks for things to hit. You just pass the attack shape to your collision test function (an intersection test function this time, instead of a motion test) and execute the 'get hit' logic for all the intersected enemies.
By the way, you may only need to write an intersection test, rather than a motion test, if objects never move fast enough to pass through other objects (or walls).
| Code: |
// This function answers the question:
// "If there were an object at the given location,
// "what would it intersect?"
TestResult hypotheticalIntersectionTest(Position, Shape);
|
When a character is trying to move, check what it would intersect if it moved, then decide what to do based on the test result.
#167775 - brave_orakio - Fri Mar 27, 2009 2:31 am
From what I read from your ideas I think my idea for my collision algorithm is a bit strange.
I'll explain a little further just to give you an idea and maybe find some flaws in my logic. It would good to know if the way I'm approaching things is wrong(not just the sorting and the collision).
The reason I have the array of function pointers is to avoid a long if else block. I can just use numbers to indicate a direction and then give it to the array of function pointers as an index and so the proper collision happens with a character going in that particular direction.
As an example, say a character is moving right and then he hit a wall. The moving right direction has a value of 2 and this would be the index used in the function pointer array. Inside the function[2] is a process that says your x posiiton should go no further because of the collision. However nothing is said of the y position because he is only moving right(Of course if I want something to happen to the y position I can do that too).
Of course as mentioned before, there will be a lot of functions that will look alike. This of course is only my idea and it is very much appreciated if you have something to say about its flaws and advantages/disadvantages.
_________________
help me
#167778 - brave_orakio - Fri Mar 27, 2009 4:59 am
The generic collision algorithm suggested by sajimori sounds good and can be implemented easily with my current structure. Give me sometime to ingest this stuff. Keep the ideas coming while I test out some of these suggestions though!
_________________
help me
#167781 - sgeos - Fri Mar 27, 2009 8:03 am
| brave_orakio wrote: |
| The reason I have the array of function pointers is to avoid a long if else block. |
Why not use a switch statement?
#167823 - brave_orakio - Mon Mar 30, 2009 2:09 am
Sorry for the late reply, I have no access to a computer on the weekends here.
If I am correct, a switch block would be slightly slower with several branches but with a array of function pointers, just one branch will do. Where the program branches is of course the address of the function required.
_________________
help me
#167825 - sajiimori - Mon Mar 30, 2009 3:12 am
It depends -- just use whichever style you'd prefer to work with.
But of course, I still think it's basically not worth it to have separate algorithms for each direction, regardless of how you split them up. =)
#167890 - brave_orakio - Thu Apr 02, 2009 2:47 am
Hi guys, I'll give you an update on my progress. I used sajimori's bounding box and sorting idea. Except that I used Y sorting instead of X(Since the character list is already Y sorted anyway. And there's something wrong with my X sorting I think heh.) It's quite fast! Thanks alot!
_________________
help me
#167891 - brave_orakio - Thu Apr 02, 2009 5:42 am
Although I'm still confused. The current build is running far faster than I could ever imagine without your help and I am quite happy with the speed(I can probably optimize further at a future time), but changing the number of sprites still greatly affect the overall speed.
Do you guys put some sort of dummy functions or something when there are less characters on screen? Or maybe functions that check if a character should be displayed on screen when moving in the game world?
For example, I have six characters right now, 1 which I control and the others doing nothing but copying frames at intervals(Just to simulate how much clock time is consumed when I implement AI). When I move left the characters of course eventually become offscreen(They will show up on the other side when I scroll further as I haven't implemented the character show and remove part). When they are offscreen, do you change the previous AI process to a function that looks for a character to be shown onscreen?
_________________
help me
#167896 - gauauu - Thu Apr 02, 2009 3:10 pm
Again, if you are getting fluctuations in speed based on the number of sprites on screen, then one of two things is happening:
1. You aren't waiting for vblank each frame, so your main loop is running as fast as it can. This will mean the framerate will drastically change with the amount of processing you have to do. This is bad.
2. When you have a lot of sprites on screen, you are running over the amount of processing you can do in video frame, and are running over into the next video frame, so when you wait for vblank, you now doing 2 video frames per iteration through your main loop.
I'm guessing it's #1, unless you're doing something horribly inefficient or rather complicated, as you really have quite a lot of processing time in each frame. (and it should be fairly easy to tell which it is....is the game jumping back and forth between 1 speed and half that speed, or is it a gradual speed change?)
The real question: are you calling VBlankIntrWait() with each iteration of your main loop?
| Quote: |
Do you guys put some sort of dummy functions or something when there are less characters on screen? |
No, the extra padding time is filled when we call VBlankIntrWait().
| Quote: |
Or maybe functions that check if a character should be displayed on screen when moving in the game world?
|
Handing off-screen characters varies significantly with your game design. Reasonable designs range from killing offscreen enemies, freezing them and not processing them offscreen, processing them just like a normal character (minus displaying them) if they are within a certain range of the screen, or just processing all characters all the time. It's hard to give you a "here's the best way to handle it" advice for this.
But if your framerate is drastically fluctuating, your first problem is figure out which of the two things I mentioned above that it is, and fix the root of the problem.
#167897 - elyk1212 - Thu Apr 02, 2009 6:27 pm
| Quote: |
Do you guys put some sort of dummy functions or something when there are less characters on screen?
|
I should also mention, if you ever want to port your code to a different system this is highly unpredictable way to judge timing. I've seen it done in hackish situations (especially from not software types) but it always makes me throw up a little in my mouth ;).
Naw, but the VBlank waiting is the best. In situations in embedded systems where you need a specific delay, using a timer is a great idea. For this kind of device though, screen updates are already deterministic so...
BTW, great thread. I was wondering what the "greats" do for character handing also. I am deciding the what and how of off screen characters. Efficiency/Accuracy trade off.
I've noticed in older games many characters just regenerate and start their pattern when you come back on the screen. Seems like they don't track too much.
#167904 - sajiimori - Thu Apr 02, 2009 8:54 pm
How I handle off-screen characters depends on the game, but at the very least, I skip all of their rendering code.
Beyond that, I usually keep them fully active when they're within a certain distance of the play area. When they're outside that range, I either kill them completely, or replace them with tiny structs that only remember their most important attributes (like their location and type) so they can be recreated when they get back in range.
#167905 - gauauu - Thu Apr 02, 2009 9:04 pm
In Anguna, I cheesed out on the issue of offscreen chracters. Everything was divided into room (like old zelda games), meaning there was a set, small number of enemies when you entered the room. Even if they were offscreen, I could still easily track every enemy in the room.
#167908 - brave_orakio - Fri Apr 03, 2009 3:03 am
| Quote: |
| No, the extra padding time is filled when we call VBlankIntrWait(). |
This makes sense. I didn't think of this one.
Although I don't have a dynamic add and remove character function yet, I did simulate this by commenting out and recompiling. I would have to say that the speed changes gradually. With less character on screen, the speed increases.
So apparently, I'm still doing more than I should be doing per frame. Most of my loops should run in O(n) especially the sorting loop since I fixed it that way. Here's the code for the quick sort.
| Code: |
int i,j;
CHARACTER_ATTR *tempSort;
OBJ_ATTR tempAttr;
for(i = 0, j = 1; j<index; i++,j++)
{
if(CharListY[i]->sprite_posNew.y>CharListY[j]->sprite_posNew.y)
{
update[i] = CharListY[i]->OAM;
}
else
{
tempAttr = CharListY[i]->OAM;
update[i] = CharListY[j]->OAM;
update[j] = tempAttr;
tempSort = CharListY[i];
CharListY[i] = CharListY[j];
CharListY[j] = tempSort;
CharListY[i]->positionY--;
CharListY[j]->positionY++;
}
}
update[i] = CharListY[i]->OAM; |
As you can see it is fixed for O(n). I'm just letting the rest of the frames further sort it if the first frame missed something. CharListY is an array of pointers and update is the buffered OAM.
_________________
help me
#167909 - brave_orakio - Fri Apr 03, 2009 3:34 am
Oh and here's the one for the collision:
| Code: |
int i,j;
int l1,l2,r1,r2,t1,t2,b1,b2;
volatile CHARACTER_ATTR *collide1, *collide2;
for(i = 0, j = i+1; i<nCollision; i++,j++)
{
if(j >= nCollision)
{
j = i+1;
continue;
}
collide1 = CharListY[i];
collide2 = CharListY[j];
t1 = collide1->sprite_posNew.y - collide1->width;
t2 = collide2->sprite_posNew.y - collide2->width;
b1 = collide1->sprite_posNew.y + collide1->width;
b2 = collide2->sprite_posNew.y + collide2->width;
if(t1>b2) continue;
if(b1<t2) continue;
l1 = collide1->sprite_posNew.x - collide1->length;
l2 = collide2->sprite_posNew.x - collide2->length;
r1 = collide1->sprite_posNew.x + collide1->length;
r2 = collide2->sprite_posNew.x + collide2->length;
i--;
if(r1<l2) continue;
if(l1>r2) continue;
collide1->sprite_posNew = collide1->sprite_pos;
collide2->sprite_posNew = collide2->sprite_pos;
i++;
j = i + 1;
} |
It looks a bit wierd maybe but here's a quick explanation:
The character list is Y sorted so I basically check first if they are in collision in the top and bottom bounds. If not on to the next set. If it is in collision check the left and right bounds. If in collison, collide then check next set, if not check the current(collide1) with the next character.
In a related question, around how many can you sort and collide like this per frame without slowing down?
_________________
help me
#167913 - elyk1212 - Fri Apr 03, 2009 6:07 am
Oh, this sounds like a great reason to start looking into I-Collide. A method of sorting all your on screen characters by each axis, by their bounding box beginning end end points (for each axis). Quite simple for 2D and really nice savings for 3D. Since they would all be pointers, as long as you don't have insane amounts of characters, it shouldn't eat up too much memory.
But yeah, a sort each frame (so long as you don't have sprites warping to other sides of the screen) should run in O(N) time if doing bubble sort or insertion sort, since each list will be almost sorted on each run.
This idea flows from the dx and dy on each frame, for each character should not be very large (no warping or any such non-sense).
Anyhow, collision detection is free when you do a swap as you can tell if a end point as crossed over a start point, there was a collision
E.g. looking at only one axis
| Code: |
Frame 1
X axis only (all end points noted)
|----------------------------| -------------------------------| ----------------|
Ob1begin Obj1end Obj2begin Ob2end
Frame 2 : Swapped Obj1End with Obj2begin.. COLLISION ON X add to a list of "active pairs"
X axis only (all end points noted)
|----------------------------| -------------------------------| ----------------|
Ob1begin Obj2begin Obj1end Ob2end
|
Similarly if you swap in the reverse manor, the objects are no longer colliding. So collision detection is free, just the cost of doing your normal sorting... kinda.
You will note, each bounding box must collide on all axis in order for a collision to have occurred.
Sometimes you can cheat in 3D though if say your guy doesn't fly, it is safe to say a collision may have occurred if just x-z is in a collision state... but depends on your game/requirements etc.
I used I-Collide for some Masters Independent study projects and it worked great (3D). However, for the lower level polygon detection (underneath the bounding box detection), I used a brute force "find a dividing plane" algorithm that wasn't the fastest, and definitely could be improved. But you would not need this for 2D, it doesn't need to be polygon/pixel exact, I wouldn't think anyhow.
#167914 - brave_orakio - Fri Apr 03, 2009 9:02 am
I think I know I-collide as another name. Recursive-something, I read it in Game Programming gems. My sort is somewhat similar, since characters are already sorted according to Y, I used part of the concept.
_________________
help me
#167924 - elyk1212 - Fri Apr 03, 2009 3:50 pm
Maybe, but I would think it would have been called V-Collide or something, as it has been slightly modified in implementation and retained only a slightly different name.
http://www.cs.unc.edu/~geom/V_COLLIDE/
I highly recommend reading the I-Collide paper:
ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/paper3dint.pdf
However, this paper exploits spatial coherency between frames, and many techniques utilize this idea for collision detection as well as visibility culling. So you may have been reading about a technique with a similar approach.
As far as I can recall, there isn't much recursive about this algorithm, unless you were traversing some type of scene hierarchy (Octrees, KDTrees, etc), which may also be a trick to improve collision detection (not caring about what's going on several nodes away and not checking for collisions between far nodes). But that complicates the endpoint sorting slightly as they may not be "almost sorted" when characters start popping on the screen (or crossing node boundaries), many at a time.
Oh, important detail I forgot to mention. Your bounding boxes must be axis aligned (no worries in 2D), and the endpoints must be in World space (so translate your bounding box endpoints by the world space cords of your character).
#167927 - elyk1212 - Fri Apr 03, 2009 4:41 pm
Your code from before:
| Code: |
int i,j;
CHARACTER_ATTR *tempSort;
OBJ_ATTR tempAttr;
for(i = 0, j = 1; j<index; i++,j++)
{
if(CharListY[i]->sprite_posNew.y>CharListY[j]->sprite_posNew.y)
{
update[i] = CharListY[i]->OAM;
}
else
{
tempAttr = CharListY[i]->OAM;
update[i] = CharListY[j]->OAM;
update[j] = tempAttr;
tempSort = CharListY[i];
CharListY[i] = CharListY[j];
CharListY[j] = tempSort;
CharListY[i]->positionY--;
CharListY[j]->positionY++;
}
}
update[i] = CharListY[i]->OAM;
|
I have another small suggestion. I think you should really only be doing assignments if something is out of place in the list. So, if you decide on the Endpoint I-collide, you'd only do a swap if something was out of place. This might save clocks.
This way, each node in the list is checked but a few memory writebacks are only done if something needs to be swapped.
Currently you're moving data around a lot. But, I don't know, that may be a small tweak. Also you're managing OAM attributes as well in the same spot? Maybe just have a visibility flag set in a Character object that states weather it should be appended to OAM?
It should not need to be placed in OAM unless it can be seen. But I am not entirely clear on the technique you have going, so I may be off here.
#167943 - brave_orakio - Sat Apr 04, 2009 12:28 am
| Quote: |
| I think you should really only be doing assignments if something is out of place in the list |
I think thats whats happening right now If I understand you correctly. Although admittedly, I have can optimize it some more now that you mentioned it.
As for the OAM, the plan is to remove an object if it isn`t visible before this sort happens and I guess I want to avoid another loop that`s why I`m building it here.
And one more thing, do you guys stagger the proccesses over several frames? Like say, frame 1 update all characters, frame 2 sort, frame 3 collision then repeat.
_________________
help me
#167947 - sajiimori - Sat Apr 04, 2009 4:01 am
What you're doing doesn't look slow at all. If you've only got 6 characters, you should be fine. Doing a single pass of swapping out-of-order sprites is a great way to get lots of speed, and it rarely causes any noticeable problems.
Your characters aren't really 'volatile', are they? If you're modifying their collision data during an interrupt, there's something horribly wrong!
But if not, then don't declare them 'volatile', because that basically turns off the optimizer. =)
BTW, you are compiling with optimizations enabled, right?
Edit: Actually, I don't understand your collision loop. Isn't this simpler?
| Code: |
// Works if objects are sorted left-to-right.
for(int i = 0; i < numObjects - 1; ++i)
{
for(int j = i + 1; j < numObjects; ++j)
{
if(j is completely to the right of i)
break;
if(i and j intersect)
flag the collision to be resolved later;
}
}
// Now resolve all the flagged collisions.
|
But of course, I still greatly prefer to let objects handle their own collision, rather than doing all collision in a single loop.
#167948 - elyk1212 - Sat Apr 04, 2009 5:50 am
| Code: |
And one more thing, do you guys stagger the proccesses over several frames? Like say, frame 1 update all characters, frame 2 sort, frame 3 collision then repeat.
|
Well, if you use I-Collide all you have to do is do a bubble sort each frame and keep track of new collisions on swaps and de-register objects that are no longer colliding on swaps. This would be in O(N) time and is very reasonable to do on a frame by frame basis :)
It is a little extra work.
BTW, yeah, it looks like you weren't moving that much data. Disregard that last statement. But, anyhow, yeah I-Collide.... You know you want to try it :P
#167949 - brave_orakio - Sat Apr 04, 2009 10:22 am
Yeah, I am compiling with the optimizations enabled. That`s the one with O# in the make file right?
| Quote: |
| Actually, I don't understand your collision loop. Isn't this simpler? |
Yes and I tested it, it works the same. I think I just over thought my collision loop!
| Quote: |
| But of course, I still greatly prefer to let objects handle their own collision, rather than doing all collision in a single loop |
Well, the my current collision process is still too slow (much faster than the last one though)and I will probably try this
| Quote: |
| But, anyhow, yeah I-Collide.... You know you want to try it :P |
and this as well! I`ll update you guys with my progress when I try both of these! Thanks for the suggestions again!
_________________
help me
#167952 - Miked0801 - Sat Apr 04, 2009 4:44 pm
How many objects are you attempting to collide each tic? In Lord of the Rings, Return of the king, we were moving dozens of sprites and checking hundreds of collides each game loop. Same for many other games. I'm having a hard time imagining you are having processing issues with 6 or so sprites.
BTW, use insert sort over bubble sort. It is always faster. And consider using shell sort which will eliminate just about any other speed concern you may have with sorting.
And again, profile to see where you are spending your time instead of guessing.
#167968 - elyk1212 - Sat Apr 04, 2009 6:26 pm
Mike: So did you check hundreds of collides indiscriminately, or was it based on some sort of subdivision or coherency? I wonder if a brute force technique was used effectively. If so, I've definitely over done it with suggesting I-Collide ;)
BTW, isn't Shell sort just insertion sort for "nearly" sorted lists? Perhaps it would be even better to use Shell, though, if you ever wanted to have objects move in different ways (and initial sort would be quicker).
I think I missed the fact you were only checking 6 objects. As Mike suggested, I think you may need to look into profiling and also skim around looking for something obvious. Nothing as complex as I a suggested is needed for 6 objects. I was using many hundreds of 3D objects that warranted the I-Collide system.
Still, fun to know and you might like it for 3D games you could make in the future. (Maybe keep it in mind).
#167981 - keldon - Sun Apr 05, 2009 1:47 am
[Very late to discussion, all of my comments are probably irrelevant]
My solution for sprite tile allocations (is also valid for background tiles)consists of a basic allocator for OAM entries, and an allocator (much like a typical memory allocator) for the sprite/tile names (since the character names refer to addresses).
My implementation uses a partitioned linked list:one partition for allocated, one for free, one for unspecified (where cells in the structure refer to MEMORY_BLOCKS's).
I'm sure it could be faster by using skip-lists, but hasn't caused me any problems.
#167982 - Miked0801 - Sun Apr 05, 2009 5:09 am
Pretty much brute force. :) We added elements to a list each gameloop if the collidable flag was set. That was the first cull. Then, we had some intermediate flags and checks to cull it further (most off screen actors didn't need to collide, but some did like platforms). Did I mention we were doing multiple types of collision boxes per actors, an attack and body collide? That along with a 3rd check for BG collisions that only collided with other bg information (and was 2D vector based.) So we did attack/body, body/attack, and body/body collides per tic skipping attack/attack. I believe we also did some basic circumscribed circle, radius/radius checking as a secondary cull, but it was dropped as AA box checks are pretty dang fast as is.
This collision pass was an O^2 / 2 type pass and was one of our top CPU eaters, but not the worst (which is always, always sound and music.)
So yeah, I feel you are really over doing it here. I've found that when the number of collidable actors is getting too high, a simple x/y grid hash will bring to results back closer to O(n). Something like x pos / some power of 2 or'd siwth a shifted y pos / a similiar power of 2 where the divisor is larger than the biggest collision box to make the spanning of areas code cleaner. RotK did not need this.
And yes, shell is just a insert sort with larger initial steps. I believe the best step results come in at 63, 21, 7, 3, 1 for the steps. It's a nice stable O^1.25 sort that has no memory overhead and sorts in place. Great for or large datasets.
#167989 - brave_orakio - Mon Apr 06, 2009 12:22 am
| Quote: |
| I'm having a hard time imagining you are having processing issues with 6 or so sprites. |
exactly. I posted my code for the sorting and collision in the last few posts(Check sajimori`s post for the collision algorithm, mine is too complex using the same logic and I did change my collision that). I tried putting volatile in my OAM buffer just to try out what sajimori said and strangely, the generated ASM is longer but the runtime is faster in the emulator.
Anyway, around how many sprites is the average before I should see any performance issues if everything is working as it should?
And perhaps one more issue, Should I stagger my character control code over several frames(Check button input 1st frame, update position 2nd frame etc.) I`ve read of suggestion that do this with AI
_________________
help me
#167991 - Miked0801 - Mon Apr 06, 2009 2:24 am
Run your game at 30hz. That will give you more than enough time to do what you need. Then you don't need to worry about how you split your code up across frames. Put a counter in your vblank handler and at the end of your game loop, wait until at least 2 vblanks have passed before continuing.
And how many sprites? Depends on what that sprite is doing. You could run a game with hundreds of sprites being updated using hblank tricks if nothing else in your game needed CPU time. If, on the other hand, you are streaming music, waiting for multiplayer communications, processing massive amounts of AI, etc. it can be as little as 1 sprite. The number of sprites shouldn't be a limiting factor to your game's performance. Sound can though :)
#167992 - sajiimori - Mon Apr 06, 2009 4:54 am
Yeah, I think all our GBA games ran at 30fps.
But also, set up a timer and measure how long each section of your code is taking. Maybe there's a bug that's causing something to take far longer than it should.
#167997 - brave_orakio - Mon Apr 06, 2009 12:07 pm
Any way to print the result of the timer without building a text system of my own?
If not, can anyone tell me how to connect a library(libgba, libmirko or tonclib)? Maybe I can use their existing system. What do I have to put in the make file to connect the libraries?
_________________
help me
#168003 - Miked0801 - Mon Apr 06, 2009 4:05 pm
Do you have any sort of debugging capability at all? No printfs, no break points?
#168011 - elyk1212 - Mon Apr 06, 2009 8:32 pm
I used libgba, and this is the ghetto fabulous way I do things:
| Code: |
//******************************************************************************
/**
* Set up the print system
*/
inline void Debug::printSetup()
{
static int setup = 0;
consoleInit( 0 , 4 , 0, NULL , 0 , 15);
BG_COLORS[0]=RGB8(58,110,165);
BG_COLORS[241]=RGB5(31,31,31);
SetMode(MODE_0 | BG0_ON | OBJ_ENABLE);
setup = 1;
}
//
// First I call the above, then I call something like:
//
/// iprintf("\x1b[0;0H current.position: %d,%d",c->position.x,c->position.y);
// Where 0,0 are the coordinates where the printing begins.
|
But after you print once, the whole screen gets messed up (cannot see sprites, BG etc). LOL., but at least you can see your data values.
I would use a debugger but I haven't ported the fix for VBA that gmiller created (to Linux) yet. As soon as I do though, I'll try and release it and make sure it works on both Win32 and Linux if possible.... or I'll get lazy and use wine. :)
#168017 - brave_orakio - Mon Apr 06, 2009 11:15 pm
I use devkitarm and programmer's notepad as an editor. There seems to be a printf but I don't know how to use it here(I tried it, it compiles correctly but nothing is displayed). As far as I can tell, no debugging. Or at least I don't know how to set it up
_________________
help me
#168018 - elyk1212 - Mon Apr 06, 2009 11:24 pm
Did you try my solution? (See above). Everything called in the printSetup function is available through libgba. Then you just call this function called iprintf which has the coordinates first, then all other parts of the string work like printf would normally work: %x for hex, %i for integer... etc.
Keep in mind, there's probably a better way, but at least it's something :)
#168019 - brave_orakio - Tue Apr 07, 2009 12:01 am
How do I connect libgba to my project? Do I need to add something to my environment variables and makefile? I'm no expert in makefiles and I have no idea how to do this manually.
_________________
help me
#168020 - Dwedit - Tue Apr 07, 2009 12:28 am
If you're using devkitarm's easy makefiles, you are already linking to libgba, just include the correct header files and it should work already.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#168023 - brave_orakio - Tue Apr 07, 2009 12:43 am
I didn't know devkitarm had it's own makefile. I'm using my own
_________________
help me
#168026 - elyk1212 - Tue Apr 07, 2009 2:08 am
Use the template if you want to have a quick solution, if not post your Makefile here and I'll let you know what to add.
Basically though, it's not a question of Makefiles so much as knowing what to pass to gcc/g++, but it sure helps to know the shell and Makefile tricks :)
So, for example when calling gcc/g++ at the linking step, use something like this in your makefile:
| Code: |
# save all your .o files in variable OBJ
g++ -L/yourlibpath $(OBJ) -lyourlibname -o binary
|
But. of course, you'll probably want to make a LIBPATHS variable, with all the areas you have libraries (-L), and a LIBS variable with all the library names (-l).
Eh... but the template devkitArm file does all this for you. Still, it's a great skill to learn makefiles and autotools etc... it really helps when porting your code around (which you may eventually want to do... maybe).
From one of my other posts:
http://forum.gbadev.org/viewtopic.php?t=16387
#168084 - brave_orakio - Thu Apr 09, 2009 1:10 pm
Sorry for the late reply, I`m gonna feel like a fool but where do I find the makefile template of devkitarm? Let me check out your other posts too.
_________________
help me
#168087 - elyk1212 - Thu Apr 09, 2009 4:15 pm
No worries. It took me awhile to find out also. It is just in the examples:
http://sourceforge.net/project/showfiles.php?group_id=114505&package_id=273883&release_id=663276
Once you untar these guys just check under the ./template folder, and there is a Makefile there to follow/use.
#168113 - brave_orakio - Fri Apr 10, 2009 11:47 am
Ah, thanks! let me check this out for a while before I post any updates again
_________________
help me
#168175 - brave_orakio - Mon Apr 13, 2009 7:23 am
Hmm, I'm not sure if I'm doing things the right way here but I have plenty of defines that are the same as libgba defines in my header files(I never intended to use libgba because I wanted to really learn from the bottom up). Would this pose a problem?
Anyway, I'm having a difficult time figuring out the devkitpro generic makefile so I'm gonna go the coward's way and post my makefile
| Code: |
#make file for game_demo
#----details------
export PATH := $(DEVKITARM)/bin:$(PATH)
PROJ := game_demo
EXT := gba
UDIR := /d/devkitpro/examples/gba/MyDemo/GameDemo
CFILESARM := $(UDIR)/updateScrManager.c
CFILES := $(UDIR)/hero.c $(UDIR)/hero_sprite.c $(UDIR)/gameDemoMain.c $(UDIR)/vramManager.c \
$(UDIR)/OAMManager.c $(UDIR)/genericBG.c $(UDIR)/bgManager.c $(UDIR)/collisionManager.c
ARMOBJ := $(CFILESARM:.c=.o)
COBJS := $(CFILES:.c=.o)
ALLOBJ := $(ARMOBJ) $(COBJS)
#----tool settings--------
CROSS := arm-eabi-
AS := $(CROSS)as
CC := $(CROSS)gcc
LD := $(CROSS)gcc
OBJCOPY := $(CROSS)objcopy
MODEL := -mthumb-interwork -mthumb
MODELARM := -mthumb-interwork -marm
SPECS := -specs=gba.specs
CFLAGS := -I./ -I$(UDIR) $(MODEL) -O3 -Wall -fno-strict-aliasing
CFLAGSARMFLAG := -I./ -I$(UDIR) $(MODELARM) -O3 -Wall -fno-strict-aliasing
LDFLAGSARM := $(SPECS) $(MODELARM) -mlong-calls
LDFLAGS := $(SPECS) $(MODEL)
#-----Build Steps ---
build : $(PROJ).$(EXT)
$(PROJ).$(EXT) : $(PROJ).elf
@$(OBJCOPY) -v -O binary $< $@
-@gbafix $@
$(PROJ).elf : $(ALLOBJ)
@$(LD) $^ $(LDFLAGS) -o $@
$(ARMOBJ) : %.o:%.c
$(CC) -c $< $(CFLAGSARMFLAG) -save-temps -o $@
$(COBJS) : %.o:%.c
$(CC) -c $< $(CFLAGS) -save-temps -o $@
#----Clean----
.PHONY : clean
clean :
@rm -fv $(COBJS) $(SOBJS)
@rm -fv $(PROJ).$(EXT)
@rm -fv $(PROJ).elf
|
Anyway, as I said above about the defines that might pose a problem, I'm going to add this question now in the event that I will have to make my own printing function(It was part of the overall design but I thought to make it later on). How do I convert an integer value to a string? Or do I just use the standard sprintf()?
_________________
help me
#168186 - elyk1212 - Tue Apr 14, 2009 7:32 am
int to string:
If you want to learn how to do this, try to think about ascii. All number characters are in a sequential, correct? This is the convenience. So, you can do something like this to create ascii character from an int:
| Code: |
int num = 4;
char c = num + '0';
|
Notice that I am adding the character zero '0' to the integer, which would be fine for any one digit integer 0-9. This works since C/C++ considers int and char to be of the same primitive type... basically, and due to each ascii character being in order.
So what happens when I add 1 to '0'? 1+ '0' == '1' ... 1+ '2' == '3'... so on :)
Now here is a little more advanced version (handles larger numbers and hex output),but maybe not the best implementation, it's from years ago, so excuse the comments and such):
| Code: |
//**************************************************************************
/**
* Convert a number to a hex equiv string (null terminates)
* @param buff buffer to place hex string in.
* @param length max length to place in buffer (not counting null)
* @param num mumber to convert.
*/
void hexToAscii_rec(char* buff, int length, int num)
{
//int temp = num >> 4;
//temp &= 0x0000000F;
int temp = num % 16;
//printf("num%16 = %d\n", temp);
// Stopping condition
// (when there are no more numbers to divide out,
// fill all more sig digits with 0s
if(num == 0)
{
while(length >=0)
{
*(buff+length) = '0';
length--;
}
return;
}
// Hex Number case
else if(temp >= 0 && temp <= 9)
{
*(buff + length) = temp + '0';
//printf("Char found was: %c", *(buff+length));
hexToAscii_rec(buff, length-1, num/16);
}
// Hex Letter case (A-F)
else if(temp >= 10 && temp <= 15)
{
// Minus 10 since this is decimal number base
*(buff + length) = temp -10 + 'A';
//printf("Char found was: %c", *(buff+length));
hexToAscii_rec(buff, length-1, num/16);
}
}
//**************************************************************************
/**
* Convert a number to a decimal equiv string (null terminates)
* @param buff buffer to place decimal string in.
* @param max_length max length to place in buffer (not counting null)
* @param num mumber to convert.
*/
int decimalToAscii(char* buff, int max_length, int num)
{
int length = digitLength(10,num);
// If the buffer will not be big enough to hold result, Flag error
if(length+1 > max_length)
{
//printf("Error! String to convert to Ascii ");
//printf("is larger than will fit in your buffer size!\r\n");
return HEX_ERROR;
}
// Null terminate string,
*(buff + length) = '\0';
decimalToAscii_rec(buff, length-1, num);
return SUCCESS;
}
//**************************************************************************
/**
* Convert a number to a decimal equiv string (null terminates)
* @param buff buffer to place decimal string in.
* @param length max length to place in buffer (not counting null)
* @param num mumber to convert.
*/
void decimalToAscii_rec(char* buff, int length, int num)
{
//int temp = num >> 4;
//temp &= 0x0000000F;
int temp = num % 10;
//printf("num%16 = %d\n", temp);
// Stopping condition
// (when there are no more numbers to divide out,
// fill all more sig digits with 0s
if(num == 0)
{
while(length >=0)
{
*(buff+length) = '0';
length--;
}
return;
}
// Hex Number case
else if(temp >= 0 && temp <= 9)
{
*(buff + length) = temp + '0';
//printf("Char found was: %c", *(buff+length));
decimalToAscii_rec(buff, length-1, num/10);
}
}
//**************************************************************************
/**
* Find out how many digits there are to convert to ascii buffer, given
* the number base.
* @param number_base base of number (10,2,16,etc).
* @param num number to find the length of.
*/
int digitLength(int number_base,int num)
{
return digitLength_rec(number_base,num,0);
}
|
Anyway, this is done in the C style, you'll probably want to take advantage of the string class if you are using C++, it is a great idea to avoid random pointer arithmetic where you can! But this is just for you to get the concept of the conversion.
There are also conversion routines built in, like for instance into ostream and the << operator (in C++ only).
For example on my Matrix class I have:
| Code: |
//**********************************************************************
template <typename T>
std::stringstream& operator<< (std::stringstream& o, const Matrix<T>& m)
{
return o <<
"\n{" <<
m.data[0] <<","<< m.data[4] <<","<< m.data[8] <<","<< m.data[12]
<< "\n" <<
m.data[1] <<","<< m.data[5] <<","<< m.data[9] <<","<< m.data[13]
<< "\n" <<
m.data[2] <<","<< m.data[6] <<","<< m.data[10] <<","<< m.data[14]
<< "\n" <<
m.data[3] <<","<< m.data[7] <<","<< m.data[11] <<","<< m.data[15]
<< "}" << endl;
}
|
Which you can convert a stringstream to a string fairly easily stream.str()
http://www.cplusplus.com/reference/iostream/stringstream/
I'll look at your makefile a little later. I've got to go to bed now :P
I forget your error message etc, off hand.
#168200 - sajiimori - Tue Apr 14, 2009 5:58 pm
Or yeah, just use sprintf. ;)
(Better yet, use snprintf to reduce the risk of overflow.)
#168203 - sgeos - Wed Apr 15, 2009 12:46 am
I agree. Why do you not want to use sprintf or snprintf?
#168204 - brave_orakio - Wed Apr 15, 2009 1:55 am
Actually, yes I guess could use that. Just curious is all about the actual process if there was anything different going on underneath. I guess I just think that sometimes it's good to know these thing in case you can use it elsewhere.
And thanks for the conversion code elyk! but is it possible to link libgba if my standard headers have almost all of the same defines and typedef as libgba? As for the errors, I can't say because I don't even know where to start!
_________________
help me
#168205 - elyk1212 - Wed Apr 15, 2009 2:14 am
Yes, I agree that knowing "what goes on" behind the scenes if probably more valuable that just using the easy solution. At least when you are learning. Once you understand it, use the easy solution.
This is why engineering and comp sci classes make you do this stuff manually, at least at first.
Oh, and yes, it's possible to link the library. You'll just get errors in the namespace (redefinition) if you have defines that are declared again (or warnings). But this is not from the actual linking, this is from the header including (which brings them into the global namespace for that file). (Linking errors could occur if there is ambiguity with function names, more than one defined (same signature), and being forward declared... so being ambiguous as to which definition to attribute the declaration to at linking time... at least I think).
To get rid of them, just comment each line that gives an error (or warning). It all depends on what flags you're throwing to gcc, if the preprocessor (for #define) throws an error (at least from what I remember).
If you are redefining classes or types in headers more than once, you'll prob have to avoid that as that should be an error (again if you're only #define -ing a label it will usually just be a warning, unless you specify otherwise using flags etc).
#168208 - elyk1212 - Wed Apr 15, 2009 4:30 am
Oh, and btw, learning how to use streams with the << operator is probably a pretty good practice if you use C++.
You can keep it in your classes for portability and debug, it is sort of like having a toString method in Java.
Allows things like:
| Code: |
// outputs nice formated object to the console... on platforms that have one ;P
cout << yourclass_obj << endl;
|
If anyone can find a printf variant that outputs a class's data (in an easy way), I'd like to know :P (but I've been wrong before, ....regardless, << seems to be the usual expected way when you're defining your own classes).
#168215 - sgeos - Wed Apr 15, 2009 5:02 pm
| elyk1212 wrote: |
| To get rid of them, just comment each line that gives an error (or warning). |
You may want to consider some combination of #ifdef #ifndef #undef #define and #endif.
| Code: |
#ifndef TRUE
#define TRUE (!0)
#endif // TRUE
// this could break something if you are not careful
#ifdef SOMETHING_I_NEED_TO_CONTROL
#undef SOMETHING_I_NEED_TO_CONTROL
#define SOMETHING_I_NEED_TO_CONTROL (MY_IMPORTANT_VALUE)
#endif // SOMETHING_I_NEED_TO_CONTROL |
#168314 - brave_orakio - Tue Apr 21, 2009 4:00 am
Finally I have a text system up and running!
Now here's the thing, at its slowest my game loop runs at around 13k cycles which is half of the amount of cycles per frame if my math is correct.
So theoretically it should not slow down even if there is only 1 character (around 2K cycles)or 6 characters(13K cycles).
I must be doing something horribly wrong if the speed changes like that!
_________________
help me
#168316 - sajiimori - Tue Apr 21, 2009 8:32 am
Add some more debug text, like a clock to display how many seconds have passed, what your calculated framerate is, etc. Maybe something will stand out as being weird.
#168317 - Cearn - Tue Apr 21, 2009 9:59 am
| brave_orakio wrote: |
Now here's the thing, at its slowest my game loop runs at around 13k cycles which is half of the amount of cycles per frame if my math is correct.
|
A full refresh is roughly 281k cycles. You're using about 5%, not 50%.
#168318 - brave_orakio - Tue Apr 21, 2009 10:25 am
Heh, my math is wrong! Right I'll do that and see what else I find out
_________________
help me
#168326 - brave_orakio - Wed Apr 22, 2009 10:13 am
My initial findings would indicate that my game is not synced to vblank.
Here's what I did. First my game loop:
| Code: |
while(1)
{
//move all characters
//check collision
//sort
//wait for vblank
check++;
//print value of check
//print number of frames passed
}
|
and then my updater thas is in a vblank interrupt
| Code: |
//copy OAM buffer to OAM
//update BG
frame++
|
So if everything is working right, check and frame should increment at the same time right? Unfortunately, check is way bigger than frame.
Whats strange is adding a loop at my screen updater to burn vblank time doesn't help at all.
Just in case I messed up with my vblank syncing code, the code should look like this right?
| Code: |
while(*REG_VCOUNT<160){}
|
_________________
help me
#168329 - sgeos - Wed Apr 22, 2009 2:58 pm
| brave_orakio wrote: |
Just in case I messed up with my vblank syncing code, the code should look like this right?
| Code: |
while(*REG_VCOUNT<160){}
|
|
Using interrupts is a better way of doing things.
How is REG_VCOUNT defined?
#168331 - kusma - Wed Apr 22, 2009 3:03 pm
| brave_orakio wrote: |
Just in case I messed up with my vblank syncing code, the code should look like this right?
| Code: |
while(*REG_VCOUNT<160){}
|
|
No. If you manage to finish your loop while still in VBLANK, this will finish right away. Instead, you should do:
| Code: |
while(REG_VCOUNT>160);
while(REG_VCOUNT<160); |
or even better
#168338 - brave_orakio - Thu Apr 23, 2009 2:37 am
REG_VCOUNT is defined as
| Code: |
#define REG_VCOUNT ((vu16*)0x4000006)
|
in my header
Yes I do use interrupts for updates but as mentioned in the post above, If my code runs too fast and don't burn V_DRAW and V_BLANK, the loop would update multiple times.
| Code: |
while(REG_VCOUNT>160);
while(REG_VCOUNT<160); |
This one seems to have done the trick! But I didn't realize that moving anything less than 1 pixel per frame seems very slow!
_________________
help me
#168341 - Ruben - Thu Apr 23, 2009 7:00 am
I fail to see why your code would run too fast if you were to use the software interrupt. All VBlankIntrWait() does is put the CPU on hold until an interrupt occurs, and puts it back to sleep or until it hits V-Blank, in which case you are returned to your code, essentially the same as doing a while(*REG_VCOUNT>160); while(*REG_VCOUNT<160);
#168342 - sgeos - Thu Apr 23, 2009 8:08 am
VBlankIntrWait() uses less power than polling VCOUNT. Are there any other reasons to use it?
#168343 - Ruben - Thu Apr 23, 2009 8:29 am
Because it's more accurate than polling REG_VCOUNT, though that can be remedied using REG_DISPSTAT's first bit ;)
#168344 - brave_orakio - Thu Apr 23, 2009 9:00 am
I didn't know about VBlankIntrWait() till now. Although wouldn't this mean that code only runs during vblank?
_________________
help me
#168345 - Ruben - Thu Apr 23, 2009 9:17 am
Not really.
From the looks of it, your loop updates stuff, waits for V-Blank (to update registers?I can't remember haha), does more stuff and starts again.
Assuming that this stuffs takes longer than 228-160 scanlines, you *will* enter V-Draw, regardless of using VBlankIntrWait or while(((*REG_DISPSTAT)&1) == 0);
#168346 - brave_orakio - Thu Apr 23, 2009 10:10 am
Oh and I guess I have one more question. How many pixels per frame does your sprite move? Around how many is the limit so it doesn't look choppy?
_________________
help me
#168347 - sgeos - Thu Apr 23, 2009 10:15 am
| brave_orakio wrote: |
| I didn't know about VBlankIntrWait() till now. Although wouldn't this mean that code only runs during vblank? |
It starts during vblank. If you take too long you enter vdraw. Entering vdraw is ok, but make sure to do all your timing critical things first (sound and then video, as a quick rule of thumb). If you are doing so much that you take more than a whole frame (vblank + vdraw), your framerate will drop, but your program updates will start during vblanks.
#168348 - Ruben - Thu Apr 23, 2009 11:43 am
I'd like to add to sgeos' suggestions
| Quote: |
| Entering vdraw is ok, but make sure to do all your timing critical things first (sound and then video, as a quick rule of thumb) |
I'd like to say that if you're on the GBA (which it looks like from REG_VCOUNT<160), sound can take its time... lots of it. So what you may want to do is call sound interrupts first. That is..
| Code: |
void VBlankISR(void) {
SoundIntr(); //Reset DMA if needed (assuming you use MaxMod,
//M4A or any of the other ones that use the "good"
//frequencies, otherwise this goes into Timer 1 (eg. Krawall)
UpdateScreenRegisters(); //You must, must, must, must, MUST
//have this run first where possible to make sure that
//you don't get muddled graphics
//Now do your other stuffs
SoundMain(); //Do the main sound work, as this takes the most time
} |
However, if you know that, in total calling of all the V-Blank call will take more than a full frame, trim down the stuff you put there, or try limiting the sound channel count to have more raster time to do other stuffs. It will save you a lot of headaches (I know it did for me >>').
#168349 - sgeos - Thu Apr 23, 2009 1:52 pm
| Ruben wrote: |
| I'd like to say that if you're on the GBA (which it looks like from REG_VCOUNT<160), sound can take its time... lots of it. So what you may want to do is call sound interrupts first. |
Certainly. The thing about sound is that you want to make sure it is refreshed with consistent timing. There are many ways to do this, but the simplest way (not necessarily the best) is to refresh sound first thing in the vblank, then handle graphics, and then do anything else related to sound, graphics or the internal game state that is not directly sending output to the hardware.
You could set your sound up so that it is refreshed when vdraw starts or at some arbitrary scanline if you don't need the interrupts for anything else.
| Quote: |
| if you know that, in total calling of all the V-Blank call will take more than a full frame, trim down the stuff you put there |
I agree, but sometimes things just end up taking more than a full frame if you are doing something repetitive on a large number of objects. There are workarounds.
EDIT: In case it is not obvious by now, pretty much everything involves synchronizing your game with the hardware.
#168350 - gauauu - Thu Apr 23, 2009 3:30 pm
| brave_orakio wrote: |
| Oh and I guess I have one more question. How many pixels per frame does your sprite move? Around how many is the limit so it doesn't look choppy? |
And for the easier question:
However many pixels per frame you need to move the speed that you want the object to move. It'll probably never look very choppy -- if it's moving slowly, you won't notice. And if it's moving much faster than a few pixels per frame, it'll be moving so quickly that your eyes won't be able to notice the choppiness.
#168390 - brave_orakio - Mon Apr 27, 2009 2:08 am
Thanks for all the replies guys! From what I'm reading though, it seems that sound would be the main reason why a lot of games run at 30 frames instead of 60.
I'll probably do a new topic on that when the time comes for me to add sound to my game. Again thank you all!
_________________
help me
#168400 - sgeos - Mon Apr 27, 2009 4:05 pm
30 FPS gives you twice as much time to get stuff done. If you need that time, you need that time.
#168402 - Miked0801 - Mon Apr 27, 2009 6:16 pm
If it makes you feel better, every single commercial game I've worked on has run at 30hz. GBC/DMG, GBA, and DS.
#168418 - sgeos - Tue Apr 28, 2009 6:05 pm
| Miked0801 wrote: |
| If it makes you feel better, every single commercial game I've worked on has run at 30hz. GBC/DMG, GBA, and DS. |
Did you force throttle 30 FPS, or did processing always take long enough to run at 30 FPS?
#168424 - Miked0801 - Tue Apr 28, 2009 11:02 pm
Both. It's just safer and looks better for the game if it always runs at a constant speed. A few could have ran at 60, but there would have been some hiccups here and there to 30 that would have looked lame. Better to keep it at 30 so no one notices.
#168427 - Dwedit - Wed Apr 29, 2009 12:09 am
I've heard a few games run the game logic at 30FPS, and tween it up to 60FPS.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#168434 - sgeos - Wed Apr 29, 2009 7:45 am
What is the "best" throttling method?
#168452 - Dwedit - Wed Apr 29, 2009 1:44 pm
To throttle to 30FPS:
Your vblank handler includes code to tell how many times it has happened.
If you run your game code, and it says vblank happed 0 times, wait for vblank twice and clear the counter. If it says vblank happened 1 times, wait once and clear the counter. If it says vblank happened 2 times, your code is too slow, you don't need to wait for vblank. Clear the counter.
To throttle to 60FPS, just wait for Vblank if vblank has not happened.
To throttle to an arbitrary frame rate, you can use timer interrupts set to any frequency you want. But you need to make sure the list of graphics to display is swapped atomically each frame, you don't want half of the sprites from one frame, and half from another.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#168458 - sverx - Wed Apr 29, 2009 4:16 pm
| Dwedit wrote: |
| To throttle to an arbitrary frame rate, you can use timer interrupts... |
Arbitrary? You mean like 30, 20, 15, 12, 10 fps... or you mean ANY like 50 or 25?
#168465 - Dwedit - Wed Apr 29, 2009 5:46 pm
I mean ANY, including 10FPS, 50FPS, 100FPS, 256FPS, anything provided that your game logic can execute on time. For example, a game designed for an arbitrary FPS can change speed as needed, slow down for 'bullet time', or gradually speed up like Wario Ware.
But if you design it for ANY fps, you need drawing logic that will handle that. Using on-demand VRAM loading depending on what graphics are visible in the frame is a good way to achieve this. But it needs to be designed to be interrupted at any time, so it won't display half-finished or inconsistent graphics.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#168469 - Miked0801 - Wed Apr 29, 2009 6:39 pm
Running a game at anything outside of the standard 60/30/20... timing is just asking for graphical shearing and the likes. VBlank is there for a reason after all :)