I don't understand why do we need any Node objects? I use something like that: ArrayDeque<point> queue = new ArrayDeque<>(); queue.add(edge); visited[edge.y][edge.x] = true; while (!queue.isEmpty()) { Point point = queue.removeFirst(); for (Direction direction : Direction.directions) { Point next = point.move(direction); if (next == null || visited[next.y][next.x]) { continue; } queue.add(next); visited[next.y][next.x] = true; } }

I create a pool of points on the first tick, so the same coodrinates are always the same object, no garbage. Directions are something like this: (UP(0, 1), RIGHT(1, 0), DOWN(0, -1), LEFT(-1, 0)). ArrayDeque has circular array implementation in java, so it is fast. This code is for floodfill, but pathfinding is the same. We can jast add HashMap, or two dimential array to trace the path.

oreshnik• 9 months agoI don't understand why do we need any Node objects?

I use something like that:

ArrayDeque<point> queue = new ArrayDeque<>();

queue.add(edge);

visited[edge.y][edge.x] = true;

while (!queue.isEmpty()) {

Point point = queue.removeFirst();

for (Direction direction : Direction.directions) {

Point next = point.move(direction);

if (next == null || visited[next.y][next.x]) {

continue;

}

queue.add(next);

visited[next.y][next.x] = true;

}

}

I create a pool of points on the first tick, so the same coodrinates are always the same object, no garbage. Directions are something like this: (UP(0, 1), RIGHT(1, 0), DOWN(0, -1), LEFT(-1, 0)). ArrayDeque has circular array implementation in java, so it is fast. This code is for floodfill, but pathfinding is the same. We can jast add HashMap, or two dimential array to trace the path.