Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualÁlvaro

Posted 28 April 2013 - 12:53 PM

I would implement something like this myself. The exact way to do it depends on the details of the movement rules, which you haven't given us. But something like breath-first search should be easy to implement. If the board is 8x8 or smaller, bitboards could be an attractive way to do it too.

This code is C++, but perhaps you can get some ideas from it:
typedef unsigned long long u64;

u64 N(u64 x) {
  return x << 8;
}

u64 E(u64 x) {
  return (x & 0x7f7f7f7f7f7f7f7full) << 1;
}

u64 S(u64 x) {
  return x >> 8;
}

u64 W(u64 x) {
  return (x & 0xfefefefefefefefeull) >> 1;
}

u64 propagate(u64 x) {
  return N(x)|E(x)|S(x)|W(x);
}

u64 targets(int origin, int max_steps, u64 obstacles) {
  u64 bb = 1ull << origin;
  for (int i=0; i<max_steps; ++i)
    bb |= propagate(bb) & ~obstacles;
  return bb;
}

#2Álvaro

Posted 27 April 2013 - 03:35 PM

I would implement something like this myself. The exact way to do it depends on the details of the movement rules, which you haven't given us. But something like breath-first search should be easy to implement. If the board is 8x8 or smaller, bitboards could be an attractive way to do it too.

This code is C++, but perhaps you can get some ideas from it:
typedef unsigned long long u64;

u64 N(u64 x) {
  return x << 8;
}

u64 E(u64 x) {
  return (x & 0x7f7f7f7f7f7f7f7full) << 1;
}

u64 S(u64 x) {
  return x >> 8;
}

u64 W(u64 x) {
  return (x & 0xfefefefefefefefeull) >> 1;
}

u64 propagate(u64 x) {
  return N(x)|E(x)|S(x)|W(x);
}

u64 targets(int origin, int max_steps, u64 obstacles) {
  u64 bb = 1ull << origin;
  for (int i=0; i<max_steps; ++i)
    bb = propagate(bb) & ~obstacles;
  return bb;
}

#1Álvaro

Posted 27 April 2013 - 03:33 PM

I would implement something like this myself. The exact way to do it depends on the details of the movement rules, which you haven't given us. But something like breath-first search should be easy to implement. If the board is 8x8 or smaller, bitboards could be an attractive way to do it too.

This code is C++, but perhaps you can get some ideas from it:
typedef unsigned long long u64;

u64 N(u64 x) {
  return x << 8;
}

u64 E(u64 x) {
  return (x & 0x7f7f7f7f7f7f7f7full) << 1;
}

u64 S(u64 x) {
  return x >> 8;
}

u64 W(u64 x) {
  return (x & 0xfefefefefefefefeull) >> 1;
}

u64 propagate(u64 x) {
  return N(x)|E(x)|S(x)|W(x);
}

u64 targets(int origin, int max_steps, u64 obstacles) {
  u64 bb = 1ull << origin;
  for (int i=0; i<max_steps; ++i)
    bb = propagate(i) & ~obstacles;
  return bb;
}

PARTNERS