   FAST Way of checking whether sprites are on screen, near each other...
  Hello,are there any ways you can check sprites, for example if they are on screen or if they are near each other? I'm currently doing it like this:void CSceneGame::SetItemsOnScreen(void){for( map<int, int>::iterator ii=m_ItemsAvailable.begin(); ii!=m_ItemsAvailable.end();++ii){int i = m_ItemsAvailable[ii->first];if(m_Collision->Collision(-256, 0, 1536, 768, m_Items[ii->first].Sprite())){m_ItemsOnScreen[ii->first] = 1;}else{m_ItemsOnScreen.erase(ii->first);}}}To explain some (maybe a bit) confusing parts: m_ItemsAvailable is an array storing the IDs of all Items that aren't already deleted (for some purpose I'm doing kinda "soft-delete". The other parts should be mostly clear. Whenever the screen moved, I iterate through all available Items, colliding their sprites position with a slightly bigger screen), and eigther adding their ID to the m_ItemsOnScreen-Map or deleting it.So, are there any faster ways than that? It seems a bit odd.. I've always got to check all Items, no matter if they are 20000 pixels away or in the middle of the screen and won't out-move the screen in the near time.. I quess the way I do it would be accurate if I only had Items, but.. I've got tiles (currently, going to change that), enemys, obstacles, .. , so that means a lot of iterating and collision-detection.. Any Ideas how to do that in a faster way? Next point is the determination whether objects like enemys are near each other. Thats my current code for that:void CSceneGame::GetEnemysInRange(void){map<int, int> TempEnemys;TempEnemys = GetEnemySprites();map<int, int> TempEnemys2;TempEnemys2 = GetEnemySprites();    CSprite *Sprite;for(map<int, int>::iterator ii=TempEnemys.begin(); ii!=TempEnemys.end(); ++ii){TempEnemys2.erase(ii->first);Sprite = GetEnemySprite(ii->first);for(map<int, int>::iterator jj=TempEnemys2.begin(); jj!=TempEnemys2.end(); ++jj){if(m_Collision->Collision(Sprite->GetPosition().x - 16, Sprite->GetPosition().y - 16, Sprite->GetWidth() + 48, Sprite->GetHeight() + 48, GetEnemySprite(jj->first))){m_EnemysInRange[ii->first][jj->first] = true;m_EnemysInRange[jj->first][ii->first] = true;}}}}So, that's where things are really getting ugly and I could need some "wonder-method". Because, actually I'm checking each and every enemy against each other. And thats just insane, imagine 100 enemys, that would be 10000 loop-runs, each consisting of a collison-check. I've made some improvements, so that no enemys are unneccesarly checked twice, but that doesn't seem to be enough. I get huge lags if there are 100 enemys on the screen. It's as bad that somehow having this check slows the game down, even if I use the values for the collision-check of the enemys. The code works nice for the player, simply because there are not that many checks, and the actual detection for a collision with anything can sometimes be executed 6 times (because I use some ray-casting-thing).Long explanation, but short question: Is there any way to make do that in a simplier and/or faster way?Last thing, what about the code for collision-detection itself? Maybe there are some possibilities of improvements here? I quess that would all be some small optimizations, but as that method is the most-called in my code, I wonder if that wouldn't give me at least some ms less to process.bool CCollision::Collision(CSprite *Sprite1, CSprite *Sprite2){int left1, left2;    int right1, right2;    int top1, top2;    int bottom1, bottom2;left1 = Sprite1->GetPosition().x;    left2 = Sprite2->GetPosition().x;    right1 = Sprite1->GetPosition().x + Sprite1->GetWidth();    right2 = Sprite2->GetPosition().x + Sprite2->GetWidth();    top1 = Sprite1->GetPosition().y;    top2 = Sprite2->GetPosition().y;    bottom1 = Sprite1->GetPosition().y + Sprite1->GetHeight();    bottom2 = Sprite2->GetPosition().y + Sprite2->GetHeight();    if (bottom1 < top2) return false;    if (top1 > bottom2) return false;    if (right1 < left2) return false;    if (left1 > right2) return false;    return true;}Well, I hope someone got some solutions/ideas here. PLS do not tell me about Quad-Trees, I already know about that and am going to implent it sometimes, but first of all I want that the existing code works better..   
  Ok, so think about this.  You're doing a spatial check for collisions, right?(space based)... How would you optimize this?  Well the easiest way is by pruning unneeded checks right?  I mean why do N^2 checks when you only need to do a very small set of checks?The key to optimizing this is doing higher level spatial checks to allow you to intelligently not check things that could not possibly be intersecting.  Why not use QuadTrees?  What is your aversion to this VERY simple solution?If you're to not use QuadTrees you will need to think up your own hierarchical spatial checking algorithm that will prune unnecessary checks (e.g. bounding circle hierarchy or something, but that could be harder than just using QuadTrees, depending on your application/requirements).Essentially a quadtree check is just asking if two items are in the same quad, if they are go one level deeper to the 4 sub quads and ask if these items are still in the same quad (etc) down to the lowest level check that makes sense.  It's really easy!  Don't let it scare you, just go for it!EDIT: FYI: In one of my GBA homebrew apps I just checked the Hero character against all enemies on the screen, wasn't slow at all, but not that many enemies at a time (10 at most).  If I checked all enemies against one another brute force? Well, this might suffer.[Edited by - RazzleGames on November 17, 2010 5:42:13 PM];  The other thing I noticed here is you hinted at checking against all tiles with all items.  Well if you have the states of the items as being within a certain tile, and the previous state (tile before) you shouldn't even need a spatial hierarchy for those checks (if I understand your requirements correctly).  The exception would be if the map tiles were moving around and all that, then QuadTrees might be the best solution (but if you have a map structure at index[N] that just goes from being TILE1=don't care to TILE2=COLLISION_STUFF, then checking is still just a map structure check, even with moving tiles. No need for Quadtree). I mean you can easily know what tile the item/character/etc is intersecting by knowing it's screen coordinates.  Most tile systems are a set size (e.g. 8 pixel by 8 pixel tiles), you just do some mod math to find out which tile the item intersects based on the map space coords of the item (screen space to map space coordinate conversion).  Of course I can see quad trees handling most of this for you also, but anyhow... either way keep the state from the previous frame.   This way you know what to do when you find a collision.Let me know if this makes sense.[Edited by - RazzleGames on November 17, 2010 6:34:42 PM];Quote:Original post by The King2To explain some (maybe a bit) confusing parts: m_ItemsAvailable is an array storing the IDs of all Items that aren't already deletedEh? I don't see an array; I see a std::map. What do the keys represent, and what do the values represent?   ;  @RazzleGames: Thanks a lot, you gave me some very constructive points. Well, let's go into detail:Quote:The key to optimizing this is doing higher level spatial checks to allow you to intelligently not check things that could not possibly be intersecting.Ok, well the point that I found kinda disturbing here was that to get less checks, you need to do other checks first. I already did so, for example determaining if objects are on screen (Thats like a quad-tree but without any childs, just the first parent is checked to determine if objects are on screen). But for anything else I would need to do a lot of other if-statement-checks.. seemed to me like I was doing something wrong oOQuote:Why not use QuadTrees? What is your aversion to this VERY simple solution?Uhm... its some facts that irritated me about that. But now from reading a tutorial on gamedev.net I think I figured it out.. The main problem was that despite of but anyway, I don't see any certain use of "real" quadtrees here. I think I go better with a custom algorythm. I already came up with another idea, could this work?DON'T READ THAT; except you want to see how hardly you can fail; see next post for an expansion of that idea that should really work.To compare this to the original idea of quadtrees, I'm coming up with an example, having 100 Enemys on the screen at timeSo bascially, before checking the enemys for collisions with each other, I would do some Kinda-like-quadtree-thing. I would split the screen into 4 areas, but instead of checking in which part of the screen a certain enemy lies, I check WHERE all the enemys lie. I sort that values so they are set in any form of container, representing the four parts of the screen. I do the check using the screen-parts position (0|0 for the first, 512|0 for the second) and the coordinate of the enemys sprite in a quite complicated way I came up with, but I think it should work fine. Some brief explainations:I devide the sprites x and y position seperatly without remainder through the screen-parts sizes. That values tell me in which screen part the sprite is (636|200 through screen parts size 512 | 384 should give me back 1 | 0 -> sprite is in upper right sprite part for resolution 1024*768). I also do that again, first adding the sprites size (for the case the sprite is in multiple parts. The results are stored in a map<xID, map<yID, vector<EnemyID>> which I work on.So, here, that would be 100 "checks" (i don't check a damn thing, just math!) in total. Let's say in every screens area there are exactly 25 sprites. So I would now go on quartering the remaining screen parts using the map from before (empty parts aren't used further), doing the check again, but with some modified conditions. The logic coordinates of the sprites are stored, and modified depending on which part of the screen they are in (posx - 512; posy - 0 for the upper right part of the screen). Now I do exactly the same as before, but with the new values for screen parts positions (0|0, 256|0, 512|0 , ..) and size (256|192).  Our example from before: Position 636|200 in Screen Part 1 | 0 would now logically be 124|192. Devide it through screen parts size will give me 0 | 0 for the new child screen part position. Add the parent position 1*4 | 0*4 would give me position 4*4 (so its in the 5th screen part from left and 1st from aboth). Storing these values in a temporary map, similar to the first one, and using this new map further on will now follow (or maybe a copy to the original map if I find a quick way to do so). Again, 100 "checks".That will now go on another 2 or 3 times. The number of "checks" will stay constantly at 100 per time, which is a good value compared checking 100 enemys against each of themself (10000 REAL checks would follow).At the end I got a map, containing pairs of enemy-ids that are in the same "leaf". When doing the actual enemys collision detection, I search for the screen-leafes in which the enemy appears, and can now easily collide only the enemys that are on the same part of the screen. I might even store any collisions between enemys so I don't have to collide enemys twice( remember, I'm iterating through my map<> of enemys. if enemy 1 collides with enemy 20 than logically enemy 20 also collides with enemy 1).Soo.. what do you think about this? I hope it is somehow clear and not too long.. Do you think that could work or will be fast? I't somewhat theoretically, actuall I'm sure I know how to implement that but I don't have access to a pc with a compiler right now.I've got to go, but I'm going to respond to the rest of the answers to that topic later..[Edited by - The King2 on November 18, 2010 10:34:26 AM];  Gosh, sports can sometimes make you really creativ - I just found out that my idea from the last post was kinda redundant. The principal was right, but the actual version should work less complicated:I devide the screen into "cols" and "rows" with a certain size (I think I'm going to choose 32*32), so no f**king around with quartering the screen anymore. Next, I iterate through all the sprites of my enemys that are on screen. I devide the sprites coordinates through the width and height of the fields without remainders (638|200 should return now 19 and 6 -> sprite is at field (19|6)). I than add the ID of the sprite to a map<xID, map<yID, vector<EnemyID>>. Now I devide the width and height of the sprite through the size of the fields, the value I get from that calculation tells me how many additional fields the sprite is at and I add the sprites ID to that fields. After the iteration, I go once through the whole map, deleting all fields where only one enemy is on. So, here is another question: How is that done the best way? Do I need to iterata using a loop again or is there any command or "trick" to allocate map<> with size 1 inside another map? After each iterate, if the field hasn't been deleted, I handle field x/y to the enemys that are on it. While colission detection, I only need to go through the fields that are shared, which shouldn't be very much, too.So, that should do it here. I haven't had the possibility to built it or test it out, but that looks just so promising (except I made some logical mistake) and so damn fast.. there seems to be as less checks as possible while collision detection and the algorythm itself appears to be very fast. Appears to be no need for a quad-tree anymore. Well, I'll try it out as soon as I come home. Ok, let's move on:Quote:}The other thing I noticed here is you hinted at checking against all tiles with all items. Well if you have the states of the items as being within a certain tile, and the previous state (tile before) you shouldn't even need a spatial hierarchy for those checks (if I understand your requirements correctly).Won't work properly, as my objects are moving with non-static speed, they can move 1 pixel, but also 2.5, and so on.. to align my objects to the ground flawless (I've seen many *bad* games having an issue that the characters are always 1-2 pixels above the ground, isn't destroying the gameplay but looks ugly) I can't simply use the last state before the collision, because that could be 2-3 pixels away from the ground. I don't really see any other possibilies to spatial checking.[qoute]The exception would be if the map tiles were moving around and all that, then QuadTrees might be the best solution (but if you have a map structure at index[N] that just goes from being TILE1=don't care to TILE2=COLLISION_STUFF, then checking is still just a map structure check, even with moving tiles. No need for Quadtree).I mean you can easily know what tile the item/character/etc is intersecting by knowing it's screen coordinates. Most tile systems are a set size (e.g. 8 pixel by 8 pixel tiles), you just do some mod math to find out which tile the item intersects based on the map space coords of the item (screen space to map space coordinate conversion).[/qoute]Hm, I need to anyway rebuild my tile system. I currently used a flexible one where the tiles are represented by sprites, which is somewhat not really usefull. I did that because working with some smw-rom-editor the tiles seemed to behave the same way.. but i think the performance on "standard"-methods is better, so i gotta take a look at some other systems for that.Eh? I don't see an array; I see a std::map. What do the keys represent, and what do the values represent?@Zahlman:Quote:Eh? I don't see an array; I see a std::map. What do the keys represent, and what do the values represent?Oh, sry, std::map was what i meant.. the first int represents the ID of an item refering to its position in the vector m_Items (so, m_Items[ii->first] will access the item). The second has not much use yet, but might be useful later on for setting certain states to special items on the screen.   ;  What you're describing sounds like a grid. Whether or not that's the best data structure to use depends on the situation.For a small number of items, checking every item in the list is just fine as long as it's fast enough for your needs.But search time increases linearly as the number of items increases, so that doesn't scale well. If you're working with more items than the naive approach can handle, you'll need something better. So, let's divide the scene into a grid and store references to items in grid cells. Determining which cells to check is a quick check that reduces the number of items to check by a certain factor.There's a few caveats, though: you'll need to filter duplicate references (due to items that overlap multiple cells), which adds overhead. So choose the cell-size wisely: if it's too fine, you'll have a lot of duplicate checking to do, but if it's too large, you won't be able to cull as many items.Also, some cells may be empty, while others may be overpopulated. So sometimes you're wasting parts of your grid on empty cells, and sometimes you'll still be checking a lot of items that could have been culled.If items are spread irregularly across the scene, a quadtree may be better. It's essentially a hierarchy of grids. It's like dividing overcrowded cells into smaller cells - so cells themselves can also contain grids. You'll have few cells in sparsely populated areas, but more in areas where items are clustering together. Each layer adds an additional check, but can reduce the number of items to check by yet another factor.Again, which structure works best for you depends on the situation. Personally, I would hide the actual implementation under a well-defined interface. Say, a class that supports the following functions:- getItemsInArea(rectangle)- addItem(item)- removeItem(item)- updateItem(item)A SimpleList class could use a simple container under the hood - so adding an item adds it to a list, and getItemsInArea would iterate over all items in that list.A Grid class could store item references in a 2D list of cells, so it's getItemsInArea function only has to check the content of the cells that touch the given area.A Quadtree class would do something similar, except that it can call the getItemsInArea function recursively on it's child nodes until all items have been found.Variations on the above or totally different data structures could still adhere to the above interface.You can then easily swap the data structure for another and see how that affects performance. Be sure to make them configurable - for the grid, you should be able to specify the size of the world and the cell-size. For the quadtree, the world size and the number of items at which a node should split into child-nodes.   ;Quote:Original post by The King2Won't work properly, as my objects are moving with non-static speed, they can move 1 pixel, but also 2.5, and so on.. to align my objects to the ground flawless (I've seen many *bad* games having an issue that the characters are always 1-2 pixels above the ground, isn't destroying the gameplay but looks ugly) I can't simply use the last state before the collision, because that could be 2-3 pixels away from the ground. I don't really see any other possibilies to spatial checking.I still have to parse through the rest of your posts, but this (before and after state tracking) should not be discounted.  I am fairly sure most sprites don't move one pixel at a time ;).  This is not an issue though, but some care is needed.  Let's say you're sprite is on one side of a "wall tile", next frame it's on the other side.  You check the path of the sprite given it's before and after position and if it was supposed to be able to pass through that "wall tile" that it clearly passed through.Also think of this:  You have two very fast moving sprites that are on a collision course, one frame they are heading towards each other, the next they have skipped over each other.  What should you do?  Well you should detect the collision and correct the sprite/character states, that's what ;)No amount of Quadtrees or spatial checks will grab this one, you have to know if the paths crossed given the before and after states.  But: Spatial checks will help you prune the amount of "path intersection" tests.(I exaggerate slightly, since this issue will only come about if your sprite can potentially move faster than a collision box per frame.  Or, well 1/2-ish a collision box per frame if they are headed straight for each other).   ;  @Captain P:Ok, I think I get what you want to tell me, but..There are some important facts unclear to me. Quote:So, let's divide the scene into a grid and store references to items in grid cells. Determining which cells to check is a quick check that reduces the number of items to check by a certain factor.Yeah, thats basically the way I do it right now. But determining to check what? If you mean what cells, or their items, to use for collision-detection, I'm already doing this. Or do you mean something else?Thats the code I use right now btw. I quess it won't be clear at all, but it should show the basic functionality:void CSceneGame::GetEnemyFields(void){map<int, int> TempEnemys;TempEnemys = GetEnemySprites();int FieldX;int FieldY;int WidthF;int HeightF;for(map<int, int>::iterator ii=TempEnemys.begin(); ii!=TempEnemys.end(); ++ii){FieldX = GetEnemySprite(ii->first)->GetPosition().x / 32 + 1;FieldY = GetEnemySprite(ii->first)->GetPosition().y / 32 + 1;WidthF = GetEnemySprite(ii->first)->GetWidth() / 32;HeightF = GetEnemySprite(ii->first)->GetHeight() / 32;m_EnemyFields[FieldX][FieldY].push_back(ii->first);m_Enemys[ii->first].AddField(FieldX, FieldY);while(WidthF > 0){m_EnemyFields[FieldX + WidthF][FieldY].push_back(ii->first);WidthF--;m_Enemys[ii->first].AddField(FieldX, FieldY);}while(HeightF > 0){m_EnemyFields[FieldX][FieldY + HeightF].push_back(ii->first);HeightF--;m_Enemys[ii->first].AddField(FieldX, FieldY);}}}So, I store all grids that are used (I use standard values of 32 in the code right now) containing the Enemy IDs on it into the earlier described map. I also handle the coordinates of every Cell each enemy is in them, and use that values later on during the collision detection to get the IDs of the other enemys that are on the same grid.Quote:There's a few caveats, though: you'll need to filter duplicate references (due to items that overlap multiple cells), which adds overhead. So choose the cell-size wisely: if it's too fine, you'll have a lot of duplicate checking to do, but if it's too large, you won't be able to cull as many items.Items overlapping multiple cells shouldn't be a problem, or, at least nothing that I have to filter.. right? I think the only thing to filter is when 2 items are sharing more than 1 cell. Did you mean that? Plus, whats the way to check a map for duplicates with the most performance? There must be something better than just iterating through the whole map..Well, using the code above has made a big improve on to the performance. While I wasn't able to display more than 40 enemys on the screen at the same time without FPS slipping down to <30 FPS from 60, I can now have about ~200 fully functional enemys walking around at the same time at the screen, while my FPS only drop to 50. The code isn't totally finished yet, it might eigther improve or get worse.. but I thinkt here is still a huge space for improvements.The main problem that I'm facing is that every frame, I have to determine the cell of every enemy AGAIN. Thats due to the fact that nearly every enemy on the screen is constantly moving. Can you give me a hint what to do here? I run the function GetEnemyFields() again every frame, and it is always running through the same algorythm, determining the grid-position of the enemy. Isn't there any faster way to determine if an enemy moved and move him to the new grid if he left the last one he was at? It can't figure out how I could simply MOVE the enemy inside of the 32*32-sized grid instead of DETERMINING the grid every frame..I mean, the grid and quad-tree-thing would work so nice for static objects (for example for tiles) but as far as more than half of the objects move around every frame, things get ugly.. - getItemsInArea(rectangle)[/source]Ehm, I wonder where I could use that thing? I wouldn't need to check a rectangular area, because I tell every enemy which grid(s) he on and then find out if there are enemy on that grids and if yes, what enemys that are. So it seems like my method is even more valid and having a better performance, because at least I only have to check the grid position of all enemys on screen 1 time and then everything works mostly on its own. Or am I mistaken?@RazzleGames:Ah, I get it. Actually I think I'm already doing this in a certain type.. I'm doing the collision detection before the sprites are actually moved, so I use the position (before?) and check the collision adding the speed (after?). Then I'm recursivly reducing the move speed 1 px per step as long as there is still a collision. Thats done first for x-movement until there is no collision, and then for added x (now correctet within the first check) and y-movement - that might occour strange at first but I came to the conclusion that adding the modified x-movement to the second check for the vertical movement would help avoiding some issues.Err, I know thats not exactly what you meant. But as you see I would be able to do what you submitted easily without much modification. But nah, objects are never moving more than a bounding-box. Ah yeah, when I said 1 px I meant per FRAME, not per SECOND, because thats the way my game is handling it. So said at a average bounding-box size of 32*54 I highly doubt that any of my objects moves more than 960 px per second xD I think that would be more an issue if I was making a sonic than a mario game.;  Hey I have a few questions for ya: 1) Are you just checking collisions with?: Hero - EnemyHero - TilesEnemy - Tiles(So mainly I am asking, are you doing enemy - enemy collisions?)2)  Why all the map structures and such?  Is there some compelling reason for a hash like structure?  I may have missed some details, I will have to reread, but I am a bit confused as to why that added complexity is needed.Why not just use a dynamic array to fill with screen objects (e.g. std::vector etc)?I am not trying to stifle creative coding, just curious.   