[All Versions] A+ Pathfinding for NPCs

[Synergy]

Deathbeam, in future, why don't you make sure the tutorial is working before you post it?

All you need do is take a blank copy of EO or whatever engine this is for and try to implement it then fix any problems. It'd be a much better tutorial than doing a half-arsed job and having to update it ~8 times before it actually works; you can also make it much harder for people who use it before any fixes.

[tslusny]

> Deathbeam, in future, why don't you make sure the tutorial is working before you post it?
>
> All you need do is take a blank copy of EO or whatever engine this is for and try to implement it then fix any problems. It'd be a much better tutorial than doing a half-arsed job and having to update it ~8 times before it actually works; you can also make it much harder for people who use it before any fixes.

Becouse i forgot that i changed names of listing constants and i thought it will 100% work 

[Synergy]

> Becouse i forgot that i changed names of listing constants and i thought it will 100% work 

You _thought_. That's why I said you should test it; it's basic programming to test your code before you publish it…

[Alerd]

Stop already complain .. doing it in his engine …

[Wortel Angels]

> This is pathfinding, not new NPC AI  They will be smart only when they will try to kill you, and not when they are hanging around

Thats logical but he stands most around too if he try to kill me xD

[cjsrch]

Deathbeam your script is causing NPCs to jump from tile to tile instead of moving smoothly when in pursuit in EO3

I installed this shortly after you posted was this one of the bugs found?

is anyone else having this issue?

my code contains this (eo3)

EDIT- I commented out the following and all of its paired end ifs and elses.. seems to do the trick but not sure if it broke somthing else.

So far seems good.. If any one who knows more then me( SO ANYONE) thinks this should be left in please let me know

"'Gonna make the npcs smarter.. Implementing a pathfinding algorithm.. we shall see what happens.

' If IsOneBlockAway(TargetX, TargetY, CLng(MapNpc(MapNum).NPC(x).x), CLng(MapNpc(MapNum).NPC(x).y)) = False Then

' If PathfindingType = 1 Then"

this is also above " ' Check if we can't move and if Target is behind something and if we can just switch dirs

If Not didwalk Then

If MapNpc(MapNum).NPC(x).x - 1 = TargetX And MapNpc(MapNum).NPC(x).y = TargetY Then

If MapNpc(MapNum).NPC(x).Dir <> DIR_LEFT Then

Call NpcDir(MapNum, x, DIR_LEFT)

End If"

could this be the issue i see no mention of this line in your tut

[Scott]

Just started working on this for one of my projects, saved me bunch of time thanks I'll let know when what I think of it/any bugs I may find when I get around to adding it.

[RyokuHasu]

I just applied this (the logic of it) to a VB.net project I was working on, I'll report back the results once i collect sufficient data to prove this works well with a mass swarm.

[Link]

Be sure to give a clear explination of what this does, not everyone knows what it is excluding myself. But make it noob friendly.

[tslusny]

> Deathbeam your script is causing NPCs to jump from tile to tile instead of moving smoothly when in pursuit in EO3
>
> I installed this shortly after you posted was this one of the bugs found?
>
> is anyone else having this issue?
>
> my code contains this (eo3)
>
> EDIT- I commented out the following and all of its paired end ifs and elses.. seems to do the trick but not sure if it broke somthing else.
>
> So far seems good.. If any one who knows more then me( SO ANYONE) thinks this should be left in please let me know
>
> "'Gonna make the npcs smarter.. Implementing a pathfinding algorithm.. we shall see what happens.
>
> ' If IsOneBlockAway(TargetX, TargetY, CLng(MapNpc(MapNum).NPC(x).x), CLng(MapNpc(MapNum).NPC(x).y)) = False Then
>
> ' If PathfindingType = 1 Then"
>
> this is also above " ' Check if we can't move and if Target is behind something and if we can just switch dirs
>
> If Not didwalk Then
>
> If MapNpc(MapNum).NPC(x).x - 1 = TargetX And MapNpc(MapNum).NPC(x).y = TargetY Then
>
> If MapNpc(MapNum).NPC(x).Dir <> DIR_LEFT Then
>
> Call NpcDir(MapNum, x, DIR_LEFT)
>
> End If"
>
> could this be the issue i see no mention of this line in your tut

In EO 3.0 there is already pathfinding lol  But this one is better, so i recommend replacing it.

> Just started working on this for one of my projects, saved me bunch of time thanks I'll let know when what I think of it/any bugs I may find when I get around to adding it.

Good 

> I just applied this (the logic of it) to a VB.net project I was working on, I'll report back the results once i collect sufficient data to prove this works well with a mass swarm.

In VB.net? Wow 

> Be sure to give a clear explination of what this does, not everyone knows what it is excluding myself. But make it noob friendly.

