# 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 function 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);

bool isNonTraverseable(dynamic str) => {'#'}.contains(str);

Dijkstra dijkstra = Dijkstra();

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

List<List<double?>> mapDistanceInverted =
dijkstra.dijkstraMapInvert(mapList, start, isNonTraverseable, 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();

bool isNonTraverseable(dynamic str) => {'#'}.contains(str);

Dijkstra dijkstra = Dijkstra();

List<List<double?>> mapDistance =
dijkstra.dijkstraMap(mapList, Point(3, 1), isNonTraverseable);

assert(expected == mapDistance);

Debug

String pretty = dijkstra.dijkstraMapPretty(mapDistance);

// 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<dynamic>> map, Point<int> start,
bool Function(dynamic obj) isNonTraverseable) {
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 &&
isNonTraverseable.call(map[neighbor.y][neighbor.x]) == false
// nonTraverse.contains(map[neighbor.y][neighbor.x]) == false
)
.toList();

for (final Point<int>? neighbour in neighbors) {
if (distance.containsKey(neighbour!) == false) {
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<dynamic>> map,
Point<int> start, bool Function(dynamic obj) isNonTraverseable,
{double factor = -1.2}) {
List<List<double?>> ret = dijkstraMap(map, start, isNonTraverseable);
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) {
} else {
}
}
}
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<dynamic>> 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<dynamic>> 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
}