6
\$\begingroup\$

As a first step to making a PacMan clone, I wrote a Breadth-First Search demonstration that updates itself live as you draw walls and drag around the start and end points. It was inspired by the site that I learned the algorithm through, which has similar demonstrations.

A sample of it:

enter image description here

To use it, use the mouse to drag the start (black) and end (pink) points, or draw on empty space to draw a wall.

My Main Concerns:

  • This is my first crack at a pathfinding algorithm, so I'm sure there is room for improvement. Any tips here would be appreciated!

  • Allowing canvas elements to be dragged was more painful than I though it'd be. I opted to use a global enum member to track what's currently being held, but it feels like a hack. Is there a more standard way of moving non-node elements?

  • Anything else that you think could be improved upon

A Couple Things to Note:

  • This demo is fairly rough around the edges. Attempting to draw out-of-bounds fails silently in the application, but results in a NoSuchElement exception being thrown behind the scenes.

  • The demo code uses a Wall class, but it currently doesn't do anything. Since the application only cares about what cells are occupied and assumes that any occupied cell is a wall, the private member wall can be replaced by any type (A number type for example), and it will still work fine.

FrontierVisual.java:

package pacmanTest;

import java.util.ArrayList;
import java.util.List;
import javafx.application.Application;
import javafx.event.EventHandler;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.input.MouseEvent;
import javafx.scene.layout.BorderPane;
import javafx.scene.paint.Color;
import javafx.scene.text.Font;
import javafx.stage.Stage;
import utils.Duple;
import utils.MainLoop;

/**
 * To record what's currently being dragged
 */
enum DragPoint {
    START, GOAL, NONE
}

public class FrontierVisual
        extends Application {

    private Stage stage;
    private Scene scene;

    private final int areaWidth = 800;
    private final int areaHeight = 800;

    private final double drawScale = 20;

    private Canvas canvas = new Canvas(800, 800);
    private GraphicsContext gc = canvas.getGraphicsContext2D();

    private final Area<Wall> area = new Area<>(areaWidth, areaHeight);
    private final Pathfinder<Wall> pathFinder = new Pathfinder<>(area);

    private Duple<Integer> startPos = new Duple<Integer>(10, 10);
    private Duple<Integer> goalPos = new Duple<Integer>(30, 30);

    private List<Duple<Integer>> path = new ArrayList<>();

    private DragPoint dragging = DragPoint.NONE;

    private final Wall wall = new SolidWall();

    private void drawSquare(Duple<Integer> position, Color color) {
        gc.setFill(color);
        gc.fillRect(position.getX() * drawScale, position.getY() * drawScale, drawScale, drawScale);
    }

    @Override
    public void start(Stage stage) {
        this.stage = stage;

        BorderPane rootNode = new BorderPane();

        scene = new Scene(rootNode);
        stage.setScene(scene);

        rootNode.setCenter(canvas);
        canvas.setOnMousePressed(dragStartHandler);
        canvas.setOnMouseDragged(dragContHandler);
        canvas.setOnMouseReleased(dragStopHandler);

        MainLoop mainLoop = new MainLoop(10000000, t -> {
            utils.Utils.clearCanvas(gc);

            gc.setFont(Font.font(20));
            gc.fillText(dragging.toString(), 10, 30);


            List<Duple<Integer>> path = pathFinder.findPathFromAToB(startPos, goalPos);

            path.stream()
                .forEach( pathPos -> drawSquare(pathPos, Color.BLUE) );

            area.forallNonEmptyCells( (pos, w) -> drawSquare(pos, Color.CHOCOLATE) );

            drawSquare(startPos, Color.BLACK);
            drawSquare(goalPos, Color.PLUM);
        });

        mainLoop.start();

        stage.show();
    }

    public static void main(String[] args) {
        launch(args);
    }

    //Handle the mouse being pressed
    private EventHandler<MouseEvent> dragStartHandler = event -> {
        double x = event.getX() / drawScale;
        double y = event.getY() / drawScale;

        //The amount off the square you can press and still shift focus to the start/goal point
        double dragRadius = 2;

        if (pointIsInCircle(x, y, startPos.getX(), startPos.getY(), dragRadius)) {
            dragging = DragPoint.START;

        } else if (pointIsInCircle(x, y, goalPos.getX(), goalPos.getY(), dragRadius)) {
            dragging = DragPoint.GOAL;

        } else {
            dragging = DragPoint.NONE;
        }

        System.out.println("Drag Started - Dragging: " + dragging.toString());
    };

    //Handle the mouse continuing to be dragged
    private EventHandler<MouseEvent> dragContHandler = event -> {
        int x = (int)(event.getX() / drawScale);
        int y = (int)(event.getY() / drawScale);

        Duple<Integer> newPos = new Duple<Integer>(x, y);

        switch (dragging) {
            case START:
                startPos = newPos;
                break;

            case GOAL:
                goalPos = newPos;
                break;

            case NONE:
                area.setCellAt(x, y, wall); 
                break;
        }
    };

    //Handle the mouse being released
    private EventHandler<MouseEvent> dragStopHandler = event -> {
        dragging = DragPoint.NONE;
    };

    private static boolean pointIsInCircle(double x, double y, double centreX, double centreY, double radius) {
        double  xDiff = x - centreX,
                yDiff = y - centreY;

        return xDiff*xDiff + yDiff*yDiff <= radius*radius;
    }
}

