worm.vala 23.2 KB
Newer Older
Iulian Radu's avatar
Iulian Radu committed
1 2
/* -*- Mode: vala; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * Gnome Nibbles: Gnome Worm Game
3
 * Copyright (C) 2015 Iulian-Gabriel Radu <iulian.radu67@gmail.com>
Iulian Radu's avatar
Iulian Radu committed
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

Michael Catanzaro's avatar
Michael Catanzaro committed
19
// This is a fairly literal translation of the GPLv2+ original by
20 21
// Sean MacIsaac, Ian Peters, Guillaume Béland.

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
public enum WormDirection
{
    NONE,
    RIGHT,
    DOWN,
    LEFT,
    UP
}

public struct Position
{
    int x;
    int y;
}

public struct WormProperties
{
    int color;
    uint up;
    uint down;
    uint left;
    uint right;
}

Iulian Radu's avatar
Iulian Radu committed
46 47 48
public class Worm : Object
{
    public const int STARTING_LENGTH = 5;
49 50 51
    public const int STARTING_LIVES = 6;
    public const int MAX_LIVES = 12;

52
    public const int GROW_FACTOR = 4;
Iulian Radu's avatar
Iulian Radu committed
53 54 55 56 57

    public Position starting_position { get; private set; }

    public int id { get; private set; }

Iulian Radu's avatar
Iulian Radu committed
58
    public bool is_human;
Iulian Radu's avatar
Iulian Radu committed
59
    public bool keypress = false;
Iulian Radu's avatar
Iulian Radu committed
60
    public bool is_stopped = false;
61 62
    public bool is_materialized { get; private set; default = true; }
    private int rounds_dematerialized;
Iulian Radu's avatar
Iulian Radu committed
63

64
    public int lives { get; set; }
65
    public int change;
66
    public int score { get; set; }
67

Iulian Radu's avatar
Iulian Radu committed
68 69 70 71 72 73
    public int length
    {
        get { return list.size; }
        set {}
    }

74 75 76 77 78 79 80
    public Position head
    {
        get
        {
            Position head = list.first ();
            return head;
        }
81 82 83 84
        private set
        {
            list.set (0, value);
        }
85 86
    }

Iulian Radu's avatar
Iulian Radu committed
87
    public WormDirection direction;
Iulian Radu's avatar
Iulian Radu committed
88 89 90 91 92 93 94 95

    public WormDirection starting_direction;

    private Gee.ArrayQueue<WormDirection> key_queue;

    public Gee.LinkedList<Position?> list { get; private set; }

    public signal void added ();
96
    public signal void finish_added ();
Iulian Radu's avatar
Iulian Radu committed
97 98 99
    public signal void moved ();
    public signal void rescaled (int tile_size);
    public signal void died ();
Iulian Radu's avatar
Iulian Radu committed
100
    public signal void tail_reduced (int erase_size);
101
    public signal void reversed ();
Iulian Radu's avatar
Iulian Radu committed
102

103
    public signal void bonus_found ();
104
    public signal void warp_found ();
105

106
    public Worm (int id)
Iulian Radu's avatar
Iulian Radu committed
107 108 109
    {
        this.id = id;
        lives = STARTING_LIVES;
110
        score = 0;
111
        change = 0;
Iulian Radu's avatar
Iulian Radu committed
112 113 114 115
        list = new Gee.LinkedList<Position?> ();
        key_queue = new Gee.ArrayQueue<WormDirection> ();
    }

116
    public void set_start (int xhead, int yhead, WormDirection direction)
Iulian Radu's avatar
Iulian Radu committed
117
    {
118 119
        list.clear ();

Iulian Radu's avatar
Iulian Radu committed
120 121 122 123 124 125 126
        starting_position = Position () {
            x = xhead,
            y = yhead
        };

        list.add (starting_position);

127
        starting_direction = direction;
Iulian Radu's avatar
Iulian Radu committed
128
        this.direction = starting_direction;
129 130
        change = 0;
        key_queue.clear ();
Iulian Radu's avatar
Iulian Radu committed
131 132
    }

Iulian Radu's avatar
Iulian Radu committed
133
    public void move (int[,] board)
Iulian Radu's avatar
Iulian Radu committed
134
    {
Iulian Radu's avatar
Iulian Radu committed
135
        if (is_human)
Iulian Radu's avatar
Iulian Radu committed
136 137
            keypress = false;

138
        var position = head;
Iulian Radu's avatar
Iulian Radu committed
139 140 141
        switch (direction)
        {
            case WormDirection.UP:
142
                position.y = --head.y;
Iulian Radu's avatar
Iulian Radu committed
143 144 145 146
                if (position.y < 0)
                    position.y = NibblesGame.HEIGHT - 1;
                break;
            case WormDirection.DOWN:
147
                position.y = ++head.y;
Iulian Radu's avatar
Iulian Radu committed
148 149 150 151
                if (position.y >= NibblesGame.HEIGHT)
                    position.y = 0;
                break;
            case WormDirection.LEFT:
152
                position.x = --head.x;
Iulian Radu's avatar
Iulian Radu committed
153 154 155 156
                if (position.x < 0)
                    position.x = NibblesGame.WIDTH - 1;
                break;
            case WormDirection.RIGHT:
157
                position.x = ++head.x;
Iulian Radu's avatar
Iulian Radu committed
158 159 160 161 162 163 164 165 166 167
                if (position.x >= NibblesGame.WIDTH)
                    position.x = 0;
                break;
            default:
                break;
        }

        /* Add a new body piece */
        list.offer_head (position);

