Search algorithm

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Sep 10, 2004 at 08:46

Hi guys, for one of my simple projects I’m doing to ease me into DirectX programming, I’m doing a remake of the old Amiga game Outfall - I don’t know if any of you ever encountered that.

I believe it was based on Columns, but basically the idea is, sets of 3 coloured balls drop from the top of the screen, and you have to make chains of 4 or more with them. You can rotate them in any direction 90 degrees at a time, much like you could with Tetris blocks. A successful chain drops rocks into the other players area, and eventually they can’t play any more - again, like Tetris.

Basically what I’m looking for, and it’s got me slightly stumped as to how to implement it, is a search algorithm I can use to detect the chains of blocks.

What I’ve come up with so far is this:

1.Step through array of blocks, one row at a time. Probably from the bottom-up.
1.a.Scan for a neighbouring block of the same colour. If no match is found, make a note of that and continue to the next neighbour. If a match IS found, make a note of it, and move to that block to begin the search again. Obviously you’d also make a note of which direction you came from, to avoid an infinite loop where you’re moving back and forth from one block to another.
1.b.If a neighbour is found, add the two blocks positions to an array (or list) which is keeping track of chains.
2.When every block has been scanned through, check the list of chains and remove any chains of less than 4 blocks. This will leave us with a list of the blocks that need to be deleted.
3.Delete the blocks relating to those chains, add the points to the players score, and increase the number of rocks to be dropped on the other player.
4.The next step is to check for combos. At this point, all the blocks in chains have been deleted, so there’s gaps in the play area. We need to close those gaps by dropping the blocks above them down, so we do that. Then we scan through the array again and check for chains. If none are found, we’re done. If we find any, we need to destroy the blocks again, apply gravity again, and keep going until we don’t find any more.
5.Then we pass control back to the player - basically all this should have happened in a matter of milliseconds anyway, aside from the animating effects.

I was hoping you guys could help me come up with a better algorithm than that. I’d be the first to admit that it’s not my strong point, and I’m sure there’s a more efficient way to do it. Any suggestions?

11 Replies

Please log in or register to post a reply.

Baaecfb3a09127d5bc5045f89025e49e
0
UnknownStranger 101 Sep 10, 2004 at 09:17

Well, since I don’t think you’ve got a playfield with hundreds of slots adn hundreds of rows, I doubt you’ll encounter much performance problems(unless your targeting very very low end systems)…

Still, if you do, the first optimization step I’d suggest, is starting your search from the top, and stoping the search, when you arrive at the highest unaffected row.
That could prevent quite some checks.

If your still experiencing performance troubles, especially with combos, you might want to take a closer look at your containers, and their performance characteristics…

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Sep 10, 2004 at 09:24

That might help. Thanks.

The play area is only about 10-12 columns wide, maybe around 20 to 24 down - I haven’t made a final decision on that yet. So there’s not a huge amount to search through. I was just more concerned about how my algorithm did the search itself, as when I last tackled this project (I keep going back to old ideas :P) I managed to crash Blitz3D every single time :( Think it was a stack overflow in that instance.

Baaecfb3a09127d5bc5045f89025e49e
0
UnknownStranger 101 Sep 10, 2004 at 09:32

Well, it’s very very very important to avoid an infinite loop by storing a “chain-direction”, but you already have that in your design, so you should be on the safe side here… ;)

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Sep 10, 2004 at 09:48

Let’s hope I can make it work then…. I’m sitting here doodling on a pad of paper trying to work it out more precisely. I don’t have access to Visual Studio or anything while I’m here at work, so it forces me to plan rather than to just sit down and code :P Probably a good thing……

Baaecfb3a09127d5bc5045f89025e49e
0
UnknownStranger 101 Sep 10, 2004 at 10:06

@Tufty

Probably a good thing…… [snapback]11165[/snapback]

Definitly :yes:

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Sep 10, 2004 at 12:32

And I’m soon going to be learning how to program games properly :) Just found out, I’ve passed the course I was doing last year, enabling me to start on my proper degree in Games Programming at the University of Teesside :) For anyone who doesn’t know, that’s in Middlesbrough, England, which is itself about 25 or so miles south of Newcastle.

Baaecfb3a09127d5bc5045f89025e49e
0
UnknownStranger 101 Sep 10, 2004 at 14:29

Congrats! :yes:

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Sep 10, 2004 at 15:28

my idea would be to store all uncompleted chains seperatly and as the colored balls touch down you simply check the balls arround them and their coresponding chains and eventually update them to include the new ball/balls. this is much less work than searching the entire set of chains

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Sep 10, 2004 at 16:18

Good idea. But I have no idea of how to store the chains themselves yet. Thought about some sort of linked list, but not gotten any further than that. For the very small play area it’s debatable whether I’d need to worry too much how I store them though.

81c280e6287b230f01c5a42a954f36b2
0
stodge 101 Sep 10, 2004 at 17:35

I went to Teesside Polytechnic, as it used to be known. If he’s still there, listen to Pete Prince; he’s a smart guy!!!! Games Development indeed! (enter Monty Python) When I were at Teesside, we had nowt but crappy Prime system, which used to crash every lesson. Y’ad to walk t’ multi-storey building just t’ pick up yer printouts the day after yer printed ‘em. That fancy glass building weren’t there on Southfield Road (is that the name?) - there were nowt there but car parks!

Hope you enjoy it there!

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Sep 10, 2004 at 19:21

Just searched on the Intranet site - Pete Prince is indeed still there, surprisingly. Whether I’ll have him for any lectures, we’ll see. Yep Southfield Road is the name, they’ve built loads of shiny new stuff since your time I guess. The systems are quite up to date these days, and Teesside was recommended by several of the UKs leading games studios - that, and the fact that it’s the uni nearest to me, were the major factors in my choice :)

They’ve even got development kits for the current generation of consoles, but I won’t get to play with them much until my 3rd year - and by then they’ll hopefully have updated again. I’m just looking forward to it now :)

If anyone’s interested in what the course involves (maybe for people considering going next year), then I’ll post more details as and when I get them. Not sure what modules I’m doing yet.