Results 1 to 20 of 27
Thread: Advice for a NPC Path Algorithm
 06102012, 08:46 PM #1Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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
 06102012, 09:36 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,881
 Blog Entries
 7
 Rep Power
 22
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,
Joscenosillicaphobia: the fear for an empty beer glass
 06102012, 09:37 PM #3Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
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.
 06102012, 09:45 PM #4Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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!
 06102012, 09:56 PM #5Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
Re: Advice for a NPC Path Algorithm
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...
 06102012, 10:04 PM #6Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
Re: Advice for a NPC Path Algorithm
It's a topdown 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...
 06102012, 11:19 PM #7Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
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.
 06102012, 11:44 PM #8Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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 03. 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.htmLast edited by Grimey; 06102012 at 11:47 PM.
 06112012, 01:59 PM #9Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
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 (pseudocode to find the shortest path from a to b):
Java 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 d1 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.
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.Last edited by lilezek; 06112012 at 07:33 PM.
 06112012, 04:39 PM #10Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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! 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.Last edited by Grimey; 06112012 at 05:18 PM.
 06112012, 07:17 PM #11Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
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 pseudocode had an error at last part. Rechek it.Last edited by lilezek; 06112012 at 07:34 PM.
 06112012, 08:24 PM #12Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
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.Last edited by lilezek; 06112012 at 08:34 PM.
 06122012, 12:32 AM #13Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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!
 06122012, 02:24 AM #14Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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?
 06122012, 07:35 AM #15
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,881
 Blog Entries
 7
 Rep Power
 22
Re: Advice for a NPC Path Algorithm
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,
Joscenosillicaphobia: the fear for an empty beer glass
 06122012, 04:34 PM #16Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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:
Java Code:Map<Node, Integer> visited = new HashMap<Node, Integer>();
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)?Last edited by Grimey; 06122012 at 06:14 PM.
 06122012, 07:45 PM #17Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
Re: Advice for a NPC Path Algorithm
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.
Originally Posted by Grimey
Java Code:if (position>terrain is wall or mountain or water) then is not walkable else it is walkable
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.
 06122012, 08:09 PM #18Member
 Join Date
 May 2012
 Posts
 30
 Rep Power
 0
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.
 06122012, 08:17 PM #19
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,881
 Blog Entries
 7
 Rep Power
 22
 06122012, 08:17 PM #20Member
 Join Date
 Jun 2012
 Posts
 23
 Rep Power
 0
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:
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.Last edited by lilezek; 06122012 at 09:04 PM.
Similar Threads

What is the equivalent of App.path (in VB) Or application.path (in C#) in JAVA
By junaid in forum New To JavaReplies: 0Last Post: 12072011, 04:22 AM 
Path solving algorithm/method help needed!
By Zee Best in forum Advanced JavaReplies: 3Last Post: 10182011, 01:32 AM 
implementing an algorithm for shortest path problem in java
By thorobred in forum New To JavaReplies: 0Last Post: 03202011, 02:17 AM 
setting classpath & Library Path in ubantu
By programmer_007 in forum EclipseReplies: 18Last Post: 02222010, 01:31 PM
Bookmarks