Iulian Radu's avatar
Iulian Radu committed
168
        if (board[head.x, head.y] == NibblesGame.WARPCHAR)
169 170
            warp_found ();

171 172 173 174 175 176
        if (change > 0)
        {
            change--;
            added ();
        }
        else
Iulian Radu's avatar
Iulian Radu committed
177
        {
Iulian Radu's avatar
Iulian Radu committed
178
            board[list.last ().x, list.last ().y] = NibblesGame.EMPTYCHAR;
Iulian Radu's avatar
Iulian Radu committed
179 180 181 182
            list.poll_tail ();
            moved ();
        }

183
        /* Check for bonus before changing tile */
Iulian Radu's avatar
Iulian Radu committed
184
        if (board[head.x, head.y] != NibblesGame.EMPTYCHAR)
185 186
            bonus_found ();

187 188 189 190 191
        /* Mark the tile as occupied by the worm's body, if it is materialized */
        if (is_materialized)
            board[head.x, head.y] = NibblesGame.WORMCHAR + id;
        else
            rounds_dematerialized -= 1;
192

Iulian Radu's avatar
Iulian Radu committed
193 194
        if (!key_queue.is_empty)
            dequeue_keypress ();
195 196 197

        if (rounds_dematerialized == 1)
            materialize (board);
Iulian Radu's avatar
Iulian Radu committed
198 199
    }

Iulian Radu's avatar
Iulian Radu committed
200
    public void reduce_tail (int[,] board, int erase_size)
Iulian Radu's avatar
Iulian Radu committed
201 202 203 204 205
    {
        if (erase_size > 0)
        {
            for (int i = 0; i < erase_size; i++)
            {
Iulian Radu's avatar
Iulian Radu committed
206
                board[list.last ().x, list.last ().y] = NibblesGame.EMPTYCHAR;
Iulian Radu's avatar
Iulian Radu committed
207 208 209 210 211 212
                list.poll_tail ();
            }
            tail_reduced (erase_size);
        }
    }

Iulian Radu's avatar
Iulian Radu committed
213
    public void reverse (int[,] board)
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
    {
        var reversed_list = new Gee.LinkedList<Position?> ();
        foreach (var pos in list)
            reversed_list.offer_head (pos);

        reversed ();
        list = reversed_list;

        /* Set new direction as the opposite direction of the last two tail pieces */
        if (list[0].y == list[1].y)
            direction = (list[0].x > list[1].x) ? WormDirection.RIGHT : WormDirection.LEFT;
        else
            direction = (list[0].y > list[1].y) ? WormDirection.DOWN : WormDirection.UP;
    }

229 230 231 232 233
    public void warp (Warp warp)
    {
        head = Position () { x = warp.wx, y = warp.wy };
    }

Iulian Radu's avatar
Iulian Radu committed
234
    public bool can_move_to (int[,] board, int numworms)
