Advice for a NPC Path Algorithm

Hey!

I am working on a game for a school project and there are a few requirements I need. One is that I need to have a recursive function. I thought that I could make a function that generates a path for the AI to follow so that their movements don't seem totally random and to make them seem a little more "intelligent". I have a few ideas, such as checking each move to see if the player is within a certaing distance, otherwise trying to move in a straight path. After a certain number of moves, change directions, and finally, checking to see proximity to other tile types, so they don't walk right into walls. I thought I'd post up here to see if anyone had any ideas that I could implement to make the function work well and to give the AI a bit of a smoother movement system.

Thanks in advance!

Grimey

Re: Advice for a NPC Path Algorithm

You AI object should have a goal, otherwise it might just as well stroll around randomly.

kind regards,

Jos

Re: Advice for a NPC Path Algorithm

You should learn about Graphs and those algorithms like Deepth First Search, Breadth First Search, Dijkstra sortest path, and more advanced and heuristic A* pathfinding.

Re: Advice for a NPC Path Algorithm

Alright, I'll look into those! The problem with a goal is that I'm not totally sure what sorts of goals to use. What I was thinking of doing is every time the functin recurs (Is that the right word?), it will check to see if the players location at the time the path is built is within a certain number of tiles. Otherwise, I may make it so that the NPCs will set a random goal based on tile types. So if there is a forest, river, or house nearby, it will randomly choose one then head for it. Once it gets there, it will then choose another. Any ideas for parameters or base cases. I will also likely have a maximum number of moves in the path. It will either go until the bot arrives at the location or until the maximum number of moves is hit. Once the bot reaches the end of the path, it will generate a new one. Again, thanks for the help!

Re: Advice for a NPC Path Algorithm

Quote:

Originally Posted by

**Grimey** Alright, I'll look into those! The problem with a goal is that I'm not totally sure what sorts of goals to use.

Normally, a goal that **you think** would make your AI useful. That is named **heuristic**. If your game is a race, the shortest (or quickest) path would be good. If you AI is runing a turn based strategy game you should need to know something about game theory. If your AI is for a shoter, a good place to hid and shoot, etc...

Re: Advice for a NPC Path Algorithm

It's a top-down adventure style game. Similar to the old Pokemon style games. Around the map, there are enemies who are walking around. They aren't neccessarily out to hunt you down though, but if you walk into one of them, then the player will be put into the combat screen. I would also like to use a similar algorithm for peasant characters who are just walking around. The issue with totally random movement is that it looks a little strange if the AI are just walking around in random directions all the time. That's why I was thinking that the best way to do it would be to select a random number of goals. I could possibly make it so that it just selects a random square on the map and they will try to get to it. The only issue would be making a base case so they don't get stuck if that square is in the middle of a lake or other impassable area. It is a pretty interesting problem I think. It's kinda neat trying to design AI that seem believable... At least somewhat...

Re: Advice for a NPC Path Algorithm

For that I would use Breadth First Search (BFS). If you game is like pokemon, then your entities have a finite way to be placed. Just call those NODES. Now, if it is like Pokemon, then your entities can move inmediately upside, downside, leftside and rightside. So, you can construct a BFS algorithm using this information. You have an entity (an AI controlled NPC) at node A, and wants to know if it can travel to node B. You just need to apply BFS with node A, node B and using the Graph described by the movement (up,down,left,right).

It is complicated if you don't have algorithm knowledge, but I can help you deeper if you want.

Re: Advice for a NPC Path Algorithm

I'd love the help! This is my third year programming, but I've basically just done it at school. I just started Java this year though and I haven't really done much with algorithms. So, you think that the BFS method is best? Okay, I will look into that. The A* method looks pretty good too, other than the fact that I'm not sure how to deal with a path that is completely obsucred. Furthermore, I think I get the basic idea of the algorithm, but I'm pretty lost as far as putting it into code goes too. The way I think I will do it is to choose a random location, then go there. Maybe you could help me translate the algorithm into code? The other thing with the A* method is storing the nodes. The map is a double array, so I need an x and y coordinate for each node. As for the movements, the way I have been doing that is choosing 0-3. 0 means up, 1 left, 2 down, and 3, right. So if it needed to move up, it would subrtract 1 from the x coordinate. I thought I could create a linked list that stores the directions, but I don't think that would work since there is no way to reference the squares surrounding it further down the path.

Thanks a lot for your help! I really appreciate it and I am certainly learning a lot!

EDIT: Here is the link I was using by the way, if it helps.

http://www.policyalmanac.org/games/aStarTutorial.htm

Re: Advice for a NPC Path Algorithm

Storing the path in a linked list is a good idea (I'll do with a Stack structure by the way). The problem is to find that path. The BFS algorithm (A* could do the same but you don't need a super AI, do you?) tells you (pseudo-code to find the shortest path from a to b):

Code:

`Let q to be a Queue (FIFO)`

Let a,b to be positions of your map, a the start and b the end of the path

Let visited to be any kind of Map structure that can store the pair <position,int>

Let r to be an Stack structure (LIFO) result of the algorithm

