post-apocalyptic-wargame / path.c

/*See LICENSE file for copyright and license details.*/

#include <stdlib.h>
#include "bool.h"
#include "list.h"
#include "utype.h"
#include "core.h"
#include "misc.h"
#include "path.h"

/*stack for filling map*/
static Stack stack = {NULL, NULL, 0};

/*Push this coordinates to stack,
  update cost and parent of this tile*/
static void
push (Mcrd m, Mcrd parent, int newcost, Dir dir) {
  Tile *t = tile(m);
  Node *n = mk_node(copy2heap(&m, sizeof(Mcrd)));
  push_node(&stack, n);
  t->cost = newcost;
  t->parent = parent;
  t->dir = dir;
}

static Mcrd
pop (void){
  Node *tmp = pop_node(&stack);
  Mcrd m = *(Mcrd*)(tmp->data);
  free(tmp->data);
  free(tmp);
  return(m);
}

/*For not to pass through visible enemy.
  Check if there are no enemy of we can't see him(ambush).
  id - player's id*/
static bool
is_tile_looks_empty (Mcrd m, int id){
  Unit *u = unit_at(m);
  bool is_occupied = u && (u->player != id) && u->is_visible;
  return(!is_occupied && tile(m)->visible);
}

/*If this is first(start) tile - no parent tile.*/
static Dir
get_parent_dir (Unit *u, Mcrd m){
  Tile *t = tile(m);
  if(t->cost == 0)
    return(u->dir);
  else
    return(m2dir(t->parent, m));
}

static int
get_tile_cost (Unit *u, Mcrd t, Mcrd nb){
  int tile_cost = unit_types[u->t].ter_mv[tile(nb)->t];
  Dir d = m2dir(t, nb);
  if(u->t == U_LIGHT_TANK || u->t == U_TRUCK){
    Dir d2 = get_parent_dir(u, t);
    tile_cost *= dir_diff(d, d2) + 1;
  }
  return(tile_cost);
}

static void
process_neibor (Unit *u, Mcrd t, Mcrd nb){
  if(is_tile_looks_empty(nb, u->player)){
    int newcost = tile(t)->cost + get_tile_cost(u, t, nb);
    if(tile(nb)->cost > newcost && newcost <= u->ap)
      push(nb, t, newcost, m2dir(t, nb));
  }
}

static void
clean_map (void){
  Mcrd m;
  FOR_EACH_MCRD(m){
    Tile *t = tile(m);
    t->cost = 30000;
    t->dir = D_UR;
    t->parent = mk_mcrd(0,0);
  }  
}

static void
try_to_push_neibors (Unit *u, Mcrd m){
  int i;
  for(i = 0; i < 6; i++){
    Mcrd neib_m = neib(m, i);
    if(inboard(neib_m))
      process_neibor(u, m, neib_m);
  }
}

/*TODO: link to algorithm*/
void
fill_map (Unit *u) {
  if(!u)
    return;
  clean_map();
  push(u->m, u->m, 0, u->dir); /*push start position*/
  while(stack.count > 0)
    try_to_push_neibors(u, pop());
  clear_list(&stack);
}

/*m - destination*/
List
get_path (Mcrd m){
  List path = {NULL, NULL, 0};
  while(tile(m)->cost != 0){
    Node *n = mk_node(copy2heap(&m, sizeof(Mcrd)));
    push_node(&path, n);
    m = tile(m)->parent;
  }
  /*Add start position.*/
  push_node(&path, mk_node(copy2heap(&m, sizeof(Mcrd))));
  return(path);
}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.