Headman and Neighbors

Hedommist (in ancient Rome) - a person who receives a buzz from programming.

Interests in programming are endangered by unsanitary conditions, neglected children, official reprimands, escaped milk, or a women's boot flying to the temple.

I remember this, overcoming alluring algorithms.

And I want to talk about a useless task that I solved a week in complete ecstasy. The task was born thanks to 3aicheg , whose commentary gave me an idea for a game under iOS (see your eyes, sho again?). The point is to make a match game on an irregular grid with gravity .
')
By the way, if you think that talking here about your free application, you can get world fame and buy a yacht, then here is the table

Article rating	Article views	Video views	Downloads
+30	20,000	5,000	18
-2	2,500	2,000	14

And therefore I admire the disinterested authors of Habr (especially those who speak Russian). Now to the point! And the thing is ...

Task 1 - Arrangement of initial data

So, consider a rectangle (the screen of our phone), the vertices of the rectangle are renumbered 0, 1, 2, 3. Inside this rectangle all sorts of disgraces will be created.


Fig. 1 Rectangle with vertices 0, 1, 2, 3

Let's randomly throw N points into this rectangle, number them from 4 to 4 + N. Why from 4? Because all the places (0-3) are already occupied by Hippo.


Fig. 2 Set of random points

Random scatter is sometimes dangerous - some points may fall too close to each other, so the player will not be able to distinguish them on the screen and click on the point he liked. Knowing the physical size of the fingerprint of the player’s index finger, I add the condition that the distance between the points must be at least 26 pixels. How to satisfy this condition? Two ways 1) Move the points in the direction of the rarefied space and 2) throw a new point until the radiusMin> 26 condition is met. The second method is easier, but more dangerous - it is possible to loop if N is too large. But N is fine with me, the reserve of free space is fivefold and therefore we move on, namely, we find the nearest neighbors for all our points. We go in order, that is, we first look for neighbors for a point with a number, as you understand, 4.

To do this, arrange clockwise all the radius vectors from our point to all the others.


Fig. 3 Arrange the radius vectors [9-7-5-10-11-8-6]

In Swift it looks like this:

let x0 = pts[4].x let y0 = pts[4].y var vtx = [Point]() for i in 5..<pts.count { let x = pts[i].x let y = pts[i].y let u = x-x0 let v = y-y0 let a = atan2(v, -u) vtx.append(Point(x:(x+x0)/2, y:(y+y0)/2, angle:a )) } } vtx = vtx.sorted(by:{ $0.angle > $1.angle }) 

Now in our vtx array we store vertices [9-7-5-10-11-8-6], go through them and build a polygon surrounding the desired point with number 4. So, initially, our point is surrounded by a rectangle with vertices [0- 1-2-3], as in fig. one.

Take the first vertex from the ordered list - this is the point with the number 9. We build a perpendicular to the segment [4-9], dividing it in half.


Fig. 4 straight line equidistant from points 4 and 9

The resulting straight line either intersects the polygon [0-1-2-3] or not. Looking at Figure 4 is easy to detect that crosses. I decided not to give the equation of the intersection of a segment and a line. Thus, instead of [0-1-2-3], we get a polygon [0-1-9-3], which we see in Figure 5.


Fig. 5 Polygon [0-1-9-3]

Go to the next point from the list [9-7-5-10-11-8-6]. This is point number 7. We do everything the same - we build a perpendicular equidistant from points 4 and 7 and check if it intersects our polygon [0-1-9-3].


Fig. 6 Polygon [0-1-9-3] does not intersect straight line [4-7]

It does not intersect, do not do anything, therefore we proceed to the next pair of points with numbers 4 and 5.


Fig. 7 Polygon [0-1-9-5-3]

And so on. The Forchun method (so beloved on Habré, already 3 articles about him) to speed up the finding of neighbors should not be used here, since we do not have 100,000 points in the problem. And there are no 1000 points. And how much? 50-70 points - this number is due to the physical size of the phone screen. Here is the final picture for the polygon around the first vertex number 4