Let d to be an int

Begin

d := 0

put a in q

while q is not empty do:

let x := q->pop

put <x,d> in visited

d := d + 1

if x is b then // You finished!!

break while

endif

if x->up is walkable and is not in visited then

put x->up in q

endif

if x->down is walkable and is not in visited then

put x->down in q

endif

if x->left is walkable and is not in visited then

put x->left in q

endif

if x->right is walkable and is not in visited then

put x->right in q

endif

endwhile

// Check if anything went wrong:

if visited[b] is not d-1 then

throw ImpossiblePathException

endif

// Now you have at visited the nodes visited and the order you visited them, so you must go from b to a looking for the shortest path:

Let x := b

while x is not a

put x in r

Let y to be a position

if x->up is in visited and visited[x->up] < d then

y := x->up

d := visited[y]

endif

if x->down is in visited and visited[x->down] < d then

y := x->down

d := visited[y]

endif

if x->left is in visited and visited[x->left] < d then

y := x->left

d := visited[y]

endif

if x->up is in visited and visited[x->right] < d then

y := x->right

d := visited[y]

endif

x := y

endwhile

End.

I think you don't need more to work with. This is pseudo-code, now you need to think (I like people thinking) why this code works and how you will implement it into java. If you need more help, just ask it.

EDIT: Be careful if the game map is huge and the path is not reachable, as this won't stop until try every path. You could stop this algorithm in a fixed distance (just check the value o variable d) so you will stop in a reasonable computing time.

Re: Advice for a NPC Path Algorithm

That's awesome! I am going to try to implement it now. I was reaing up on A* algorithm, and it seems like it might be a little over my head for now, still cool though! :8): The only other issue I have is storing the path. Since it is a recursive algorithm, I would assume that you need the actualy coordinates rather than the directions. I would make a class that just stores a coordinate, as in holding an x and a y value, but I have no idea how to access that. I've tried it and am still looking for a good way to do that. The other option would be two lists. I guess you could store the directions and just have a temp x and y coordinate and keep those updated. What do you think?

Again, thanks for the help. I've always wanted to get into algorithms a little more but never really have...

EDIT: I think I see how this is working. Is the idea basically to inspect the x postitions, then the y positions? You may get a good few edits here over the next hour!

EDIT YET AGAIN: I have been looking a little at the Dijkstra method. My teacher thinks that for the purposes of my game, this is probably the easiest method for now. I think I will stick with it for simplicity sake until I hand the game in, then I will continue to work on it over the summer. I found out how to acces data from within a class, so I have made a class called node which simply holds the x, y coordinates, and the distance to that coordinate.

Re: Advice for a NPC Path Algorithm

I'm in dissapoint with your teacher. Dijkstra is efficient for Graphs with weights, but you have an unweighted uniform map (you don't need to know what is this, just trust me and look at Dijkstra's algorithm). BFS is much simplier, as the main idea is: expand yourself to 4 sides (up, down, left, right) with any unvisited node (that is why you need a map of <position,int> called visited) and walkable node (avoid walls, water...). Do it until you run out of unvisited nodes (objective unreachable) or until you get to the objective.

That is the first part of the algorithm (surrounded with "while queue is no empty"), the second part just retrieves the path from the Map. If you reached the objective, you know that you followed the shortest path and you stored distances in visited Map. So just go from B to A by the quickest path possible (checking that the next distance is less than actual distance). If you don't understand it yet, I could do a draw for you, but I think to be better you to print my algorithm and show to your teacher, and then tell him to explain you why the algorithm works.

EDIT: I'm writting the solution in C++ so you can see how it works. By the way, the pseudo-code had an error at last part. Rechek it.

Re: Advice for a NPC Path Algorithm

Modified a bit the code to fit C++. Here is:

Ideone.com | Online C++ Compiler & Debugging Tool

You can see the result of the code at the end of page.

Re: Advice for a NPC Path Algorithm

I think it was more that he hasn't seen much as far as pathfinding algorithms go, so he thought that the Dijkstra method would be best for simplicity's sake. I was looking at the BFS method again though, and it seems to me like it would be more efficient and would probably work better if I wanted to later implement terrain effects. Thanks again, I shall go to work again for a while now and tell you how it goes once I am done!

Re: Advice for a NPC Path Algorithm

Just wanted to make sure. I have a class called MapDat which just stores an array of characters that define the tile type (i.e. grass, mountain, etc.). This isn't the same as your 'visited' though, correct? From what I understand, visited is just a position and the shortest known distance to said node, am I right?

Re: Advice for a NPC Path Algorithm

Quote:

Originally Posted by

**lilezek** I'm in dissapoint with your teacher. Dijkstra is efficient for Graphs with weights, but you have an unweighted uniform map (you don't need to know what is this, just trust me and look at Dijkstra's algorithm). BFS is much simplier

No it isn't; if there are no weights, you can assume a weight of, say, 1, on each edge; both a BFS algorithm and a Dijkstra algorithm end up with a path having the same number of edges on the path. The Dijkstra algorithm can be improved a bit here: don't use an ordinary cost function (the cost of the path equals the number of edges in the path) but add the Euclidean distance to the target. This heuristic 'pulls' the path towards the target and normally results in a faster algorithm.

