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
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?
Please log in or register to post a reply.
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
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.
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… ;)
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
Probably a good thing……
Probably a good thing……
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.
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
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.
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!
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.