Bug 597 - The ending point for which A* should find a path is null
Summary: The ending point for which A* should find a path is null
Status: RESOLVED FIXED
Alias: None
Product: Group14-Pacman
Classification: Unclassified
Component: Game (show other bugs)
Version: 0.0.2
Hardware: PC Windows
: High major
Assignee: YANG Tianxia
URL:
Depends on:
Blocks:
 
Reported: 2021-11-21 01:27 HKT by Aleksa
Modified: 2021-12-06 22:57 HKT (History)
1 user (show)

See Also:

Attachments
Test case which revealed that method Tuple BFS(Tuple, ArrayList<Direction>) is buggy (299 bytes, text/plain)
2021-11-21 01:33 HKT, Aleksa 		Details
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Aleksa 2021-11-21 01:27:35 HKT 
I ran Main.java and input a sequence of movement commands until I got a console like this:
 

* is PacMan's starting position
P is PacMan

W W W W W W W W W W W W W W W W W W W W W W W W W W W W W
W F F F F F F F F F F F F F F F F F F F F F F F F F F F W 
W F W W W W W W W W W W F W W W F W W W W W W W W W W F W
W F W W W W W W W W W W F W W W F W W W W W W W W W W F W 
W F W W W W W W W F F F F W W W F F F F W W W W W W W F W 
W F F F F F F F W F W W W W W W W W W F W F F F F F F F W
W W W W W W W F W F W W W W W W W W W F W F W W W W W W W 
            W F W F W W W W W W W W W F W F W
            W F F F F F F F F F F F F F F F W
            W F W F W W W W W W W W W F W F W
      W W W W P W F W W W W W W W W W F W F W W W W
      W         W F W W W W W W W W W F W F F F F W
      W   W W W W F F F F F F F F F F F W W W W F W
  W W W   W W W W F W W W W B W W W W F W W W W F W W W
  W     R F F F F I W         O     W F F F F F F F F W
  W   W W W F W W F W               W F W W F W W W F W
  W   W W W F W W F W               W F W W F W W W F W
  W       W F W W F W W W W W W W W W F W W F W F F F W
  W W W   W F W W F F       * F F F F F W W F W F W W W
      W   W F W W W W   W W W W W F W W W W F W F W
W W W W   W F W W W W   W W W W W F W W W W F W F W W W W
W F F F                 W W W W W F F F F F F F F F F F W
W W W W F W W W W F W W W W W W W W W F W W W W F W W W W
      W F W W W W F W W W W W W W W W F W W W W F W
      W F W F F F F F F F F F F F F F F F F F W F W
      W F W F W W W W F W W W W W F W W W W F W F W
  W W W F W F W W W W F W W W W W F W W W W F W F W W W
  W F F F F F W W F F F W W W W W F F F W W F F F F F W
  W F W W W F W W F W W W W W W W W W F W W F W W W F W
  W F W W W F W W F W W W W W W W W W F W W F W W W F W
  W F F F F F W W F F F F F F F F F F F W W F F F F F W
  W W W W W W W W W W W W W W W W W W W W W W W W W W W

Now, the Eclipse threw an exception:
Exception in thread "main" java.lang.NullPointerException
        at Game.Tuple.distance(Tuple.java:67)
        at Game.A_star.getPath(A_star.java:50)
        at Game.A_star.getNextDirection(A_star.java:167)
        at Game.Ghost.moveToTarget(Ghost.java:119)
        at Game.ChasePatrol.behave(ChasePatrol.java:40)
        at Game.Game.moveGhosts(Game.java:174)
        at Game.Game.handleMovements(Game.java:114)
        at Game.Game.gameTick(Game.java:61)
        at Game.Main.main(Main.java:30)

It looks that the A* star had to calculate a path where the ending position was null
Comment 1 Aleksa 2021-11-21 01:33:24 HKT 
Created attachment 95 [details]
Test case which revealed that method Tuple BFS(Tuple, ArrayList<Direction>) is buggy
Comment 2 Aleksa 2021-11-21 01:42:09 HKT 
Solution: BFS() should not stop when a tile is surrounded by all walls. Instead, it should keep searching for a reachable goal (for A*). Thus, when we pop a node from the queue, we do not check whether his children are walls, we just put them in the queue.