One major thing I’ve been working on recently is the overall game structure. I wanted a Mario-esque overworld map, so I mocked up a simple graveyard for the first tomb-themed world. Something like this:

Navigating this map becomes an interesting problem to solve. On a console, you would use the joypad to move from stage to stage, and then press a button to enter a stage. On mobile, that doesn’t work. Well, unless of course you have an onscreen joypad, which I generally try to avoid.

The preferred interaction would be: tap on any stage anywhere on the map and the player will walk through the world, following the path, until he arrives at the chosen destination (assuming it can be reached). The key phrase being “following the path.” Despite the simplicity of the map this will require a pathfinding solution, mainly because the path can split.

After reading some articles and doing some research, I found this excellent video explaining the A* pathfinding process step-by-step. I’m not going to try to explain the intricacies of the pathfinding problem because this video does it so well. I recommend it to anyone trying to research this stuff.

I was able to implement the pseudo code from this video very quickly and the results were perfect, almost on the first try. It’s surprisingly concise too. Here is the Dart method I came up with for finding the (probable) shortest path through the map:

class PathNode {
  Vector3 pos;
  List<int>edges = []; // indices of connections to other nodes
  int previous;
  int f;
  int g;
}

List<int> pathFinder(List<PathNode> nodes, int start, int end) {
  List<int> path = [];

  var heuristic = (Vector3 a, Vector3 b){
    // calc the 'Manhattan Distance'
    return (b.x - a.x).abs() + (b.y - a.y).abs();
  };

  var current = start;
  var open = ListQueue<int>();
  var closed = ListQueue<int>();

  while (current != end) {
    for (int i in nodes[current].edges) {
      if (!open.contains(i) && !closed.contains(i)) {
        open.add(i);
        var g = heuristic(nodes[i].pos, nodes[start].pos).round();
        var h = heuristic(nodes[i].pos, nodes[end].pos).round();
        var f = g + h;
        if (nodes[i].f == null || nodes[i].f > f) {
          nodes[i].f = f;
          nodes[i].previous = current;
        }
      }
    }
    closed.add(current);
    var low = open.reduce((curr, next) => nodes[curr].f < nodes[next].f ? curr : next);
    open.removeWhere((i){return i == low;});
    current = low;
  }

  path.add(end);
  current = end;
  while (current != start) {
    current = nodes[current].previous;
    path.add(current);
  }

  return path.reversed.toList();
}

And in game it looks like this: