ovcc-board.vala 15.9 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
/* 
 * 
 * Copyright (C) 2009-2011 Colomban Wendling <ban@herbesfolles.org>
 *                         Jonathan Michalon <studios.chalmion@no-log.org>
 *
 * 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/>.
 * 
 */


/* TODO : implement do_try_place_tile, is_tile_placeable (foreach) */

namespace OVCC
{
  public struct Position
  {
    public int x;
    public int y;
30
    
31 32 33 34
    public bool equals (Position pos)
    {
      return this.x == pos.x && this.y == pos.y;
    }
35 36 37 38 39 40 41 42 43 44 45 46 47 48
    
    public uint hash ()
    {
      /* from g_str_hash, do a direct in-memory hash */
      char  *p = (char *) (&this);
      uint32 h = p[0];
      size_t i = 0;
      
      for (i = 1; i < sizeof (Position); i++) {
        h = (h << 5) - h + p[i];
      }
      
      return (uint) h;
    }
49 50 51 52
  }

  public class Board : Object
  {
53 54
    private HashTable<Position?,Tile> _board = new HashTable<Position?,Tile> ((k) => { return k.hash (); },
                                                                              (a, b) => { return a.equals (b); });
55 56 57 58 59 60
    /* private HashTable<Pawns>    _pawns = new HashTable<Pawns> (); */

    private int leftedge = 0;
    private int topedge = 0;
    private int rightedge = 0;
    private int bottomedge = 0;
61

62 63
    private Position _last_position = Position ();
    public Position last_position { get { return _last_position; } }
64 65
    
    public signal void tile_added (Tile t, Position pos);
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
    /**
     * Signal emitted when a pawn was added to the board
     * 
     * @param pawn The placed pawn
     * @param obj The object on which the pawn was placed
     * @param pos The position of the tile containing @p pos
     */
    public signal void pawn_added (Pawn        pawn,
                                   TileObject  obj,
                                   Position    pos);
    /**
     * Signal emitted when a pawn was removed
     * 
     * @param pawn The removed pawn
     * @param obj The object on which the pawn was
     * @param pos The position of the tile containing the object
     */
    public signal void pawn_removed (Pawn        pawn,
                                     TileObject  obj,
                                     Position    pos);
86
    
87
    public Board (Tile first)
88
    {
89
      do_add_tile (first, {0, 0});
90 91

      tile_added.connect ((t, p) => {
92
        _last_position = p;
93
      });
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
    }
    
    public bool is_tile_there (Position pos)
    {
      return get_tile (pos) != null;
    }

    public Tile get_tile (Position pos)
    {
      return this._board.lookup (pos);
    }

    private void do_add_tile (Tile     tile,
                              Position pos)
    {
      this._board.insert (pos, tile);
      this.leftedge   = int.min (pos.x, leftedge);
      this.topedge    = int.min (pos.y, topedge);
      this.rightedge  = int.max (pos.x, rightedge);
      this.bottomedge = int.max (pos.y, bottomedge);

      this.tile_added (tile, pos);
    }
    
    public bool add_tile (Tile     tile,
                          Position pos)
    {
      bool placed = false;
      
      if (add_tile_check (tile, pos)) {
        do_add_tile (tile, pos);
        placed = true;
      }
      
      return placed;
    }
  
    /* TODO: try & check this! */
    public bool add_tile_check (Tile     tile,
                                Position pos)
    {
      bool valid = true;           /* whether the relations are consistent */
      bool have_neighbour = false; /* whether the tile have a neighbour */
  
      /* cannot place a tile if there is already one */
      if (is_tile_there (pos)) {
        valid = false;
      } else {
142
        /* check for each possible tile around, looping on the links */
143
        foreach (var links in TileObjectLinks.SIDES) {
144 145 146 147 148 149 150 151 152 153 154 155
          var tmppos = pos;
          
          switch (links) {
            case TileObjectLinks.TOP:     tmppos.y--; break; /* top */
            case TileObjectLinks.RIGHT:   tmppos.x++; break; /* right */
            case TileObjectLinks.BOTTOM:  tmppos.y++; break; /* bottom */
            case TileObjectLinks.LEFT:    tmppos.x--; break; /* left */
            default: assert_not_reached ();
          }
          
          var tmptile = this.get_tile (tmppos);
          /* TODO: check if the sides matches */
156
          valid = (tmptile == null) || tile.match (links, tmptile);
157 158 159
          if (tmptile != null) {
            have_neighbour = true;
          }
160 161
          if (!valid)
            break;
162
        }
163 164 165 166
      }
      
      return valid && have_neighbour;
    }
167 168 169 170
    
