[gnome-nibbles/wip/vala] Implement AI



commit b7890c7062f806f357ee6acf502a8c88aeb64c7f
Author: Iulian Radu <iulian radu67 gmail com>
Date:   Mon Aug 17 22:32:29 2015 +0300

    Implement AI
    
    Needs UI design for selecting the number of AI worms.

 src/gnome-nibbles.vala |    2 +-
 src/nibbles-game.vala  |   12 +-
 src/worm.vala          |  414 +++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 401 insertions(+), 27 deletions(-)
---
diff --git a/src/gnome-nibbles.vala b/src/gnome-nibbles.vala
index 7df3f30..80571fc 100644
--- a/src/gnome-nibbles.vala
+++ b/src/gnome-nibbles.vala
@@ -118,7 +118,7 @@ public class Nibbles : Gtk.Application
 
         settings = new Settings ("org.gnome.nibbles");
         worm_settings = new Gee.ArrayList<Settings> ();
-        for (int i = 0; i < NibblesGame.NUMHUMANS; i++)
+        for (int i = 0; i < NibblesGame.NUMWORMS; i++)
         {
             var name = "org.gnome.nibbles.worm%d".printf(i);
             worm_settings.add (new Settings (name));
diff --git a/src/nibbles-game.vala b/src/nibbles-game.vala
index 02a0884..e16309b 100644
--- a/src/nibbles-game.vala
+++ b/src/nibbles-game.vala
@@ -49,6 +49,8 @@ public class NibblesGame : Object
     public const int WIDTH = 92;
     public const int HEIGHT = 66;
 
+    public const int CAPACITY = WIDTH * HEIGHT;
+
     public const char EMPTYCHAR = 'a';
     public const char WORMCHAR = 'w';
 
@@ -59,9 +61,9 @@ public class NibblesGame : Object
 
     public Gee.LinkedList<Worm> worms;
 
-    public int numhumans = NUMHUMANS;
-    public int numai = NUMAI;
-    public int numworms = NUMHUMANS + NUMAI;
+    public int numhumans;
+    public int numai;
+    public int numworms;
 
     public int speed = 1;
 
@@ -200,6 +202,7 @@ public class NibblesGame : Object
         {
             var worm = new Worm (i);
             worm.bonus_found.connect (bonus_found_cb);
+            worm.is_human = (i < numhumans);
             worms.add (worm);
         }
     }
@@ -262,6 +265,9 @@ public class NibblesGame : Object
             if (worm.list.is_empty)
                 continue;
 
+            if (!worm.is_human)
+                worm.ai_move (walls, numworms, worms);
+
             foreach (var other_worm in worms)
             {
                 if (worm.will_collide_with_head (other_worm)
diff --git a/src/worm.vala b/src/worm.vala
index 285ad3b..375aeaf 100644
--- a/src/worm.vala
+++ b/src/worm.vala
@@ -43,22 +43,7 @@ public class Worm : Object
         set {}
     }
 
-    private WormDirection _direction;
-    public WormDirection direction
-    {
-        get { return _direction; }
-        set
-        {
-            if (keypress)
-            {
-                queue_keypress (value);
-                return;
-            }
-
-            _direction = value;
-            keypress = true;
-        }
-    }
+    public WormDirection direction;
 
     public WormDirection starting_direction;
 
@@ -78,7 +63,6 @@ public class Worm : Object
     public Worm (int id)
     {
         this.id = id;
-        is_human = true;
         lives = STARTING_LIVES;
         score = 0;
         change = 0;
@@ -205,8 +189,7 @@ public class Worm : Object
         var position = position_move ();
 
         if (walls[position.x, position.y] > NibblesGame.EMPTYCHAR
-            && walls[position.x, position.y] < 'z' + numworms
-            && position != list.last ()) /* The last position of the worm won't exist in the next frame */
+            && walls[position.x, position.y] < 'z' + numworms)
         {
             return false;
         }
@@ -292,6 +275,26 @@ public class Worm : Object
         return position;
     }
 
