Key assumptions for our plain maze router.

I will always expand the cheapest cell next.

I will reach each cell just once. I will expand each cell just once and I'm

guaranteed to find the minimum cost path. Alright, so the cheapest cell next that's

easy. expand each reach each cell once, and

expand each cell once, that seems kind of obvious.

And the fact that I'm gaurenteed to find the minimum cost path, based on, you

know, the fact that this is, basically, an implementation of the Dijkstra

algorithm, that seems good. Here's a very strange question.

What constraints must be true in order for this simple search strategy to

actually get the best path, you know, to actually get the minimum cost path?

Well if I say this to you in a different way is there anything we can do wrong

that can break any of these nice assumptions?

Okay, and the thing that's really quite amazing answers is yes, there really is.

And if you choose to do the program that's associated with this assignment we

will ask you to break things because it's just easier than the implement the case

that doesn't break them. And your going to see it yourself in your

routing benchmarks. So, there is a name for what we're

talking about, for these constraints on the path cost and, and one of the names

is consistency. And what consistency means is that.

I want it to be true that the cost of adding a cell to a path, right, reaching

it, is independent of the path itself. So I don't care how you got to Cell C on

the routing surface. When you get to Cell C on the routing

surface, there's only one pathcost it can be.

And it doesn't depend on the shape of the path in the grid.

Alright, and it turns out that if you have a consistency cost function it

guarantees that you reach every cell once from the cheapest path and you expand

every cell once it will all work. And the thing that's big surprise, is

that its incredibly easy to create a cost scheme that is inconsistent which

violates all these nice properties and which makes good, physical, geometric

sense in a router. So, here it is.

I'm going to put a big star over it. So, I've got my diagram again from the

expanding reaching diagram. It's a little bit more to it.

So there's a pink cell C, I'm sorry, a pink cell B.

Which is on the wavefront and it's being expanded.

And its pathcost is 12, and its predecessor is north, so I, I was reached

from above B. And B is expanding to the east, to touch

C. Reach C expand reach C, and B is

expanding to the south to reach D. And C costs 3 and D costs 3.

So we're expanding B, we're reaching C and D.

Here's the new thing. I'm going to penalize paths with bends.

I'm just going to add another cost whenever you reach a cell that requires

you to turn. And that's actually really easy to tell.

So, I'm just going to draw this sort of the wire.

We know that cell B was reached from north because its predecessor is north.

So the wire that sort of Got to cell B is coming from the north.

If we keep expanding and we go into cell D, that wire is a straight line.

Okay? But if we, you know, expand from cell B,

and we turn and we go into cell C, that is bending.

That's a wire with a bend in it. All right?

And so we're going to penalize that. Now, technically, how do you check if

there's a bend? you look at the predecessor label you're

about to put in the re, in the new cell you're reaching.

And you look at the predecessor of the cell you're expanding.

And if they're different you made a bend. All right?

It's, it's as simple as that. You know, B is the north.

C is going to be a west. Those aren't the same.

And it must be a bend. B is a north.

D is going to be a north. No bend.