    /**
     * Checks whether a tile is placeable on the board
     * 
171
     * @param tile a {@link tile}
172 173
     * @return true if the tile can be placed, false otherwise.
     */
174
    public bool is_tile_placeable (Tile tile)
175
    {
176
      var tiledup = tile.dup();
177 178 179 180 181 182 183 184 185 186 187
      return false == this.foreach ((b, p, t) => {
        for (var i = 0; i < 4; i++) {
          var npos = p;
          
          switch (i) {
            case 0: npos.y--; break; /* top */
            case 1: npos.x++; break; /* right */
            case 2: npos.y++; break; /* bottom */
            case 3: npos.x--; break; /* left */
          }
          for (var j = 0; j < 4; j++) {
188
            if (this.add_tile_check (tiledup, npos)) {
189 190
              return false;
            } else {
191
              tiledup.rotate (1);
192 193 194 195 196 197
            }
          }
        }
        return true;
      });
    }
198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216

    /**
     * Checks whether a pawn of the given kind can be placed on that TileObject
     *
     * This function performs a check to determine whether a pawn of the kind
     * given can be placed on the given TileObject (which is on the board at
     * the position given).
     * 
     * @param kind The kind of pawn to use
     * @param object The TileObject to check against
     * @param pos The position on the board of the TileObject
     * @return True if ok, false otherwise
     */
    public bool add_pawn_check (PawnKind kind,
                                TileObject object,
                                Position pos)
    {
      if (kind == PawnKind.ARCHITECT) /* FIXME not so easy */
        return true;
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260

      /* use a queue because with lists either we should append (bad perfs)
       * or we "forget" already visited objects (the prepend problem) */
      var checked  = new Queue<TileObject>();

      return add_pawn_check_rec (object, pos, checked);
    }



    /* recursive helper for pawn check */
    private bool add_pawn_check_rec (TileObject object,
                                     Position pos,
                                     Queue<TileObject> checked)
    {
      if (checked.find (object) != null)
        return true;
      if (object.occupant != null)
        return false;

      checked.push_head (object);

      /* loop on each link */
      foreach (var link in object.links) {
        var otherpos = pos;
        if (link in TileObjectLinks.TOP)
          otherpos.y--;
        else if (link in TileObjectLinks.RIGHT)
          otherpos.x++;
        else if (link in TileObjectLinks.BOTTOM)
          otherpos.y++;
        else if (link in TileObjectLinks.LEFT)
          otherpos.x--;
        else
          assert_not_reached ();

        var tile = get_tile (otherpos);
        if (tile != null) {
          var neighbour = tile.get_object_linking (link.mirror_links ());
          if (neighbour != null &&
              !add_pawn_check_rec (neighbour, otherpos, checked))
            return false;
        }
      }
261 262
      return true;
    }
263

264 265 266 267 268 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 298 299 300
    /**
     * Tries to place a pawn on the given TileObject
     *
     * To succeed the object must be free (ie. no other pawn on the same
     * "object").  By "object" it is meant the given TileObject AND all of its
     * neighbours, doing recursion on the tiles
     *
     * @param pawn The concerned pawn
     * @param object The TileObject where to place the pawn
     * @param pos The position where the object's tile is located on the board
     * @return true if the pawn was correctly placed, false otherwise
     */
    public bool add_pawn (Pawn pawn, TileObject object, Position pos)
    {
      var ok = add_pawn_check (pawn.kind, object, pos);
      if (ok) {
        pawn.place (object, pos);
        pawn_added (pawn, object, pos);
      }
      return ok;
    }

    /**
     * Removes a pawn
     *
     * Removes a pawn from the board.
     * 
     * @param pawn The pawn
     */
    public void remove_pawn (Pawn pawn)
    {
      var o   = pawn.location;
      var pos = pawn.position;
      pawn.player.retrieve_pawn (pawn);
      pawn_removed (pawn, o, pos);
    }

301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364
    /**
     * Calculates the list of connected objects starting from the given one
     *
     * This method builds a list of {@link TileObject} that are connected each
     * other. It starts on the given one (which is at the given {@link Position}
     * on the board) and recurses until all are found.
     * 
     * @param object The {@link TileObject} to start from
     * @param pos The {@link Position} of the given object on the board
     * @param complete An out parameter saying whether the list builds a
     *        complete set of objects (ie. the path is finished on both sides)
     * @return The promised list
     */
    public SList <TileObject> get_connected (TileObject object,
                                             Position pos,
                                             out bool complete)
    {
      var component = new SList<TileObject>();

      complete = get_connected_rec (object, pos, ref component);

      return component;
    }

