Java Simple 2D Grid Pathfinding

Question

I want to code some basic pathfinding for my bot in Java. Below is a 2D grid representation of the 3D world. 0s being the places you can go, and 1s being the places that you cannot go.

int[][] data = {
            {0, 0, 0, 0, 0},
            {0, 0, 1, 0, 1},
            {1, 0, 0, 1, 1},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 0, 1}
    };

How can I write a simple pathfinder in Java, where if I say that I'm currently at (2D coords) and I want to go to (2D coords), it will generate the shortest path there. I don't need a fancy cost system, because each move will have the same cost, and each 1 will have the same danger level. There are already some posts about this online that I've seen, but most of them look a little too overkill for my simple project.

EDIT: The cost can be decided by how many moves are necessary to get to the player. The best path is the shortest; least moves necessary. In the best case scenario, the path finder will return a list of all the coordinates I have to walk on to get to the target.

Thank you for all the help!

Answer 1

This is a typical example of using something like Dijkstra's algorithm or A* to find a path.

Both will work for what you're describing and you can pick either one, there are plenty of online examples of both.

Very simplified the algorithms works by finding the next available step that is available and not yet tried, and then repeating that step until there are no more available steps or the destination is reached.

A simple version might look like:

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class Main {
    public static class Point {
        public int x;
        public int y;
        public Point previous;

        public Point(int x, int y, Point previous) {
            this.x = x;
            this.y = y;
            this.previous = previous;
        }

        @Override
        public String toString() { return String.format("(%d, %d)", x, y); }

        @Override
        public boolean equals(Object o) {
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() { return Objects.hash(x, y); }

        public Point offset(int ox, int oy) { return new Point(x + ox, y + oy, this);  }
    }

    public static boolean IsWalkable(int[][] map, Point point) {
        if (point.y < 0 || point.y > map.length - 1) return false;
        if (point.x < 0 || point.x > map[0].length - 1) return false;
        return map[point.y][point.x] == 0;
    }

    public static List<Point> FindNeighbors(int[][] map, Point point) {
        List<Point> neighbors = new ArrayList<>();
        Point up = point.offset(0,  1);
        Point down = point.offset(0,  -1);
        Point left = point.offset(-1, 0);
        Point right = point.offset(1, 0);
        if (IsWalkable(map, up)) neighbors.add(up);
        if (IsWalkable(map, down)) neighbors.add(down);
        if (IsWalkable(map, left)) neighbors.add(left);
        if (IsWalkable(map, right)) neighbors.add(right);
        return neighbors;
    }

    public static List<Point> FindPath(int[][] map, Point start, Point end) {
        boolean finished = false;
        List<Point> used = new ArrayList<>();
        used.add(start);
        while (!finished) {
            List<Point> newOpen = new ArrayList<>();
            for(int i = 0; i < used.size(); ++i){
                Point point = used.get(i);
                for (Point neighbor : FindNeighbors(map, point)) {
                    if (!used.contains(neighbor) && !newOpen.contains(neighbor)) {
                        newOpen.add(neighbor);
                    }
                }
            }

            for(Point point : newOpen) {
                used.add(point);
                if (end.equals(point)) {
                    finished = true;
                    break;
                }
            }

            if (!finished && newOpen.isEmpty())
                return null;
        }

        List<Point> path = new ArrayList<>();
        Point point = used.get(used.size() - 1);
        while(point.previous != null) {
            path.add(0, point);
            point = point.previous;
        }
        return path;
    }

    public static void main(String[] args) {
        int[][] map = {
                {0, 0, 0, 0, 0},
                {0, 0, 1, 0, 1},
                {1, 0, 0, 1, 1},
                {0, 0, 0, 1, 0},
                {1, 1, 0, 0, 1}
        };

        Point start = new Point(0, 0, null);
        Point end = new Point(3, 4, null);
        List<Point> path = FindPath(map, start, end);
        if (path != null) {
            for (Point point : path) {
                System.out.println(point);
            }
        }
        else
            System.out.println("No path found");
    }
}

The above will print the path as a solution from (0, 0) to (3, 4):

(0, 1)
(1, 1)
(1, 2)
(1, 3)
(2, 3)
(2, 4)
(3, 4)