• 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