kind regards,

Jos

Re: Advice for a NPC Path Algorithm

Hmmm. I must say that this is pretty interesting stuff. Now using heuristics with Dijkstra's algorithm would be the A* method, am I correct? For now I may just stick to the BFS method. I may modify this later on if I decide that I want to alter the game further in the future. Thanks again!

EDIT: By the way, I have created a map using the java.util class which stores the node and integer, like this:

Code:

`Map<Node, Integer> visited = new HashMap<Node, Integer>();`

I have no idea how to manipulate it though. I believe that the integer value is meant to hold the distance from the start to the given node associated with the map. Is this correct? Other than that, I think the algorithm is coming nicely.

I am definitely getting this, but there is one part I am unsure of. So, it looks to me like the integer in visited is the distance to the given node, which can then be used to determine the shortest path. As mentioned, I created a visited using the Map class. To access the integer, am I right to use get.visited(n)? Also, how would I change the integer associated with a given node (or key)?

Re: Advice for a NPC Path Algorithm

Quote:

Originally Posted by

**JosAH** No it isn't; if there are no weights, you can assume a weight of, say, 1, on each edge; both a BFS algorithm and a Dijkstra algorithm end up with a path having the same number of edges on the path. The Dijkstra algorithm can be improved a bit here: don't use an ordinary cost function (the cost of the path equals the number of edges in the path) but add the Euclidean distance to the target. This heuristic 'pulls' the path towards the target and normally results in a faster algorithm.

kind regards,

Jos

First, I think we are talking about Manhattan distance, not the Euclidean (as you can move Up, Down, Left, Right).

Second, before apply Dijkstra's Algorithm you need a graph, and you don't have a graph, you have a set of disctete points. You could construct a graph from it with all edges

with weight 1 if walkable, and infinite weight if not walkable, but that is more expensive than just a BFS.

The unique (I think) way to use Dijkstra here, is that the map is static. So if a path is walkable now, it will be walkable always. Then you can create a small graph of walkable zones connected with Manhattan distance and then use Dijkstra with that graph.

Quote:

Originally Posted by **Grimey**

Just wanted to make sure. I have a class called MapDat which just stores an array of characters that define the tile type (i.e. grass, mountain, etc.). This isn't the same as your 'visited' though, correct? From what I understand, visited is just a position and the shortest known distance to said node, am I right?

No. The 'grass', 'mountain', etc... information will help you to know which position is walkable. For instance:

Code:

`if (position->terrain is wall or mountain or water) then is not walkable`

else it is walkable

Visited is to avoid to revisit a position visited (and to know the distance from start point to that point). If you don't make sure that the path you are looking is unvisited, you could (and will) get into an infinite loop.

For a person without algorithm knowledge (this problem is not Java relationed, but algorithmic) this is a hard task. I suggest you to try to understand everything asked here.

Re: Advice for a NPC Path Algorithm

Okay, I understand the concepts, but I am a little lost as gar as syntax goes. From what I understand the Map class prevents you from entering repeated data. Is this right? So, my Map<Node, Integer> will hold both pieces of data. The node, and the distance to said node. If the given node is already within the list, you can ignore it. You initially loop through all the elements of the map to find the distances to each, then you enter another loop which works backwards from the target node to the start node to create the path. Just wanted to make sure, there are three checks in the second loop. One checks to see if the distance through that node is shorter, one to see if the path has already been travelled, but what is visited.count?

Thanks again! Iam learning a ton about algorithm design and pathfinding.

Re: Advice for a NPC Path Algorithm

Quote:

Originally Posted by

**lilezek** Second, before apply Dijkstra's Algorithm you need a graph, and you don't have a graph, you have a set of disctete points. You could construct a graph from it with all edges

with weight 1 if walkable, and infinite weight if not walkable, but that is more expensive than just a BFS.

You can construct a graph while solving (using Dijkstra); a discrete point is a vertex and the adjacent points create the outgoing edges and costs.

kind regards,

Jos

1 Attachment(s)

Re: Advice for a NPC Path Algorithm

In C++, map<Key,Value>::count(Value) (or simply visited.count(node)) is the way you check if node is in visited. True (or 1) means is in, false (or 0) means is not in.

If you know C++ look at my code. If not, you should think the way you are going to implement it into Java. My C++ code is quickly done for you to show an example, but is terrible written.

By the way, the process of finding the path I wrote is like:

Attachment 3855

This is an image of Dijkstra's algorithm (with the difference that your game is taxicub geometric), which is equivalent to BFS in this kind of problem.

Blue points are unwalkable nodes. Green point is target node, and point's color represent the distance from the start point (that is what you saved into visited Map).

There is a better algorithm if your map only contains convex obstacles, but this is good enough for a game I think. In Google's AI contest I managed to compute more than 50 BFS in a big map (big compared to pokemon's like game maps) in less than 100 ms, so you won't have any problem.