Introduction

When I entered the Alte Kantonsschule Aarau, I was very excited about the coming matura paper to finish my studies. I had no plan what I’ll write about, but I was very excited.
Due to the fact that I’m very interested in computer science and physics, it was pretty clear that I’d do something in this area.
Furthermore I’m not very interested in theoretical work. So I decided to create a product.
One day, I was discussing with a German mate who and we came through the theme of 3D modeling. So he proposed to build a model of my school. This idea did not just suck, but it was not what I was looking for. I stored the idea in my mind.
As there aren’t any free places to sit outside at anytime, I did not came around, to discuss with my mates about the amount of students and the missing space. We insulted on the large amount of new students that siege all the places all day long.
So finally, there was a theme for my matura paper
I decided to simulate the students, teachers, staff-people, just all the human beings walking around at our school all day long.


Path finding

Today I’d like to introduce you to the path-finding algorithm A* (spoken a-star).
This is he algorithm I’m using for my work with human streams. A real human completes a few path-finding operations a day. When we try to think about the shortest way, this is a path-finding operation. So, actually, this is a really actual theme. We gauge which way is the shortest.
Actually this algorithm does the same. He compares the different Ways to the target and shows us the shortest, what means that the actual distance a human has to go is the shortest. Not the beeline.
Our mind is a very complex construct. Computers are different and not as complex. They just know 0 or 1. And they do not have real intention or the possibility to gauge. So we got a problem. When we think of the shortest way, we can include the direction and all obstacles in our way. A Computer does not know such things. It just sees the start and the end.

To solve this Problem, there is an algorithm, created by Dijkstra, a Dutch computer scientist. When I mention Dijkstra in further content, I’m speaking about his algorithm, not about himself.
But first I’d like to introduce u to graphs.

Each common path-finding algorithm is based on a graph. A graph could look like this:

Graph-Image

The graph contains all the points that are accessible and point – called node in further content – has assigned neighbors to it.
So in lower words, we can say, that the graph contains all walkable ways.

Dijkstra needs this information plus the start-node and the target-node to calculate the shortest way to target.

Dijkstra is an algorithm that always follows the most possible shortest way to target.It picks the nearest node to target, so far and calculates the ways for its neighbors. Then it picks the neighbor with the shortest way to it and calculates new ways for its neighbors. When we reach the target, we got the shortest way. Very simple. Now, this is not the most effective way. Because maybe, we could walk very straight so far. Then we did not have to go many other ways. But it might be, that there will come many shapes in our further path. So maybe we better followed another one.
Because we never know what still is coming, – there might be also an incomplete way, that suddenly stops and we have to go all the way back – A* was invented.

A* can master heuristic. That means it can calculate the hypothetical shortest way to target. To say, it can gauge. That sounds strange – how should a machine master to gauge?
Actually, the algorithm does not really gauge. It just calculates the beeline – there are also a few other options – to target.
This hypothetical way plus the actual way compose the hypothetically shortest path.
With that procedure we can exclude many ways that Dijkstra can’t.
A* is called „an optimized algorithm“ because it just calculates the lowest possible number of possible ways.