[gnome-games/gnibbles-clutter] Added a bunch of code from worm.c to worm-clutter.c related to AI

[Guillaume Béland <guillaubel src gnome org>]

commit c9dcede0f36f5e05b493e9623587d4ce7919fd18
Author: Guillaume Beland <guillaume beland gmail com>
Date:   Wed Jun 3 19:57:02 2009 -0400

    Added a bunch of code from worm.c to worm-clutter.c related to AI
    
    Most of this code shouldn't change, the rest will and has started to be adapted
    for the new code.
---
 gnibbles/board.h        |   10 +-
 gnibbles/main.c         |   10 +-
 gnibbles/worm-clutter.c |  525 ++++++++++++++++++++++++++++++++++++++++++++++-
 gnibbles/worm-clutter.h |    9 +-
 4 files changed, 544 insertions(+), 10 deletions(-)

diff --git a/gnibbles/board.h b/gnibbles/board.h
index 6851b91..defc148 100644
--- a/gnibbles/board.h
+++ b/gnibbles/board.h
@@ -28,11 +28,11 @@
 #include "level.h"
 
 typedef struct {
-        gint width;
-        gint height;
-        GtkWidget *clutter_widget;
-        ClutterActor *surface;
-        ClutterActor *level;
+  gint width;
+  gint height;
+  GtkWidget *clutter_widget;
+  ClutterActor *surface;
+  ClutterActor *level;
 } GnibblesBoard;
 
 GnibblesBoard* gnibbles_board_new (gint t_w, gint t_h);
diff --git a/gnibbles/main.c b/gnibbles/main.c
index be9fc12..cd04265 100644
--- a/gnibbles/main.c
+++ b/gnibbles/main.c
@@ -86,6 +86,8 @@ extern GdkPixbuf *logo_pixmap;
 
 GnibblesProperties *properties;
 
+GnibblesLevel *level;
+
 GnibblesScoreboard *scoreboard;
 
 GdkPixbuf *wall_pixmaps[11] = { NULL, NULL, NULL, NULL, NULL,
@@ -1329,11 +1331,13 @@ main (int argc, char **argv)
 
   int i;
 
-  gnibbles_board_load_level (board, gnibbles_level_new (1));
+  level = gnibbles_level_new (1);
+
+  gnibbles_board_load_level (board, level);
  
   for (i = 0; i < properties->numworms; i++) {
-   clutter_container_add_actor (CLUTTER_CONTAINER (stage), cworms[i]->actors);
-   clutter_actor_raise_top (cworms[i]->actors);
+    clutter_container_add_actor (CLUTTER_CONTAINER (stage), cworms[i]->actors);
+    clutter_actor_raise_top (cworms[i]->actors);
   }
 
   //render_logo_clutter (board);
diff --git a/gnibbles/worm-clutter.c b/gnibbles/worm-clutter.c
index 4614793..32224a5 100644
--- a/gnibbles/worm-clutter.c
+++ b/gnibbles/worm-clutter.c
@@ -21,7 +21,7 @@
  */
 #include <config.h>
 #include <glib/gprintf.h>
-
+#include <ctype.h>
 #include <glib/gi18n.h>
 #include <gdk/gdk.h>
 #include <stdlib.h>
@@ -29,11 +29,21 @@
 #include <clutter-gtk/clutter-gtk.h>
 #include "main.h"
 #include "gnibbles.h"
+#include "level.h"
+#include "boni.h"
+#include "bonus.h"
+#include "warpmanager.h"
 #include "properties.h"
+
 #include "worm-clutter.h"
 
 extern GnibblesProperties *properties;
 extern GdkPixbuf *worm_pixmaps[];
+extern GnibblesLevel *level;
+extern GnibblesBoni *boni;
+extern GnibblesWarpManager *warpmanager;
+extern GnibblesCWorm *cworms[NUMWORMS];
+
 
 GnibblesCWorm*
 gnibbles_cworm_new (guint number, guint t_xhead,
@@ -229,3 +239,516 @@ gnibbles_cworm_resize (GnibblesCWorm *worm, gint newtile)
   }
 
 }
