**Difficulty: 5/5**

Need to understand!

Need to understand!

**19/07/2007**

**I strongly suggest that it you are going to try to make this tutorial, READ ALL THE THINGS AT THE LINKS INSIDE THIS TUTORIAL!!!**

**AND BACKUP YOUR SOURCE!!!!**

Well, initially, I'd like to thank William for this opportunity and I think this is going to be a great tutorial. The idea of this tutorial is to improve the AI(Artificial Intelligence) of your Mirage Source game. The actual AI is very dumb and it can easily miss the target, not going through the correct/best path. What I did was replace the hole AI with a better code. Let's examine the actual code(that's inside 2 loops, the main is looping the maps and the second is for each MapNpc):

Code:

```
' /////////////////////////////////////////////
' // This is used for NPC walking/targetting //
' /////////////////////////////////////////////
' Make sure theres a npc with the map
If Map(y).Npc(x) > 0 And MapNpc(y, x).Num > 0 Then
Target = MapNpc(y, x).Target
' Check to see if its time for the npc to walk
If Npc(NpcNum).Behavior <> NPC_BEHAVIOR_SHOPKEEPER Then
' Check to see if we are following a player or not
If Target > 0 Then
' Check if the player is even playing, if so follow'm
If IsPlaying(Target) And GetPlayerMap(Target) = y Then
DidWalk = False
i = Int(Rnd * 5)
```

Code:

```
' Lets move the npc
Select Case i
Case 0
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
Case 1
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
Case 2
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
Case 3
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
End Select
```

Code:

```
' Check if we can't move and if player is behind something and if we can just switch dirs
If Not DidWalk Then
If MapNpc(y, x).x - 1 = GetPlayerX(Target) And MapNpc(y, x).y = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_LEFT Then
Call NpcDir(y, x, DIR_LEFT)
End If
DidWalk = True
End If
If MapNpc(y, x).x + 1 = GetPlayerX(Target) And MapNpc(y, x).y = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_RIGHT Then
Call NpcDir(y, x, DIR_RIGHT)
End If
DidWalk = True
End If
If MapNpc(y, x).x = GetPlayerX(Target) And MapNpc(y, x).y - 1 = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_UP Then
Call NpcDir(y, x, DIR_UP)
End If
DidWalk = True
End If
If MapNpc(y, x).x = GetPlayerX(Target) And MapNpc(y, x).y + 1 = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_DOWN Then
Call NpcDir(y, x, DIR_DOWN)
End If
DidWalk = True
End If
' We could not move so player must be behind something, walk randomly.
If Not DidWalk Then
i = Int(Rnd * 2)
If i = 1 Then
i = Int(Rnd * 4)
If CanNpcMove(y, x, i) Then
Call NpcMove(y, x, i, MOVING_WALKING)
End If
End If
End If
End If
```

Code:

```
Else
MapNpc(y, x).Target = 0
End If
Else
i = Int(Rnd * 4)
If i = 1 Then
i = Int(Rnd * 4)
If CanNpcMove(y, x, i) Then
Call NpcMove(y, x, i, MOVING_WALKING)
End If
End If
```

Code:

```
End If
End If
End If
```

This is a Screen Shot I've taken from a simple MSE map attached with this little balls and lines connecting the tiles that you can move from one to an other. That's basically a graph... a little bit simplified.

(take a look at <!-- m --><a class="postlink" href="http://en.wikipedia.org/wiki/Graph_theory">http://en.wikipedia.org/wiki/Graph_theory</a><!-- m --> and <!-- m --><a class="postlink" href="http://en.wikipedia.org/wiki/Graph_%28data_structure%29">http://en.wikipedia.org/wiki/Graph_%28data_structure%29</a><!-- m -->)

**20/07/2007**

If you read all the links and didn't understand anything or you are still missing something on your mind,

**READ IT AGAIN or ask for someone's help**. Don't go further if you don't understand the things before this!

Well, now I'm going to talk about this graph and how the heck this is going to help us out with the AI.

What I did was showing you guys how this graph is represented on a visual world, but there is no such thing in programing so we need to store this data somewhere, somehow.

For this, I numerated each vertex and made a big matrix that holds the information of the connections. That's named adjacency matrix(<!-- m --><a class="postlink" href="http://en.wikipedia.org/wiki/Graph_%28data_structure%29#Choices_of_representation">http://en.wikipedia.org/wiki/Graph_%28d ... esentation</a><!-- m -->). It's like this: we create a matrix NxN(N being the number of vertices we hold, in our case, (MAX_MAPX + 1) * (MAX_MAPY + 1) and fill it with zeros. Then we check if we can move directly from tile X to tile Y(X and Y is the tile number, the enumerated tiles), we just make matrix(X, Y) = 1. So if we look at the matrix and there is a 1 at position (3, 8), it means that we can move from tile 3 to tile 8. But we want our npc to move both ways so we make the same thing but from Y to X, like this matrix(Y, X) = 1.

Considering we already have this adjacency matrix filled with our data, we need now to find the shortest path from point A to point B and that's where the magic is, the BFS algorithm, Breadth-First Search algorithm(<!-- m --><a class="postlink" href="http://en.wikipedia.org/wiki/Breadth-first_search">http://en.wikipedia.org/wiki/Breadth-first_search</a><!-- m -->).

This is where the important thing happens, and the hard part too... This algorithm searches for the shortest path between vertex A and vertex B. By doing this, it loops thru all the vertices, starting from the end. So it's just like we do to find the correct path in a puzzle game. Instead of starting from the real start, we start from the end and tries to find the path, at least I do that xD. The BFS algorithm is quite easy to implement and there are not much problems, so I'll start to do it now. Focus on this because it's all the magic happening.

First, we need our adjacency matrix declared, let's do that inside

**modGeneral**header.

Code:

```
' Used for AI
Public NV As Integer ' Number of Vertices
Public Mat() As Byte ' Our Adjacency Matrix
```

Under

Code:

`Call SpawnAllMapNpcs`

Code:

```
NV = (MAX_MAPX + 1) * (MAX_MAPY + 1) - 1
ReDim Mat(0 To NV, 0 To NV) As Byte
```

Inside GameAI Sub, remove all this code:

Code:

```
i = Int(Rnd * 5)
' Lets move the npc
Select Case i
Case 0
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
Case 1
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
Case 2
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
Case 3
' Left
If MapNpc(y, x).x > GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
End If
' Right
If MapNpc(y, x).x < GetPlayerX(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
' Up
If MapNpc(y, x).y > GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
End If
' Down
If MapNpc(y, x).y < GetPlayerY(Target) And DidWalk = False Then
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
End If
End Select
```

Code:

```
' /////////////////////////////////////////////
' // This is used for NPC walking/targetting //
' /////////////////////////////////////////////
' Make sure theres a npc with the map
If Map(Y).Npc(X) > 0 And MapNpc(Y, X).num > 0 Then
Target = MapNpc(Y, X).Target
' Check to see if its time for the npc to walk
If Npc(NpcNum).Behavior <> NPC_BEHAVIOR_SHOPKEEPER Then
' Check to see if we are following a player or not
If Target > 0 Then
' Check if the player is even playing, if so follow'm
If IsPlaying(Target) And GetPlayerMap(Target) = Y Then
DidWalk = False
```

Code:

```
' /////////////////////////////////////////////
' // This is used for NPC walking/targetting //
' /////////////////////////////////////////////
' Make sure theres a npc with the map
If Map(y).Npc(x) > 0 And MapNpc(y, x).Num > 0 Then
Target = MapNpc(y, x).Target
' Check to see if its time for the npc to walk
If Npc(NpcNum).Behavior <> NPC_BEHAVIOR_SHOPKEEPER Then
' Check to see if we are following a player or not
If Target > 0 Then
' Check if the player is even playing, if so follow'm
If IsPlaying(Target) And GetPlayerMap(Target) = y Then
DidWalk = False
' Check if we can't move and if player is behind something and if we can just switch dirs
If Not DidWalk Then
If MapNpc(y, x).x - 1 = GetPlayerX(Target) And MapNpc(y, x).y = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_LEFT Then
Call NpcDir(y, x, DIR_LEFT)
End If
DidWalk = True
End If
If MapNpc(y, x).x + 1 = GetPlayerX(Target) And MapNpc(y, x).y = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_RIGHT Then
Call NpcDir(y, x, DIR_RIGHT)
End If
DidWalk = True
End If
If MapNpc(y, x).x = GetPlayerX(Target) And MapNpc(y, x).y - 1 = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_UP Then
Call NpcDir(y, x, DIR_UP)
End If
DidWalk = True
End If
If MapNpc(y, x).x = GetPlayerX(Target) And MapNpc(y, x).y + 1 = GetPlayerY(Target) Then
If MapNpc(y, x).Dir <> DIR_DOWN Then
Call NpcDir(y, x, DIR_DOWN)
End If
DidWalk = True
End If
' We could not move so player must be behind something, walk randomly.
If Not DidWalk Then
i = Int(Rnd * 2)
If i = 1 Then
i = Int(Rnd * 4)
If CanNpcMove(y, x, i) Then
Call NpcMove(y, x, i, MOVING_WALKING)
End If
End If
End If
End If
Else
MapNpc(y, x).Target = 0
End If
Else
i = Int(Rnd * 4)
If i = 1 Then
i = Int(Rnd * 4)
If CanNpcMove(y, x, i) Then
Call NpcMove(y, x, i, MOVING_WALKING)
End If
End If
End If
End If
End If
```

Code:

`DidWalk = False`

Code:

```
CloseToPlayer = False
If (GetPlayerY(Target) + 1 = MapNpc(y, x).y) And (GetPlayerX(Target) = MapNpc(y, x).x) Then
CloseToPlayer = True
Else
If (GetPlayerY(Target) - 1 = MapNpc(y, x).y) And (GetPlayerX(Target) = MapNpc(y, x).x) Then
CloseToPlayer = True
Else
If (GetPlayerY(Target) = MapNpc(y, x).y) And (GetPlayerX(Target) + 1 = MapNpc(y, x).x) Then
CloseToPlayer = True
Else
If (GetPlayerY(Target) = MapNpc(y, x).y) And (GetPlayerX(Target) - 1 = MapNpc(y, x).x) Then
CloseToPlayer = True
End If
End If
End If
End If
```

Code:

`Dim CloseToPlayer As Boolean`

Now add an If to make sure the npc is not close to the player, like this:

Code:

```
If Not CloseToPlayer Then
End If
```

Here it is. Took me a while of time to make this, with all the numbers xD

Well, now we can perfectly see that the npc(the pink thing) need to go from vertex 153 to vertex 51(the player).

If we where using the old AI it maybe(maybe) could go to vertex 53 but it's random, so it could also go only to 57 and stay there xD. The AI we are making here will literally be a genius. It will find the best path from vertex 153 to 51 and save this path into a vector. A vector? Wait, we didn't declared this vector! We'll need it! So come back to modGeneral's header and add this 3 variables

Code:

```
Public Marked() As Byte
Public PathLine() As Integer
Public Path() As Integer
```

Code:

` ReDim Mat(0 To NV, 0 To NV) As Byte`

Code:

```
ReDim Marked(0 To NV) As Byte
ReDim PathLine(0 To NV) As Integer
ReDim Path(0 To NV) As Integer
```

Marked vector will store the information about the vertices we've already walked thru(a correct tile, that's part of the algorithm), PathLine will also store information that's part of the algorithm, we always add the tile we found(remember, destiny to origin(B->A)) to the PathLine. When the PathLine(o) is filed with information, doesn't mather when, the first time this is done, then we have the best path(it means we have it all).

That's complicated, it's how the algorithm works.

Now we need to store the information about where we are and where we want to go. For this we create 2 new variables, "o"(Origin) and "d"(Destiny). Create them at the top of GameAI Sub:

Code:

```
Dim o As Long
Dim d As Long
```

Code:

```
o = MapNpc(Y, X).Y * (MAX_MAPX + 1) + MapNpc(Y, X).X
d = GetPlayerY(Target) * (MAX_MAPX + 1) + GetPlayerX(Target)
```

Code:

```
For i = 0 To NV
Marked(i) = 0
PathLine(i) = -1
Path(i) = -1
Next i
```

Code:

```
For i = 0 To NV
VY = Int(i / (MAX_MAPX + 1))
VX = i Mod (MAX_MAPX + 1)
If VX >= 0 And VX < MAX_MAPX Then Mat(i, i + 1) = 1
If VX > 0 And VX <= MAX_MAPX Then Mat(i, i - 1) = 1
If VY >= 0 And VY < MAX_MAPY Then Mat(i, i + MAX_MAPX + 1) = 1
If VY > 0 And VY <= MAX_MAPY Then Mat(i, i - MAX_MAPX - 1) = 1
Next i
```

Code:

```
Dim VX As Integer
Dim VY As Integer
```

Code:

```
For i = 0 To NV
VY = Int(i / (MAX_MAPX + 1))
VX = i Mod (MAX_MAPX + 1)
If (Map(y).Tile(VX, VY).Type = TILE_TYPE_BLOCKED Or Map(y).Tile(VX, VY).Type = TILE_TYPE_NPCAVOID Or Map(y).Tile(VX, VY).Type = TILE_TYPE_WARP Or (Map(y).Tile(VX, VY).Type = TILE_TYPE_KEY And TempTile(y).DoorOpen(VX, VY) = NO)) Then
For J = 0 To NV
Mat(J, i) = 0
Mat(i, J) = 0
Next J
End If
For J = 1 To MAX_PLAYERS
If IsPlaying(J) Then
If GetPlayerMap(J) = y Then
If GetPlayerX(J) = VX And GetPlayerY(J) = VY And J <> Target Then
For K = 0 To NV
Mat(i, K) = 0
Mat(K, i) = 0
Next K
End If
End If
End If
Next J
For J = 1 To MAX_MAP_NPCS
If Map(y).Npc(J) > 0 And MapNpc(y, J).Num > 0 Then
If MapNpc(y, J).x = VX And MapNpc(y, J).y = VY And J <> x Then
For K = 0 To NV
Mat(i, K) = 0
Mat(K, i) = 0
Next K
End If
End If
Next J
Next i
```

Code:

```
Dim J As Integer
Dim K As Integer
```

Code:

`' Check if we can't move and if player is behind something and if we can just switch dirs`

**make sure you understand ALL OF IT until now. I really mean ALL!!!**

**21/07/2007**

Now we are going to make the magic happens! The search happens inside a while so we need a flag to warn the while to exit the repeating process, a flag to exit the while. We also need two more variables, Start and Finish that stores the information about the first and the last path tile we are at the moment. So declare them all at the header of GameAI Sub, like this:

Code:

```
Dim Flag As Byte
Dim Start As Long
Dim Finish As Long
```

Code:

```
Flag = 0
PathLine(0) = d
Start = 0
Finish = 1
```

Code:

```
If o <> d Then
End If
```

Code:

```
While (PathLine(Start) <> -1 And Flag = 0)
Wend
```

Code:

```
For i = 0 To NV
If Mat(PathLine(Start), i) = 1 And PathLine(Start) <> i And Marked(i) = 0 And Flag = 0 Then
Path(i) = PathLine(Start)
PathLine(Finish) = i
Marked(i) = 1
Finish = Finish + 1
If PathLine(Finish - 1) = o Then
Flag = 1
End If
End If
If i = NV Then
Marked(PathLine(Start)) = 1
PathLine(Start) = -1
Start = Start + 1
End If
Next i
```

Continuing...

**Once again, if you are not understanding what is happening here, RE-MAKE THE TUTORIAL!!!**

Now, we can keep going...

We need now a way to make the computer understands that if we need to move from vertex x to x+1 we need to go right and if we want to move from vertex x to x+max_mapx+1 we need to go down, etc... That's quite simple if you understand what you are doing. The AI may not found a path, but only if really there is no path to the player. We need to check this, and for this we use the Flag variable, if it's 1 then we found our path, else we didn't and just walk randomly. Use this If statement :

Code:

` If Flag = 1 Then`

Code:

```
VY = Int(Path(o) / (MAX_MAPX + 1))
VX = Path(o) Mod (MAX_MAPX + 1)
DoEvents
```

Code:

```
If MapNpc(y, x).y > VY Then
If CanNpcMove(y, x, DIR_UP) Then
Call NpcMove(y, x, DIR_UP, MOVING_WALKING)
DidWalk = True
End If
ElseIf MapNpc(y, x).y < VY Then
' Down
If CanNpcMove(y, x, DIR_DOWN) Then
Call NpcMove(y, x, DIR_DOWN, MOVING_WALKING)
DidWalk = True
End If
ElseIf MapNpc(y, x).x > VX Then
' Left
If CanNpcMove(y, x, DIR_LEFT) Then
Call NpcMove(y, x, DIR_LEFT, MOVING_WALKING)
DidWalk = True
End If
ElseIf MapNpc(y, x).x < VX Then
' Right
If CanNpcMove(y, x, DIR_RIGHT) Then
Call NpcMove(y, x, DIR_RIGHT, MOVING_WALKING)
DidWalk = True
End If
End If
```

**DONE!**Now it should work, run your game and take a look at the AI. Make a simple puzzle at the map and add a attack on sight npc, with a big range of sight. Just great, it should be working by now! But there really are a lot of improvements that needs to be done, and I really mean it. If you use this code right now, we won't be able to play, I mean, you will, but with a lot of players and a lot of npcs, just impossible, the npcs will have too much lag...

For fixing this, we will improve a LOT this code. what we are going to do is replace the:

Code:

`For i = 0 To NV`

Code:

```
For J = 0 To NV
Mat(J, i) = 0
Mat(i, J) = 0
Next J
```

Code:

```
Mat(J, i) = 0
Mat(i, J) = 0
```

Code:

```
If VX >= 0 And VX < MAX_MAPX Then Mat(i, i + 1) = 0
If VX > 0 And VX <= MAX_MAPX Then Mat(i, i - 1) = 0
If VY >= 0 And VY < MAX_MAPY Then Mat(i, i + MAX_MAPX + 1) = 0
If VY > 0 And VY <= MAX_MAPY Then Mat(i, i - MAX_MAPX - 1) = 0
```

Code:

```
For K = 0 To NV
Mat(i, K) = 0
Mat(K, i) = 0
Next K
```

Replace all the code that's inside the While with this:

Code:

```
VY = Int(PathLine(Start) / (MAX_MAPX + 1))
VX = PathLine(Start) Mod (MAX_MAPX + 1)
If VY >= 0 And VY < MAX_MAPY Then
If Mat(PathLine(Start), PathLine(Start) + MAX_MAPX + 1) = 1 And Marked(PathLine(Start) + MAX_MAPX + 1) = 0 And Flag = 0 Then
Path(PathLine(Start) + MAX_MAPX + 1) = PathLine(Start)
PathLine(Finish) = PathLine(Start) + MAX_MAPX + 1
Marked(PathLine(Start) + MAX_MAPX + 1) = 1
Finish = Finish + 1
If PathLine(Finish - 1) = o Then
Flag = 1
End If
End If
End If
VY = Int(PathLine(Start) / (MAX_MAPX + 1))
VX = PathLine(Start) Mod (MAX_MAPX + 1)
If VX > 0 And VX <= MAX_MAPX Then
If Mat(PathLine(Start), PathLine(Start) - 1) = 1 And Marked(PathLine(Start) - 1) = 0 And Flag = 0 Then
Path(PathLine(Start) - 1) = PathLine(Start)
PathLine(Finish) = PathLine(Start) - 1
Marked(PathLine(Start) - 1) = 1
Finish = Finish + 1
If PathLine(Finish - 1) = o Then
Flag = 1
End If
End If
End If
VY = Int(PathLine(Start) / (MAX_MAPX + 1))
VX = PathLine(Start) Mod (MAX_MAPX + 1)
If VX >= 0 And VX < MAX_MAPX Then
If Mat(PathLine(Start), PathLine(Start) + 1) = 1 And Marked(PathLine(Start) + 1) = 0 And Flag = 0 Then
Path(PathLine(Start) + 1) = PathLine(Start)
PathLine(Finish) = PathLine(Start) + 1
Marked(PathLine(Start) + 1) = 1
Finish = Finish + 1
If PathLine(Finish - 1) = o Then
Flag = 1
End If
End If
End If
VY = Int(PathLine(Start) / (MAX_MAPX + 1))
VX = PathLine(Start) Mod (MAX_MAPX + 1)
If VY > 0 And VY <= MAX_MAPY Then
If Mat(PathLine(Start), PathLine(Start) - MAX_MAPX - 1) = 1 And Marked(PathLine(Start) - MAX_MAPX - 1) = 0 And Flag = 0 Then
Path(PathLine(Start) - MAX_MAPX - 1) = PathLine(Start)
PathLine(Finish) = PathLine(Start) - MAX_MAPX - 1
Marked(PathLine(Start) - MAX_MAPX - 1) = 1
Finish = Finish + 1
If PathLine(Finish - 1) = o Then
Flag = 1
End If
End If
End If
Marked(PathLine(Start)) = 1
PathLine(Start) = -1
Start = Start + 1
```

**FINISHED**