2D 'Shifted Grid' collision detection

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|526\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> Collisions and Physics

LostUser	Created : 23 June 2008 System : Windows Language : Blitz 2D 'Shifted Grid' collision detection collision detection demo by big10p (A.K.A. Chris Chadwick) 2004.
; ; 2D 'Shifted Grid' collision detection demo by big10p (A.K.A. Chris Chadwick) 2004. ; ; Written with Blitz3D v1.86 ; ; Based on an original C/C++ article by Tom Moertel. ; ; ; The 'shifted grid' method is great for doing collision detection when huge numbers ; of sprites are involved! Basically, it involves dividing the play area into a grid of ; sectors and then only checking for collisions between sprites that occupy the same sector. ; Because of the mechanics of this method, it's also necessary to 'shift' this grid right, ; down and down-right, re-checking for collisions each time. This may sound wasteful/slow but ; it's really not - it's MUCH faster than checking every sprite against every other sprite! ; ; This demo shows how the shifted grid method works well with large scrolling playfields, ; when you still need to check for collisions between objects that are currently off-screen. ; ; The key to getting the best performance out of this method is in setting the grid sectors ; to the optimal size (see SECTOR_SIZE, below). What is optimal? That depends on the type of ; situation it's being used in, for example: ; - If the objects in your game tend to bunch together into large clusters, use a small ; sector size. ; - If your game has a large, scrolling playfield and the objects tend to be fairly well ; spaced apart, use a larger sector size. ; ; Basically: set SECTOR_SIZE so that it's unlikely that a large amount of sprites will ever ; occupy a single sector of this size! ;) ; Const SCREEN_WIDTH% = 800 Const SCREEN_HEIGHT% = 600 Const MAP_WIDTH% = 40 Const MAP_HEIGHT% = 40 Const PIXEL_WIDTH% = MAP_WIDTH * 32 Const PIXEL_HEIGHT% = MAP_HEIGHT * 32 Const MAX_WINDOW_X% = PIXEL_WIDTH - SCREEN_WIDTH Const MAX_WINDOW_Y% = PIXEL_HEIGHT - SCREEN_HEIGHT Const SCROLL_SPEED% = 4 Const NUM_SPRITES% = 1000 Graphics SCREEN_WIDTH,SCREEN_HEIGHT,32 SetBuffer BackBuffer() SeedRnd MilliSecs() Global frame_count% Global fps% Global slowest_fps% Global fps_timeout% Global frame_time% Global slowest_frame% Global frame_start% fps_timer = CreateTimer(60) slowmo% = False ; Pseudo sprite object, just for demo purposes. Type spriteT Field x#, y# ; World coords, not screen! Field vx#, vy# Field r%, g%, b% Field width%, height% Field sector_link.spriteT ; Links all sprites within a given sector. Field hit% ; Flag to indicate if sprite has collided. End Type ; Collision detection grid control consts/vars. ; Note: to work properly, SECTOR_SIZE must conform to the following: ; 1) Must be a power of 2 in order to enable the fast method of sorting sprite's ; into sectors, using a bit-shift operation with find_sector (see update_sectors()). ; 2) Must be big enough to catch collisions of sprites with the largest bounding box length. ; That is: biggest bounding box length allowed = (SECTOR_SIZE/2)+1 ; E.g., A sector size of 64 will work for sprite's upto 33x33 in size. Const SECTOR_SIZE% = 64 ; Length of sector side (in pixels). Const SECTOR_SHIFT% = SECTOR_SIZE/2 ; Sector offset for 4-shift operation. Const NUM_X_SECTORS% = (PIXEL_WIDTH+SECTOR_SIZE-1)/SECTOR_SIZE ; Horizontal sectors in grid. Const NUM_Y_SECTORS% = (PIXEL_HEIGHT+SECTOR_SIZE-1)/SECTOR_SIZE ; Vertical sectors in grid. Global find_sector% = Log(SECTOR_SIZE)/Log(2) ; Right bit-shift to get sector from coord. ; Linked list heads - one for each sector in the collision detection grid. Dim sector_head.spriteT(NUM_X_SECTORS,NUM_Y_SECTORS) create_sprites(NUM_SPRITES) Global tiles Dim map(MAP_WIDTH-1,MAP_HEIGHT-1) create_tiles() create_map() Global window_x% = MAX_WINDOW_X% / 2 Global window_y% = MAX_WINDOW_Y% / 2 ; --- Main Loop --- While Not KeyDown(1) frame_start = MilliSecs() If KeyHit(57) Then slowmo = Not slowmo If KeyDown(203) window_x = window_x - SCROLL_SPEED If window_x < 0 Then window_x = 0 Else If KeyDown(205) window_x = window_x + SCROLL_SPEED If window_x > MAX_WINDOW_X Then window_x = MAX_WINDOW_X EndIf If KeyDown(200) window_y = window_y - SCROLL_SPEED If window_y < 0 Then window_y = 0 Else If KeyDown(208) window_y = window_y + SCROLL_SPEED If window_y > MAX_WINDOW_Y Then window_y = MAX_WINDOW_Y EndIf render_map() act_on_collisions() ; Draw all sprites and update their position. For spr.spriteT = Each spriteT If RectsOverlap(spr\x,spr\y,spr\width,spr\height, window_x,window_y,SCREEN_WIDTH,SCREEN_HEIGHT) ; Convert world->screen coords. swx# = spr\x - window_x swy# = spr\y - window_y Color spr\r,spr\g,spr\b Rect swx,swy,spr\width,spr\height,1 EndIf new_x# = spr\x + spr\vx If new_x < 0 Or new_x > PIXEL_WIDTH-1 Then spr\vx = -spr\vx spr\x = spr\x + spr\vx new_y# = spr\y + spr\vy If new_y < 0 Or new_y > PIXEL_HEIGHT-1 Then spr\vy = -spr\vy spr\y = spr\y + spr\vy Next frame_time = MilliSecs() - frame_start show_info() WaitTimer(fps_timer) VWait Flip(0) If slowmo Then Delay 200 Wend FreeImage tiles FreeTimer fps_timer End ; ; Renders screen portion of tile map. ; Function render_map() map_y = window_y/32 screen_y = -(window_y Mod 32) m_x = window_x/32 s_x = -(window_x Mod 32) While screen_y < SCREEN_HEIGHT map_x = m_x screen_x = s_x While screen_x < SCREEN_WIDTH DrawBlock tiles,screen_x,screen_y,map(map_x,map_y) map_x = map_x + 1 screen_x = screen_x + 32 Wend map_y = map_y + 1 screen_y = screen_y + 32 Wend End Function ; ; Creates simple, background tile map. ; Function create_map() For x = 0 To MAP_WIDTH-1 For y = 0 To MAP_HEIGHT-1 If x=0 Or x=MAP_WIDTH-1 map(x,y) = 1 Else If y=0 Or y=MAP_HEIGHT-1 map(x,y) = 1 Else map(x,y) = 0 EndIf EndIf Next Next End Function ; ; Creates a couple of tile images. ; Function create_tiles() tiles = CreateImage(32,32,2) SetBuffer ImageBuffer(tiles,1) Color 128,0,128 Rect 0,0,32,32 Color 192,0,192 Rect 0,0,31,1 : Rect 0,0,1,31 Color 32,0,32 Rect 31,1,1,31 : Rect 1,31,31,1 SetBuffer ImageBuffer(tiles,0) Color 0,0,128 Rect 0,0,32,32 Color 0,0,192 Rect 0,0,31,1 : Rect 0,0,1,31 Color 0,0,32 Rect 31,1,1,31 : Rect 1,31,31,1 SetBuffer BackBuffer() End Function ; ; Creates requested number of sprites. ; ; Params: ; num - Number of sprites to create. ; Function create_sprites(num%) For n = 1 To num spr.spriteT = New spriteT spr\r = 50 + Rand(205) spr\g = 50 + Rand(205) spr\b = 50 + Rand(205) spr\x = Rand(0,PIXEL_WIDTH-1) spr\y = Rand(0,PIXEL_HEIGHT-1) vel# = Rnd(.1,5.0) vx# = vel-Rnd(0,vel) vy# = vel-vx If Rand(0,1) Then vx = -vx If Rand(0,1) Then vy = -vy spr\vx = vx spr\vy = vy s = Rand(10,20) spr\width = s spr\height = s Next End Function ; ; Calculate and act on all collisions. ; Function act_on_collisions() ; Reset all sprites' collision hit flag. For spr.spriteT = Each spriteT spr\hit = False Next ; Check all sectors, shifting the grid as we go in order ; to catch collisions that occur across a sector boundary. ; Note: due to this mechanism, it's possible some collisions ; will be detected more than once. The actual collision ; detection/action code must take this into account. update_sectors(0, 0) check_all_sectors() update_sectors(SECTOR_SHIFT, 0) check_all_sectors() update_sectors(0, SECTOR_SHIFT) check_all_sectors() update_sectors(SECTOR_SHIFT, SECTOR_SHIFT) check_all_sectors() End Function ; ; Put all sprites into correct sector linked list. ; ; Params: ; shift_x_off - Horizontal offset to shift sector grid by. ; shift_y_off - Vertical offset to shift sector grid by. ; 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 ; ; Check all sectors for collisions. ; Function check_all_sectors() For sx% = 0 To NUM_X_SECTORS For sy% = 0 To NUM_Y_SECTORS check_sector_collisions(sector_head(sx,sy)) Next Next End Function ; ; Checks for collisions between all sprites in the given sector linked list. ; ; Params: ; sprite_list - Linked list of sprites to check collisions between. ; Function check_sector_collisions(sprite_list.spriteT) ; Ignore sectors with 0 or only 1 sprite in them. If sprite_list = Null Return ElseIf sprite_list\sector_link = Null Return EndIf ; Check for collisions between all sprites in this sector. spr1.spriteT = sprite_list While spr1\sector_link <> Null spr2.spriteT = spr1\sector_link While spr2 <> Null ; Don't bother checking if spr1 & spr2 have already been involved in collisions. If spr1\hit = False Or spr2\hit = False ; Time to actually see if these 2 sprites have collided! ; For demo purposes, we'll simply see if their rects are intersecting. If RectsOverlap(spr1\x,spr1\y,spr1\width,spr1\height, spr2\x,spr2\y,spr2\width,spr2\height) ; OK, spr1 & spr2 have collided! Let's simply swap their velocity vectors ; in an 'attempt' to make them bounce off each other. :P temp_x# = spr1\vx temp_y# = spr1\vy spr1\vx = spr2\vx spr1\vy = spr2\vy spr2\vx = temp_x spr2\vy = temp_y ; Indicate these 2 sprites were involved in a collision. spr1\hit = True spr2\hit = True EndIf EndIf spr2 = spr2\sector_link Wend spr1 = spr1\sector_link Wend End Function ; ; Display debug info ; Function show_info() If fps_timeout frame_count = frame_count + 1 If MilliSecs() > fps_timeout Then fps_timeout = MilliSecs() + 1000 fps = frame_count frame_count = 0 If fps < slowest_fps Or slowest_fps = 0 Then slowest_fps = fps EndIf If frame_time > slowest_frame Then slowest_frame = frame_time If 1 Color 255,255,255 Text 10,10,"(Press ARROW keys to scroll, SPACEBAR to toggle slow motion)" Text 10,40," Sprites: " + NUM_SPRITES Text 10,55," Millisecs: " + frame_time Text 10,70," Slowest: " + slowest_frame Text 10,85," FPS: " + fps Text 10,100," Worst: " + slowest_fps Text 10,130,"Sector Size: " + SECTOR_SIZE Text 10,145," X Sectors: " + NUM_X_SECTORS Text 10,160," Y Sectors: " + NUM_Y_SECTORS Text 10,175," Shift: " + find_sector Text 10,185," Window X: " + window_x% Text 10,195," Window Y: " + window_y% Text 10,205,"Map Size (pixels): " + PIXEL_WIDTH + "x" + PIXEL_HEIGHT EndIf Else ; First call initialization. fps_timeout = MilliSecs() + 1000 EndIf End Function --v

Comments
Tuesday, 24 June 2008, 05:01
JL235	It says at the top that it is 'Based on an original C/C++ article by Tom Moertel', where is this article? Is it online?
Thursday, 26 February 2009, 00:40
LostUser	I don't know, try emailing big10p on BlitzBasic.com
Thursday, 26 February 2009, 01:04
Jayenkai	See here

2D 'Shifted Grid' collision detection

Comments