Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

### 2018-05-02 Maze Frontier

posted May 2, 2018, 10:20 AM by Konstantinovich Samuel
Reminder:
Practice Exam 2, bring in on Monday.

Exam next week (Friday):
multiple choice only
general java stuff (studied already for the AP)
Stacks, Queues, Trees, Heaps

Goal: Frontier Based Maze Solver

Frontier: a list of yet-to-be-explored locations.
You can add to the frontier, or get (and remove) the next element.

Q
How does the frontier grow in the maze solver we wrote before?
What locations are added to this frontier, and what order are they processed?

Example:

s _ _ _ _

_ # # # e

_ _ _ # _

_ # _ # _

_ _ # # _

_ A B C D

E # # # F

G H I # J

K # L # M

N O # # P

Our frontier was treated like a ______.

How does a frontier solver work?

done = false
Initialize your frontier with the starting node
while not done and not empty:
get next node from the frontier
if you found the end:
done = true
else:
process that node (which adds new nodes to the frontier)
if done:
you solved it
else:
no solution

Q
How can we change the way the frontier is processed?
Instead of a ____ we can use a ____

What would happen if we did this?
Draw the sample maze:

_ A B C D

E # # # F

G H I # J

K # L # M

N O # # P

Try the alternate form of the frontier. What is the resulting pattern?

Now we must design a data structure to have the ability to process nodes in 2 different ways.
What java construct allows a single set of methods to behave in different ways?

HW: Design the UML diagram for this maze solver.

Preliminary Results up to 8:
Lab 8: less than 8 with no fails means your add end / beginning was non-constant.

 OSIS PASS / 46 FAIL / 46 05PASS 05FAIL 05#lin 06PASS 06FAIL 06#lin 07PASS 07FAIL 07#lin 08PASS 08FAIL 08#lin 208652602 46 0 20 0 23 10 0 11 10 0 11 6 0 7 208824680 46 0 20 0 23 10 0 11 10 0 11 6 0 7 208817148 46 0 20 0 23 10 0 11 10 0 11 6 0 7 211521372 46 0 20 0 23 10 0 11 10 0 11 6 0 7 213149834 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209314327 46 0 20 0 23 10 0 11 10 0 11 6 0 7 214700411 46 0 20 0 23 10 0 11 10 0 11 6 0 7 214586992 46 0 20 0 23 10 0 11 10 0 11 6 0 7 214269698 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209062025 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209180272 46 0 20 0 23 10 0 11 10 0 11 6 0 7 208974055 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209563600 46 0 20 0 23 10 0 11 10 0 11 6 0 7 208979344 46 0 20 0 23 10 0 11 10 0 11 6 0 7 236729943 46 0 20 0 23 10 0 11 10 0 11 6 0 7 236929352 46 0 20 0 23 10 0 11 10 0 11 6 0 7 219403144 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209343813 46 0 20 0 23 10 0 11 10 0 11 6 0 7 241802008 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209908870 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209152545 46 0 20 0 23 10 0 11 10 0 11 6 0 7 231851098 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209767730 46 0 20 0 23 10 0 11 10 0 11 6 0 7 208891606 46 0 20 0 23 10 0 11 10 0 11 6 0 7 214521304 46 0 20 0 23 10 0 11 10 0 11 6 0 7 209729425 46 0 20 0 23 10 0 11 10 0 11 6 0 7 215543406 46 0 20 0 23 10 0 11 10 0 11 6 0 7 208313379 44 0 20 0 4077 8 0 9 10 0 11 6 0 7 208393082 44 0 20 0 23 10 0 11 10 0 11 4 0 5 209381243 44 0 20 0 23 8 0 9 10 0 11 6 0 7 209319474 44 0 20 0 23 8 0 9 10 0 11 6 0 7 208544494 43 0 20 0 23 10 0 11 10 0 11 3 0 4 209167725 43 0 19 0 22 8 0 9 10 0 11 6 0 7 207695149 43 1 20 0 23 8 0 9 10 0 11 5 1 7 209489475 42 2 18 2 23 10 0 11 10 0 11 4 0 5 208992594 41 0 15 0 18 10 0 11 10 0 11 6 0 7 233536242 40 2 19 1 23 10 0 11 10 0 11 1 1 4 208709410 40 0 20 0 23 10 0 11 10 0 11 0 0 1 207519570 38 0 20 0 23 8 0 9 10 0 11 0 0 1 209262609 38 6 14 6 23 8 0 9 10 0 11 6 0 7 209725308 36 4 16 4 23 10 0 11 4 0 5 6 0 7 214592685 36 0 20 0 23 10 0 11 0 0 1 6 0 7 209682293 36 0 20 0 33 10 0 11 0 0 1 6 0 7 215062944 33 3 10 0 13 10 0 11 10 0 11 3 3 7 208719062 31 13 10 10 23 8 0 9 10 0 11 3 3 7 209343888 31 4 16 4 23 10 0 11 0 0 1 5 0 6 211671136 30 0 20 0 23 2 0 3 2 0 3 6 0 7 208942532 26 0 0 0 3 10 0 11 10 0 11 6 0 7 209322718 22 22 2 18 23 10 0 11 4 4 9 6 0 7 209180512 19 9 11 9 23 2 0 3 0 0 1 6 0 7 207142159 12 4 0 0 3 4 4 9 2 0 3 6 0 7 214466500 12 17 2 17 22 0 0 316 10 0 11 0 0 1 208356410 10 20 1 19 23 0 0 1 8 0 9 1 1 4 213463227 10 0 0 0 3 10 0 11 0 0 1 0 0 1 208781666 3 0 0 0 3 0 0 1 2 0 3 1 0 2 209028257 3 0 0 0 3 0 0 1 2 0 3 1 0 2 209046838 1 0 0 0 3 0 0 1 0 0 1 1 0 2 206939092 0 0 0 0 3 0 0 1 0 0 1 0 0 1 208791855 0 0 0 0 3 0 0 1 0 0 1 0 0 1 214377137 0 0 0 0 3 0 0 1 0 0 1 0 0 1