Dijkstra Map of Generic Map in Dart
Jump to navigation
Jump to search
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.0Dart 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) {
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<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) {
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<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
}