Gadommist and nearest neighbors

Gedommist (in Ancient Rome) - a person who gets high from programming.

Passion for programming is accompanied by dangers - unsanitary conditions, forgotten children, official reprimands, escaped milk or a woman’s boots flying into the temple.

I remember this, overcoming algorithms beckoning with complexity.

And I want to talk about one useless task that I solved a week in complete ecstasy. The task was born thanks to 3aicheg , whose comment gave me an idea for playing for iOS (see your eyes, Shaw again?). The point is to make a match game on an irregular grid with gravity .

By the way, if you think that talking about your free application here, 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 unselfish authors of Habr (especially those who own the Russian syllable). Now to the point! But the thing is ...

Task 1 - placement of the initial data

So, consider a rectangle (the screen of our phone), the vertices of the rectangle are numbered 0, 1, 2, 3. Inside this rectangle, all sorts of ugliness will happen.


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

Let us 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 hippos.


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 between them on the screen and click on the point he likes. Knowing the physical size of the player’s index fingerprint, I add the condition that the distance between the points should be at least 26 pixels. How to satisfy this condition? Two ways: 1) Move points in the direction of rarefied space and 2) throw a new point until the condition radiusMin> 26 is fulfilled. The second way is easier, but more dangerous - it is possible to loop at too large values ​​of N. But I have everything in order with N, 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, first we look for neighbors for a point with a number, as you know, 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.. $1.angle })
 

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

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


Fig. 4 A line equidistant from points 4 and 9

The resulting line either intersects the polygon [0-1-2-3] or not. Looking at Figure 4 it is easy to find what crosses. I decided not to give the equation of intersection of a line segment and a line. Thus, instead of [0-1-2-3], we get the 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 the same thing - 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 a straight line [4-7]

Does not intersect, nothing needs to be done, 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. Fortune’s method (he’s so beloved on Habré, has been leafing through 3 articles about him) to speed up finding neighbors is not worth using here, since we do not have 100,000 points in the problem. And there are no 1000 points. How much? 50-70 points - this number is due to the physical size of the phone screen. Here are the final picture for a polygon around the first vertex number 4


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

To draw polygons, I use my own UIKit with a texture fill (from there I draw lines). Sample 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 Tired of composing. Mash your fingers, play a couple of levels in the resulting Zabivaka game



Move on. The result was such a random, but nice picture.




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

If you had such a desire (click and clear the blue chain) - then the game is not the worst. As you can see, it was necessary to come up with a law on the flow of colored cells into empty empty cells. Why should they flow or shift? Because the game includes a gravity field. After numerical experiments, I came across the Trump-Galileo 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 should be below the center of gravity of the original particle - this means that jelly does not flow through the high edge of the glass. In the gameplay, this law was immediately tested and approved by me.

The only thing that needed to be programmed for this law was an algorithm for calculating the center of gravity of an arbitrary polygon. At first, I thought it was easy - like in a triangle - to find the arithmetic mean of the coordinates of the vertices! Loshara, you say, and you will be right. He divided the polygon into triangles, summed up the centers of gravity of the triangles in proportion to their size (area). Everything has become beautiful. If there are reviews from you about the game - write, I live alone now - I will be glad to any comment.

Menu

In any game, you need a goal - usually you have to go through all the levels. The levels are depicted in every way - 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. Indeed, I uploaded a list of world cities with geo-coordinates and built a grid on this data using 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 spurious points that emulate the sea or neighboring countries. I added 16 points to each map, some spurious 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 cowardly increased this number to 16. In addition, I found an error at the last move, but did not fix it - this error helps to overcome seemingly impossible situations. And gives mood to the game. For a great masterful level passing he added bonuses - animation of a busty girl and pirate music. In short, I am personally pleased. Well, and I hope it wasn’t boring for you to read a story about a toy on Swifte in this inclement time.

See you brothers ...