It´s pathfinding, i think everyone will got what it is 

[RyokuHasu]

Yep, a VB.net project. Though its not hard, I just have to convert every line one by one to fit a completely different setup lol

though, I've already taken care of the 1 unit per 1 target, and shortest distance calculations… this will be hard since im doing it for a looping map lol

P.S.... this is going up against a highly efficient BFS path finding sub I made, so lets see what wins =D

[RyokuHasu]

The results are in! This isn't path finding… it's a random bulkier version of the existing "path finding".

I implemented the 2 path finding methods into to other wise identical AIs... And i only implemented it in the bot's ability to find resources.

the results were BFS winning by a landslide due to its ability to seek out resources at an exponential rate while the one using this method bumbled around aimlessly.

The map and resource distribution was symmetrical so each AI had the same opportunities and chances as the other.

I will make a video of the findings and post it shortly, It is my recommendation that you do not use this tutorial as it has little more to offer than the default.

I will also post the exact 2 path finding subs used.

[Ryo]

something like this? 

http://www.youtube.com/watch?v=DINCL5cd_w0

[RyokuHasu]

> something like this? 
>
> -Vid Snip-

Not quite… Though the path-finding that I made is a version of BFS, The point is to test the viability of the one in this tut. An i don't have that tool... so i used some other tools i had XD

~~==============================================================================================~~

Due to an overwhelming case of dyslexia… This data is false, sorry.

~~**My Findings:**

**Video:**

[media]http://www.youtube.com/watch?v=bHjGihRUu5E[/media]

**Summary of Test Conditions:**

-The map and resource distribution was symmetrical so each AI had the same opportunities and chances as the other.

-I will make a video of the findings and post it shortly, It is my recommendation that you do not use this tutorial as it has little more to offer than the default.

-I will also post the exact 2 path finding subs used.

**Death Beam's logic (slightly modified to fit but still the same)**

```

Public Function APlus(ByVal a As Ants, ByVal StartLoc As Location, ByVal EndLoc As Location) As Boolean

Dim Directions() As Direction = {Direction.e, Direction.s, Direction.n, Direction.w}

Dim i As Integer

Dim DidWalk As Boolean

DidWalk = False

i = CInt(Math.Floor(Rnd() * 4))

' Lets move the npc

Select Case i

Case 0

' Up

If StartLoc.Row < EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.n)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.n) Then

Return True

End If

End If

End If

' Down

If StartLoc.Row > EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.s)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.s) Then

Return True

End If

End If

End If

' Left

If StartLoc.Col < EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.w)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.w) Then

Return True

End If

End If

End If

' Right

If StartLoc.Col > EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.e)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.e) Then

Return True

End If

End If

End If

Case 1

' Right

If StartLoc.Col > EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.e)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.e) Then

Return True

End If

End If

End If

' Left

If StartLoc.Col < EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.w)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.w) Then

Return True

End If

End If

End If

' Down

If StartLoc.Row > EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.s)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.s) Then

Return True

End If

End If

End If

' Up

If StartLoc.Row < EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.n)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.n) Then

Return True

End If

End If

End If

Case 2

' Down

If StartLoc.Row > EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.s)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.s) Then

Return True

End If

End If

End If

' Up

If StartLoc.Row < EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.n)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.n) Then

Return True

End If

End If

End If

' Right

If StartLoc.Col > EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.e)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.e) Then

Return True

End If

End If

End If

' Left

If StartLoc.Col < EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.w)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.w) Then

Return True

End If

End If

End If

Case 3

' Left

If StartLoc.Col < EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.w)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.w) Then

Return True

End If

End If

End If

' Right

If StartLoc.Col > EndLoc.Col And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.e)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.e) Then

Return True

End If

End If

End If

' Up

If StartLoc.Row < EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.n)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.n) Then

Return True

End If

End If

End If

' Down

If StartLoc.Row > EndLoc.Row And Not DidWalk Then

Dim CheckDir As Location = a.Destination(StartLoc, Direction.s)

If a.Passable(CheckDir) Then

If DoMoveDirection(a, StartLoc, Direction.s) Then

Return True

End If

End If

End If

End Select

End Function

```

**The BFS that I made:**