+
+
+
+void
+gnibbles_cworm_draw_head (GnibblesCWorm * worm)
+{
+  //worm->keypress = 0;
+
+  switch (worm->direction) {
+  case WORMUP:
+    //worm->xoff[worm->start] = 0;
+    //worm->yoff[worm->start] = 1;
+    worm->yhead--;
+    break;
+  case WORMDOWN:
+    //worm->xoff[worm->start] = 0;
+    //worm->yoff[worm->start] = -1;
+    worm->yhead++;
+    break;
+  case WORMLEFT:
+    //worm->xoff[worm->start] = 1;
+    //worm->yoff[worm->start] = 0;
+    worm->xhead--;
+    break;
+  case WORMRIGHT:
+    //worm->xoff[worm->start] = -1;
+    //worm->yoff[worm->start] = 0;
+    worm->xhead++;
+    break;
+  }
+
+  if (worm->xhead == BOARDWIDTH) {
+    worm->xhead = 0;
+    //worm->xoff[worm->start] += BOARDWIDTH;
+  }
+  if (worm->xhead < 0) {
+    worm->xhead = BOARDWIDTH - 1;
+    //worm->xoff[worm->start] -= BOARDWIDTH;
+  }
+  if (worm->yhead == BOARDHEIGHT) {
+    worm->yhead = 0;
+    //worm->yoff[worm->start] += BOARDHEIGHT;
+  }
+  if (worm->yhead < 0) {
+    worm->yhead = BOARDHEIGHT - 1;
+    //worm->yoff[worm->start] -= BOARDHEIGHT;
+  }
+
+  if ((level->walls[worm->xhead][worm->yhead] != EMPTYCHAR) &&
+      (level->walls[worm->xhead][worm->yhead] != WARPLETTER)) {
+    //gnibbles_cworm_grok_bonus (worm);
+    if ((level->walls[worm->xhead][worm->yhead] == BONUSREGULAR + 'A') &&
+	      !gnibbles_boni_fake (boni, worm->xhead, worm->yhead)) {
+      gnibbles_boni_remove_bonus_final (boni, worm->xhead, worm->yhead);
+      
+      if (boni->numleft != 0)
+	      gnibbles_add_bonus (1);
+
+    } else
+      gnibbles_boni_remove_bonus_final (boni, worm->xhead, worm->yhead);
+  }
+
+  if (level->walls[worm->xhead][worm->yhead] == WARPLETTER) {
+    //gnibbles_warpmanager_worm_change_pos (warpmanager, worm);
+    //games_sound_play ("teleport");
+  }
+
+  worm->start++;
+
+  if (worm->start == CAPACITY)
+    worm->start = 0;
+
+  level->walls[worm->xhead][worm->yhead] = WORMCHAR + worm->number;
+/*
+  gnibbles_draw_pixmap (properties->wormprops[worm->number]->color,
+			worm->xhead, worm->yhead);
+
+  if (key_queue[worm->number] && !g_queue_is_empty (key_queue[worm->number])) {
+    gnibbles_cworm_dequeue_keypress (worm);
+  }
+*/
+}
+
+gint
+gnibbles_cworm_can_move_to (GnibblesCWorm * worm, gint x, gint y)
+{
+  if (worm->xhead == x)
+    return worm->yhead - 1 == y || worm->yhead + 1 == y;
+  if (worm->yhead == y)
+    return worm->xhead - 1 == x || worm->xhead + 1 == x;
+  return FALSE;
+}
+
+void
+gnibbles_cworm_position_move_head (GnibblesCWorm * worm, gint *x, gint *y)
+{
+  *x = worm->xhead;
+  *y = worm->yhead;
+
+  switch (worm->direction) {
+  case WORMUP:
+    *y = worm->yhead - 1;
+    break;
+  case WORMDOWN:
+    *y = worm->yhead + 1;
+    break;
+  case WORMLEFT:
+    *x = worm->xhead - 1;
+    break;
+  case WORMRIGHT:
+    *x = worm->xhead + 1;
+    break;
+  }
+
+  if (*x == BOARDWIDTH) {
+    *x = 0;
+  }
+  if (*x < 0) {
+    *x = BOARDWIDTH - 1;
+  }
+  if (*y == BOARDHEIGHT) {
+    *y = 0;
+  }
+  if (*y < 0) {
+    *y = BOARDHEIGHT - 1;
+  }
+}
+
+gint
+gnibbles_cworm_test_move_head (GnibblesCWorm * worm)
+{
+  int x, y;
+
+  gnibbles_cworm_position_move_head(worm, &x, &y);
+
+  if (level->walls[x][y] > EMPTYCHAR && level->walls[x][y] < 'z' + properties->numworms)
+    return (FALSE);
+
+  return TRUE;
+}
+
+gint
+gnibbles_cworm_is_move_safe (GnibblesCWorm * worm)
+{
+  int x, y, i;
+
+  gnibbles_cworm_position_move_head(worm, &x, &y);
+
+  for (i = 0; i < properties->numworms; i++) {
+    if (i != worm->number) {
+      if (gnibbles_cworm_can_move_to (cworms[i], x, y))
+        return (FALSE);
+    }
+  }
+
+  return TRUE;
+}
+
+void
+gnibbles_cworm_move_tail (GnibblesCWorm * worm)
+{
+  if (worm->change <= 0) {
+    //gnibbles_draw_pixmap (BLANKPIXMAP, worm->xtail, worm->ytail);
+    //worm->xtail -= worm->xoff[worm->stop];
+    //worm->ytail -= worm->yoff[worm->stop];
+    worm->stop++;
+    if (worm->stop == CAPACITY)
+      worm->stop = 0;
+    if (worm->change) {
+      //gnibbles_draw_pixmap (BLANKPIXMAP, worm->xtail, worm->ytail);
+      level->walls[worm->xtail][worm->ytail] = EMPTYCHAR;
+      //worm->xtail -= worm->xoff[worm->stop];
+      //worm->ytail -= worm->yoff[worm->stop];
+      worm->stop++;
+      if (worm->stop == CAPACITY)
+	      worm->stop = 0;
+      worm->change++;
+      worm->length--;
+    }
+  } else {
+    worm->change--;
+    worm->length++;
+  }
+}
+
+/* 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 guint deadendboard[BOARDWIDTH][BOARDHEIGHT] = {{0}};
+static guint deadend_runnumber = 0;
+static gint
+gnibbles_cworm_ai_deadend (gint x, gint y, gint lengthleft)
+{
+  gint cdir, cx, cy;
+
+  if (x >= BOARDWIDTH)
+    x = 0;
+  if (x < 0)
+    x = BOARDWIDTH - 1;
+  if (y >= BOARDHEIGHT)
+    y = 0;
+  if (y < 0)
+    y = BOARDHEIGHT - 1;
+
+  if (! lengthleft)
+    return 0;
+
+  cdir = 5;
+  while (--cdir) {
+    cx = x;
+    cy = y;
+    switch (cdir) {
+    case WORMUP:
+      cy -= 1;
+      break;
+    case WORMDOWN:
+      cy += 1;
+      break;
+    case WORMLEFT:
+      cx -= 1;
+      break;
+    case WORMRIGHT:
+      cx += 1;
+      break;
+    }
+
+    if (cx >= BOARDWIDTH)
+      cx = 0;
+    if (cx < 0)
+      cx = BOARDWIDTH - 1;
+    if (cy >= BOARDHEIGHT)
+      cy = 0;
+    if (cy < 0)
+      cy = BOARDHEIGHT - 1;
+
+    if ((level->walls[cx][cy] <= EMPTYCHAR
+	 || level->walls[x][y] >= 'z' + properties->numworms)
+	&& deadendboard[cx][cy] != deadend_runnumber) {
+      deadendboard[cx][cy] = deadend_runnumber;
+      lengthleft = gnibbles_cworm_ai_deadend(cx, cy, lengthleft - 1);
+      if (!lengthleft)
+	return 0;
+    }
+  }
+  return lengthleft;
+}
+
+/* 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. */
+static gint
+gnibbles_cworm_ai_deadend_after (gint x, gint y, gint dir, gint length)
+{
+  gint cx, cy, cl, i;
+
+  if (x < 0 || x >= BOARDWIDTH || y < 0 || y >= BOARDHEIGHT) {
+    return 0;
+  }
+
+  ++deadend_runnumber;
+
+  if (dir > 4)
+    dir = 1;
+  if (dir < 1)
+    dir = 4;
+
+  i = properties->numworms;
+  while(i--) {
+    cx = cworms[i]->xhead;
+    cy = cworms[i]->yhead;
+    if(cx != x || cy != y) {
+      if(cx > 0) deadendboard[cx-1][cy] = deadend_runnumber;
+      if(cy > 0) deadendboard[cx][cy-1] = deadend_runnumber;
+      if(cx < BOARDWIDTH-1) deadendboard[cx+1][cy] = deadend_runnumber;
+      if(cy < BOARDHEIGHT-1) deadendboard[cx][cy+1] = deadend_runnumber;
+    }
+  }
+
+  cx = x;
+  cy = y;
+  switch (dir) {
+  case WORMUP:
+    cy -= 1;
+    break;
+  case WORMDOWN:
+    cy += 1;
+    break;
+  case WORMLEFT:
+    cx -= 1;
+    break;
+  case WORMRIGHT:
+    cx += 1;
+    break;
+  }
+
+  if (cx >= BOARDWIDTH)
+    cx = 0;
+  if (cx < 0)
+    cx = BOARDWIDTH - 1;
+  if (cy >= BOARDHEIGHT)
+    cy = 0;
+  if (cy < 0)
+    cy = BOARDHEIGHT - 1;
+
+  deadendboard[x][y] = deadend_runnumber;
+  deadendboard[cx][cy] = deadend_runnumber;
+
+  cl = (length * length) / 16;
+  if (cl < BOARDWIDTH)
+    cl = BOARDWIDTH;
+  return gnibbles_cworm_ai_deadend (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. */
+static gint
+gnibbles_cworm_ai_tooclose (GnibblesCWorm * worm)
+{
+  gint i = properties->numworms;
+  gint dx, dy;
+  while (i--) {
+    dx = worm->xhead - cworms[i]->xhead;
+    dy = worm->yhead - cworms[i]->yhead;
+    switch (worm->direction)
+    {
+    case WORMUP:
+      if (dy > 0 && dy <= 3 && dx >= -1 && dx <= 1)
+	return 1;
+      break;
+    case WORMDOWN:
+      if (dy < 0 && dy >= -3 && dx >= -1 && dx <= 1)
+	return 1;
+      break;
+    case WORMLEFT:
+      if (dx > 0 && dx <= 3 && dy >= -1 && dy <= 1)
+	return 1;
+      break;
+    case WORMRIGHT:
+      if (dx < 0 && dx >= -3 && dy >= -1 && dy <= 1)
+	return 1;
+      break;
+    }
+  }
+  return 0;
+}
+
+static gint
+gnibbles_cworm_ai_wander (gint x, gint y, gint dir, gint ox, gint oy)
+{
+  if (dir > 4)
+    dir = 1;
+  if (dir < 1)
+    dir = 4;
+
+  switch (dir) {
+  case WORMUP:
+    y -= 1;
+    break;
+  case WORMDOWN:
+    y += 1;
+    break;
+  case WORMLEFT:
+    x -= 1;
+    break;
+  case WORMRIGHT:
+    x += 1;
+    break;
+  }
+
+  if (x >= BOARDWIDTH)
+    x = 0;
+  if (x < 0)
+    x = BOARDWIDTH - 1;
+  if (y >= BOARDHEIGHT)
+    y = 0;
+  if (y < 0)
+    y = BOARDHEIGHT - 1;
+
+  switch (level->walls[x][y] - 'A') {
+  case BONUSREGULAR:
+  case BONUSDOUBLE:
+  case BONUSLIFE:
+  case BONUSREVERSE:
+    return 1;
+    break;
+  case BONUSHALF:
+    return 0;
+    break;
+  default:
+    if (level->walls[x][y] > EMPTYCHAR && level->walls[x][y] < 'z' + properties->numworms) {
+      return 0;
+    } else {
+      if (ox == x && oy == y)
+	return 0;
+      return gnibbles_cworm_ai_wander (x, y, dir, ox, oy);
+    }
+    break;
+  }
+}
+
+/* Determines the direction of the AI worm. */
+void
+gnibbles_cworm_ai_move (GnibblesCWorm * worm)
+{
+  int opposite, dir, left, right, front;
+  gint bestyet, bestdir, thislen, olddir;
+
+  opposite = (worm->direction + 1) % 4 + 1;
+
+  front = gnibbles_cworm_ai_wander
+    (worm->xhead, worm->yhead, worm->direction, worm->xhead, worm->yhead);
+  left = gnibbles_cworm_ai_wander
+    (worm->xhead, worm->yhead, worm->direction - 1, worm->xhead, worm->yhead);
+  right = gnibbles_cworm_ai_wander
+    (worm->xhead, worm->yhead, worm->direction + 1, worm->xhead, worm->yhead);
+
+  if (!front) {
+    if (left) {
+      // Found a bonus to the left
+      dir = worm->direction - 1;
+      if (dir < 1)
+        dir = 4;
+      worm->direction = dir;
+    } else if (right) {
+      // Found a bonus to the right
+      dir = worm->direction + 1;
+      if (dir > 4)
+        dir = 1;
+      worm->direction = dir;
+    } else {
+      // Else move in random direction at random time intervals
+      if (rand () % 30 == 1) {
+        dir = worm->direction + (rand() % 2 ? 1 : -1);
+        if (dir != opposite) {
+          if (dir > 4)
+            dir = 1;
+          if (dir < 1)
+            dir = 4;
+          worm->direction = 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). */
+  olddir = worm->direction;
+  bestyet = CAPACITY*2;
+  bestdir = -1;
+  for (dir = 1; dir <= 4; dir++) {
+    worm->direction = dir;
+    if (dir == opposite) continue;
+    thislen = 0;
+    if(!gnibbles_cworm_test_move_head (worm))
+      thislen += CAPACITY;
+    if(gnibbles_cworm_ai_tooclose (worm))
+      thislen += 4;
+    if(!gnibbles_cworm_is_move_safe (worm))
+      thislen += 4;
+    thislen += gnibbles_cworm_ai_deadend_after
+      (worm->xhead, worm->yhead, dir, worm->length + worm->change);
+    if (dir == olddir && !thislen)
+      thislen -= 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 (thislen <= 0)
+      thislen -= random() % 100;
+    if (thislen < bestyet)
+    {
+      bestyet = thislen;
+      bestdir = dir;
+    }
+  }
+  if (bestdir == -1) /* this should never happen, but just in case... */
+    bestdir = olddir;
+  worm->direction = bestdir;
+
+  /* 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 (!gnibbles_cworm_test_move_head (worm)) {
+      worm->direction = dir;
+    } else {
+      continue;
+    }
+  }
+}
diff --git a/gnibbles/worm-clutter.h b/gnibbles/worm-clutter.h
index 1cea665..3b887c9 100644
--- a/gnibbles/worm-clutter.h
+++ b/gnibbles/worm-clutter.h
@@ -43,6 +43,7 @@ typedef struct {
   GList *list;
   gint xstart, ystart;
   guint xhead, yhead;
+  guint xtail, ytail;
   gint direction;
   gint direction_start;
   gint length;
@@ -50,6 +51,9 @@ typedef struct {
   guint score;
   guint number;
   gboolean inverse;
+  gint start;
+  gint stop;
+  gint change;
 } GnibblesCWorm;
 
 typedef struct {
@@ -72,9 +76,12 @@ gint gnibbles_cworm_lose_life (GnibblesCWorm * worm);
 void gnibbles_cworm_resize (GnibblesCWorm *worm, gint newtile);
 
 gint gnibbles_cworm_handle_keypress (GnibblesCWorm * worm, guint keyval);
+void gnibbles_cworm_draw_head (GnibblesCWorm * worm);
 gint gnibbles_cworm_can_move_to (GnibblesCWorm * worm, gint x, gint y);
+void gnibbles_cworm_position_move_head (GnibblesCWorm * worm, gint *x, gint *y);
+gint gnibbles_cworm_test_move_head (GnibblesCWorm * worm);
 gint gnibbles_cworm_is_move_safe (GnibblesCWorm * worm);
-void gnibbles_cworm_reset (GnibblesCWorm * worm);
+void gnibbles_cworm_move_tail (GnibblesCWorm * worm);
 void gnibbles_cworm_ai_move (GnibblesCWorm * worm);
 
 #endif