In the last post, I analyzed those UI related sprite of the Melting Line puzzle game. In this post, I would like to introduce the list structure and how to judge pass/fail condition of the game. All of these functions are implemented by Algorithm Sprite.
“when I receive start a level” Code Segment
In this code segment, the program does all the initialization job. It sets “Cut Times” variable to 0 and deletes all of the 5 lists used in this project. It then fills data into “start_point_list” and “end_point_list”. The total segment number is decided by variable “Total_Segments”. The starting point of a segment clone is picked randomly from 1 to 20. The length of each clone is chosen randomly from 1 to 8. Based on start point and segment length, the program automatically calculates the end point and fills the list “end_point_list”.
After filling the lists, the program calls two blocks “Sort_list” and “Get_min_times” to calculated the expected minimum cutting times. It waits till the variable “Cut Times” equal to the length of “Prospect_list”. If any segment clone still displays on the stage, it means the cutting operation is not the optimal one, and the program broadcasts “fail” message. Otherwise, it broadcasts “pass the level” message.
From the above code segment, we could also see that each time the game is running, a new set of random data fills the lists of “start_point_list” and “end_point_list”, so how could we make the program calculate the minimum cutting times to judge the pass/fail condition?
In the following section, I will explain the method to solve this problem.
The whole idea for the program to calculate minimum cutting times is based on greedy algorithm. To use this method, the first thing is to sort all the segment data in a sequential way. The program sorts starting point value and put the sorted data in the other two lists: “sorted_start_list” and “sorted_end_list”.
Please note that we still want the segment clones show on stage in a unsorted way. Therefore, the program chooses to store sorted data separately from the original ones. The sorting method is easy to be understood. It iterates the whole list of “start_point_list” and puts items in an incremental order into the new list “sorted_start_list”.
Please note that when inserting items into “sorted_start_list”, the corresponding item in “end_point_list” is inserted to the same index of “sorted_end_list”.
In the below diagram, the left image shows the unsorted data, while the right one displays the sorted data. Please note these two diagrams are just for illustration. In real game, all the data shown on the stage is unsorted, as shown in the left image.
So what is the purpose of sorting data? After sorting data, the program could start seeking the prospected cutting place in an incremental sequence. It starts checking the 1st segment and assumes to set cutting place at the end point of the 1st segment. The program will check if any other segment whose end point is smaller than that of 1st segment. If there is, the cutting place should move to the smaller end point, so that the program would not miss any cutting place.
Once deciding the cutting place, the program will record the cutting place in a list. The index would move forward by 1 as the new start place. At that moment, any segment clones whose start point bigger than or equal to the current start point should still stay on the stage and the next iteration of seeking cutting place starts again.
The following code is the implementation of the above mentioned method.
That is all the main code for this puzzle game. Some supplementary sprites, such as banner sprite and info sprite, are not explained here. Hope this post could help you understand more about how to design and develop puzzle game. Enjoy the coding and have fun!
Note: All the analysis articles are copyright products of http://www.thecodingfun.com. Anyone re-posting them should credit author and original source. Anyone using them for commercial purposes or translating them into other languages should notify TheCodingFun and get confirmation first. All Rights Reserved.