Introduction or as I wrote my first AI

Good day. I wrote my first artificial intelligence many years ago when I was in college. Then it was an AI for a snake in an unusual game for snakes - Serpent's Madness (link leads to my game site), in which the latter can move in any direction. The screenshot below demonstrates this:



Then it was a deterministic algorithm, i.e. an algorithm with a clear sequence of actions, when at each step you can say exactly what will be next. He looked something like this (pseudocode):

 rwarn = 0 // danger threatening the snake on the right
 lwarn = 0 // danger threatening the snake on the left
 for all opponents op {
	 If the point is the center of the opponent's bone op lies within the semicircle of the snake, then {
		 If the point lies to the right of the snake, then
			 rwarn ++;
		 If the point lies to the left of the snake, then
			 lwarn ++;
	 }
	 If we move parallel to one of the walls at a distance not more than the specified one with the maximum deviation of the motion vector along one of the coordinates (x or y) not more than the specified one, then {
		 If the wall is to the right of the snake, then
			 rwarn + = 100;
		 If the wall is to the left of the snake, then
			 lwarn + = 100;
	 }
	 If rwarn! = 0 and lwarn! = 0, then {
		 If rwarn> lwarn, then turn left.  Otherwise - to the right.
	 }
 } // for all opponents op

Those. this AI for the given arrangements of snakes always does the same thing: turns in the direction where there are fewer snakes and / or walls. Yes, yes, I indicated the magic number "100", which increases the danger if there is a wall. Magic numbers are a bad programming style, but at the time it was excusable. I did this so that the snakes more often hit other snakes than the walls, although the condition is relatively relative: if there are more than 100 bones (= parts) of other snakes within the semi-circle of the snake, the algorithm will choose to crash into the wall. Despite this, the algorithm worked quite well: the AI ​​circled around the snakes from different angles, circled the walls (never crashed into them, if other snakes were not forced), and also balanced between the wall and the snake when it was done.
However, he had 2 drawbacks:
1) When the snake was traveling close to the wall, and the AI ​​was between the wall and the snake, then even if it was where to go, the following occurred periodically: the AI ​​got confused, jerked - slightly to the left, slightly to the right, slightly to the left ... and died.
2) At the same predetermined distance from the snake, the AI ​​always began to turn. If it turned out that the snake was at a greater distance from the AI, and a little later - at a much smaller one (turned sharply in the direction of the AI), then the AI ​​crashed. Provided that he could turn in advance or at least start turning. I was thinking about introducing another semicircle with a large radius - for which you need to turn "a little". Then I told myself stop, because the algorithm became, it seems to me, too complicated. Well, if you complicate things, you will definitely enter waypoints, I thought.
These two flaws can be described in one word - the snake was in some cases "jerky" and because of this, it occasionally died.
Now, when after 5 years, I have ported Serpent's Madness to android , I decided that this shortcoming must be fought. And this helped me "fuzzy logic." I understand fuzzy logic as a tool for inserting our “fuzzy” reasoning into an algorithm. So, take a look at the task from a new point of view.
')

Principle

The snake in Serpent's Madness , which I am developing, can move left, right or forward. She cannot move at all. Thus, the AI ​​will have the following outputs:
1) turn left
2) turn right
3) go ahead
In accordance with this, we will present a table with linguistic variables — variables that can take on the meaning of phrases from a natural or artificial language.

	Distance to snakes	Snake density	Distance to the walls	Hitting the corner
Left
On right
Ahead

There will be terms in the cells. By term, I mean the very meaning of the phrase for variables (linguistic).
far, just, close - when it comes to distance (columns 1 and 3)
no, small, medium, many - when it comes to the density of snakes (column 2)
No, perhaps for sure - when it comes to hitting a corner (column 4)

For each term, membership functions are determined. In the sense here it will be “danger function” from 0 to 1, the greater the value, the greater the danger of going in a given direction.
For each row i, we calculate the maximum values ​​in the cells m (i). So let's say the maximum danger for the parameters in a given direction. Then from all such m (i) we find the minimum. At a minimum, this will be the answer to the question - what to do, turn left / right or go straight.