Iulian Radu's avatar
Iulian Radu committed
235
    {
Iulian Radu's avatar
Iulian Radu committed
236
        var position = position_move ();
237
        int next_position = board[position.x, position.y];
Iulian Radu's avatar
Iulian Radu committed
238

239 240
        if (next_position > NibblesGame.EMPTYCHAR
            && next_position < NibblesGame.WORMCHAR)
Iulian Radu's avatar
Iulian Radu committed
241
            return false;
242 243 244 245

        if (next_position >= NibblesGame.WORMCHAR
            && next_position < NibblesGame.WORMCHAR + numworms)
            return !is_materialized;
Iulian Radu's avatar
Iulian Radu committed
246 247 248 249

        return true;
    }

Iulian Radu's avatar
Iulian Radu committed
250
    public bool will_collide_with_head (Worm other_worm)
Iulian Radu's avatar
Iulian Radu committed
251
    {
252 253 254
        if (!is_materialized || !other_worm.is_materialized)
            return false;

Iulian Radu's avatar
Iulian Radu committed
255 256 257 258 259
        var worm_pos = position_move ();
        var other_worm_pos = other_worm.position_move ();

        if (worm_pos == other_worm_pos)
            return true;
Iulian Radu's avatar
Iulian Radu committed
260 261 262 263

        return false;
    }

Iulian Radu's avatar
Iulian Radu committed
264
    public void spawn (int[,] board)
Iulian Radu's avatar
Iulian Radu committed
265
    {
Iulian Radu's avatar
Iulian Radu committed
266
        change = STARTING_LENGTH - 1;
Iulian Radu's avatar
Iulian Radu committed
267
        for (int i = 0; i < STARTING_LENGTH; i++)
Iulian Radu's avatar
Iulian Radu committed
268
            move (board);
Iulian Radu's avatar
Iulian Radu committed
269 270
    }

271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297
    private void materialize (int [,] board)
    {
        foreach (var pos in list)
        {
            if (board[pos.x, pos.y] != NibblesGame.EMPTYCHAR)
            {
                rounds_dematerialized += 1;
                return;
            }
        }
        foreach (var pos in list)
            board[pos.x, pos.y] = NibblesGame.WORMCHAR + id;
        is_materialized = true;
        rounds_dematerialized = 0;
    }

    public void dematerialize (int [,] board, int rounds)
    {
        rounds_dematerialized = rounds;
        is_materialized = false;
        foreach (var pos in list)
        {
            if (board[pos.x, pos.y] == NibblesGame.WORMCHAR + id)
                board[pos.x, pos.y] = NibblesGame.EMPTYCHAR;
        }
    }

298 299 300 301 302 303 304 305 306
    public void add_life ()
    {
        if (lives > MAX_LIVES)
            return;

        lives++;
    }

    private void lose_life ()
Iulian Radu's avatar
Iulian Radu committed
307 308 309 310
    {
        lives--;
    }

Iulian Radu's avatar
Iulian Radu committed
311
    public void reset (int[,] board)
Iulian Radu's avatar
Iulian Radu committed
312
    {
Iulian Radu's avatar
Iulian Radu committed
313
        is_stopped = true;
314 315 316
        is_materialized = false;
        rounds_dematerialized = 0;

317 318
        key_queue.clear ();

Iulian Radu's avatar
Iulian Radu committed
319 320 321 322
        lose_life ();

        died ();
        foreach (var pos in list)
Iulian Radu's avatar
Iulian Radu committed
323
            board[pos.x, pos.y] = NibblesGame.EMPTYCHAR;
Iulian Radu's avatar
Iulian Radu committed
324 325 326

        list.clear ();
        list.add (starting_position);
327 328
        added ();

Iulian Radu's avatar
Iulian Radu committed
329
        direction = starting_direction;
330
        change = 0;
Iulian Radu's avatar
Iulian Radu committed
331
        spawn (board);
Iulian Radu's avatar
Iulian Radu committed
332

333
        finish_added ();
Iulian Radu's avatar
Iulian Radu committed
334 335 336 337
    }

    private Position position_move ()
    {
338
        Position position = head;
Iulian Radu's avatar
Iulian Radu committed
339 340 341 342

        switch (direction)
        {
            case WormDirection.UP:
343
                position.y = --head.y;
Iulian Radu's avatar
Iulian Radu committed
344 345 346 347
                if (position.y < 0)
                    position.y = NibblesGame.HEIGHT - 1;
                break;
            case WormDirection.DOWN:
348
                position.y = ++head.y;
Iulian Radu's avatar
Iulian Radu committed
349 350 351 352
                if (position.y >= NibblesGame.HEIGHT)
                    position.y = 0;
                break;
            case WormDirection.LEFT:
353
                position.x = --head.x;
Iulian Radu's avatar
Iulian Radu committed
354 355 356 357
                if (position.x < 0)
                    position.x = NibblesGame.WIDTH - 1;
                break;
            case WormDirection.RIGHT:
358
                position.x = ++head.x;
Iulian Radu's avatar
Iulian Radu committed
359 360 361 362 363 364 365 366 367 368
                if (position.x >= NibblesGame.WIDTH)
                    position.x = 0;
                break;
            default:
                break;
        }

        return position;
    }