    /* helper to determine whether an object links to a complete set of objects
     * (ie. a complete path) and produces the list of connected objects.
     */
    private bool get_connected_rec (TileObject object,
                                    Position pos,
                                    ref SList <TileObject> component)
    {
      if (component.find (object) != null)
        return true;

      var complete = true;
      
      component.prepend (object);

      /* loop on each link */
      foreach (var link in object.links) {
        var otherpos = pos;
        if (link in TileObjectLinks.TOP)
          otherpos.y--;
        else if (link in TileObjectLinks.RIGHT)
          otherpos.x++;
        else if (link in TileObjectLinks.BOTTOM)
          otherpos.y++;
        else if (link in TileObjectLinks.LEFT)
          otherpos.x--;
        else
          assert_not_reached ();

        var tile = get_tile (otherpos);
        if (tile != null) {
          var neighbour = tile.get_object_linking (link.mirror_links ());
          if (neighbour != null &&
              !get_connected_rec (neighbour, otherpos, ref component))
            complete = false;
        } else {
          complete = false;
        }
      }
      return complete;
    }
365
    
366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440
    /**
     * Get a list of TileObjects of a city and together the list forming the
     * fileds around it
     * 
     * @param object The first city object
     * @param pos The position of that objects on the board
     * @param city An out list of CITY objects
     * @param fields An out list of FIELDs objects
     * @return Whether the city is complete
     */
    public bool get_city_with_fields (TileObject object,
                                      Position pos,
                                      out SList<TileObject> city,
                                      out SList<TileObject> fields)
    {
      city   = new SList<TileObject>();
      fields = new SList<TileObject>();

      var complete = get_city_with_fields_rec (object, pos, ref city, ref fields);

      return complete;
    }

    /* recursive handler for the previous function */
    private bool get_city_with_fields_rec (TileObject object,
                                           Position pos,
                                           ref SList <TileObject> city,
                                           ref SList <TileObject> fields)
    {
      if (city.find (object) != null)
        return true;

      var complete = true;

      city.prepend (object);

      /* loop on each link */
      foreach (var link in object.links) {
        var otherpos = pos;
        if (link in TileObjectLinks.TOP)
          otherpos.y--;
        else if (link in TileObjectLinks.RIGHT)
          otherpos.x++;
        else if (link in TileObjectLinks.BOTTOM)
          otherpos.y++;
        else if (link in TileObjectLinks.LEFT)
          otherpos.x--;
        else
          assert_not_reached ();

        var othertile = get_tile (otherpos);
        if (othertile != null) {
          var neighbour = othertile.get_object_linking (link.mirror_links ());
          if (neighbour != null &&
              !get_city_with_fields_rec (neighbour, otherpos, ref city, ref fields))
            complete = false;
        } else {
            complete = false;
        }
        var tile = get_tile (pos);
        assert (tile != null);
        var newfields = tile.get_touching_objects(object, TileObjectType.FIELD);
        foreach (var f in newfields) {
          bool dummy;
          var components = get_connected (f, pos, out dummy);
          foreach (var c in components) {
            if (fields.find (c) == null) {
              fields.prepend (c);
            }
          }
        }
      }
      return complete;
    }
    
441 442 443 444 445 446
    public void get_bounds (out int left,
                            out int top,
                            out int right,
                            out int bottom,
                            out int width,
                            out int height)
447 448 449 450 451 452 453 454 455
    {
      left   = leftedge;
      top    = topedge;
      right  = rightedge + 1;
      bottom = bottomedge + 1;
      width  = (leftedge - rightedge).abs()  + 1;
      height = (topedge  - bottomedge).abs() + 1;
    }
    
456 457 458 459 460 461 462 463 464 465 466 467 468
    public delegate bool BoardForeachFunc (Board    board,
                                           Position pos,
                                           Tile     tile);
    
    /**
     * Calls @f for each tile in the board, giving the tile and its position.
     * 
     * @param f a function to call on each tile
     * @return the return value of the last iteration of @func. In other words,
     *         %TRUE if the callback never stopped iterating, %FALSE otherwise.
     */
    public bool @foreach (BoardForeachFunc f)
    {
469 470 471 472 473 474 475 476 477
      HashTableIter<Position?,Tile> iter = HashTableIter<Position?,Tile> (this._board);
      Position? pos;
      Tile tile;
      bool went_through = true;

      while (iter.next (out pos, out tile)) {
        if (f (this, pos, tile) == false) {
          went_through = false;
          break;
478
        }
479 480
      }
      return went_through;
481
    }
Jonathan Michalon's avatar
Jonathan Michalon committed
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
    
    /**
     * dump:
     * 
     * Outputs a representation of the given board (only IDs for now).
     */
    public void dump ()
    {
      int       i, j;
      Position  pos = {0, 0};

      /* Output the position numbers */
      for (j = leftedge; j <= rightedge; j++) {
        stdout.printf ("|%3i  |", j);
      }
      stdout.printf ("\n");
      
      for (i = topedge; i <= bottomedge; i++) {
        pos.y = i;
          for (j = leftedge; j <= rightedge; j++) {
            pos.x = j;
            if (is_tile_there (pos)) {
              stdout.printf ("| ");
              get_tile (pos).dump();
              stdout.printf (" |");
            } else {
              stdout.printf ("       ");
            }
          }
          stdout.printf ("\n");
      }
      /* Output the position numbers */
      for (j = leftedge; j <= rightedge; j++) {
        stdout.printf ("|%3i  |", j);
      }
      stdout.printf ("\n");
    }
519 520
  }
}