Match-3 code

BlitzMax Forums/BlitzMax Programming/Match-3 code

Tri|Ga|De

(Posted 2009) [#1]

I want to try an make a Match-3 game, I know is boring, but I have got a good idea for the game.

Now I ran into trouble with the match algoritme! Any one have some source to help me getting started.

I have a grid of 20x20 and want to check for match 3 og more. And I only need to match horizontally and vertically.

Anything that can get me started would be nice (sourcecode)

ziggy

(Posted 2009) [#2]

There's a basic match-3 game in the BlitzMax samples. Maybe you can take a look to that source code. It is the tiledrop sample.

Grey Alien

(Posted 2009) [#3]

Work out a pseudo code algorithm first and then test it out, something like:

- Start in top left corner.
- Store the value of the current item
- Horizontal testing: Move right to the next tile. If the value doesn't match, move onto the vertical testing below. If it does match, keep going right. When you either reach a non-matching item or the right edge, you can see if the number of matches is 3 or greater. I used to store the matches in a separate grid array so I could explode them all at once later.
- Vertical testing: Move down to the next tile. Test for a match or hitting the bottom of the grid etc. Pretty much the same as horizontal testing.

That's it, it's pretty easy.

What is harder is testing for *possible* matches that a player could make. That algorithm needs a lot more work. Then when you start to introduce locked items, gaps, falling shapes, bonuses etc it gets even more complex.

GfK	(Posted 2009) [#4]

What is harder is testing for *possible* matches that a player could make. That algorithm needs a lot more work. Then when you start to introduce locked items, gaps, falling shapes, bonuses etc it gets even more complex.

I thought that the worst bit was getting it to check for matches and let the player take a turn and all the rest of it, when tiles are already moving/falling.

There was a thread recently where somebody was complaining along the lines of "are Match Three games all Blitzmax is capable of" - like match three games are some sort of irrelevant easy-to-write bile. Its straightforward to write a working prototype but its difficult to get it to play well.

I started mine two years ago (don't ask), and up until about a month ago its had a bug that I just couldn't get to the bottom of. I thought I'd fixed it at least half a dozen times, but then it appeared again. One of those "once in a blue moon" bugs. I ended up spending a day rewriting several of the major code functions and using a totally different implementation of keeping track of everything. Its rock solid now.

</tangent>

Anyway, following on from what Jake said, my code keeps track of what's moved/been moving and only check for matches where those tiles can affect things. There's little point in checking for matches on whole sections of tiles that haven't gone anywhere.

Jesse

(Posted 2009) [#5]

I have a source code for the one Qube(David Templer) did in my download's link. If you want to take a look at it. I think it's comercial quality.

http://www.filefront.com/12217541/holiday-swapz-BMX-sourcem3.zip

_Skully

(Posted 2009) [#6]

Acually I hate to toot my own horn, but this would be extremely easy in TileMax..

Basically, when a piece moved all you would have to do is test to see if adjacent tiles contain like item id's and if the count is sufficient Start the fireworks!

In TileMax..

All tiles are referenced relatively... connected in 9 directions xy (-1 to 1)+1
Something like...

Function Match(ID:Int=ID_GREENGEM, MT:TMTile)
   Local Count=0
   For X:int=0 to 2
     For Y:int=0 to 2
        if x=1 and y=1
            ' This equates to a tiles warp point
        Else
            If MT.Nav(x,y) and MT.Nav(x,y).Actors
               if MT.Nav(x,y).Actors.First().ID=ID
                   Count:+1
               Endif
            EndIF
        Endif
     Next
     If Count>2 LetTheFireworksGo()
   Next
End Function

GaryV

(Posted 2009) [#7]

Besides the match 3 source included with BM, there have been two complete match 3 games that have had the source released and one half-assed (sorry Chroma) attempt that had the source released.

Grey Alien

(Posted 2009) [#8]

There was a thread recently where somebody was complaining along the lines of "are Match Three games all Blitzmax is capable of" - like match three games are some sort of irrelevant easy-to-write bile. Its straightforward to write a working prototype but its difficult to get it to play well.

100% agree here. I saw that comment too. As well as the mechanics, a commercial quality match-3 will test blitzmax out in many other ways.

Amon	(Posted 2009) [#9]

TomToads full match 3 engine with source (blitzmax).

http://www.blitzbasic.com/Community/posts.php?topic=70555#792829

Tri|Ga|De

(Posted 2009) [#10]

Thanks alot guys!

GaryV

(Posted 2009) [#11]

Qube also released the source to his Christmas match-3 game

Jesse

(Posted 2009) [#12]

Qube also released the source to his Christmas match-3 game

really? ;)

GaryV

(Posted 2009) [#13]

really? ;)

Yes and it was commercial grade, ready for release. Qube had posted it on his forums.

Jesse

(Posted 2009) [#14]

LOL
I was being sarcastic look at post #5

Qube	(Posted 2009) [#15]

Qube also released the source to his Christmas match-3 game

I did? oh no, quick grab it back! :p

Before anyone asks, no, you're not getting your mitts on the vastly improved match-3 engine which accompanies the iPhone version of holiday swapz (available in all good stockists) :D

Jesse

(Posted 2009) [#16]

@Qube
if you don't want me to have It available I can take it of my filefront download. I just thought it might be helpful for other trying to understand the logic behind it. No harm intended.

Qube	(Posted 2009) [#17]

if you don't want me to have It available I can take it of my filefront download. I just thought it might be helpful for other trying to understand the logic behind it. No harm intended.

I was joking, hence the :p - The old PC version of Holiday Swapz I released as public domain so it's good there's a backup :)

GaryV

(Posted 2009) [#18]

I was being sarcastic look at post #5

Gotcha, I mised that one ;)

Tri|Ga|De

(Posted 2009) [#19]

I can't get it right, I mean I can find 3(or more) in a row/col, but I want to find "1" like in ex 1.

Ex 1.
000000000
000000000
000011100
000000110
000000000

Look at ex 1, I want to find all "1" in the grid, that touched. I try to figure it out but I can't get IT!!

Any help would be very nice.

GfK	(Posted 2009) [#20]

What you're asking for is the equivalent of a 'flood fill' function, which basically boils down to using recursion.

Pseudocode:

Find the first tile in the grid (i.e 5,2)
Set its 'marked' flag to True
Call Search() function

'when you get to here, all '1' tiles will be marked

Iterate through all tiles
Remove any with 'marked = true'


Function Search()
  Check all four adjoining tiles
  If they're the same value (i.e. 1) AND tile.marked = False
    Set its 'marked' flag to True.
    Call Search() function.
  EndIf
EndFunction

Tri|Ga|De

(Posted 2009) [#21]

Thanks GFK it works now.

I finally got it to work, thanks everyone!
Heres my code if anyones interested, it proberly could be optimized but for now it should work. It checks for matching fields that touch.

Remark to code:
PlayField is playfield
CheckArray is filled with PlayField values for testing
Marked is to mark fields to remove
Nabors just checks for nabors.



	Graphics 1024, 768

	Global Rows:Int = 20
	Global Cols:Int = 20	
	Global PlayField:Int[Rows, Cols]
	Global CheckArray:Int[Rows, Cols]
	Global Marked:Int[Rows, Cols]
	Global Nabors:Int[Rows, Cols]
	Global CountingYs:Int = 0
	Global ones:Int = 0

	'** Place random values in playfield
	PlaceRandomFields(50, 6, 7, 13)

	'** Fyld arrays
	FillArraysWithZero()
	'InsertDataIntoPlayField()
	CopyFromPlayFieldIntoCheckArray()

	While Not KeyHit(KEY_ESCAPE)
		Cls
		DisplayCheckArray(100, 40)
		DisplayNabors(500, 40)
		DisplayMarked(100, 420)
		DisplayPlayField(500, 420)
				
		If KeyHit(KEY_SPACE) And ones=0
			For Local ys:Int=1 To 6
				RemoveNonCheckTiles(ys)
				FindAndRemoveStandAloneTiles(ys)
				FindFirstTitle(ys)
				FindAndRemoveTwos(ys)
				RemoveFromPlayField()

				FillArraysWithZero()
				CopyFromPlayFieldIntoCheckArray()
			Next

 			ones=1
		End If

		If KeyHit(KEY_TAB)
			FillArraysWithZero()
			PlaceRandomFields(50, 6, 7, 13)
			'InsertDataIntoPlayField()
			CopyFromPlayFieldIntoCheckArray()
			ones = 0
		End If

		'** Flip
		Flip -2

	Wend
	
'*********************************************
'* Function: Remove fields not to be checked *
'*********************************************
Function RemoveNonCheckTiles(checkTile:Int)
	For Local x:Int=0 To Rows-1
		For Local y:Int= 0 To Cols-1
			If CheckArray[x, y] <> checkTile Then CheckArray[x,y] = 0
		Next
	Next	
	
End Function	
'****************************************************
'* Function: Fill CheckArray with PlayField         *
'****************************************************
Function CopyFromPlayFieldIntoCheckArray()
	'** Copy PlauField into CheckArray
	For Local x2:Int=0 To Rows-1
		For Local y2:Int= 0 To Cols-1
			CheckArray[x2,y2] = PlayField[x2, y2]
		Next
	Next	
End Function

'********************************************
'* Function: Fill arrays with zeros         *
'********************************************
Function FillArraysWithZero()
	For Local x:Int=0 To Rows-1
		For Local y:Int= 0 To Cols-1
			CheckArray[x,y] = 0
			Marked[x,y] = 0
			Nabors[x,y] = 0
		Next
	Next	
End Function

'********************************************
'* Function_ Find first nabor field         *
'********************************************
Function FindFirstTitle(tileType:Int)
	Local tileValue:Int
	For Local x:Int=0 To Rows-1
		For Local y:Int=0 To Cols-1
			tileValue = CheckArray[x,y]
			If tileValue = tileType
				Marked[x,y] = 1
				SearchTiles(x,y, tileType)
			End If	
		Next
	Next	
End Function

'************************************************************************
'* Function: Loop through all fields to find who has nabors             *
'************************************************************************
Function SearchTiles(x:Int, y:Int, tileType:Int)
	If CountingYs = 0 Then
		y = y + 1
		If y > Cols-1 Then
			x = x + 1
			If x > Rows-1 Then x = 0
			y = 0
		End If
	End If
	If CheckArray[x,y] = tileType And checknabors(x, y) And Marked[x,y] = 0
		Marked[x,y] = 1
		SearchTiles(x,y, tileType)		
	End If
End Function

'****************************************************
'* Function: Remove all '1' in Nabors and Marked    *
'****************************************************
Function FindAndRemoveTwos(tileType:Int)
	Local naborTiles:Int
	
	For Local x:Int=0 To Rows-1
		For Local y:Int=0 To Cols-1
			'** We found a match
			If CheckArray[x, y] = tileType
				'** Its got match from side fields
				naborTiles = checknaborsTwo(x,y)
				If naborTiles <> 0
					If naborTiles = 1 Or naborTiles = 2 Or naborTiles= 4 Or naborTiles = 8 Then Nabors[x,y] = 1
					If naborTiles = 3 Or naborTiles = 6 Or naborTiles = 12 Or naborTiles = 9 Or naborTiles = 10 Or naborTiles = 5 Then Nabors[x,y] = 2
					If naborTiles =7 Or naborTiles = 14 Or naborTiles= 13 Or naborTiles = 11 Then Nabors[x,y] = 3
					If naborTiles = 15 Then Nabors[x,y] = 4
				End If
			End If
		Next
	Next
	
	'** Loop through Nabors, find all '2' and make next '1' field to '2'
	Local numberTwoTiles:Int
	Local naborTilesOfOnes:Int
	
	For Local x2:Int=0 To Rows-1
		For Local y2:Int=0 To Cols-1
			numberTwoTiles = Nabors[x2, y2]		
			'** We found a double
			If numberTwoTiles = 2 Or numberTwoTiles = 3 Or numberTwoTiles = 4
				If Nabors[x2+1,y2] = 1 Then Nabors[x2+1,y2]=2
				If Nabors[x2-1,y2] = 1 Then Nabors[x2-1,y2]=2
				If Nabors[x2,y2+1] = 1 Then Nabors[x2,y2+1]=2
				If Nabors[x2,y2-1] = 1 Then Nabors[x2,y2-1]=2
			End If
		Next
	Next
	
	'** Remove all double '1' in Marked
	Local numberOneTiles:Int

	For Local x3:Int=0 To Rows-1
		For Local y3:Int=0 To Cols-1
			numberOneTiles = Nabors[x3, y3]
			If numberOneTiles = 1
				Marked[x3,y3] = 0
			End If	
		Next
	Next				 	
End Function

'*************************************************
'* Function: Remove all '1' fields in CheckArray *
'*************************************************
Function FindAndRemoveStandAloneTiles(tileType:Int)
	Local checknabor:Int
	Local tilevalue:Int
	Local in3x:Int = False
	Local in3y:Int = False

	'** Gennemg� array og fjern single tal	
	For Local x:Int=0 To Rows-1
		For Local y:Int=0 To Cols-1
			tilevalue = CheckArray[x,y]
			If tilevalue <> 0 '** Onlu check if current field is different from zero
				checknabor = checknabors(x,y)
				If checknabor = False
					CheckArray[x,y] = 0
				End If
			End If
		Next
	Next
	
End Function

'********************************************
'* Function: Check next fields              *
'********************************************
Function checknabors:Int(xpos:Int, ypos:Int)
	Local zeros:Int = 0
	Local checkvalue:Int
	
	'** Checks if next x is zero
	If xpos <=Rows-1 '** Only if its not the last
		checkvalue = CheckArray[xpos+1, ypos]
		If  checkvalue <> 0
			zeros = zeros + 1
		End If
	End If
	
	'** Check if previous x is zero
	If xpos >= 1 '** Only if its not the first one
		checkvalue = CheckArray[xpos-1, ypos]
		If checkvalue <> 0
			zeros = zeros + 1
		End If
	End If
		
	'** Check if next y is zero
	If ypos <= Cols-1 '** Only if its not the last
		checkvalue = CheckArray[xpos, ypos+1]
		If checkvalue <> 0
			zeros = zeros + 1
		End If
	End If

	'** Check if previous y is zero
	If ypos >= 1 '** Only if its not the first one
		checkvalue = CheckArray[xpos, ypos-1]
		If checkvalue <> 0
			zeros = zeros + 1
		End If
	End If
	If zeros = 0
		Return False
	Else
		Return True	
	End If
End Function

'*****************************************************
'* Function: Check all next to '2' field in Nabors   *
'*****************************************************
Function checknaborsTwo:Int(xpos:Int, ypos:Int)
	Local zeros:Int = 0
	Local checkvalue:Int
	
	'** Checks if next x is zero
	If xpos <=Rows-1 '** Only if its not the last
		checkvalue = CheckArray[xpos+1, ypos]
		If  checkvalue <> 0
			zeros = zeros + 2
		End If
	End If
	
	'** Check if previous x is zero
	If xpos >= 1 '** Only if its not the first one
		checkvalue = CheckArray[xpos-1, ypos]
		If checkvalue <> 0
			zeros = zeros + 8
		End If
	End If
		
	'** Check if next y is zero
	If ypos <= Cols-1 '** Only if its not the last
		checkvalue = CheckArray[xpos, ypos+1]
		If checkvalue <> 0
			zeros = zeros + 4
		End If
	End If

	'** Check if previous y is zero
	If ypos >= 1 '** Only if its not the first one
		checkvalue = CheckArray[xpos, ypos-1]
		If checkvalue <> 0
			zeros = zeros + 1
		End If
	End If
	If zeros = 0
		Return 0
	Else
		Return zeros	
	End If
End Function

'**********************************
'* Function: Place random fields  *
'**********************************
Function PlaceRandomFields(numberOfFields:Int, maxNumber:Int, startGrid:Int, endGrid:Int)
	Local randomX:Int, randomY:Int, fieldValue:Int
	
	For Local x:Int = 1 To numberOfFields
		randomX = Rand(startGrid,endGrid)
		randomY = Rand(startGrid,endGrid)
		fieldValue = Rand(1,maxNumber)
		PlayField[randomX, randomY] = fieldValue		
		'CheckArray[randomX, randomY] = fieldValue		
	Next
End Function

'**********************************************
'* Function: Remove from PlayField via Marked *
'**********************************************
Function RemoveFromPlayField()
	For Local x:Int = 0 To Rows-1
		For Local y:Int = 0 To Cols-1
			If Marked[x, y] = 1 Then PlayField[x, y] = 0
		Next
	Next	
End Function

'****************************************
'* Function: Insert data into PlayField *
'****************************************
Function InsertDataIntoPlayField()
	PlayField[6,1] = 1
	PlayField[7,1] = 1
	PlayField[8,1] = 1

	PlayField[10,1] = 1
	
	PlayField[1,4] = 2
	PlayField[1,5] = 2
	PlayField[1,6] = 2

	PlayField[5,3] = 3
	PlayField[6,3] = 3
	PlayField[7,3] = 3
	PlayField[7,4] = 3
	PlayField[8,4] = 3
	
	PlayField[5,13] = 4
	PlayField[6,13] = 4
	PlayField[7,13] = 4
	PlayField[7,14] = 4
	PlayField[8,14] = 4

	PlayField[5,7] = 5
	PlayField[6,7] = 5
	PlayField[7,7] = 5
	PlayField[7,8] = 5
	PlayField[8,8] = 5

	PlayField[5,10] = 6
	PlayField[6,10] = 6
	PlayField[7,10] = 6
	PlayField[7,11] = 6
	PlayField[8,11] = 6

	PlayField[12,12] = 6
	PlayField[12,13] = 6
	PlayField[12,14] = 6
End Function

'********************************************
'* Function: Show CheckArray                *
'********************************************
Function DisplayCheckArray(startXPos:Int, startYPos:Int)
	DrawText "CheckArray", startXpos, startYPos-16
	For Local x:Int=0 To Rows-1
		For Local y:Int=0 To Cols-1
			If CheckArray[x,y] <> 0
				DrawText CheckArray[x,y], startXPos + x * 16, startYPos + y * 16
			End If
		Next
	Next	
End Function

'********************************************
'* Function: Show PlayField                 *
'********************************************
Function DisplayPlayField(startXPos:Int, startYPos:Int)
	DrawText "PlayField", startXpos, startYPos-16
	For Local x:Int=0 To Rows-1
		For Local y:Int=0 To Cols-1
			If PlayField[x,y] <> 0
				DrawText PlayField[x,y], startXPos + x * 16, startYPos + y * 16
			End If
		Next
	Next	
End Function

'********************************************
'* Function: Show Marked fields             *
'********************************************
Function DisplayMarked(startXPos:Int, startYPos:Int)
	DrawText "Marked", startXpos, startYPos-16
	For Local x:Int=0 To Rows-1
		For Local y:Int=0 To Cols-1
			If Marked[x,y] <> 0
				DrawText Marked[x,y], startXPos + x * 16, startYPos + y * 16
			End If
		Next
	Next	
End Function

'********************************************
'* Function: Show Nabors fields             *
'********************************************
Function DisplayNabors(startXPos:Int, startYPos:Int)
	DrawText "Nabors", startXpos, startYPos-16
	For Local x:Int=0 To Rows-1
		For Local y:Int=0 To Cols-1
			If Nabors[x,y] <> 0
				DrawText Nabors[x,y], startXPos + x * 16, startYPos + y * 16
			End If
		Next
	Next	
End Function

Tri|Ga|De

(Posted 2009) [#22]

I put up my final code!!

Chroma

(Posted 2010) [#23]

@GaryV: you must not have followed that old thread fully. It was working great and I got a lot of compliments on it. But I got bored because Match-3 is no challenge. And it's not commercially viable these days anyways imo.

Most people here are trying to make a game they can turn a quick profit on. I'm more into making something unique. I look at coding as a means of expression. Not turning a quick buck.

GaryV

(Posted 2010) [#24]

@GaryV: you must not have followed that old thread fully.

I was it showed the initial promise of your game framework and quickly suffered the same fate as your game framework ;)

Most people here are trying to make a game they can turn a quick profit on. I'm more into making something unique. I look at coding as a means of expression. Not turning a quick buck.

I agree 100%

Chroma

(Posted 2010) [#25]

Everyone please welcome GaryV as the newest member of the Chroma fan club! :)

And what sir have YOU finished/released? hehe

TriGaDa: Are you scanning through the whole lists and storing matches and popping all present matches at the same time? (Didn't look)

Tri|Ga|De

(Posted 2010) [#26]

I take the play array and make an new array with the tiles I want to check.
Then I deletes all single tiles.
Then I make an new array where i put in how many nabors each tile have.
Compare two arrays and delete all tiles with only 1 nabor.

BUT my code has an error, it can not check border tiles.
So en a 20x20 grid it can only check from 2 to 19.

GaryV

(Posted 2010) [#27]

Everyone please welcome GaryV as the newest member of the Chroma fan club! :)

I actually am, get the chip off your shoulder. I was really looking forward to your game framework. IMHO, it was the only one that showed promise after Gray's was pulled off the market.

Chroma

(Posted 2010) [#28]

Ah ok...sorry then. I guess I'm a defensive product of the mostly negative attitudes around here.

I haven't been keeping up with the Blitz Community Framework. How is that one shaping up?

Pharmhaus

(Posted 2010) [#29]

Its running fine thank you for asking. :)
Why not helping the Community Framework ? it could be the challenge You are looking for...