Mirage Source

Well, since I dont know if old posts from old forums will be backed up back I'll continue the discusion we were having on the old forums. I prepared this post to post on Xackery Topic and I'll post it here:

A while ago I PM Xackery telling a few things, I'll rewrite them here.

BFS is simple, but before the explenation about the BFS I need to explain what are graphs. Graphs are modeling structures that can... modelate something xD They have 2 basics things: Edge and Vertex.
So a graph is build of an amount of Edges and Vertex. A Vertex is like a computer on a network. And the lan cable between each computer is an Edge. We can modelate anything like this. So, our mirage maps can be modelated as a graph. Its simple. Each square is a Vertex and if you can move from vertex X to vertex Y you have an Edge between them.
Lets see how our maps are now:

0 1 2 3

0 0 0 0 0
1 0 0 0 0
2 0 0 0 0
3 0 0 0 0

This is how our maps are now. Each 0 is the square.
So to modelate our map as a graph it should look like this:

0 1 2 3

0 0 1 2 3
1 4 5 6 7
2 8 9 10 11
3 12 13 14 15

Each Edge has a number, an identification number. So going from position 0,0 to 3,3 is the same as going from edge 0 to edge 15.

This is basicly what a graph is. Now, the BFS algorithm search to an edge on a graph. Graphs actualy does not need to look like this. I used to study graphs using this one:


Lets use this one to explain how BFS works. We'll go from vertex 1 to vertex 7. On the beggining, the For look if vertex 7 is connected to vertex I(from the for), if it is, it add that vertex to a line. The line start with only vertex 7, so it is like this:

7

In this case, our next number on the line will be 5, couse the for will use it first and it has a connection to vertex 7. Now it will mark it on an other array, only to make sure you dont look at that vertice again. Now the line will look like this:

7
5

Then it will do the for again, it will find vertex 2, couse it is connected to vertex 5. Our line is like this:

7
5
2

Then it will search again, now vertex 1, which is our initial vertex is connected to the end of the line, so the algorithm stops and thats our path from vertex 1 to 7:

7
5
2
1

Thats a simple explanation about ghaphs and BFS. This is enougth to understand and I think that a lot of programers from here can already do their own AI. Good luck ^^