Bug 597

Summary:	The ending point for which A* should find a path is null
Product:	Group14-Pacman	Reporter:	Aleksa <ajelaca2-c>
Component:	Game	Assignee:	YANG Tianxia <tianxyang3-c>
Status:	RESOLVED FIXED
Severity:	major	CC:	tianxyang3-c
Priority:	High
Version:	0.0.2
Hardware:	PC
OS:	Windows
Attachments:	Test case which revealed that method Tuple BFS(Tuple, ArrayList<Direction>) is buggy

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.