```

Private Function BFS(ByVal a As Ants, ByVal StartLoc As Location, ByVal EndLoc As Location) As Boolean

Dim q As Queue(Of Location) = New Queue(Of Location)

Dim Marked As List(Of Location) = New List(Of Location)

Dim Directions() As Direction = {Direction.e, Direction.s, Direction.n, Direction.w}

Dim CurrentTile, LastTile As Location

Dim loops As Integer

q.Enqueue(EndLoc)

Marked.Add(EndLoc)

loops = 0

While (q.Count > 0 And loops < 5)

If a.TimeRemaining < 10 Then

Return False

End If

CurrentTile = q.Dequeue

If CurrentTile.Col = StartLoc.Col And CurrentTile.Row = StartLoc.Row Then

Return False

End If

For Each d As Direction In Directions

Dim CheckDir As Location = a.Destination(CurrentTile, d)

If Not Marked.Contains(CheckDir) Then

If a.Passable(CheckDir) Then

Marked.Add(CheckDir)

q.Enqueue(CheckDir)

End If

End If

Next

LastTile = CurrentTile

loops += 1

End While

Dim directions2 As List(Of Direction) = a.GetDirections(StartLoc, LastTile)

For Each d As Direction In directions2

If DoMoveDirection(a, StartLoc, d) Then

Return True

End If

Next

Return False

End Function

```~~

~~**As you can see there is a clear lack or any path-finding in the A+ side.**~~

[tslusny]

So my pathfinding is not working? I do not understand what you are trying to show in that video  But it is searching for shortest path imo. But i tested it only on small map, so i can be wrong and maybe NPCs are just walking around blocked tiles.

[RyokuHasu]

What I tested was that i set Each AI to seek out food/resources using the 2 different path finding solutions… BFS found the food .. your's didn't.

[tslusny]

> What I tested was that i set Each AI to seek out food/resources using the 2 different path finding solutions… BFS found the food .. your's didn't.

But in my game (RoM) that NPCs will always found me  Ok nevermind, right now i found real A* pathfinding code, so i will try to implement ti 

[abhi2011]

> What I tested was that i set Each AI to seek out food/resources using the 2 different path finding solutions… BFS found the food .. your's didn't.

They are to BFS, Breadth-First-Search which is slow and Best-First-Search which is actually comparatively faster than A*

[tslusny]

> They are to BFS, Breadth-Fast-Search which is slow and Best-Fast-Search which is actually comparatively faster than A*

But A* is da best 

Btw for everyone: This pathfinding is real pathfinding, Ryoku just tested wrong snippet 

[abhi2011]

> But A* is da best 
>
> Btw for everyone: This pathfinding is real pathfinding, Ryoku just tested wrong snippet 

BestFS is comparatively faster.

[cjsrch]

seems like this is causing massive issue when the map is bigger tehn 100 by 100\.

NPCs wont follow or attack and even the random movement they usualy make is slowed or stopped.

id say movement speed by npc drops 100 times over…

any one else have an issue? smaller maps it seems fine on.

At first i thought maybe it was a server issue since i upped all the maximums (1000 max items 500 max maps and 1000 max npcs) but that wasnt causing issues before either.

[tslusny]

I will check it.

[cjsrch]

This is what i current have

I commented out a line and commented out anything to do with it

Npcs move buggy

I added a statement to allow me to turn on and off blocks of code if 1=0 blablabla

the if so i could disable everything after pathfinding.. doing so the npcs will follow and attack… and fast.. but there is no pathfinding..

if i walk around a corner they will get stuck

with it on the npc movement is slowed and seems to fail'