Pathfinder.java:

package pacmanTest;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Date;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.BiConsumer;

import utils.Duple;

public class Pathfinder<T> {

    //To track walls
    Area<T> area;

    public Pathfinder(Area<T> a) {
        area = a;
    }

    /**
     * Preset offsets representing each of the four directions.
     */
    private static final List<Duple<Integer>> fourDirectionOffsets = Collections.unmodifiableList(Arrays.asList(
        new Duple<Integer>(1,0), new Duple<Integer>(-1,0), new Duple<Integer>(0,1), new Duple<Integer>(0,-1) ));

    /**
     * Finds a path from aStart to bGoal, taking into consideration walls
     * 
     * @param aStart The start position
     * @param bGoal The goal position
     * @return A list representing the path from the start to the goal
     */
    public List<Duple<Integer>> findPathFromAToB(Duple<Integer> aStart, Duple<Integer> bGoal) {
        Deque<Duple<Integer>> frontier = new ArrayDeque<>();
        Map<Duple<Integer>, Duple<Integer>> cameFrom = new HashMap<>();

        frontier.push(aStart);

        while (!frontier.isEmpty()) {
            Duple<Integer> current = frontier.pop();

            if (current.equals(bGoal)) break;

            List<Duple<Integer>> neighbors = cellsAround(current, fourDirectionOffsets);

            neighbors.stream()
                .filter(location -> !cameFrom.containsKey(location) && area.cellIsInBounds(location) && area.getCellAt(location) == null)
                .forEach( neighbor -> {
                    frontier.add(neighbor);
                    cameFrom.put(neighbor, current);

                });

        }

        return reconstructPath(cameFrom, aStart, bGoal);
    }

    /**
     * Transforms a backtracking map into a path
     * 
     * @param cameFrom Backtracking map
     * @param start Start position
     * @param goal Goal position
     * @return A list representing the path from the start to the goal
     */
    private static List<Duple<Integer>> reconstructPath(Map<Duple<Integer>, Duple<Integer>> cameFrom, Duple<Integer> start, Duple<Integer> goal) {
        List<Duple<Integer>> path = new ArrayList<>();
        path.add(goal);

        Duple<Integer> current = goal;

        do {
            path.add(current);

            current = cameFrom.get(current);

        } while (current != null && !current.equals(start));

        Collections.reverse(path);

        return path;
    }

    /**
     * Calculates the cells surrounding pos as indicated by the given offsets
     * @param pos The position to find the surrounding cells of
     * @param offsets Positions relative to pos to check
     * @return
     */
    private static List<Duple<Integer>> cellsAround(Duple<Integer> pos, List<Duple<Integer>> offsets) {
        List<Duple<Integer>> surroundingCells = new ArrayList<>();

        offsets.stream()
            .map( offset -> pos.map(offset, (x1, x2) -> x1 + x2) )
            .forEach(surroundingCells::add);

        return surroundingCells;
    }
}

Duple.java:

package utils;

import java.util.function.BinaryOperator;
import java.util.function.UnaryOperator;

/**
 * A simple immutable Duple class where both members are the same type
 * 
 * @author Brendon
 *
 * @param <T> The type of its members
 */
public class Duple<T> {

    private final T xPos;
    private final T yPos;

    public Duple(T x, T y) {
        xPos = x;
        yPos = y;
    }

    public T getX() {
        return xPos;
    }

    public T getY() {
        return yPos;
    }

    /**
     * Applies the function to each member of the Duple
     * @param f The function to apply to each member
     * @return The resulting Position
     */
    public Duple<T> map(UnaryOperator<T> f) {
        return new Duple<T>(f.apply(xPos), f.apply(yPos)); 
    }

    /**
     * Applies the function to this and the other Position
     * @param otherPos The other Position to use
     * @param f A function taking 2 Positions, where the first parameter is a member of this, and the second is a member of otherPos
     * @return The resulting Position
     */
    public Duple<T> map(Duple<T> otherPos, BinaryOperator<T> f) {
        return new Duple<T>(f.apply(xPos, otherPos.xPos), f.apply(yPos, otherPos.yPos)); 
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((xPos == null) ? 0 : xPos.hashCode());
        result = prime * result + ((yPos == null) ? 0 : yPos.hashCode());
        return result;
    }


