Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm making hack&slash game and I want my characters move like for example in Torchlight, Diablo, etc. Currently I generate set of nodes for all walkable areas of a floor. When I click somewhere player goes there through interpolated path of nodes. This doesn't look very natural. Player moves like a robot. Enemies also use this node system for movement and share the same issue but I have one more problem with them. When enemies detect player they go to him by a shortest path. Sometimes they use the same path and line up to the player instead of surrounding him. I don't know how to make enemies choose different paths and surround the player. Do you know how can I solve this problems? Maybe I should use different approach for character movement?


My current technique:

enter image description here


Torchlight screenshot:enter image description here

---UPDATE---

I want to know how to deal with these situations:

Situation 1, I have dynamic/static obstalces on my way

enter image description here

Situation 2, Enemies have the sam path to player ( get into queue to fight with us ) enter image description here

share|improve this question
10  
+1 for diagrams and screenshots (and a good question). Always useful. –  The Communist Duck May 31 '11 at 20:51
    
This is an awesome question (+1) for which I hope there will be a lot of discussion and suggestion about different ways to deal with this challenge (randomized influences to alter routes, AI, etc.). –  Randolf Richardson Jun 1 '11 at 2:44
1  
I find it good practice to use a scoring system when you are creating an AI. Depending on each enemies' score (time to reach player for example), you can give them specific behaviour. For example if 8 mobs are the max that can attack the player, the ones who have a score higher than the first eight can knowingly try to find a longer path to the player, making them look more intelligent. –  Jonathan Connell Jun 1 '11 at 8:49
3  
I would deal with your acceptance rate. –  The Communist Duck Jun 4 '11 at 17:23
    
I'm still looking for answer, how can I deal with obstalces ( dynamic/static ) on nav mesh? , I can't use Recast –  piotrek Jun 4 '11 at 17:23
add comment

5 Answers

up vote 21 down vote accepted
+50

Steering Behaviours in combination with a navigation data structure.

There are a number of ways to do this, but that's the basic concept. It might be easier to use a navigation mesh so that you can apply pathfinding within each convex section.

If you're adamant about keeping a graph, you can use a Seek behaviour to each node in the path, rather than rigidly following a path from node to node.

Another method you could employ is Path Smoothing but bear in mind that this is fairly computationally expensive.

Hope that helps.

EDIT:

To help with your obstacle avoidance issues, use some sort of Obstacle Avoidance.

share|improve this answer
    
Thx for answer, do you know how can I generate navigation mesh ? Or is there other way to make it ? My map, is created with seamless pieces of floor (quads/triangles). –  piotrek Jun 1 '11 at 13:03
1  
You can always use Recast (code.google.com/p/recastnavigation) for generating a navigation mesh. You just need to give it a "triangle soup" (a bunch of polygons) and it'll generate it for you. –  Ray Dey Jun 1 '11 at 13:21
add comment

Basically for enemies what you want to do is do pathfinding on a macro level (think about generating convex areas and pathing to the area the player is in), and do some boid-style steering behaviors on the micro level (once you're close to the player).

Here's an example of boid behavior: http://www.red3d.com/cwr/boids/

For the player I think torchlight does pathfinding on a nav mesh for where you click/drag, and that works pretty well. It may feel a bit more disconnected than direct control, but it does lead to better results for the player.

share|improve this answer
    
But, what for example with stairs ? Enemy can attack me there too, make it another nav mesh ? –  piotrek May 31 '11 at 19:55
    
It should be part of the nav mesh, being its own convex shape. –  Tetrad May 31 '11 at 19:57
1  
Alternatively you could continue to use your point to point pathing, and fall back onto physics-based steering behaviors when you get "close". –  Tetrad May 31 '11 at 19:58
    
How can I deal with dynamic obstalces on navigation meshes ? –  piotrek Jun 1 '11 at 16:11
1  
Here's a blog post on how recast is working on handling it: digestingduck.blogspot.com/2011/03/…. –  Tetrad Jun 1 '11 at 16:35
add comment

If you'd rather stick with a nodegraph rather than switch to a nav mesh as others have suggested, then you can solve the "line up to the player instead of surrounding him" problem by assigning each enemy to attack from a particular direction.

There are many ways to accomplish this, but I usually use a 'token' system to assign unique directions to monsters, where the player object possesses one token for each direction (north, northeast, east, etc). When an enemy wants to path to the player, it must first acquire a token from him. The direction specified by the token tells the monster which side of the player it is allowed to pathfind to. Since the player only has one token for each direction, and monsters need a token before they can attack, multiple monsters won't all try to path to the same side of the player, which should break up their paths a bit.

Additionally you might also want to apply a small penalty to nodes during the process of finding paths, to encourage monsters to approach from a direction that matches the token they have. (That is, if a monster has the token which allows it to attack from the east, then for the purpose of determining the "shortest path" for that monster, treat any path nodes which are north/west/south of the player as if they are several nodes, instead of just one). This will make monsters separate faster and try to flank the player, instead of marching up to the player in single-file and only spreading at the last step.

share|improve this answer
add comment

there is an algorithm named rrt which is used for realworld pathfinding problem. the surface your hero (or enemies) can walk on is an input along with the suface that objects can move, and using some optimization algorithm it finds a path to your destination. as much as I know this algorithm is greatly used in robocup leagues. it's fast, finds the shortest path and avoids collision and sharp turns. you can use this powerpoint show to get a grasp on how it generates path.

share|improve this answer
    
after more look it seems the presentation I provided just tells what rrt does and also suggest a new approch, which it claims to work better in some cases, and he suggested that algorithm for RTS games pathfinding hope it'll help you. –  Ali.S Jun 4 '11 at 18:03
add comment

To make pathfinding routes look more "realistic", I suggest you check out the article about natural-looking A* in Game Programming Gems Vol.1

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.