Iulian Radu's avatar
Iulian Radu committed
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
    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;
    }

389 390 391 392 393 394 395 396 397 398 399 400 401 402 403
    /*\
    * * Keys and key presses
    \*/
    private uint upper_key (uint keyval)
    {
        if (keyval > 255)
            return keyval;
        return ((char) keyval).toupper ();
    }

    public void handle_direction (WormDirection dir)
    {
        direction_set (dir);
    }

Iulian Radu's avatar
Iulian Radu committed
404
    public bool handle_keypress (uint keyval, Gee.HashMap<Worm, WormProperties?> worm_props)
Iulian Radu's avatar
Iulian Radu committed
405
    {
406 407 408
        if (lives <= 0 || is_stopped)
            return false;

Iulian Radu's avatar
Iulian Radu committed
409 410 411
        WormProperties properties;
        uint propsUp, propsDown, propsLeft, propsRight, keyvalUpper;

Iulian Radu's avatar
Iulian Radu committed
412
        properties = worm_props.get (this);
Iulian Radu's avatar
Iulian Radu committed
413 414 415 416 417 418 419 420 421 422 423
        propsUp = upper_key (properties.up);
        propsLeft = upper_key (properties.left);
        propsDown = upper_key (properties.down);
        propsRight = upper_key (properties.right);
        keyvalUpper = upper_key (keyval);

        if ((keyvalUpper == propsUp) && (direction != WormDirection.DOWN))
        {
            handle_direction (WormDirection.UP);
            return true;
        }
Iulian Radu's avatar
Iulian Radu committed
424 425
        if ((keyvalUpper == propsDown) && (direction != WormDirection.UP))
        {
Iulian Radu's avatar
Iulian Radu committed
426 427 428
            handle_direction (WormDirection.DOWN);
            return true;
        }
Iulian Radu's avatar
Iulian Radu committed
429 430
        if ((keyvalUpper == propsRight) && (direction != WormDirection.LEFT))
        {
Iulian Radu's avatar
Iulian Radu committed
431 432 433
            handle_direction (WormDirection.RIGHT);
            return true;
        }
Iulian Radu's avatar
Iulian Radu committed
434 435
        if ((keyvalUpper == propsLeft) && (direction != WormDirection.RIGHT))
        {
Iulian Radu's avatar
Iulian Radu committed
436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454
            handle_direction (WormDirection.LEFT);
            return true;
        }

        return false;
    }

    public void queue_keypress (WormDirection dir)
    {
        /* Ignore duplicates in normal movement mode. This resolves the key
         * repeat issue
         */
        if (!key_queue.is_empty && dir == key_queue.peek ())
            return;

        key_queue.add (dir);
    }

    public void dequeue_keypress ()
Iulian Radu's avatar
Iulian Radu committed
455
                requires (!key_queue.is_empty)
Iulian Radu's avatar
Iulian Radu committed
456
    {
Iulian Radu's avatar
Iulian Radu committed
457 458 459
        direction_set (key_queue.poll ());
    }

460 461 462 463
    /*\
    * * AI
    \*/