    @SuppressWarnings("rawtypes")
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        Duple other = (Duple) obj;
        if (xPos == null) {
            if (other.xPos != null) return false;
        } else if (!xPos.equals(other.xPos)) return false;
        if (yPos == null) {
            if (other.yPos != null) return false;
        } else if (!yPos.equals(other.yPos)) return false;
        return true;
    }

    @Override
    public String toString() {
        return "(" + xPos + "," + yPos + ")";
    }

}

MainLoop.java:

package utils;

import java.util.function.Consumer;

import javafx.animation.AnimationTimer;

/**
 * An extension of an {@link AnimationTimer} that allows the user to select their framerate.<p>
 * 
 * Also allows for a more convenient syntax to declare the main loop routine
 * 
 * @author Brendon
 *
 */
public class MainLoop extends AnimationTimer {

    private final long updateGraphicsEvery;

    private final Consumer<Long> doEveryUpdate;

    private long lastTime = IDEALFRAMERATENS;

    /**
     * @param updateEveryNS How often to run the loop.
     * @param f The main-loop body. Its parameter is the number of nanoseconds since the last update.
     */
    public MainLoop(long updateEveryNS, Consumer<Long> f) {
        this.updateGraphicsEvery = updateEveryNS;
        doEveryUpdate = f;
    }

    @Override
    public void handle(long currentTime) {

        long nanosElapsed = currentTime - lastTime;

        if (nanosElapsed < updateGraphicsEvery) {
            return;

        } else {
            lastTime = currentTime;
            doEveryUpdate.accept(nanosElapsed);

        }

    }

    public final static long NANOSPERSECOND = 1000000000;
    public final static long IDEALFRAMERATENS = (long)(1 / 60.0 * NANOSPERSECOND);

}

Utils.java:

package utils;

import java.util.function.Consumer;

import javafx.animation.AnimationTimer;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;

public class Utils {
    private Utils() {

    }

    /**
     * Clears the canvas associated with the given {@link GraphicsContext}
     * 
     * @param gc The associated GraphicsConetext to clear
     */
    public static void clearCanvas(GraphicsContext gc) {
        Canvas c = gc.getCanvas();
        gc.clearRect(0, 0, c.getWidth(), c.getHeight());
    }

}
\$\endgroup\$
2
  • \$\begingroup\$ A minor matter of terminology: your pathfinding algorithm is not A* but rather a BFS (breadth-first search). However, I believe that in your use cases BFS is enough. \$\endgroup\$ – coderodde Oct 20 '15 at 11:52
  • \$\begingroup\$ @coderodde Oh. I'm just following the guide on A*. They might be just opening with BFS as an introduction. Thanks, I'll update the title. \$\endgroup\$ – Carcigenicate Oct 20 '15 at 11:54
4
\$\begingroup\$

Separate Model from Rendering

The FrontierVisual class contains at least two semantically distinct groups of fields:

  1. Visual component related properties, like stage, scene, areaWidth, areaHeight and drawScale.
  2. Virtual space definition, like area, pathFinder, startPos etc.

They should be separated. All JavaFx-related stuff would remain in FrontierVisual class and the model would be better described within a dedicated entity. For small applications like this one, there is probably no need to implement fully the Model-View-Controller pattern, but at least model-view separation would be beneficial, bringing more flexibility and extensibility.

Don't Abuse of Generics

Please look closer at these declarations:

Map<Duple<Integer>, Duple<Integer>> cameFrom = ...
List<Duple<Integer>> path = ...

Do you find this pollution with generics, spread everywhere in the code, useful, readable and aesthetically pleasant?

I guess that what you are trying to do here is to anticipate a probable future replacement of Integers with Doubles and so on.

Update. To reduce this overflow of generics, that may be useful to transform Duple<T> into an abstract class and add a short one that inherits from it with the right numeric type. But I doubt that this is necessary at all. Your virtual space is better defined using integers. Why not just have a Point class with int x, y? That will avoid boxing/unboxing with Integer in many cases.

Similar changes may be done with the other generics used... Genericity is good, of course, but it should be pondered if it's really necessary here.

Consider Using Existing API

The Duple<T> class seems to have a number of features similar to java.awt.Point or javafx.geometry.Point2D. They may be considered for reuse here.

p.s. Please change package names to something that respects Java naming conventions.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you. I've never used the MVC pattern before. Maybe this'll be a good start point to try it. And I'm using a generic Duple because I'm using the same class for all my projects, and most use Double, but you're right, it ends up taking up a lot of extra space. I wish Java had type synonyms. I really don't like the idea of rewriting the entire class just to change the types; to me that almost defeats the purpose of generics in the first place. I didn't know about the existing Point classes, so I'll probably switch to them; I'm sure they have more functionality. \$\endgroup\$ – Carcigenicate Oct 20 '15 at 11:08
  • \$\begingroup\$ And what do you mean my package names don't respect Java conventions? I though the only requirement was that they start with a lower case. \$\endgroup\$ – Carcigenicate Oct 20 '15 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.