Sign in to follow this  
blackgame

rectangle combination problem

Recommended Posts

blackgame    122
this is main part of a super puzzle fighter like game. i have a function which may create a map contains many cells (say 20x20 for instance which means there're 400 cells in total), in each cell there may be an element with a value from 1-8 by shuffle, or 0 means an empty cell. and next step is to check the whole map and try to find if there're any cells with same color could be rectangles. here's a picture to demonstrate that: [url]http://img6.imageshack.us/img6/5378/spf25nq.jpg[/url] for example we have a map like this: 0000 0110 0110 or this: 0000 0111 0111 if so, all 4(6) cells with a value 1 could be combined into one special cell as follows: (9 means one cell of a rectangle) 0000 0990 0990 or 0000 0999 0999 it looks very simple, but pls check a map like this: 01100 11110 11110 as u can c there're several cross gems which could be a rectangle gem which some of its neighbors, and also could be another rectangle with other nieghbors. and here's my problem, how could we decide which rectangle is bigger ? if so finally the map should be looked like: 01100 99990 99990 not 09900 19910 19910 because first form is bigger. any idea ?

Share this post


Link to post
Share on other sites
Vorpy    869
Do a search for the biggest rectangle. If you're clever, the complexity of the algorithm will be linear in the number of cells on the board. If you're not so clever and just do a more brute force approach, it will still be more than fast enough since it's an operation that is done far less than once a frame.

Brute force approach: Loop through each cell and find the biggest rectangle that can be made with that cell being the top left corner (write this as a separate helper function that is called within the loop).

After finding the biggest such rectangle, create that rectangle.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this