Below are a few examples. I draw attention to the fact that the numerical interpretation is given only as an example. Actually, in the developed system, there may be other values.

Example №1

	Distance to snakes	Snake density	Distance to the walls	Hitting the corner
Left	just	few	not	not
On right	long away	not	just	exactly
Ahead	close	lot	long away	not

The result should be a decision to turn left.
What is obtained from the calculations:
min (max (0.5, 0.33, 0, 0), max (0, 0, 0.5, 1), max (1, 1, 0, 0)) = min (0.5, 1, 1) = 0.5 = turn left

Example 2

	Distance to snakes	Snake density	Distance to the walls	Hitting the corner
Left	close	average	long away	not
On right	long away	not	long away	not
Ahead	close	average	long away	not

The result should be the decision to turn right.
min (max (1, 0.75, 0, 0), max (1, 0.75, 0, 0), max (0,0,0,0) = min (1,1,0) = 0 = turn right

Example 3

	Distance to snakes	Snake density	Distance to the walls	Hitting the corner
Left	close	average	long away	not
On right	long away	not	close	not
Ahead	close	average	long away	not

The resulting decision is difficult to make - everywhere there is a danger of inevitable death.
What the snake will solve:
min (max (1, 0.75, 0,0), max (1, 0.75, 0, 0), (0,0, 1, 0)) = min (1,1,1) = 1 = turn left

I want to add to the logic in perspective the following: the same term (let's say close) for snakes has a lesser degree of belonging than for walls. This will give in case of imminent death, say in all directions a collision with a snake, and not a wall - this is so that players can score points faster.

Calculation Rules

When developing I will pay attention to the following moments. They save CPU time.
1) if the term for the function max is calculated and is 1, then there is no sense in calculating the rest, the maximum will give 1.
2) if the term for the min function is calculated and is 0, then there is no point in calculating the rest, the min will give 0.

Graphic interpretation

At the left, in front, on the right - 1,2,3 respectively. The vertical bar is the snake symbol.
These are areas of analysis. It makes no sense for us to analyze what is behind, so areas 1 and 2 are bounded below by a horizontal line. It should be noted that when “filling” the sector with walls, it is not the sector of the circle that is used (as is the case with the bones of snakes), but the triangle inscribed in it.
Implementation of membership functions for terms
It turns out that we have 3 areas:
left, right and front. All these areas add up to half the circumference, and one by one - sectors of 1/3 each.
A sector may contain:
1) the bones of all snakes (including the snake itself - you need to go around your tail), i.e. their coordinates and number
2) walls (maximum two, when the angle they have a common point)
Such a sector is fed to the input of the function “distance to snakes”, “density of snakes”, “distance to walls” and “hitting the corner”. Next comes the degree of belonging, and with them we already know what to do. The functions themselves are also not complicated.
The most difficult moment is to form such sectors.

Sector fields and responsibilities

Circle Sector class CircleSector
Behavior:
1) check the ownership of the point sector
2) find the intersection with the rectangle (from 0 to 4 points), bearing in mind that the sector is always centered inside the rectangle
3) Initialize according to snake bones and walls (using the methods above)
4) learn the min. Distance to snakes (lingv. Variable 1)
5) find out the density of snakes (ling. Trans. 2)
6) learn the min. Distance to the walls (ling. Trans. 3)
7) find out the degree of hitting the corner
8) find out the degree of maximum danger
From 4 to 7 - the implementation of membership functions.
8 - looking for a maximum of 4-7.
Fields:
points - coordinates (centers) of snake bones
points - coordinates of wall segments (0, 2, 3 (angle), 4)

Alteration

Having implemented the first version of fuzzy AI, I launch Serpent's Madness and see a number of flaws.
It is revealed that the snake is spinning and spinning when there is no danger.
Minmax function with the same values ​​of threats in the sectors returns the first sector. And the first - right. I did the first - the front sector. Now the default snake goes forward, as required.
Noticed that the snake, when traveling perpendicular to the wall - crashes into it. In this case, the analysis proceeds as usual (everything is initialized correctly). It seems that when moving perpendicularly, all sectors equally contain one wall, and the front sector turns out to be “closest” to it, respectively, the threat in it is minimal. Fix it, let the front sector be slightly longer than the rest. Then the membership function will return a greater threat when moving perpendicular to the wall. Already increasing the radius of the sector by 1.1 times compared with other sectors saves us from this bug.
Sometimes snakes hit their heads together or even the four of us. It was established experimentally that with the increase in all sectors twice the collisions become less frequent. But then the snakes become overly cautious - at a great distance from the minimal danger they turn and it becomes not so interesting to play. Nevertheless, snakes still sometimes encounter "foreheads" together. This, in my opinion, is the problem of this kind of intelligence: an analysis of only a nearby area at the current moment without an analysis of possible actions of the enemy in the following points in time.

Listings of Java & Android SDK (v2.1)

And now I will give the working code, which for some reason is rarely done in most articles (which I have seen) on artificial intelligence with fuzzy logic. You can clearly see how this AI works by playing in Serpent's Madness long-snake levels. At the time of editing the article, this is the 4th level.

