Diablo® III

Pathing using Search, A* Search?

Posts: 1
Hi,

I'm writing an academic paper on AI Search algorithms and A* Search, and I was looking for some real-world examples of where basic search and A* Search are used. Does Diablo III use A* search, or any other basic search algorithm, in any notable places?

My first guess was for pathing, or finding the shortest, traversable path for a player or NPC.
Reply Quote
Posts: 24
Hi,

I'm writing an academic paper on AI Search algorithms and A* Search, and I was looking for some real-world examples of where basic search and A* Search are used. Does Diablo III use A* search, or any other basic search algorithm, in any notable places?

My first guess was for pathing, or finding the shortest, traversable path for a player or NPC.


Hi andylgd,

A* is an algorithm used for finding optimal paths, which means I don't think it is so good over continuous spaces like in D3. A* has some nice properties if your heuristic function is admissable and consistent that allow you to guarentee the optimality of the solution, but that requires you to evaluate the cost of every neighboring "node" and expand the one with the lowest cost. This is a problem in continuous space because there are infinite nodes. From my understanding, you would use A* more in a discrete search space, like a pacman game or something.

Maybe I'm wrong though.
Reply Quote

Please report any Code of Conduct violations, including:

Threats of violence. We take these seriously and will alert the proper authorities.

Posts containing personal information about other players. This includes physical addresses, e-mail addresses, phone numbers, and inappropriate photos and/or videos.

Harassing or discriminatory language. This will not be tolerated.

Forums Code of Conduct

Report Post # written by

Reason
Explain (256 characters max)

Reported!

[Close]