My baby steps towards a match 3+ game

I never thoughd i would be doing it, but i actualy plan to make a match 3+ game. Something using this princaple:

[imghttp://images.midasplayer.com/images/games/jungle_bubble_348_screenshoot.jpg]
(no, this i not my game :P just googled it up.)

But i have no clue on how todo the matching.
I can imagine, i shoot my 3D sphere() towards the masses, then on collission... ..well, then im lost.

It would be awesome if one can tell me how todo this. Now, a piece of sourcecode would be nice, but i prefer to understand the "technique" behind it, instead of having something to copy and paste.

Does it work on "grid" basis? if so, im much closer to understanding how this works. Than i would just need to loop through the surrounding childs. But i only have experiance on square grids.

I dunno if there's a standard rule for it (Grey?), but for a 2d array of balls I'd do:

- make another array, the same size of the ball-array
- a 2d forloop to check each ball
- for each ball you check its two neighbors, horzontal, vertical and 2x diagonal. If there are 3 the same, then you put a '1' in that 2nd array at the point where you have a match in your first array.
- if you've scanned the whole 2d array, then you have the 2nd array filled with 1's where there are match-3's.

I believe I've done something like this, and iirc it worked.

I have this old bit of demo code (Blitz3D) I did for someone else years ago. It may be of some use, I dunno. Uses a recursive function to check all connected balls. I haven't looked too deeply at the code again - I may well do things differently, now.

	Graphics3D 800,600,32
	SetBuffer BackBuffer()

	WireFrame 0
	AntiAlias 0

	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
	wiref% = False
	
	cam = CreateCamera()
	PositionEntity cam,0,1.5,-36
	CameraZoom cam,1.5
	
	light = CreateLight()
	
	Type gridT
		Field entity
		Field ID
		Field row%, col%
	End Type
			
	Const END_ROW% = 14
	Const END_COL% = 20
	Const GRID_START_X# = Float(-END_COL)
	Const GRID_START_Y# = Float(END_ROW)
	Const KEY_MOVE_FRAMES% = 8
	Const SHOOT_SPEED# = 1.0
	
	; Grid object IDs.
	Const ID_NEW_PLAYER% = -1
	Const ID_SPACE% = 0
	Const ID_WALL% = 1
	Const ID_RED_BALL% = 2
	Const ID_GREEN_BALL% = 3
	Const ID_YELLOW_BALL% = 4
	Const ID_CYAN_BALL% = 5
	Const ID_HORZ_END% = 7
	Const ID_VERT_END% = 8
	Const ID_SET_RANDOM% = 9
	
	Const CLOCKWISE% = 1
	Const ANTICLOCKWISE% = -1

	Const TYPE_PLAYER% = 1
	Const TYPE_WALL% = 2
	Const TYPE_BALL% = 3
	
	Global move_row% = 0
	Global move_col% = 1
	Global move_dx#, move_dy#
	Global move_count%
	Global player_moving% = False

	Dim grid.gridT(END_ROW,END_COL)
	create_level()

	Global player.gridT = New gridT
	player\entity = CreateSphere()
	player\ID = ID_NEW_PLAYER
	position_player(2,10)
	EntityShininess player\entity,1
	EntityType player\entity,TYPE_PLAYER
	EntityRadius player\entity,.9,.9

	Collisions TYPE_PLAYER,TYPE_BALL,1,1
	Collisions TYPE_PLAYER,TYPE_WALL,1,1

	
	; --- Main loop ---
	
	While Not KeyHit(1)
		frame_start = MilliSecs()
	
		If KeyHit(28) Then slowmo = Not slowmo
		If KeyHit(14)
			wiref = Not wiref
			WireFrame wiref
		EndIf

		control_player()
		update_player()	
		
		UpdateWorld
		RenderWorld
		
		frame_time = MilliSecs() - frame_start	
		show_info()

		WaitTimer(fps_timer)
		Flip(1)

		If slowmo Then Delay 500
	Wend

	ClearWorld	

	End


; Initial level grid layout info.
.grid_data
Data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,7,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,0,1
Data 1,0,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,1
Data 1,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,1
Data 1,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,1
Data 1,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,1
Data 1,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,1
Data 1,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,1
Data 1,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,1
Data 1,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,1
Data 1,0,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,1
Data 1,0,0,7,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1



;
; Player control handler.
;
Function control_player()

	If Not player_moving
		
		mxs = MouseXSpeed()
		MoveMouse 400,300
		
		If mxs
			frames = Abs(mxs/3)
			If frames > 10 Then frames = 10
			frames = 11 - frames
			move_player(Sgn(mxs),frames)
		Else
			If KeyHit(57) Or MouseHit(1)
				shoot_player()
			Else
				If KeyDown(203) Then move_player(-1,KEY_MOVE_FRAMES)
				If KeyDown(205) Then move_player(1,KEY_MOVE_FRAMES)
			EndIf
		EndIf
	EndIf

End Function


;
; Updates player's movement and handles collisions.
;
Function update_player()

	If player_moving
		ent = EntityCollided(player\entity,TYPE_BALL)
		If ent
			; A ball was hit...
			ball.gridT = Object.gridT(EntityName(ent))
			
			If player\ID <> ball\ID
				player_is_ball(ball\ID)
				reset_player()
				position_player(player\row,player\col)
			Else
				remove_connected(ball)
				reset_player()
				position_player(player\row,player\col)
			EndIf
		Else
			ent = EntityCollided(player\entity,TYPE_WALL)
			If ent
				; A wall was hit...
				reset_player()
				position_player(player\row,player\col)
			Else
				; Player moving clockwise/anti-clockwise...
				TranslateEntity player\entity,move_dx,move_dy,0		
				move_count = move_count - 1
				If Not move_count Then reset_player()
			EndIf
		EndIf
	EndIf
		
End Function


;
; Recusively removes all connected balls of the same type.
;
Function remove_connected(ball.gridT)

	row = ball\row
	col = ball\col
	ID = ball\ID

	HideEntity ball\entity
	ball\ID = ID_SPACE

	If grid(row,col-1)\ID = ID Then remove_connected(grid(row,col-1))
	If grid(row,col+1)\ID = ID Then remove_connected(grid(row,col+1))
	If grid(row-1,col)\ID = ID Then remove_connected(grid(row-1,col))
	If grid(row+1,col)\ID = ID Then remove_connected(grid(row+1,col))
		
End Function


;
; Turns player into a ball of type ID.
;
Function player_is_ball(ID)

	Select ID
		Case ID_RED_BALL
			EntityColor player\entity,155,0,0
		Case ID_GREEN_BALL
			EntityColor player\entity,0,155,0
		Case ID_YELLOW_BALL
			EntityColor player\entity,155,155,0
		Case ID_CYAN_BALL
			EntityColor player\entity,0,155,155
	End Select

	player\ID = ID

End Function


;
; Resets player's status ready for a new movement.
;
Function reset_player()

	player_moving = False
	
	; Flush all input accumulated while moving.
	MouseXSpeed()
	FlushMouse 
	FlushKeys

End Function


;
; Moves player around ball grid.
; dir    - 1=clockwise, -1=anti-clockwise
; frames - Number of animation frames to make the move.
;
Function move_player(dir%, frames%)
	
	mr = move_row * Sgn(dir) ; Sgn() ensures dir is either CLOCKWISE
	mc = move_col * Sgn(dir) ; or ANTICLOCKWISE.

	new_row = player\row + mr
	new_col = player\col + mc

	If dir = CLOCKWISE
		Select grid(new_row,new_col)\ID
			Case ID_HORZ_END
				move_row = mc : move_col = 0
				new_row = player\row + (move_row*2)
				new_col = player\col + (mc*2)
			Case ID_VERT_END	
				move_col = -mr : move_row = 0
				new_row = player\row + (mr*2)
				new_col = player\col + (move_col*2)
		End Select
	Else
		Select grid(new_row,new_col)\ID
			Case ID_HORZ_END
				move_row = mc : move_col = 0
				new_row = player\row + (move_row*-2)
				new_col = player\col + (mc*2)
			Case ID_VERT_END
				move_col = -mr : move_row = 0
				new_row = player\row + (mr*2)
				new_col = player\col + (move_col*-2)
		End Select
	EndIf
				
	player\row = new_row
	player\col = new_col
	
	; Calculate movement animation to get from old position to new one.
	start_x# = EntityX(player\entity)
	start_y# = EntityY(player\entity)		
	end_x# = GRID_START_X + (new_col*2)
	end_y# = GRID_START_Y - (new_row*2)
	move_dx# = (end_x - start_x) / frames
	move_dy# = (end_y - start_y) / frames
	move_count = frames
	player_moving = True

End Function

;
; Set up player to shoot forward.
;
Function shoot_player()

	If player\row = 2
		move_dx = 0 : move_dy = -SHOOT_SPEED
	ElseIf player\row = END_ROW-2
		move_dx = 0 : move_dy = SHOOT_SPEED
	ElseIf player\col = 2
		move_dx = SHOOT_SPEED : move_dy = 0
	ElseIf player\col = END_COL-2
		move_dx = -SHOOT_SPEED : move_dy = 0
	EndIf

	player_moving = True
	move_count = 9999		; Make sure we can reach a wall!

End Function


;
; Positions player onscreen at level grid row,col.
;
Function position_player(row%, col%)

	player\row = row
	player\col = col
	PositionEntity player\entity,GRID_START_X+(col*2),GRID_START_Y-(row*2),0
	ResetEntity player\entity
	
End Function


;
; Create all level objects.
;
Function create_level()

	pos_x# = GRID_START_X
	pos_y# = GRID_START_Y

	Restore grid_data

	For row = 0 To END_ROW
		For col = 0 To END_COL
			this.gridT = New gridT
			this\row = row
			this\col = col
						
			Read datum
			
			Select datum
				Case ID_WALL
					ent = CreateCube()
					ScaleMesh ent,1,1,Rnd(1,3)			; For a more interesting looking wall
					EntityColor ent,0,0,Rand(100,255)   ;
					PositionEntity ent,pos_x,pos_y,0			
					EntityType ent,TYPE_WALL
					EntityRadius ent,1,1
					NameEntity ent,Handle(this) 
					this\entity = ent
					this\ID = ID_WALL
				Case ID_SET_RANDOM
					ent = CreateSphere()
					EntityShininess ent,1
					PositionEntity ent,pos_x,pos_y,0			
					EntityType ent,TYPE_BALL
					EntityRadius ent,1,1
					NameEntity ent,Handle(this)
					this\entity = ent

					random_ball = Rand(ID_RED_BALL,ID_CYAN_BALL)
					Select random_ball
						Case ID_RED_BALL
							EntityColor ent,155,0,0
						Case ID_GREEN_BALL
							EntityColor ent,0,155,0
						Case ID_YELLOW_BALL
							EntityColor ent,155,155,0
						Case ID_CYAN_BALL
							EntityColor ent,0,155,155
					End Select
					this\ID = random_ball
				Default
					this\ID = datum
			End Select
			
			grid(row,col) = this
			pos_x = pos_x + 2.0
		Next

		pos_x = GRID_START_X
		pos_y = pos_y - 2.0
	Next

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
		
		Color 0,255,0
		Text 10,10," Triangles: " + TrisRendered()
		Color 255,255,0
		Text 10,25," Millisecs: " + frame_time
		Text 10,40,"   Slowest: " + slowest_frame
		Color 0,255,255
		Text 10,55,"       FPS: " + fps
		Text 10,70,"     Worst: " + slowest_fps
		Color 255,255,255
		Text 200,10,"Move mouse right or press right arrow key to move clockwise"
		Text 200,25,"Move mouse left or press left arrow key to move anti-clockwise"
		Text 200,40,"Click left mouse button or press SPACE to shoot"
	Else
		; First call initialization.
		fps_timeout = MilliSecs() + 1000 
	EndIf
	
End Function

Traverse the grid.

Hey big10p, thanks for the usefull piece of code! It sort of confirms some ideas that i had but was not sure about. I think a hexagon grid is more apealing tough. I will look into that, and see if i can get it done. Shouldnt be to hard.

Make a TList called MatchList. Loop through horizontally and vertically. Keep track of how many indexes match sequentially. If it's more than 2 then you have 3 or more of the same tiles in sequence in a row or column.

Hex is easy. It's just a 2d grid, you just display it differently.

2d representation:
00  10  20  30  40  50
01  11  21  31  41  51
02  12  22  32  42  52
03  13  23  33  43  53
04  14  24  34  44  54
05  15  25  35  45  55

hex representation:
00  10  20  30  40  50
  01  11  21  31  41  51
02  12  22  32  42  52
  03  13  23  33  43  53
04  14  24  34  44  54
  05  15  25  35  45  55

The only difference is where you check for matches. Horizontal = horizontal, vertical = \ diagonal, / diagonal doesn't exist.

Ok I'll go a bit more indepth. Let's say you have a standard 8x8 grid just like Bejeweled. And let's say that row 0 is set up like this:

01033302

Each number above represents a tile index. You can possibly have more than 3 matching so you need to let it accumulate as many in a row as possible. As long as the indexes keep matching then you keep adding 1 to indexMatches and add it to MatchList. If the index doesn't match or you get to the end of the row then you check for matches and reset indexMatches =0 and MatchList.Clear(). In this manner you dont access each tile individually and then check it's neighbors, you're checking the entire row from left to right without going backwards. It's much faster this way.

EDIT: Just thought of an even faster way. Don't check for a specific index...ie don't loop through and check just for index 0, then loop through again and check for index 1 etc etc...but let the index change to what the current tile is. That way you just look through once and find all matches > 2 without forcing it to look for a certain index. The code has been updated for the dynamic index checking.

Local cur_index:Int
Local old_index:Int
For a = 0 To 7
     cur_index = tile[a,0]
     If a = 0 old_index = cur_index
     If cur_index = old_index
          indexMatches :+ 1
          MatchList.AddLast( tile )
     Else
          If indexMatches > 2
               For tile = Eachin MatchList
                    tile.kill = True
               Next
          EndIf
          indexMatches = 0
          MatchList.Clear()
     EndIf
     If a = 7
          If indexMatches > 2
               For tile = Eachin MatchList
                    tile.kill = True
               Next
          EndIf
          indexMatches = 0
          MatchList.Clear()
     EndIf
     old_index = cur_index
Next

Here's another suggestion:
esc=quit, space=new random table

This is a little hardwired, but if you can live with a maximum of 32 different balls then you should be ok. If you know what you're doing you could raise it yourself ofcoz, but omfg 32+ balltypes would play like hell..

Don't forget to 'Reset' after each FindM3 call, basically you don't really need it as the match algo does "AND 31" all the time, but if you want to add routines then you usually want values 0..31 in that table.

Is it bloat? Dunno, it works, that I know.. :P For hex applications, you can choose what to check and what not to check, using that flag.

; m3 matcher, CS_TBL

Graphics 640,480

Dim m3array(24,16) ; make space for oodles o' balls




Ballify 7
FindM3 1+2+4+8

Repeat
	Cls
	show
	Flip
	
	If KeyHit(1) quit=1
	
	If KeyHit(57)
		ResetM3
		Ballify Rnd(3,15)
		FindM3 1+2+4+8
	EndIf
Until quit


End

Function Ballify(d)
	; ball'ify
	For y=0 To 16-1
		For x=0 To 24-1
			m3array(x,y)=Rnd(d)
		Next
	Next

End Function

Function ResetM3()
	For y=0 To 16-1
		For x=1 To 24-1
			If m3array(x,y)>=32
				m3array(x,y)=m3array(x,y) And 31
			EndIf
		Next
	Next
End Function

Function FindM3(flags=15)

	; horizontal checks
	If flags And 1
		For y=0 To 16-1
			For x=1 To 24-1-1
				ball=m3array(x,y) And 31
				If (m3array(x-1,y) And 31)=ball And (m3array(x+1,y) And 31)=ball ; match found!
					m3array(x-1,y)=m3array(x-1,y) Or 32
					m3array(x  ,y)=m3array(x  ,y) Or 32
					m3array(x+1,y)=m3array(x+1,y) Or 32
				EndIf
			Next
		Next
	EndIf

	; vertical checks
	If (flags Shr 1) And 1
		For y=1 To 16-1-1
			For x=0 To 24-1
				ball=m3array(x,y) And 31
				If (m3array(x,y-1) And 31)=ball And (m3array(x,y+1) And 31)=ball ; match found!
					m3array(x,y-1)=m3array(x,y-1) Or 32
					m3array(x,y  )=m3array(x,y  ) Or 32
					m3array(x,y+1)=m3array(x,y+1) Or 32
				EndIf
			Next
		Next
	EndIf
	

	; \ checks
	If (flags Shr 2) And 1
		For y=1 To 16-1-1
			For x=1 To 24-1-1
				ball=m3array(x,y) And 31
				If (m3array(x-1,y-1) And 31)=ball And (m3array(x+1,y+1) And 31)=ball ; match found!
					m3array(x-1,y-1)=m3array(x-1,y-1) Or 32
					m3array(x  ,y  )=m3array(x  ,y  ) Or 32
					m3array(x+1,y+1)=m3array(x+1,y+1) Or 32
				EndIf
			Next
		Next
	EndIf

	; / checks
	If (flags Shr 3) And 1
		For y=1 To 16-1-1
			For x=1 To 24-1-1
				ball=m3array(x,y) And 31
				If (m3array(x+1,y-1) And 31)=ball And (m3array(x-1,y+1) And 31)=ball ; match found!
					m3array(x+1,y-1)=m3array(x+1,y-1) Or 32
					m3array(x  ,y  )=m3array(x  ,y  ) Or 32
					m3array(x-1,y+1)=m3array(x-1,y+1) Or 32
				EndIf
			Next
		Next
	EndIf
		
End Function

Function show()
	For y=0 To 16-1
		s$=""
		For x=0 To 24-1
			ball=m3array(x,y)
			If ball>=32
				Color 255,0,0
				Rect x*24,y*12,16,12,True
			EndIf
			s$=s$+LSet(ball And 31,2)+" "	
		Next
		Color 255,255,255
		Text 0,y*12,s$
	Next
End Function

Thanks for all the help everyone!!

This is what i made so far (mainly interface)
[imghttp://www.goldstarpcgames.com/dev/ballbusterdx.jpg]

good luck with it. Look forward to seeing a demo.

Yeah basically you gotta loop through the grid but it can be well optimised using some of the techniques that have already been mentioned. Just be sure to really test it carefully as it's easy to let bugs creep into optimised functions. I used to have a random grid but then for testing I'd fill it with fixed values in certain areas so that I could test all possible scenarios.

Yeah as for approach you could have a second array which is a copy of the grid and set values for each matching one that you want to explode OR you could have a single grid of types and each type has a field that you set to "matched" or "exploding" or whatever.

A key thing in matching games is do you allow the player to make more matches when other shapes are still exploding or do you wait for the current animation to finish first (easier but crapper to play). So if you want to allow matches at the same time as animation your matching routine can check the matches array (or field on the types) and exclude those items when testing for matches.

As you get into it and have shapes moving (dropping down) and special items etc, your matching code will become more and more complex.

Right now, the match3 engine I have waits until the tiles on screen are full then checks the board for all matches, pops them, then waits until tiles are full, checks again, repeat etc etc.

One thing that might speed it up even more is using an array to store each tile object. That way instead of looping through all the tiles and looking for one particular tile. You could just do a:

Local tempTile:TTile
tempTile = TileArray[a,b]
If tempTile <> Null

And just update the TileArray with the correct tile pointers only when those particular tiles move or die off etc. Yeah! Off to code that...

I dunno how exactly you implemented that, but to me it sounds quite easy: wipe all matches at once, but before being wiped feed them to a particle system that simulates matching jewels to animate away.. Naturally, this particle system runs alongside with the normal user input/gameplay so that the user can indeed continue to match things.

Yeah that's the smart way to do it, which I didn't do at first also I did this thing on my game where when they explode, the ones above didn't immediately drop down so that you could see the explosion. Otherwise it gets covered up by falling gems.

Chroma: yeah that's exactly what I did.

-post deleted-

Bah, I'd try a Bejeweled-type clone before doing anything like Bibble-Bobble/Bust-A-Move.

-post deleted- (problem solved)

Hello guys,

I have uploaded a demo, it has now a working collision check except that the collisionsbox is too big.
Dont expect to much of this demo, not much changed.

Anyway, this zip contains 3 demos:
1) Ticker loop based game with Tweening & Captureworld
2) Ticker loop based game without tweening
3) Standaart loop know to be causing speed issues on differend machines.

Can you please leave a note which one works best?
That is why i am posting this demo really.

After testing i had to find out that a "ticker" based loop WITHOUT tweening works smoother and faster that one that does use tweening. How odd?

www.goldstarpcgames.com/dev2/ballbusterdx.zip