Imitation QQ Look at [Thinking, Source]
Direct record a connection of the requirements of the second point can connect three maps no prompt four connection prompt function five items problem six map problems
I. Requirements of Lianlian
1: The graphics to be connected are the same. 2: There is no "obstacle" and no more than two routes between the two points. So, you can see it, it is generally divided into three situations.
[Image Description] Assume that a two-dimensional number of groups represent a connected map, the elements value of 0 in the array represents the space gardens in the game interface, the value of the value greater than 0 representing various connection objects in the game (1 representative stars) 2 represents the class of penguins 1: Two points to connect to the same line 0 0 0 0 0 0 0 0 0 0 0 0 0 ------ * 0 0 0 0 0 0
Situation 2: Connected by a pen point ( "representative perspective)
0 0 0 0 0 0 0 2 0 0 0 * ------ 0 0 0 0 2 ------ * (two roads can be connected)
Sitle 3: After two discount points (for penguins, ie numbers 2) 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 2 0 1 0 2 0 0 0 0 0 or 0 0 0 0
Due to one obstacle, two discount points can be connected
Second, whether any two points can connect
The path finding algorithm is the core algorithm for the entire game. There are many versions of online implementation. The method here is a method I am more likely to understand ^ o ^, I also hope that everyone can propose Bao Gui's critical opinions and suggestions, thank you.
The idea is as follows:
1 No two points on the line can be connected to it (a simple loop judgment)
2 For the case of the above legend, the coordinates of the discount point are fixed, that is, the discount point is either
[Coordinate X, Coordinate Y] either [Coordinate Y, Coordinate X] Y
| | | | * ------ | ---- * --------------- X
Therefore, we only need to judge whether the cispoint 1 to the perspective can be connected, and the coded 2 to the perspective can be connected to whether or not the cis 1 and the cistem 2 can communicate. And because the depot and the two points are on the same straight line, the first step is easily judged to the conclusion.
3 Transformation of the three transformations into the case, (this step is how to transform the most influential performance and what you need to improve in this algorithm)?
0 0 0 0 0 2 0 1 0 2 0 0 0 0 0 (case three)
Will be the point of the point on the same line on the same line, then the case is transformed into the case of the case 2 0 2 0 0 0 0 * 0 1 0 2 (the asterisk is the original point) 0 0 0 0 0 (After the transformation, the upper left pan has been replaced) The situation between the two connection objects 2 is now variable. 4 By you can see, finding this replacement point is a key. Because its coordinates are not fixed, they only have a recursive one. Looking for this point, you need to do a lot of optimization (I didn't think of it) 2 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 * 0 0 0 0 0 0 1 2 * 0 2 1 0 0 0 0 2 1 2 0 0
The above three pictures, number is the discount point, the * is the need to replace it.
Suppose A, B is the same graph, to think about the following route
0 0 0 0 0 0 0 1 0 B 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
If our algorithm is looking for it, rotate clockwise, then a point to the right movement 1 to reach the location of the AA. At this time, the test AA and B can connect (according to the case), the result is not, due to There are "obstacles" (two 1), then AAA at point A, then arrive at AAA
0 0 0 0 0 0 0 0 0 B 0 0 0 0 0 0 0 A aa aaa 1 0 0 0 0 0 0 0 0 0 0 0 0
At AAA, when it is connected to the B point (second processing), the result is that the A point can communicate with B, the route is * |
Increase an obstacle
0 0 0 0 0 0 0 1 1 B 0 0 0 0 0 0 0 0 A AAA 1 0 0 0 0 0 0 0 0 0 0 0 0
This time, when looking into the AAA position, the result is not connected. On the right, due to the obstacle, the road to the right, the declaration failed, the recursive returned to the origin, changed from the A point downwards to start judgment
0 0 0 0 0 0 0 1 1 B 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (still unconnected down) to the left, Final upward
0 0 0 0 0 0 0 1 1 B 0 0 aa 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (AA point and the B point meet the case, can be connected)
Route * | ----------- | *
The worst case, calculated in the size of QQ 11 * 19, transferring 28 times, the case 2 Circular no more than 500 times
0 0 0 0 0 0 0 1 1 B 0 0 0 0 1 1 1 0 A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Third, the map does not solve the prompt
Because the position of the connection object is fixed (the position is also fixed after the proppins), I record these location information in n string (1 dimensional array) (N ==) in the game. ), A string records one, formatted as:
10208110507151218 First-digit 1, indicating the category of the object (Is Penguin? Is the stars?) 16 bits of each 4-bit group, indicating the location information of an object belonging to this category, 0208 represents the coordinate array in the array [2] [8 ], In this category of the stars, there is a coordinates in the game in the game to be [2] [8].
In this way, we are in the same category, looking for any combination of existing in this category to connect. That is, an object in this class can communicate with other objects in this category.
Just find one, that is, it is solved. If you look up all, then you will not be able to solve it.
When we eliminate a pair of connection objects, the location information of the two connection objects (corresponding position string becomes -1) is deleted in the corresponding string, such as 0208 to -1-1.
Fourth, the connection prompt function According to the array of location information above, the connection object can be configured to instantly and other connection objects in this class in turn. For example, read the first element of the array, extract information of the first connection object in this string, such as 1-1-11105-1-11218, extract 11, 5 location information, use it Connections 12, 18 can be connected.
V. props
1. The mirror is still based on the location information string array, extracts the position of each object, and then takes an absolute value with the coordinate X- (game width -1) of the connection object. 0 0 0 0 0 0 0 * 0 0 0 0 0 0 * 0 - 3 = -3 0 * 0 0 0 0 0 1 - 3 = -2 0 0 0 0 0 0 0 ----- ---- 0 1 2 3 0 1 2 32, it is assumed that we have 15 connection objects in some games in some games, each 4, representing the penguin with 1 representative stars 2 ..., then we A string 444444444444444 is still 15 4, each of which corresponds to a connection object, such as how many (4) in the game in the game, the second represents the penguin in the game How many ... When we pin a picture, the location of this string corresponds to the position of each bit of the string, is the current game. Image number (QQ prompt). When other players use increase the obstacle props to add obstacles, they can be 2.
Now the location of the connection object in the game knows (location information), quantity knows (defined strings), a connection object is randomly based on the location, if the connection object is still valued in the front definition string (not 0 ), We are recorded in another string (identical to the previous functional structure), if the corresponding value on the new string is equal to the corresponding value on the original string, it is not in this type ( The number of types and prior to the previous type, scan all the positions, thereby realizing the list. (The newly old character string should wait, because only change the location of a connection object, and the quantity has not changed)
3. When did I appear? I feel like a relatively fairness of QQ items (you have anyone, others are also seeing this: in a time (after some quantity, or how much to connect quickly) then randomly appear Some props.
Sixth, the map problem uses such an array represents the arrangement of our customized
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 arrays 0 It is the space in the game, which represents some kind of connection object, so that we can customize any shape. According to this array, if the value of a certain point is not 0, a connection object is randomly generated, and the corresponding position in the previous type of detailed quantity string 1 (QQ is 4), when this location (kind The value is 4, it will no longer be added.
I like to play QQ, I really want to write one, so I have this article.
April 21, 2005
(Endlessly)
