Dijkstra Map of Generic Map in Dart

Dart Implementation of Dijkstra Maps

The Dart code below calculates a map of distances, based on an input map.

It is versatile in that it is agnostic of any map engine.

The input consists of:

• A map is represented by a List-of-lists.
• A start Point.
• A set of Strings defining non-traversables.

The code will return a map (list-of-lists) with the distances as double values relative to the start Point.

Usage

Basic

List<List<String>> mapList = [ ... ];

Point<int> start = Point(3, 1);

Set<String> wallTypes = {'#'};

Dijkstra dijkstra = Dijkstra();

List<List<double?>> mapDistance = dijkstra.dijkstraMap(mapList, start, wallTypes);

List<List<double?>> mapDistanceInverted = 
    dijkstra.dijkstraMapInvert(mapList, start, wallTypes, factor: -1.2);

Details

final mapString =
    '''
##########
###....###
###....###
###....###
###....###
###....###
######.###
######▒▒▒#''';

final expected = [
  [null, null, null, null, null, null, null, null, null, null],
  [null, null, null, 0.0, 1.0, 2.0, 3.0, null, null, null],
  [null, null, null, 1.0, 2.0, 3.0, 4.0, null, null, null],
  [null, null, null, 2.0, 3.0, 4.0, 5.0, null, null, null],
  [null, null, null, 3.0, 4.0, 5.0, 6.0, null, null, null],
  [null, null, null, 4.0, 5.0, 6.0, 7.0, null, null, null],
  [null, null, null, null, null, null, 8.0, null, null, null],
  [null, null, null, null, null, null, 9.0, 10.0, 11.0, null]
];

List<List<String>> mapList =
    mapString.split('\n').map((row) => row.split('')).toList();

Dijkstra dijkstra = Dijkstra();
List<List<double?>> mapDistance = 
    dijkstra.dijkstraMap(mapList, Point(3, 1), {'#'});

assert(expected == mapDistance);

Debug

String pretty = dijkstra.dijkstraMapPretty(result);

// call only for small maps

print(pretty);

                 0.0  1.0  2.0  3.0
                 1.0  2.0  3.0  4.0
                 2.0  3.0  4.0  5.0
                 3.0  4.0  5.0  6.0
                 4.0  5.0  6.0  7.0
                                8.0
                                9.0 10.0 11.0

Dart Implementation

import 'dart:math';

class Dijkstra {

  /// Based on the [start] [Point] and the [map] a Dijkstra Map
  /// will be calculated and returned.
  ///
  /// The numeric values of the cells of the Dijkstra Map indicate
  /// the distance to the [start] [Point], excluding [nonTraverse] tiles.

  List<List<double?>> dijkstraMap(
      List<List<String>> map, Point<int> start, Set<String> nonTraverse) {
    final List<List<double?>> dijkstraMap = List.generate(
        map.length,
        (index) =>
            List.generate(map.first.length, (index) => null, growable: false),
        growable: false);

    final List<Point<int>> frontier = [start];
    final Map<Point<int>, double> distance = {};
    distance[start] = 0;

    while (frontier.isNotEmpty) {
      final current = frontier.removeAt(0);

      final (left, _, top, _, right, _, bottom, _) =
          _getNeighborsLTRB(map, current);

      final List<Point<int>?> neighbors = [left, top, right, bottom]
          .where((neighbor) =>
              neighbor != null &&
              nonTraverse.contains(map[neighbor.y][neighbor.x]) == false)
          .toList();

      for (final Point<int>? neighbour in neighbors) {
        if (distance.containsKey(neighbour!) == false) {
          frontier.add(neighbour);
          distance[neighbour] = 1 + distance[current]!;
        }
      }
    }

    for (final entry in distance.entries) {
      final tile = entry.key;
      final dist = entry.value;
      dijkstraMap[tile.y][tile.x] = dist;
    }

    return dijkstraMap;
  }

  /// Calculates an inverted Dijkstra map.
  List<List<double?>> dijkstraMapInvert(
      List<List<String>> map, Point<int> start, Set<String> nonTraverse,
      {double factor = -1.2}) {
    List<List<double?>> ret = dijkstraMap(map, start, nonTraverse);
    for (int y = 0; y < ret.length; y++) {
      for (int x = 0; x < ret[y].length; x++) {
        if (ret[y][x] != null) {
          ret[y][x] = ret[y][x]! * factor;
        }
      }
    }
    return ret;
  }

  /// The parameter [map] is the result of [dijkstraMap] or [dijkstraMapInvert].
  ///
  /// The result is a formated [String] with distance values.
  String dijkstraMapPretty(List<List<double?>> map) {
    final maxLength = map
        .expand((e) => e)
        .toList()
        .map((e) => e == null ? '' : e.toStringAsFixed(1))
        .fold(0, (prev, curr) => prev > curr.length ? prev : curr.length);
    final padding = maxLength + 1;

    final List<List<String>> ret = [];
    for (final row in map) {
      final List<String> rowNew = [];
      for (final double? entry in row) {
        if (entry == null) {
          rowNew.add(" ".padLeft(padding));
        } else {
          rowNew.add(entry.toStringAsFixed(1).padLeft(padding));
        }
      }
      ret.add(rowNew);
    }
    return ret.map((e) => e.join('')).join('\n');
  }

  // -----------------------------------------------------------------------
  // NEIGHBORS
  // -----------------------------------------------------------------------

  (
    Point<int>?,
    Point<int>?,
    Point<int>?,
    Point<int>?,
    Point<int>?,
    Point<int>?,
    Point<int>?,
    Point<int>?
  ) _getNeighborsLTRB(List<List<String>> map, Point<int> tile) {
    return (
      _getNeighbor(map, tile.x, tile.y, _Direction.west),
      _getNeighbor(map, tile.x, tile.y, _Direction.northwest),
      _getNeighbor(map, tile.x, tile.y, _Direction.north),
      _getNeighbor(map, tile.x, tile.y, _Direction.northeast),
      _getNeighbor(map, tile.x, tile.y, _Direction.east),
      _getNeighbor(map, tile.x, tile.y, _Direction.southeast),
      _getNeighbor(map, tile.x, tile.y, _Direction.south),
      _getNeighbor(map, tile.x, tile.y, _Direction.southwest),
    );
  }

  Point<int>? _getNeighbor(
      List<List<String>> map, int x, int y, _Direction direction) {
    Point<int>? ret;

    if (x < 0 || y < 0 || x > map.first.length - 1 || y > map.length - 1) {
      ret = null;
    } else {
      switch (direction) {
        case _Direction.north:
          y--;
          break;
        case _Direction.south:
          y++;
          break;
        case _Direction.east:
          x++;
          break;
        case _Direction.west:
          x--;
          break;
        case _Direction.northeast:
          y--;
          x++;
          break;
        case _Direction.northwest:
          y--;
          x--;
          break;
        case _Direction.southeast:
          y++;
          x++;
          break;
        case _Direction.southwest:
          y++;
          x--;
          break;
      }
      if (x >= 0 && x < map.first.length && y >= 0 && y < map.length) {
        ret = Point(x, y);
      }
    }
    return ret;
  }
}

enum _Direction {
  west,
  northwest,
  north,
  northeast,
  east,
  southeast,
  south,
  southwest
}