+    private void direction_set (WormDirection dir)
+    {
+        if (!is_human)
+            return;
+
+        if (dir > 4)
+            dir = (WormDirection) 1;
+        if (dir < 1)
+            dir = (WormDirection) 4;
+
+        if (keypress)
+        {
+            queue_keypress (dir);
+            return;
+        }
+
+        direction = (WormDirection) dir;
+        keypress = true;
+    }
+
     public bool handle_keypress (uint keyval, Gee.HashMap<Worm, WormProperties?> worm_props)
     {
         WormProperties properties;
@@ -340,7 +343,7 @@ public class Worm : Object
 
     public void handle_direction (WormDirection dir)
     {
-        direction = dir;
+        direction_set (dir);
     }
 
     public void queue_keypress (WormDirection dir)
@@ -357,7 +360,371 @@ public class Worm : Object
     public void dequeue_keypress ()
                 requires (!key_queue.is_empty)
     {
-        direction = key_queue.poll ();
+        direction_set (key_queue.poll ());
+    }
+
+    /* Check whether the worm will be trapped in a dead end. A location
+     * within the dead end and the length of the worm is given. This
+     * prevents worms getting trapped in a spiral, or in a corner sharper
+     * than 90 degrees.  runnumber is a unique number used to update the
+     * deadend board. The principle of the deadend board is that it marks
+     * all squares previously checked, so the exact size of the deadend
+     * can be calculated in O(n) time; to prevent the need to clear it
+     * afterwards, a different number is stored in the board each time
+     * (the number will not have been previously used, so the board will
+     * appear empty). Although in theory deadend_runnumber may wrap round,
+     * after 4 billion steps the entire board is likely to have been
+     * overwritten anyway.
+     */
+    static uint[,] deadend_board = new uint[NibblesGame.WIDTH, NibblesGame.HEIGHT];
+    static uint deadend_runnumber = 0;
+
+    static int ai_deadend (int[,] walls, int numworms, int x, int y, int length_left)
+    {
+        int cdir, cx, cy;
+
+        if (x >= NibblesGame.WIDTH)
+            x = 0;
+        if (x < 0)
+            x = NibblesGame.WIDTH - 1;
+        if (y >= NibblesGame.HEIGHT)
+            y = 0;
+        if (y < 0)
+            y = NibblesGame.HEIGHT - 1;
+
+        if (length_left <= 0)
+            return 0;
+
+        cdir = 5;
+        while (--cdir > 0)
+        {
+            cx = x;
+            cy = y;
+            switch (cdir)
+            {
+                case WormDirection.UP:
+                    cy -= 1;
+                    break;
+                case WormDirection.DOWN:
+                    cy += 1;
+                    break;
+                case WormDirection.LEFT:
+                    cx -= 1;
+                    break;
+                case WormDirection.RIGHT:
+                    cx += 1;
+                    break;
+            }
+
+            if (cx >= NibblesGame.WIDTH)
+                cx = 0;
+            if (cx < 0)
+                cx = NibblesGame.WIDTH - 1;
+            if (cy >= NibblesGame.HEIGHT)
+                cy = 0;
+            if (cy < 0)
+                cy = NibblesGame.HEIGHT - 1;
+
+            if ((walls[cx, cy] <= NibblesGame.EMPTYCHAR
+                || walls[x, y] >= 'z' + numworms)
+                && deadend_board[cx, cy] != deadend_runnumber)
+            {
+                deadend_board[cx, cy] = deadend_runnumber;
+                length_left = ai_deadend (walls, numworms, cx, cy, length_left - 1);
+                if (length_left <= 0)
+                    return 0;
+            }
+        }
+
+        return length_left;
+    }
+
+    /* Check a deadend starting from the next square in this direction,
+     * rather than from this square. Also block off the squares near worm
+     * heads, so that humans can't kill AI players by trapping them
+     * against a wall.  The given length is quartered and squared; this
+     * allows for the situation where the worm has gone round in a square
+     * and is about to get trapped in a spiral. However, it's set to at
+     * least BOARDWIDTH, so that on the levels with long thin paths a worm
+     * won't start down the path if it'll crash at the other end.
+     */
+    private static int ai_deadend_after (int[,] walls, Gee.LinkedList<Worm> worms, int numworms, int x, int 
y, int dir, int length)
+    {
+        int cx, cy, cl, i;
+
+        if (x < 0 || x >= NibblesGame.WIDTH || y < 0 || y >= NibblesGame.HEIGHT)
+            return 0;
+
+        ++deadend_runnumber;
+
+        if (dir > 4)
+            dir = 1;
+        if (dir < 1)
+            dir = 4;
+
+        i = numworms;
+        while (i-- > 0)
+        {
+            cx = worms[i].head ().x;
+            cy = worms[i].head ().y;
+            if (cx != x || cy != y) {
+                if (cx > 0)
+                    deadend_board[cx-1, cy] = deadend_runnumber;
+                if (cy > 0)
+                    deadend_board[cx, cy-1] = deadend_runnumber;
+                if (cx < NibblesGame.WIDTH-1)
+                    deadend_board[cx+1, cy] = deadend_runnumber;
+                if (cy < NibblesGame.HEIGHT-1)
+                    deadend_board[cx, cy+1] = deadend_runnumber;
+            }
+        }
+
+        cx = x;
+        cy = y;
+        switch (dir)
+        {
+            case WormDirection.UP:
+                cy -= 1;
+                break;
+            case WormDirection.DOWN:
+                cy += 1;
+                break;
+            case WormDirection.LEFT:
+                cx -= 1;
+                break;
+            case WormDirection.RIGHT:
+                cx += 1;
+                break;
+        }
+
+        if (cx >= NibblesGame.WIDTH)
+            cx = 0;
+        if (cx < 0)
+            cx = NibblesGame.WIDTH - 1;
+        if (cy >= NibblesGame.HEIGHT)
+            cy = 0;
+        if (cy < 0)
+            cy = NibblesGame.HEIGHT - 1;
+
+        deadend_board[x, y] = deadend_runnumber;
+        deadend_board[cx, cy] = deadend_runnumber;
+
+        cl = (length * length) / 16;
+        if (cl < NibblesGame.WIDTH)
+            cl = NibblesGame.WIDTH;
+        return Worm.ai_deadend (walls, numworms, cx, cy, cl);
+    }
+
+    /* Check to see if another worm's head is too close in front of us;
+     * that is, that it's within 3 in the direction we're going and within
+     * 1 to the side.
+     */
+    private bool ai_too_close (Gee.LinkedList<Worm> worms, int numworms)
+    {
+        int i = numworms;
+        int dx, dy;
+
+        while (i-- > 0)
+        {
+            dx = head ().x - worms[i].head ().x;
+            dy = head ().y - worms[i].head ().y;
+            switch (direction)
+            {
+                case WormDirection.UP:
+                    if (dy > 0 && dy <= 3 && dx >= -1 && dx <= 1)
+                        return true;
+                    break;
+                case WormDirection.DOWN:
+                    if (dy < 0 && dy >= -3 && dx >= -1 && dx <= 1)
+                        return true;
+                    break;
+                case WormDirection.LEFT:
+                    if (dx > 0 && dx <= 3 && dy >= -1 && dy <= 1)
+                        return true;
+                    break;
+                case WormDirection.RIGHT:
+                    if (dx < 0 && dx >= -3 && dy >= -1 && dy <= 1)
+                        return true;
+                    break;
+            }
+        }
+
+        return false;
+    }
+
+    private static bool ai_wander (int[,] walls, int numworms, int x, int y, int dir, int ox, int oy)
+    {
+        if (dir > 4)
+            dir = 1;
+        if (dir < 1)
+            dir = 4;
+
+        switch (dir)
+        {
+            case WormDirection.UP:
+                y -= 1;
+                break;
+            case WormDirection.DOWN:
+                y += 1;
+                break;
+            case WormDirection.LEFT:
+                x -= 1;
+                break;
+            case WormDirection.RIGHT:
+                x += 1;
+                break;
+        }
+
+        if (x >= NibblesGame.WIDTH)
+            x = 0;
+        if (x < 0)
+            x = NibblesGame.WIDTH - 1;
+        if (y >= NibblesGame.HEIGHT)
+            y = 0;
+        if (y < 0)
+            y = NibblesGame.HEIGHT - 1;
+
+        switch (walls[x, y] - 'A')
+        {
+            case BonusType.REGULAR:
+                return true;
+            case BonusType.DOUBLE:
+                return true;
+            case BonusType.LIFE:
+                return true;
+            case BonusType.REVERSE:
+                return true;
+            case BonusType.HALF:
+                return false;
+            default:
+                if (walls[x, y] > NibblesGame.EMPTYCHAR
+                    && walls[x, y] < 'z' + numworms)
+                {
+                        return false;
+                }
+                else
+                {
+                    if (ox == x && oy == y)
+                        return false;
+
+                    return Worm.ai_wander (walls, numworms, x, y, dir, ox, oy);
+                }
+        }
+    }
+
+    /* Determines the direction of the AI worm. */
+    public void ai_move (int[,] walls, int numworms, Gee.LinkedList<Worm> worms)
+    {
+        var opposite = (direction + 1) % 4 + 1;
+
+        var front = Worm.ai_wander (walls, numworms, head ().x, head ().y, direction, head ().x, head ().y);
+        var left = Worm.ai_wander (walls, numworms, head ().x, head ().y, direction - 1, head ().x, head 
().y);
+        var right = Worm.ai_wander (walls, numworms, head ().x, head ().y, direction + 1, head ().x, head 
().y);
+
+        int dir;
+        if (!front)
+        {
+            if (left)
+            {
+                /* Found a bonus to the left */
+                dir = direction - 1;
+                if (dir < 1)
+                    dir = 4;
+
+                direction = (WormDirection) dir;
+            }
+            else if (right)
+            {
+                /* Found a bonus to the right */
+                dir = direction + 1;
+                if (dir > 4)
+                    dir = 1;
+
+                direction = (WormDirection) dir;
+            }
+            else
+            {
+                /* Else move in random direction at random time intervals */
+                if (Random.int_range (0, 30) == 1)
+                {
+                    dir = direction + (Random.boolean () ? 1 : -1);
+                    if (dir != opposite)
+                    {
+                        if (dir > 4)
+                            dir = 1;
+                        if (dir < 1)
+                            dir = 4;
+
+                        direction = (WormDirection) dir;
+                    }
+                }
+            }
+        }
+
+        /* Avoid walls, dead-ends and other worm's heads. This is done using
+         * an evalution function which is CAPACITY for a wall, 4 if another
+         * worm's head is in the tooclose area, 4 if another worm's head
+         * could move to the same location as ours, plus 0 if there's no
+         * dead-end, or the amount that doesn't fit for a deadend. olddir's
+         * score is reduced by 100, to favour it, but only if its score is 0
+         * otherwise; this is so that if we're currently trapped in a dead
+         * end, the worm will move in a space-filling manner in the hope
+         * that the dead end will disappear (e.g. if it's made from the tail
+         * of some worm, as often happens).
+         */
+        var old_dir = direction;
+        var best_yet = NibblesGame.CAPACITY * 2;
+        var best_dir = -1;
+
+        int this_len;
+        for (dir = 1; dir <= 4; dir++)
+        {
+            direction = (WormDirection) dir;
+
+            if (dir == opposite)
+                continue;
+            this_len = 0;
+
+            if (!can_move_to (walls, numworms))
+                this_len += NibblesGame.CAPACITY;
+
+            if (ai_too_close (worms, numworms))
+                this_len += 4;
+
+            this_len += ai_deadend_after (walls, worms, numworms, head ().x, head ().y, dir, length + 
change);
+
+            if (dir == old_dir && this_len <= 0)
+                this_len -= 100;
+
+            /* If the favoured direction isn't appropriate, then choose
+             * another direction at random rather than favouring one in
+             * particular, to stop the worms bunching in the bottom-
+             * right corner of the board.
+             */
+            if (this_len <= 0)
+                this_len -= Random.int_range (0, 100);
+            if (this_len < best_yet)
+            {
+                best_yet = this_len;
+                best_dir = dir;
+            }
+        }
+
+        direction = (WormDirection) best_dir;
+
+        /* Make sure we are at least avoiding walls.
+         * Mostly other snakes should avoid our head.
+         */
+        for (dir = 1; dir <= 4; dir++)
+        {
+            if (dir == opposite)
+                continue;
+
+            if (!can_move_to (walls, numworms))
+                direction = (WormDirection) dir;
+            else
+                continue;
+        }
     }
 }
 
@@ -369,10 +736,11 @@ public struct Position
 
 public enum WormDirection
 {
-    UP,
+    NONE,
+    RIGHT,
     DOWN,
     LEFT,
-    RIGHT
+    UP
 }
 
 public struct WormProperties


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]