50
\$\begingroup\$

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

\$\endgroup\$
4
  • 10
    \$\begingroup\$ +1 for diagrams and screenshots (and a good question). Always useful. \$\endgroup\$
    – PrettyPrincessKitty FS
    Commented May 31, 2011 at 20:51
  • \$\begingroup\$ 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.). \$\endgroup\$
    – Randolf Richardson
    Commented Jun 1, 2011 at 2:44
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Jonathan Connell
    Commented Jun 1, 2011 at 8:49
  • \$\begingroup\$ I'm still looking for answer, how can I deal with obstalces ( dynamic/static ) on nav mesh? , I can't use Recast \$\endgroup\$
    – piotrek
    Commented Jun 4, 2011 at 17:23

5 Answers 5

Reset to default
24
+50
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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). \$\endgroup\$
    – piotrek
    Commented Jun 1, 2011 at 13:03
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Ray Dey
    Commented Jun 1, 2011 at 13:21
  • \$\begingroup\$ Am I the only one encounter this but the link: ai-blog.net/archives/000152.html is dead. Actually I can't access www.ai-blog.net \$\endgroup\$
    – 123iamking
    Commented Oct 30, 2017 at 7:23
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Ali1S232
    Commented Jun 4, 2011 at 18:03
0
\$\begingroup\$

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

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .