AI Pathfinding in FINAL FANTASY XIV: A Realm Reborn
Square Enix held a two day “Square Enix Open Conference” on November 23rd and 24th. The last portion of the conference was the “AI Session” which was divided into two parts. The first half was about FINAL FANTASY XIV: A Realm Reborn and gave a detailed overview of how they implemented pathfinding for enemy NPCs. The second half was a more conceptual/general presentation on the AI engine used in Luminous Studio by Youichiro Miyake.
The theme of the first half was “How To Determine The Path Enemy NPCs Use To Move Around A Map in MMORPGs”. As MMORPGs use expansive, complicated maps, deciding the paths NPCs use wisely is a very difficult issue to tackle.
The presentation was by given by Luminous Studio project members Takanori Yokoyama (AI Programmer) and Fabien Gravot (AI Researcher).
4gamer.net posted a write up of the event which we’ve gone ahead and summarized after the jump!
For FFXIV:ARR, one of the hard issues to tackle was the number of monsters. A single map, for example, could have 1000 monsters all moving around at the same time. Processing their routes individually would cause a huge strain on the servers. However, they can’t have enemies only move when players get near them (something used in some first person shooters) because there are so many players online at the same time.
The NPC paths are determined server side. As such, they couldn’t use a normal algorithm like the A* method. The A* method has NPCs look for the shortest path between point A and point B. The number of calculations for moving each NPC by this method would put a huge strain on the servers. It also takes a lot of memory.
Instead, FFXIV:ARR uses a “Path Table” method. The paths are predetermined between spot to spot. This method has been used in video games for a long time. One example is listed below. When the NPC wants to move from point 1 to point 5, it looks up the route information in the table. The table says the NPC needs to move to point 3 first. Once it gets to point 3, it looks up the info from point 3 to point 5. Since it’s set to 4, it then moves to point 4 and so on until it reaches its goal.
The table basically already lists the shortest path it takes to get between two spots. The lack of constant calculating reduces the server’s CPU strain. However, the amount of memory used ends up increasing.
You need a lot of memory. For a 20,000 by 20,000 navigation mesh on a map, it takes around 1.1 GB. That’s pretty tough on a server. That’s just one map, so you can imagine how hard it’d be for the server to process all maps in an MMORPG even if it’s of the highest specs.
In the end, this method can cause bigger memory/strain issues than going a non-table route.
That’s why they looked for a way to get the benefits of the table method while keeping the amount of memory needed down. They decided to divide each map into sections (or grids). The tables are not symmetrical because sometimes there are one-way paths (like if you jump down from a higher level).
To start, they gave each grid a table. Just reducing the number of columns and rows reduced the memory needed by quite a lot. If a monster needs to move across the entire map, it first reaches a destination on the first grid, then uses the table for the second grid, and so on. They did this by using “connection points” predetermined on each grid. By breaking up that 20,000 by 20,000 mesh that took 1.1 GB into 100 by 100 grids, the memory requirement was also lowered to about 11MB.
The downside of the “connection points” system is that in the end, the NPC might not be taking the best course to its destination. They could end up at a number of points not on the shortest distance path. This makes the path look a bit clumsy.
To correct this, they ended up making tables of connecting grids. This replaces the need for connection points. Instead, it makes sub-goals and then advances forward swapping tables when it meets a grid boundary.
This system is called “HiNT” or “Hierarchical Neighborhood lookup-Table”. This system reduces the amount of memory needed as well as the strain on the CPU. The enemies also end up taking smarter routes. Even though the tables are 9 times the size of the grids, it didn’t end up causing a big problem.
The video shows a character moving from grid to grid.
The red line is the optimal path as determined by using calculations from the table and a funnel algorithm.
The colored path was made from a “drop mesh”. If the NPC jumps off the side of a small cliff for example, the drop mesh can be used to direct how the NPC climbs its way back up.
To create the navigation mesh, they used an open source tool called Recast. It would have taken an extraordinary long time to make the mesh by hand. However, when they automated the process, the team also had to battle issues with narrow paths and areas where it was questionable about if the enemy could really use a path or not. On the plus side, a mesh for a large map would only take about 1 minute 30 seconds to make and used about 7MB of data. They were also able to use the navigation mesh to create the 2D world maps displayed in game.
Some very technical stuff to be sure, but it’s an interesting look at some of the underlying systems that went into FINAL FANTASY XIV: A Realm Reborn!