Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
27 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

Collapsing elements

Started by
5 comments, last by Zakwayda 13 years ago
Im currently working on a "bust a move" style game, but have no idea how to solve the collapsing elements problem.
The gamefield is represented as a simple 2D array, and no color matching rule right now (like in the mentioned game).
The main question, how can i check if a cell (or a groups of cells) is separated from the others?

I made a picture:
bam_coll.png
Here, i marked the separated cell group that i need to remove.
Is there any general algorithm that can solve this problem?
Advertisement
Perhaps 'flood-fill' is what you're looking for.
The correct problem to look for is connected components labelling: http://en.wikipedia...._(graph_theory)

You can solve it in linear time using any standard graph traversal (ie breadth first/depth first search). However, since it seems like you are updating the graph by incrementally adding elements and removing sets, you may be better off using a union-find data structure to keep track of each component. Here is a link to the relevant material: http://en.wikipedia...._data_structure

The union-find will give you nearly constant time cost for locating and updating connected components, and it is also pretty damn easy to code up.
Thank you! :)

Thank you! :)

Does that mean you found a solution? :) If so, what was it? (It might be helpful to others who might read the thread in the future.)
Ohh, sorry.
Yes, i found the solution. The flood-fill works like a charm (with heavy optimizations). :)
The wiki article about flood-fill starts with a list of games using this method, and this games are the same type like what i working on...

Thanks again, i never managed to find it out from myself this solution. :)

The flood-fill works like a charm (with heavy optimizations).

Great, glad it worked :)

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
AliAbdulKareem
Understanding the wavy-like shape in alpha-testing magnification for text rendering Graphics and GPU Programming
Advertisement

Recommended Tutorials

Azaral
Game Crafting Activities in Real Life - Blacksmithing Part 2 Game Design and Theory
kevinharwood
Humble Bundle Distribution Business and Law
doug25
Animating Characters with DirectX Graphics and GPU Programming
mikeshafer
Design of an Indie Action Game Game Design and Theory
Myopic Rhino
High Resolution Timing In Games General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top