Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Chat / design logic for match 3 game

Author
Message
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 13th Mar 2018 16:36
Match 3 as in bejeweled, candy crush, etc... (cause a week ago I didn't know they were called match3)

I wrote a version of a workable example of this style of game in DBP years ago and now I'm making one for AGK. My current method requires looping through all gems 3 times per cycle, which I feel could be improved. Not that running through an 8x8 nest loop 3 times would really affect performance, but I feel it's inefficient.

Initially, I had a 1D array containing gems. To find a gem at a particular grid location, I had to loop through all the gems to find the one at that location. Terrible! But AppGameKit doesn't let you use a UDT in a multi-dimensional array. So, second idea, store gems in an array as before, then build a 2D array for the map which references an index in the gem array. It's not my preferred method but it's manageable.

Here's what I mean:


The tricky part comes from the fact that gems can move into different map locations, so the data in the map array must be constantly juggled around. That's fine, I can do that. Now here's why everything takes 3 separate loops.

First, apply gravity to the gems so they drop. A gem cannot drop beyond the one below it. Therefore, if a gem hits another one below it, it loses all acceleration. I also start at the top row and work my way down. The reason for this to create a cascade effect in that column when a gem is removed. If I started at the bottom and worked my way up, the entire column would shift down together, never spacing apart. If I start at the top, each gem in that column will drop in the next cycle following the last one, creating the cascading effect rather than dropping like they're stuck together. This is merely personal preference.

Once the gems have settled (stopped moving/updating), I need to update their positions in the map array. I can't do it in the first loop I just described because I need to loop through the gems starting at the bottom row and working my way up, otherwise I'd overwrite a gem. Because the gems drop down, I know the bottom most spot is where a gem was deleted, thus that spot is free. So if a gem was previously at (3,4) and I deleted (3,5) then (3,5) is free to overwrite first. Once (3,4) is copied, that space then becomes free to overwrite and so on.

So because my gravity needs to work from reading top to bototm but updating gem positions needs to work from bottom to top, that's 2 separate loops there that I can't integrate. The 3rd loop comes from when I begin to check for gem matches. I can't check matches unless everything (gravity and positions) have finalized updating.

It's clear in my head, hopefully my explanation was clear too. So my actual question is, does anyone see a way to integrate this all together to reduce the number of iterations over the map data? Or perhaps a better way to go about it altogether? Like I said, my method works, it just seems tedious and a bit unnecessary I think.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Scraggle
VIP Member
15
Years of Service
User Offline
Joined: 10th Jul 2003
Location: Yorkshire
Posted: 13th Mar 2018 16:47 Edited at: 13th Mar 2018 16:52
That was a lot of information to try to parse. So instead of doing that, I'm going to quote Murphy's law to you:
"If it ain't broke, don't fix it!"

From what you are saying, you have a system that works. So personally, I would stick with it and be happy. Move on, continue with the rest of the code and then at the end when everything was complete I would consider optimising it but only if the end result required it.

I know that's not the answer you want but I'm just offering my opinion for a stress-free life
Bengismo
User Offline
Joined: 20th Nov 2017
Location: Yorkshire, England
Posted: 13th Mar 2018 17:09
A stress-free life ?? Whats that??
Scraggle
VIP Member
15
Years of Service
User Offline
Joined: 10th Jul 2003
Location: Yorkshire
Posted: 13th Mar 2018 17:17
Neat, structured, well maintained and reusable code is the secret to a stress free life.

Everything else is meaningless nonsense
AFA
6
Years of Service
User Offline
Joined: 29th May 2012
Location: Germany
Posted: 14th Mar 2018 01:56
Hi Phalanx
I can follow nearly every thought you've described because I've worked on something similar before.

My first attempts were much more complicated giving every gem the information about color and things like that - and where it is, column and row. Reason for this was to get the input, ask every sprite if it has been touched and then know immediately everything because the sprite knows. Not the sprite of course but the sprite IDs stored in a type variable like .ID and .color and .row and .colomn etc. This attempt had a lot of disadvantages e.g. to move some sprites together I got mad updating these values for their position:
Because beyond that it was necesarry to have an array as a map and coordinate map containing the IDs and the IDs own information was effortful so all this was nonsense.

My target was always to have only ONE array as you wish to have.

Now I have an array containing types, so every row/column nows everything whats in at the position: color, size and these things or 'empty' or may be 'blocked' etc.

Yes I have to cycle but this is as you agree no problem concerning performance. To keep everything easly well-structured I have some (not many) functions to to things like moving sprites and moving values in the map-array. This way to manage it is the right way to me and my little brain.

So in your example moving some sprites downwards in a gap.
1 search for gaps beginning at the top as you do
2 found a gap
3 start function
look if something above, collect and store IDs
4 start function
move stored sprites
5 start function
move values in map-array

1 go on searching...
and so on

Yes internally in these functions we have to cylcle but it's 'hidden' and so it is tidy.
Van B
Moderator
16
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 15th Mar 2018 12:27
Good old match 3.

I would keep it simple as possible - use a 2D array for the board, and give each cell its own sprite, so cell 10,10 always uses the same sprite. Let the sprite drop down by a maximum of 1 cell, so if theres a gap below, the sprite will drop down until it fills the cell, then that cell absorbs the value and keeps dropping if theres a gap. So, rather than keeping track of several sprites dropping to several heights - you treat each drop as a limited movement of 1 cell... shifting the sprite that is moving each time, so the sprites can snap right back to where they are supposed to be.

So, if you have the pieces drop down if theres a gap, but only for 1 cell, if theres still a gap then you move the cells sprite each time.

When sprites have stopped dropping, scan through and check each cell, if there are matching cells at the left and right, mark those, and the same for up and down. You only ever need to check for 3 matches then mark them, after the scan you would destroy them and let the drop cycle start again. Consider, if you have a row of 4 matching pieces... that's just 2 matches of 3 pieces. It keeps the piece checking real simple, just check the neighbouring cells for matches - matches of more than 3 in a row are calculated as well.

Once you have all the matches marked, total the score bonus and destroy them.
The code is dark and full of errors
Zep
16
Years of Service
User Offline
Joined: 31st Aug 2002
Location: From PA, USA. Currently reside in Hanoi, Vietnam
Posted: 15th Mar 2018 13:03 Edited at: 15th Mar 2018 13:05
Match 3 is the perfect thing to use Function Recursion on (ie: a function calling itself from within it's own function...for finding matches)

I uploaded a Match 3 game here about 13-14 years ago. I can find my old post here on this forum, but the attachment is gone. (DBPRO)

The game was called Bubble Blast.
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 17th Mar 2018 00:05
Van, are you saying to only drop one gem at a time?

Zep, I think I know where you're going with the recursion. I think could produce slightly smaller code and maybe look a little cleaner, but the nested function calls might be more impact than using a simple FOR loop to check in each direction as I'm doing now.

In reality, any attempt to improve the existing code would likely have no real impact, as a map no greater than 10x10 is small.


Quote: "But AppGameKit doesn't let you use a UDT in a multi-dimensional array. "


So I have no idea why I said that. Maybe I made a typo trying to initialize it and figured it wasn't allowed. I actually think I read it from somewhere on the forum. Either way, that's obviously wrong. I'm redoing everything now.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Van B
Moderator
16
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 17th Mar 2018 08:29 Edited at: 17th Mar 2018 08:31
Nah, I mean drop just 1 slot at a time. I would store the Y offset for each sprite, if the sprite is dropping then increase that until it gets to the next slot below, then take over that empty slot with the sprite.

Anytime I've done this, I just use a 2D array to store the board data, and step through it from bottom to top, increasing the drop offset, shifting the sprite if it lands in a new slot, and keeping a record of how many sprites are dropping. Once no sprites are dropping, I step through again and check the left and right, and top and bottom neighboring slots for a match, flag those and remove them, start dropping again, and keep doing that until nothing is dropping and theres no more matches.

Also, I think it's easiest to just have a top row of slots that isn't shown, instead it feeds the empty slots from the top - just have to check to make sure there's always a piece in all those slots and it'll constantly feed the board.
The code is dark and full of errors
Zep
16
Years of Service
User Offline
Joined: 31st Aug 2002
Location: From PA, USA. Currently reside in Hanoi, Vietnam
Posted: 17th Mar 2018 11:06
Quote: "Zep, I think I know where you're going with the recursion. I think could produce slightly smaller code and maybe look a little cleaner, but the nested function calls might be more impact than using a simple FOR loop to check in each direction as I'm doing now.
"



Give it a try, I found (in DBPRO) the recursion was quicker than for loops. Might be the same in AGK.
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 18th Mar 2018 01:42
I think I have everything worked out now. Sometimes I just need to bounce ideas off the internet, even if I don't listen to the feedback

Zep, I went ahead with your idea using recursion. I don't know if it's better or worst than using loops, but I think the code is simpler.

Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Zep
16
Years of Service
User Offline
Joined: 31st Aug 2002
Location: From PA, USA. Currently reside in Hanoi, Vietnam
Posted: 18th Mar 2018 03:01
Quote: "Zep, I went ahead with your idea using recursion. I don't know if it's better or worst than using loops, but I think the code is simpler.
"


Nice. Did you try any speed test between for loops vs. recursion?

I didn't notice any loss of performance in DBPRO, but I have yet to try AGK.
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 18th Mar 2018 14:53
Nah, I didn't bother. I call the function 4 times, once for each direction. Realistically, it shouldn't call itself more than 3 times after the initial call, so that's a pretty low stack.

I whipped up some candy crush graphics last night, even though I don't plan on using them in the final product.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Attachments

Login to view attachments
Zep
16
Years of Service
User Offline
Joined: 31st Aug 2002
Location: From PA, USA. Currently reside in Hanoi, Vietnam
Posted: 19th Mar 2018 00:07
Looking good.
PSY
Valued Member
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 20th Mar 2018 09:12 Edited at: 20th Mar 2018 09:16
When it comes down to deep recursions, AppGameKit is very slow compared to compiled languages, simply because it's byte code run under an interpreter.
I coded a recursion for the 8 Queens Problem in both Blitz3D and AGK2.
It takes B3D 455 millisecs to solve the problem 1000 times. In AGK2, it takes about 18 seconds...

Simple recursions like the ones used for a match 3 game are not a problem at all in AppGameKit, but you don't need them to move the gems.
They make sense when you do explosions, though ( like blowing up 3 or more adjacent gems).
Or when you count gems of the same type, like you did with your recursion.

For the map, you could use a 2D array and another array where you set a flag whether a gem is moving down or not.
You simple run through the map from bottom to top.


That eliminates the problem of multiple gems in the same column falling simultaneously.
You wouldn't even need to store the gems' position data.
I used that method for a Boulder Dash Clone, where the movement is far more complex

There are of course a lot of different approaches to that problem, using types for example...

Nice topic. A match 3 game has been on my to-do list for a some time now


PSY


PSY LABS Games
Coders don't die, they just gosub without return
Zep
16
Years of Service
User Offline
Joined: 31st Aug 2002
Location: From PA, USA. Currently reside in Hanoi, Vietnam
Posted: 20th Mar 2018 09:22 Edited at: 20th Mar 2018 09:29
Quote: "Simple recursions like the ones used for a match 3 game are not a problem at all in AppGameKit, but you don't need them to move the gems.
"


Of course. But you only use the recursion to find out the matches (if you even need to go that route, no matches, no code). Then you deal with it in whatever way.

Maybe I'll ask TGC if my old attachment is still in their archives somewhere. It's no longer attached to my old post.

Although, I don't think I attached the code...just the EXE.
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 20th Mar 2018 12:11
The basic mechanics are done, it's really just a matter of making everything look cool now.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Zep
16
Years of Service
User Offline
Joined: 31st Aug 2002
Location: From PA, USA. Currently reside in Hanoi, Vietnam
Posted: 20th Mar 2018 13:53
My game had a few minor bugs which weren't reported til like 4 or 5 months after it was released, but by then I had already moved on and didn't fix them.

I asked TGC if they could find the old attachment.

Mine wasn't exactly "match 3", it was more like, click on the things that already match and hope you made the best choice.
Imagination Engineer
4
Years of Service
User Offline
Joined: 30th May 2014
Playing: Street Fighter V
Posted: 20th Mar 2018 18:51
Some good info in here.
Imaginations' greatest gift is the knowledge you supply it.
PSY
Valued Member
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 20th Mar 2018 19:45
Quote: "The basic mechanics are done, it's really just a matter of making everything look cool now."

You got a screenshot to show off maybe?


PSY LABS Games
Coders don't die, they just gosub without return
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 20th Mar 2018 19:52
Not at the moment, but I used the same kitten graphics (all my own) as my DB version for the moment. Also a video of the mechanics in action from the old version. But the AppGameKit version is neater code.

https://forum.thegamecreators.com/thread/203868
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
PSY
Valued Member
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 20th Mar 2018 20:07
Okay.

It's done when it's done


PSY LABS Games
Coders don't die, they just gosub without return

Login to post a reply

Server time is: 2018-10-17 11:12:28
Your offset time is: 2018-10-17 11:12:28