Log in

No account? Create an account
Game AI Pathfinding - UR DOING IT RONG - Adventures in Engineering — LiveJournal
The wanderings of a modern ronin.

Ben Cantrick
  Date: 2008-08-02 00:54
  Subject:   Game AI Pathfinding - UR DOING IT RONG
  Tags:  reddit

Figure 9. Navigating from A to B on the navigation mesh

Many modern games do have high-quality pathfinding, and pathfinding often works well in some of the games shown here. But there are still too many games that do pathfinding the same way that games did in the 1990s.

To the best of my knowledge, most of these games use waypoint graphs for pathfinding. I think that's the reason for several of the pathfinding issues you see in this video, and many of the pathfinding problems we face in the industry as a whole. I believe waypoint graphs are now obsolete. This article explains the limitations of the waypoint graph approach and lays out a five-point argument for a better approach.

There was a time when it made sense to use waypoints for pathfinding. Back in the 1980s and 1990s, we were working under serious technical constraints and we had to cut a lot of corners. But we're a multi-billion-dollar industry now. Our target platforms have multiple cores and ever-increasing amounts of memory, and we can afford to do pathfinding correctly.

There's a saying among AI developers in the industry: "pathfinding is solved." We have good approaches to every pathfinding problem modern games face. We just don't always use them.

There's no reason not to have pathfinding that works in every game, every time.

Post A Comment | 2 Comments | | Link

  User: (Anonymous)
  Date: 2008-08-03 13:14 (UTC)
  Subject:   (no subject)
Glanced at it briefly and seems fascinating. Especially b/c while I enjoy mmo's and WoW, most recently, I don't delve into the mechanics of the game, rarely. Well, there are obvious things I need to know. Mob ai behavior and abilities, boss mob ai behavior and abilities, lay out of zones, dungeons, etc. A good grasp of your character's abilities are a must to be a competent player and it never hurts (and more frequently, benefits) to know the capabilities of your group/raid mates for knowing what strategies and abilities to employ for certain encounters - which is not limited to just pve fights, but, more crucially, in pvp fights. Sometimes, exploiting mob pathing or mob ai is part of overcoming a fight as well or surviving it long enough when you lose teammates and just need to hold out long enough to outlast the mob at that particular moment.

Anyway, aside from these things, it's rare that I get a glimpse of the actual mechanics and things 'under the hood' so to speak, but it is interesting, nonetheless. I'll probably have more to comment on when I get a chance to actually watch and read the article in its entirety.


PS I never did pvp for Halaa much. Halaa being an outdoor, neutral city in Nagrad that can be taken by either faction, Alliance or Horde, and has some beneficial points for those who control it. It's unique in a way because most traditional pvp in WoW takes place in instanced areas called battlegrounds (like Warsong Gulch, Alterac Valley, Arathi Basin, and Eye of the Storm) where teams of 10v10, 40v40, 15v15, and, again, 15v15 battle for a multitude of objectives ranging from CTF style fights to defeating an npc general to fighting for resource nodes that earn points to a combination of CTF and fighting for resource nodes. The other, more recently implemented pvp combat format, takes place in arenas. In arenas, there are 'brackets' for 2v2, 3v3, and 5v5 combat. The format is always a deathmatch and is not necessarily cross faction combat. It's very reminiscent of a fps-style deathmatch game, but only consists of 3 different maps; Lordaeron, Blade's Edge Mountains, and Nagrand arenas for the sake of simplicity and fairness. Like I said, Halaa is unique in that it and all the other world pvp objectives in the Outlands are outdoors instead of instances and where you can use your flying mounts though there's not much need to use the flying mounts for the other world pvp objectives. It's convenient for Halaa since Halaa is, essentially, an island with bridges to it.
Reply | Thread | Link

  User: (Anonymous)
  Date: 2008-08-03 16:12 (UTC)
  Subject:   (no subject)
Oops... That should have been 'I don't delve into the mechanics of the game, frequently.'

Reply | Parent | Thread | Link

May 2015