package com.iz.serpents.tools; import java.util.Collections; import java.util.LinkedList; import java.util.List; import android.graphics.RectF; import com.iz.serpents.model.Movement; import com.iz.serpents.model.Serpent; import com.iz.serpents.model.SerpentCollidable; /** * @author Deepscorn * There are three sectors, which in sum gives us one half of circle, * these sectors corresponds to aim, specified in constructor. * Each sector (LEFT, RIGHT, FORWARD) is 60 degrees. * So, sector is 1/6 of circle square. * */ public class CircleSector { /* * Checks if circle sector has the given point. * Algorithm is: * 1) check distance < radius * 2) check point is to the left of the first line * 3) check point is to the right of the second line */ public boolean hasPoint(Vector pt) { return (pt.qdist(O) < rad && pt.isOnLine(O, A)<0 && pt.isOnLine(O, B)>0); } /* * Creates sector * @param movementType - one of Movement.*, used in sector creation, different * movementTypes means different sectors * Note, that FORWARD sector will have radius greater, than specified in circleRadius. */ public CircleSector(float circleRadius, int movementType, Vector aim, Vector circleCenter) { if(movementType == Movement.FORWARD) rad = circleRadius * 1.1f; else rad = circleRadius; O = circleCenter; type = movementType; _ptBones = new LinkedList<Vector>(); _ptWalls = new LinkedList<Vector>(); Vector ortAim = (Vector) aim.clone(); ortAim.normalize(); Vector vC = ortAim.mul(rad); Vector vAC = null, vCB = null; if(type == Movement.LEFT || type == Movement.FORWARD) { vAC = (Vector) vC.clone(); vAC.qrotate(30, Movement.LEFT); } if(type == Movement.FORWARD || type == Movement.RIGHT) { vCB = (Vector) vC.clone(); vCB.qrotate(30, Movement.RIGHT); } switch(type) { case Movement.LEFT: Vector lo = (Vector) ortAim.clone(); lo.leftOrtogonalRotate(); A = O.add( lo.mul(rad) ); B = O.add(vAC); break; case Movement.FORWARD: A = O.add(vAC); B = O.add(vCB); break; case Movement.RIGHT: Vector ro = (Vector) ortAim.clone(); ro.rightOrtogonalRotate(); A = O.add(vCB); B = O.add( ro.mul(rad) ); break; } possibleBonesInside = (int) ((rad*rad)/ (6f*Serpent.boneRad()*Serpent.boneRad())); } /* * Fills sector with content */ public void addBones(List<? extends Serpent> serpents, int indAI) { _indAI = indAI; for(int j = 0;j<serpents.size();j++) { Serpent s = serpents.get(j); int start = 0; if(j==indAI) start = SerpentCollidable.afterNeckInd; for(int i=start;i<s.numBones();i++) { if(hasPoint(s.bone(i))) _ptBones.add(s.bone(i)); } } } /* * Gets number of bones in sector */ public int getNumBones() { return _ptBones.size(); } /* * Fills sector with content */ public void addWalls(RectF walls) { List<Vector> walls_points = new LinkedList<Vector>(); walls_points.add(Vector.create(walls.left, walls.top)); walls_points.add(Vector.create(walls.right, walls.top)); walls_points.add(Vector.create(walls.right, walls.bottom)); walls_points.add(Vector.create(walls.left, walls.bottom)); walls_points.add(Vector.create(walls.left, walls.top)); for(int i=0;i<walls_points.size()-1;i++) { Vector common; //left common = Vector.intersect(walls_points.get(i), walls_points.get(i+1), O, A); if(common!=null) _ptWalls.add(common); //right common = Vector.intersect(walls_points.get(i), walls_points.get(i+1), O, B); if(common!=null) _ptWalls.add(common); //forward common = Vector.intersect(walls_points.get(i), walls_points.get(i+1), A, B); if(common!=null) _ptWalls.add(common); //corner if(_ptWalls.size()==1) _ptWalls.add(walls_points.get(i+1)); } } /* * Gets number of wall's ends in sector: * 0 - no walls * 2 - one wall * 3 - two walls (corner) * 4 - two walls * wall is a line with two (!) ends */ public int getNumWallEnds() { return _ptWalls.size(); } /* * Gets distance to closest serpent in range [0;rad] * Attention! Distance = rad, when there actually * no serpents! */ public float distToClosestSerpent() { float res = rad; for(int i=0;i<_ptBones.size();i++) { float dist = _ptBones.get(i).qdist(O); if(dist < res) res = dist; } return res; } /* * Gets distance to closest wall in range [0;rad] * Attention! Distance = rad, when there actually * no walls! */ public float distToClosestWall() { float res = rad; for(int i=0;i<_ptWalls.size();i++) { float dist = _ptWalls.get(i).qdist(O); if(dist < res) res = dist; } return res; } //RELATION FUNCTIONS// //all relation functions returns value in ragne [0;1], //where 1 - is "the worst" or "the biggest" threat //and 0 - means no threat at all public float rel_distToClosestSerpent() { return 1 - distToClosestSerpent()/rad; } public float rel_serpentsStrength() { return ((float)getNumBones())/possibleBonesInside; } public float rel_distToClosestWall() { return 1 - distToClosestWall()/rad; } public float rel_inCorner() { float res = 0; if(getNumWallEnds()==4) res = 0.5f; if(getNumWallEnds()==3) res = 1f; return res; } public float rel_max_threat() { return Math.max( Math.max(rel_distToClosestSerpent(), rel_serpentsStrength()), Math.max(rel_distToClosestWall(), rel_inCorner())); } /* * Finds minimal threat and returns index of the element. * Keep in mind, that if all threats are equal, than the first * sector will be returned. */ public static int findMinThreatReturnIndex(ICircleSectorReadable sector[]) { float min = sector[0].rel_max_threat(); int result = 0; for(int i=1;i<sector.length;i++) { float cur = sector[i].rel_max_threat(); if(min>cur) { result = i; min = cur; } } return result; } //RELATION FUNCTIONS END// //sector geometry private Vector O; private Vector A; private Vector B; private final float rad; private final int type; private final int possibleBonesInside; //sector is presented as two lines: (O,A) - left line, (0,B) - right line, //O - is center of circle, which sector it is //rad - radius of circle, which sector it is //type is one of Movement.*, used in sector creation, different //movementTypes means different sectors //when working with walls there used triangular instead of circle center - for //performance reasons //initialed if necessary: //sector content private List<Vector> _ptBones = null; private List<Vector> _ptWalls = null; //sector owner private int _indAI; } 

results

Below are screenshots from Serpent's Madness in AI debugging mode.
White marked the boundaries of the sectors - triangles (for the walls, for the bones - easy to imagine).

Yellow highlighted bones in the sector.

And red - the walls in the sector.

Sometimes they still collide. As I wrote above, this is eliminated by an increase in sectors. But within the framework of the game, an invincible AI was not needed.

But overall, the AI ​​is great:

This is my first development for the Android platform and the first AI with fuzzy logic, if you have any suggestions and comments - always ready to listen. Thanks for attention. If you are interested in the game, you can download it from Android Market:
Serpent's Madness