Jump to content

  • Log In with Google      Sign In   
  • Create Account

Diablo style AI pathfinding help


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 littletray26   Members   -  Reputation: 267

Like
0Likes
Like

Posted 28 June 2012 - 05:44 PM

I am in the design process for a more Sacred style game (I said Diablo in the title as its more familiar).

I was thinking of using a sort of tile engine for it, and was going over the code in my head and then I got stuck when thinking about the AI

How would I go about implementing pathfinding? I've heard about A* and understand the concept, but not how I'd implement it.
Also it seems like the process would be fairly expensive if I was using it for 5 or 6 monsters simultaneously.

My question is, what kinds of pathfinding could I use? and how would I go about implementing them?
Could I get some code samples of how I'd go about using the A* pathfinding method?

Edit: I probably should have made this in the AI forum xD

Edited by littletray26, 28 June 2012 - 05:45 PM.

The majority of Internet Explorer users don't understand the concept of a browsing application, or that there are options.
They just see the big blue 'e' and think "Internet". The thought process usually does not get much deeper than that.

Worms are the weirdest and nicest creatures, and will one day prove themselves to the world.

I love the word Clicky :)

Sponsor:

#2 Postie   Members   -  Reputation: 1123

Like
0Likes
Like

Posted 28 June 2012 - 09:22 PM

If implemented correctly, A* can be very fast. Fast enough to handle 100's of monsters simultaneously, so I wouldn't fret about that expense quite yet. I'd recommend checking out the AI forum as A* is discussed there all the time.
Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#3 JTippetts   Moderators   -  Reputation: 8664

Like
0Likes
Like

Posted 28 June 2012 - 10:25 PM

In a Diablo-clone, it is quite frequent to have more than 5 or 6 enemies at a time dinging the pathfinder. It is important, then, to clearly define your goals and design, and to allow for all scenarios. A* is only one tool in the tool box. You might notice that in some D clones, the enemies don't chase very far, or if you can put enough space between them and you you can leave them behind. Also, they don't "aggro" until you are nearby. One reason for this is it allows you to constrain your pather to a limited radius, and thus drastically reduce the time spent calculating paths. Target went out of range? Switch to idle mode. You can put checks in your A* pather to bail if no path less than a maximum length is found, and preliminary checks to keep the pather from being called.

It is also important that you use the pathfinder most appropriate to a situation. On a tile grid, this is likely to be A* (just ensure you only call the A* pather if you need to; if there exists a straight line path, then use that instead). However, just blindly calculating an A* path and having the enemies follow it in a grid-based game is unlikely to lead to realistic movement. In this case, once you have the path you can perform a post-processing pass upon it. This pass will iterate the path from end to start and find the node that is furthest along the path to which the unit can path in a straight line. This will clip off any jaggies or zig-zags, and give the unit the impression of intelligence by having it head directly toward the route around the nearest blockage, instead of meandering in a wobbly line across the ground.

Even if you are on a grid, you still might want to look into using navigation meshes. There exist libraries such as Recast and Detour that can help with the generation of nav meshes and pathfinding upon them. Using a navigation mesh library can boost performance immensely, especially if your levels tend to be large and open. Large, open levels partitioned on a grid tend to devolve to a lot of testing of nodes and overhead to cover the large open spaces, whereas a nav mesh will tend to condense all of those grid-sized nodes into larger mesh nodes, making the actual A* step a lot less computationally expensive at the expense of some pre-processing to build the nav mesh. The method you use to pathfind on a nav mesh may also allow you to eliminate the post-process step of finding the furthest node you can path to, as a nav mesh path tends not to have the regular jaggies and grid steps that an A* path on a tile grid has.

Edited by JTippetts, 28 June 2012 - 10:55 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS