Shifted Grid collision

http://www.blitzbasic.com/codearcs/codearcs.php?code=1065

Now, I think I understand most of it, but I have some questions.

Just to make sure I don't have the entirely wrong idea about the system here, it works by:

dividing the area into a grid, and having a TList per square, the TLists saved inside an array. When I am to check objects for collisions, I only check the objects within a grind against each other, and not against those of an outside grind. Thus, objects that are really far apart won't check collisions against each other.
---

Function update_sectors(shift_x_off%, shift_y_off%)

	; Reset sector linked list heads.
	For sx% = 0 To NUM_X_SECTORS
		For sy% = 0 To NUM_Y_SECTORS
			sector_head(sx,sy) = Null
		Next
	Next

	; Put each sprite into it's sector's linked list.
	For spr.spriteT = Each spriteT
		sx = Int(spr\x + shift_x_off) Shr find_sector
		sy = Int(spr\y + shift_y_off) Shr find_sector
		spr\sector_link = sector_head(sx,sy)
		sector_head(sx,sy) = spr
	Next
	
End Function

So, as I've understood this, this is a bit-shift operation in order to quickly and effectively sort the sprites into the right sectors. But, I really don't understand exactly how it works. What does the Shr command do? the documentation didn't help me at all. >_>

Can anybody explain just how this works step by step?

---

Next, I have a bit different setup than the example game inside the code (it's just some basic sprites moving around). You see, my game doesn't a limit to the world size in any way.

I do it in a simple way. There is an X and Y for the screen, and all objects are modified according to this X and Y.

So, if the screen is at 100,100, and an object is at 150,150, then the object will be drawn at 50,50. Thus, by just adding and subtracting to the screen X and Y, we move around on an unlimited map (well, until the integer can't hold such a large number anymore ^^).

Any units outside a certain distance is deleted, preventing the massive load that would come after a while. And of course, objects are randomly created as you travel ahead, to simulate that you travel and stumble upon random stuff.

I don't see a problem, but is it possible that this can crash with the way the sectors are divided across the world? All I see that I need to do is have the sectors move as the screen does, but I don't exactly understand how the shift things works, so I might be missing out on something big here.

---

Another question. The reason why 4 sectors needs to be checked all at once is because objects may overlap some sectors, right? If so, then I understand that part, I think.



So, anyway, I had a hard time explaining some of the things here in short terms, so just give a friendly pointer if I didn't give enough information about something in order for you to answer my question, or if you need to look at my code, and not just my explanation of my code, to understand something.

Thanks in advance.

You need to check:
1 grid... when no overlapping

4 grids... when overlapping occours and dimension of object are smaller than height or width of grid-cell

up to 9 grids.. when the dimension of this object is bigger in height or width.

This may happen if there are really rare but big objects in the scene... instead of making the grid-cells bigger you may compute these objects in a special way. Otherwise the many small objects will produce bigger lists to compare against.

As I also don't really know things about bit-shifting:
---
SHR (from a basic dialect, dunno if its nearly the same - 5 bits - in BMax)


Reallocates bit-by-bit to the right. The least significant bits are lost. The zeros are incorporated subsequently in the most significant bits. Only the 5 least significant bits from <number> are always considered with the values of <number> being located between 0 and 31.
SHR relays an unsigned integer division with powers of two ("X SHR Y" corresponds to "X\(2^Y)").
---

Short example:

81 SHR 3 = 81 / 2^3 = 81 / 8 = 10 (like a ceil(result) used)
87 SHR 3 = 87 / 8 = 10
88 SHR 3 = 88 / 8 = 11


So I assume that the shift does:

The find_sector is a global based on a calculation with the gridcell-size (eg. 32) - in this case the variable is 5.0000 .

If object.X is 103 and your gridcell-size is 32 then: Objext.x SHR find_sector

This is the same as: 103 SHR 5 ( ceil(103 / 2^5) = ceil(103 / 32))

Result will be 3 ... the coordinate x=103 lies in grid[3,y]
Remember that grid[0,0] exists (zero based start).


Assuming this, you can say that bitshifting is a shortcut to ceil a variable ... It's a useful thing like MOD.

So it may be also possible to calculate the correct grid by:
GridX = ceil(Object.X / gridsizeX)

But when the SHR-command is used, we can nearly be sure that it's done for the thought of speed improvement.


Hope I'm not totally wrong... if it's correct, I learnt something ;D.

bye
MB

Ah, I see, so the SHR command is used to quickly identify which list the object is going into without dividing and all that slow crap that I would do. Genius!

Hmm, yes, then I think I know enough to start making these grinds. However, is somebody knows the answer to my other questions, then please answer!

Create a collision grid the size of the rectangle defined by the distance you're using to delete sprites that are 'out of range'. You MUST ensure that no sprite can exist outside of this range!

Have grid_x and grid_y variables that specify where the grid is in world coordinates. You can then alter these to scroll around your world.

Have screen_dx and screen_dy constants that specify where the screen is, relative to the top-left of the collision grid.



When sorting the sprites into sectors, subract grid_x and grid_y from the sprites x/y world coords. This'll give the sprites position within the grid.

To find the screen coords of the sprites (i.e. where to draw them), subract screen_dx and screen_dy from the sprites grid coords.

Right.

thanks big10p, that will be very useful.

One last question though.

I have a pretty big universe, often with very small objects, that often have massive collision parties in small areas (due to magnets pulling them into a small area).

This would obviously fit well with small grinds.

However, I have the odd occational big object, like a really big rock or a mothership.

How should I deal with this the most effectivly?

1. Make the grinds bigger.
2. Check more than 4 sectors at once?
3. Have really big objects ignore the grind system and check collisions against everything like the old system (since big objects are rare).

Which would you recommend? Or if you can think of a better method than listed here, then spit out. :D

Are you using a collision layer with the tiles?
If that's the case, then you can also add the "big" sprites to the same (or a separate, if you wish) layer, just as you do with the tiles.

Hmm. It sounds like your game isn't particularly well suited to shifted grid. It works best in games where sprites are usually quite well spaced apart. However, shifted grid may still be useful to you...

Well, if the magnetism causes loads of sprites to group together regularly, I'd definately avoid making the grids bigger.

Option 3 may be worth trying. Remeber that the grid sector size has to be twice the size of the largest sprite, so this could really kill performance considering you also have lots of smaller sprites grouped together, due to magnetism.

Another option is to break your big sprites up into smaller sprite tiles. In this case, make the sprite tiles as big as possible - i.e. just small enough to fit the collision grid limitations.

If the sprites cluster together somewhat can't you have a large grid system which keeps track of how many sprites in each sector. Once that sector reaches a threshold it uses a smaller grid. Never done it and no idea if it works. In addition would Leadwerk's Scene Graph help at all?