6
\$\begingroup\$

Currently, I'm working on a game with directional movement influenced by the numpad. The player AI should intelligently pick a direction to move (so it's not entirely random, and can be somewhat coherent).

For reference, this is the numpad I'm using:

7 | 8 | 9
- - - - -
4 | x | 6
- - - - -
1 | 2 | 3

(5 is ignored as moving to your current location is considered invalid).

Essentially, I want to take the players prior movement direction and prioritize it where possible, making it "fan out" into lesser probabilities the more "unlikely" the movement is. Suppose the players prior direction was 8, the probability distribution should look like this:

60 | 80 | 60
-- | -- | --
30 | xx | 30
-- | -- | --
20 | 10 | 20

Just to provide another example, a prior movement of 1 would look like this:

30 | 20 | 10
-- | -- | --
60 | xx | 20
-- | -- | --
80 | 60 | 30

The algorithm I've come up with looks like this:

let neighbors = {
  1: [4, 2],
  2: [1, 3],
  3: [2, 6],
  4: [7, 1],

  6: [9, 3],
  7: [4, 8],
  8: [7, 9],
  9: [8, 6]
};

let probabilities = [80, 60, 30, 20, 10];

let recurse = (obj, pos, level = 0) => {
  if(!probabilities[level] || obj[pos]) return;

  obj[pos] = probabilities[level];
  recurse(obj, neighbors[pos][0], level+1);
  recurse(obj, neighbors[pos][1], level+1);
};

export default (firstDir) => {
  var ret = {}; 
  recurse(ret, firstDir); 
  return ret; 
}

The implementation spits out a hash with the probabilities, so, the output from the 8 situation above would look like this:

{ 
  1: 20,
  2: 10,
  3: 20,
  4: 30,
  6: 30,
  7: 60,
  8: 80,
  9: 60
}

I'm not really sold on this implementation - it requires a map of neighbors for recursion. I can't quite figure out if there's some fancy math I can use to derive this, so I'm instead using recursion.

Could this be done better?

\$\endgroup\$
  • 1
    \$\begingroup\$ On a side note, I think this would be an awesome question for code-golf.SE \$\endgroup\$ – Seiyria Jul 18 '15 at 16:46
  • \$\begingroup\$ (off-topic (this remark not your question)) you should totally post this on CodeGolf! \$\endgroup\$ – Caridorc Jul 18 '15 at 19:45
7
\$\begingroup\$

There’s no need for recursion here. You have some base probability map, and you want to rotate it such that the maximum element points in some particular direction. You could implement that fairly simply:

var INDICES = [1, 2, 3, 6, 9, 8, 7, 4];
var PROBABILITIES = [80, 60, 30, 20, 10, 20, 30, 60];

function generateProbabilities(lastNumpadDirection) {
    var lastIndexDirection = INDICES.indexOf(lastNumpadDirection);
    var shifted = PROBABILITIES.slice(PROBABILITIES.length - lastIndexDirection)
        .concat(PROBABILITIES.slice(0, PROBABILITIES.length - lastIndexDirection));
    var result = {};
    for(var i = 0, l = INDICES.length; i < l; i++) {
        result[INDICES[i]] = shifted[i];
    }
    return result;
}

Much of the complexity here comes from needing to deal with directions represented as arrows on the numpad–here, I convert them to 45-degree-offsets going clockwise from northwest, shift the probabilities array, and then convert back to your desired numpad format. Illustrated:

\$\endgroup\$
  • \$\begingroup\$ This is quite an interesting approach. One thing to note - in your first array, you have 5 as an index. That should be 6, as 5 is invalid. \$\endgroup\$ – Seiyria Jul 18 '15 at 17:14
  • \$\begingroup\$ @Seiyria: Oops, good catch. \$\endgroup\$ – icktoofay Jul 18 '15 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.