```

' /////////////////////////////////////////////

' // This is used for NPC walking/targetting //

' /////////////////////////////////////////////

' Make sure theres a npc with the map

If Map(mapnum).NPC(x) > 0 And MapNpc(mapnum).NPC(x).Num > 0 Then

If MapNpc(mapnum).NPC(x).StunDuration > 0 Then

' check if we can unstun them

If GetTickCount > MapNpc(mapnum).NPC(x).StunTimer + (MapNpc(mapnum).NPC(x).StunDuration * 1000) Then

MapNpc(mapnum).NPC(x).StunDuration = 0

MapNpc(mapnum).NPC(x).StunTimer = 0

End If

Else

target = MapNpc(mapnum).NPC(x).target

targetType = MapNpc(mapnum).NPC(x).targetType

' Check to see if its time for the npc to walk

If NPC(npcNum).Behaviour <> NPC_BEHAVIOUR_SHOPKEEPER Then

If targetType = 1 Then ' player

' 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) = mapnum Then

didwalk = False

target_verify = True

TargetY = GetPlayerY(target)

TargetX = GetPlayerX(target)

Else

MapNpc(mapnum).NPC(x).targetType = 0 ' clear

MapNpc(mapnum).NPC(x).target = 0

End If

End If

ElseIf targetType = 2 Then 'npc

If target > 0 Then

If MapNpc(mapnum).NPC(target).Num > 0 Then

didwalk = False

target_verify = True

TargetY = MapNpc(mapnum).NPC(target).y

TargetX = MapNpc(mapnum).NPC(target).x

Else

MapNpc(mapnum).NPC(x).targetType = 0 ' clear

MapNpc(mapnum).NPC(x).target = 0

End If

End If

End If

If target_verify Then

' if map has a working matrix, use a* pathfinding

If mapMatrix(mapnum).created Then

If GetPlayerX(target) <> MapNpc(mapnum).NPC(x).TargetX Or GetPlayerY(target) <> MapNpc(mapnum).NPC(x).TargetY Then

' player has moved, re-find the path

MapNpc(mapnum).NPC(x).hasPath = APlus(mapnum, CLng(MapNpc(mapnum).NPC(x).x), CLng(MapNpc(mapnum).NPC(x).y), CLng(GetPlayerX(target)), CLng(GetPlayerY(target)), Void, MapNpc(mapnum).NPC(x).arPath)

' set the npc's cur path location

If MapNpc(mapnum).NPC(x).hasPath Then MapNpc(mapnum).NPC(x).pathLoc = UBound(MapNpc(mapnum).NPC(x).arPath)

End If

' if has path, follow it

If MapNpc(mapnum).NPC(x).hasPath Then

' follow path

NpcMoveAlongPath mapnum, x

didwalk = True

End If

End If

If 0 = 1 Then

'Gonna make the npcs smarter.. Implementing a pathfinding algorithm.. we shall see what happens.

If IsOneBlockAway(TargetX, TargetY, CLng(MapNpc(mapnum).NPC(x).x), CLng(MapNpc(mapnum).NPC(x).y)) = False Then

If PathfindingType = 1 Then

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

If Not didwalk Then

If MapNpc(mapnum).NPC(x).x - 1 = TargetX And MapNpc(mapnum).NPC(x).y = TargetY Then

If MapNpc(mapnum).NPC(x).Dir <> DIR_LEFT Then

Call NpcDir(mapnum, x, DIR_LEFT)

End If

didwalk = True

End If

'

If MapNpc(mapnum).NPC(x).x + 1 = TargetX And MapNpc(mapnum).NPC(x).y = TargetY Then

If MapNpc(mapnum).NPC(x).Dir <> DIR_RIGHT Then

Call NpcDir(mapnum, x, DIR_RIGHT)

End If

didwalk = True

End If

If MapNpc(mapnum).NPC(x).x = TargetX And MapNpc(mapnum).NPC(x).y - 1 = TargetY Then

If MapNpc(mapnum).NPC(x).Dir <> DIR_UP Then

Call NpcDir(mapnum, x, DIR_UP)

End If

didwalk = True

End If

If MapNpc(mapnum).NPC(x).x = TargetX And MapNpc(mapnum).NPC(x).y + 1 = TargetY Then

If MapNpc(mapnum).NPC(x).Dir <> DIR_DOWN Then

Call NpcDir(mapnum, x, DIR_DOWN)

End If

didwalk = True

End If

' We could not move so Target must be behind something, walk randomly.

If Not didwalk Then

i = Int(Rnd * 2)

If i = 1 Then

i = Int(Rnd * 4)

If CanNpcMove(mapnum, x, i) Then

Call NpcMove(mapnum, x, i, MOVING_WALKING)

End If

End If

End If

End If

Else

i = FindNpcPath(mapnum, x, TargetX, TargetY)

If i < 4 Then 'Returned an answer. Move the NPC

If CanNpcMove(mapnum, x, i) Then

NpcMove mapnum, x, i, MOVING_WALKING

End If

Else 'No good path found. Move randomly

i = Int(Rnd * 4)

If i = 1 Then

i = Int(Rnd * 4)

If CanNpcMove(mapnum, x, i) Then

Call NpcMove(mapnum, x, i, MOVING_WALKING)

End If

End If

End If

End If

Else

Call NpcDir(mapnum, x, GetNpcDir(TargetX, TargetY, CLng(MapNpc(mapnum).NPC(x).x), CLng(MapNpc(mapnum).NPC(x).y)))

End If

Else

i = Int(Rnd * 4)

If i = 1 Then

i = Int(Rnd * 4)

If CanNpcMove(mapnum, x, i) Then

Call NpcMove(mapnum, x, i, MOVING_WALKING)

End If

End If

End If

End If

End If

End If

End if

' /////////////////////////////////////////////

' // This is used for npcs to attack targets //

' /////////////////////////////////////////////

```

[cjsrch]

Well commenting all of that out allowed them to start attacking again however pathfinding is still pretty bad

i made a small map maze

Spawn

=============== |

1 |==============

| |

| |

| ==================

4 | 2 |

| |

=================

3

with him spawning at spawn point

me standing at position 1 he will find me by going around

if i stand anywhere else he will get stuck

if he is at poistion 2 and i am at 4 he will get stuck on wall

if i stand at 3 and he is at 4 he will get stuck

I have tried usiing both attribute blocks and directional blocks with no change

[tslusny]

Wait… You imlemented it to EO 3.0? There is already pathfinding (so it will overlay)