Iulian Radu's avatar
Iulian Radu committed
464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479
    /* 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;

Iulian Radu's avatar
Iulian Radu committed
480
    static int ai_deadend (int[,] board, int numworms, int x, int y, int length_left)
Iulian Radu's avatar
Iulian Radu committed
481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525
    {
        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;

Iulian Radu's avatar
Iulian Radu committed
526 527
            if ((board[cx, cy] <= NibblesGame.EMPTYCHAR
                || board[x, y] >= 'z' + numworms)
Iulian Radu's avatar
Iulian Radu committed
528 529 530
                && deadend_board[cx, cy] != deadend_runnumber)
            {
                deadend_board[cx, cy] = deadend_runnumber;
Iulian Radu's avatar
Iulian Radu committed
531
                length_left = ai_deadend (board, numworms, cx, cy, length_left - 1);
Iulian Radu's avatar
Iulian Radu committed
532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548
                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.
     */
Iulian Radu's avatar
Iulian Radu committed
549
    private static int ai_deadend_after (int[,] board, Gee.LinkedList<Worm> worms, int numworms, int x, int y, int dir, int length)
Iulian Radu's avatar
Iulian Radu committed
550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565
    {
        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)
        {
566 567
            cx = worms[i].head.x;
            cy = worms[i].head.y;
Iulian Radu's avatar
Iulian Radu committed
568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612
            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;
Iulian Radu's avatar
Iulian Radu committed
613
        return Worm.ai_deadend (board, numworms, cx, cy, cl);
Iulian Radu's avatar
Iulian Radu committed
614 615 616 617 618 619 620 621 622 623 624 625 626
    }

    /* 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)
        {
627 628
            dx = head.x - worms[i].head.x;
            dy = head.y - worms[i].head.y;
Iulian Radu's avatar
Iulian Radu committed
629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652
            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;
    }

Iulian Radu's avatar
Iulian Radu committed
653
    private static bool ai_wander (int[,] board, int numworms, int x, int y, int dir, int ox, int oy)
Iulian Radu's avatar
Iulian Radu committed
654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684
    {
        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;

Iulian Radu's avatar
Iulian Radu committed
685
        switch (board[x, y] - 'A')
Iulian Radu's avatar
Iulian Radu committed
686 687 688 689 690 691 692 693 694 695 696 697
        {
            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:
Iulian Radu's avatar
Iulian Radu committed
698 699
                if (board[x, y] > NibblesGame.EMPTYCHAR
                    && board[x, y] < 'z' + numworms)
Iulian Radu's avatar
Iulian Radu committed
700 701 702 703 704 705 706 707
                {
                        return false;
                }
                else
                {
                    if (ox == x && oy == y)
                        return false;

Iulian Radu's avatar
Iulian Radu committed
708
                    return Worm.ai_wander (board, numworms, x, y, dir, ox, oy);
Iulian Radu's avatar
Iulian Radu committed
709 710 711 712 713
                }
        }
    }

    /* Determines the direction of the AI worm. */
Iulian Radu's avatar
Iulian Radu committed
714
    public void ai_move (int[,] board, int numworms, Gee.LinkedList<Worm> worms)
Iulian Radu's avatar
Iulian Radu committed
715 716 717
    {
        var opposite = (direction + 1) % 4 + 1;

Iulian Radu's avatar
Iulian Radu committed
718 719 720
        var front = Worm.ai_wander (board, numworms, head.x, head.y, direction, head.x, head.y);
        var left = Worm.ai_wander (board, numworms, head.x, head.y, direction - 1, head.x, head.y);
        var right = Worm.ai_wander (board, numworms, head.x, head.y, direction + 1, head.x, head.y);
Iulian Radu's avatar
Iulian Radu committed
721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785

        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;

Iulian Radu's avatar
Iulian Radu committed
786
            if (!can_move_to (board, numworms))
Iulian Radu's avatar
Iulian Radu committed
787 788 789 790 791
                this_len += NibblesGame.CAPACITY;

            if (ai_too_close (worms, numworms))
                this_len += 4;

Iulian Radu's avatar
Iulian Radu committed
792
            this_len += ai_deadend_after (board, worms, numworms, head.x, head.y, dir, length + change);
Iulian Radu's avatar
Iulian Radu committed
793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820

            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;

Iulian Radu's avatar
Iulian Radu committed
821
            if (!can_move_to (board, numworms))
Iulian Radu's avatar
Iulian Radu committed
822 823 824 825
                direction = (WormDirection) dir;
            else
                continue;
        }
Iulian Radu's avatar
Iulian Radu committed
826 827
    }
}