Fig. 8 Polygon [0-6-9-10-8-3]

To draw polygons, I use my native UIKit with a texture fill (from there and drawing lines). Example code inside func draw (_ rect: CGRect):

  let colors:[UIColor] = [UIColor.black, UIColor(patternImage: UIImage(named: "b_19.png")!), UIColor(patternImage: UIImage(named: "b_20.png")!), UIColor(patternImage: UIImage(named: "b_21.png")!), UIColor(patternImage: UIImage(named: "b_22.png")!), UIColor(patternImage: UIImage(named: "b_23.png")!), ] func renderSimple(_ t:Convex) { let path = UIBezierPath() let strokeColor = UIColor.black strokeColor.setStroke() path.lineWidth = 1.0 let clr = t.color var i = 0 for p in t.vtx { if i == 0 { i = 1 path.move(to: p) } else { path.addLine(to: p) } } if clr>0 { let fillColor = colors[clr] fillColor.setFill() path.fill() } path.stroke() } 

Wow I'm tired of writing. Marry fingers play a couple of levels in the resulting game Zabivaka



Go ahead. It turned out such a random, but pretty picture.




Fig. 9 Level Kansas - I want to press and clear the blue chain

If you have such a desire (to press and clear the blue chain), it means that the game is not the worst. As you can see, it was necessary to invent a law for the flow of colored cells into vacated empty cells. Why should they flow or shift? Because the game has a gravity field included. After numerical experiments, I came across the Trump-Galilean law - a particle moves to an empty neighboring one if the center of gravity of the latter is below the center of gravity of the original particle. Jelly does not flow up. And the second condition - the lowest point of the common border of two particles must be below the center of gravity of the original particle - this means that the jelly does not flow through the high edge of the glass. In the game process, this law was immediately tested and approved by me.

The only thing that needed to be programmed for this law is an algorithm for calculating the center of gravity of an arbitrary polygon. At the beginning, I thought it was easy — as in a triangle — to find the arithmetic mean of the coordinates of the vertices! Loshara, you will say and you will be right. He divided the polygon into triangles, summed the centers of gravity of the triangles in proportion to their sizes (areas). Everything became beautiful. If you have feedback about the game from you - write, I live alone now - I will be glad to any comment.

Menu

In any game you need a goal - usually you must complete all levels. Levels depict on everyone - for example, these are cities on the map that you must conquer. I decided that triangulation is a great way to draw real maps (schematically, animatedly) without any effort. And indeed, I downloaded a list of cities in the world with geo-coordinates and built a grid on this data according to the algorithm described above. And that's what happened.




Fig. 10 Maps of recognizable countries

The list of geo-coordinates for, for example, Italy looks like this:

  City(name:"Rome",x:41.9000,y:12.4833,s:4), City(name:"Ancona",x:43.6333,y:13.5000,s:4), City(name:"Ascoli",x:42.8500,y:13.5667,s:4), City(name:"Bari",x:41.1333,y:16.8500,s:4), City(name:"Bologna",x:44.4833,y:11.3333,s:4), City(name:"Brescia",x:45.5500,y:10.2500,s:4), City(name:"Catania",x:37.5000,y:15.1000,s:4), City(name:"Cesena",x:44.1433,y:12.2497,s:4), City(name:"Cagliari",x:39.2167,y:9.1167,s:4), City(name:"Florence",x:43.7667,y:11.2500,s:4), 

In my opinion, a great way to build game cards. Of course, you need to add parasitic points, emulating the sea or neighboring countries. I added 16 points to each map, some parasitic points had to be edited with pens.

To intimidate a player, I introduced a rule - no more than 15 clicks per game. It was difficult to test the game in such conditions, I faintly increased this number to 16. In addition, I found a mistake on the last move, but did not correct it - this error helps to overcome the seemingly impossible decompositions. And gives the mood of the game. For a great masterful passing level added bonuses - animation busty girls and pirated music. In short, I am personally pleased. Well, I hope it was not boring for you to read the story about a toy on Swifte in this inclement time.

See you, brothers ...