We were unable to load Disqus. If you are a moderator please see our troubleshooting guide.

oreshnik • 9 months ago

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.

ThomasNicoullaud • 1 year ago

nice post thx MSmits