AI - Artificial Inteligence

[Dragoons Master]

I would like to continue talking about this w/ the community so I'll quote this post from the old forums

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 ^^

Actualy, I used the same system to build Mouse Movement, so player's can move w/ mouse ^^

[Misunderstood]

I did this too(in KoC), though I used a slightly different algorithm. I remember us talking about it on the other forums. Well I did the mouse movement, I didn't get to change the npcs movement, but it wouldn't be that hard.

[Krloz]

Sry but I dont get it

[Misunderstood]

right now npc searching sucks. You could be on the other side of several blocks, like around a table, with the npc on the other side, and he could never get to you. This makes it more advanced, allowing the npc to actually get to you. Its kinda complicated.

[Dragoons Master]

Well, I'll try to explain better. Look at this:


This is a simple graph. Graphs are made of vertexes(the dots) and edges(the lines). Mirage's map can be consider a graph, but a very specific graph becouse all vertex havefrom 2 to 4 edges(connections, and most of them have 4):

We can say that a distance from vertex(1) and vertex(13) is 4, becouse that's the shortest path between them going thru other vertexes. For a human, to find this path is prety easy becouse this graph is veeery simple, and for a computer its even easier. You have a few algorithms to do that. I think that BFS(Breadth-first search) is the best on for our case, becouse an other thing tha make this graphs very unique is that the edges have all value 1, graph's edges can have any value, even

[Krloz]

Ah I see and I think this will be a bit hard

[Obsidian]

there was a link on the other forums to a much better algorithm that i was going to start trying to convert over for my MS game.

If i end up doing it, i'll release a tutorial on it, so it can be included in future versions of MSE, because it is a pretty needed thing.