• Advertisement
Sign in to follow this  

rectangle combination problem

This topic is 4004 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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: http://img6.imageshack.us/img6/5378/spf25nq.jpg 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
Advertisement
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
Sign in to follow this  

  • Advertisement